Lecture notes — Introduction

Published

2026-08-19 00:00

Keywords

ver. 1.0.1

Where we are

This is the first unit of the module, so nothing is assumed from an earlier one. What we do assume is that you have written programs in an imperative language — Pascal, C, Java, Python — and are comfortable with variables, assignment, loops and arrays.

That experience is exactly what this unit works against. We are going to remove the assignment statement and see what is left.

What you will be able to do

say-what-functional-programming-is — Say what functional programming is, in terms of what a program is made of.
contrast-names-and-values — Contrast how imperative and functional languages associate names with values.
explain-order-independence — Explain why the order of evaluation does not change a functional program’s result.
write-repetition-as-recursion — Express repetition as recursion rather than as a loop.
use-functions-as-values — Pass a function as an argument and return a function as a result.
describe-explicit-data-structures — Describe how functional languages build data explicitly from nested structures.
place-functional-programming-historically — Place functional programming among the 1936 computability results and the systems that followed.
say-why-lambda-calculus-is-the-core — Say why the λ calculus is treated as the machine code of functional programming.

What we will cover

Functional programming — an approach based on function calls as the primary programming construct.
Imperative programming — programming as a sequence of commands that change variables.
Name–value association — the rule governing what a name stands for, and whether it can change.
Execution order independence — the property that evaluation order does not affect the result.
Recursion — repetition through nested function calls rather than command repetition.
Functions as values — functions that can be passed as arguments and returned as results.
λ calculus — Church’s system of function abstraction and application.
Church–Rosser theorem — if different evaluation orders terminate, they give the same result.
Denotational semantics — describing language constructs by giving each an equivalent function.

Why another way to program

Most of the programming you have done treats a program as a sequence of commands that change a store. Read a variable, compute, write it back, repeat.

This module asks what happens if you remove that entirely. No assignment. No statement order. No mutable variables.

What is left?

The answer is that nothing is lost. Every computable function can still be expressed. Making that case is what this unit is for, and it takes the rest of the module to carry out in full.

We will work through the differences one at a time:

what a name means, which is where the two styles first part company
why execution order stops mattering once names cannot be reassigned
how repetition happens without a loop
how data is built, and why functions can be values like any other

Then we turn to where these ideas came from. Functional programming is not a recent style. It is the programming face of results proved in 1936, at the same time as the Turing machine and shown equivalent to it.

Finally we name the object the rest of the module is about: the λ calculus. This unit motivates it and does not yet teach it.

Learning outcomes

say-what-functional-programming-is: Say what functional programming is, in terms of what a program is made of.
contrast-names-and-values: Contrast how imperative and functional languages associate names with values.

What functional programming is

Here is the definition the book works from:

Functional programming is an approach to programming based on function calls as the primary programming construct.

Functional programming provides practical approaches to problem solving, and — with its roots in the theory of computing — it forms a bridge between formal methods in computing and their application. That bridge is worth keeping in view. The reason this style has such a clean theory is that it started as theory.

Set against it is imperative programming, which we will use as the contrast throughout: programming as a sequence of commands, each typically changing the value of a variable.

The rest of the unit works through four differences in turn — names, execution order, repetition, and data — and then turns to the history and to the λ calculus itself.

One framing to carry with you. Every difference we meet follows from a single decision about what a name is allowed to mean. The next section makes that decision explicit, and everything after it is a consequence.

Learning outcomes

say-what-functional-programming-is: Say what functional programming is, in terms of what a program is made of.

Concepts

functional-programming: defines functional programming and states its bridge role between formal methods and practice
imperative-programming: sets up the contrast this unit works against

Names and values

Start somewhere simpler than a programming language: an electronic calculator.

A calculator does arithmetic on numbers, and its limitation is that there is no way to generalise a calculation. To do the same calculation with different values, you re-enter the whole thing.

Programming languages fix this with names. We write a program using names to stand for values in general, then run it with the names taking particular values from the input. The program does not change; only the input does.

So far both styles agree. They part company over what the association between a name and a value is allowed to do.

The imperative rule

Traditional languages are built around a variable: a changeable association between a name and values. They are called imperative because a program is a sequence of commands:

<command1> ;
<command2> ;
<command3> ;
...

Each command is typically an assignment, which works out the value of an expression and associates the result with a name:

<name> := <expression>

Each command’s expression may refer to variables that earlier commands changed. That is how values travel from command to command.

In imperative languages, the same name may be associated with different values.

The functional rule

Functional languages are built around structured function calls. A program is an expression: a function call that calls other functions in turn.

<function1>(<function2>(<function3> ... ) ... ))

Each function receives values from its caller and passes new values back. This is function composition, or nesting.

Names are only introduced as the formal parameters of functions, and are given values by function calls supplying actual parameters. Once a formal parameter is associated with an actual parameter value, there is no way for it to be associated with a new one. There is no assignment, so there is no command sequence and no command repetition.

In functional languages, a name is only ever associated with one value.

Why this one difference matters so much

To know what a name means in an imperative program, you must know when you are asking — which commands have already run. To know what a name means in a functional program, you look at where it was bound. Time does not enter.

The next three sections are all consequences of this.

Learning outcomes

contrast-names-and-values: Contrast how imperative and functional languages associate names with values.

Concepts

name-value-association: contrasts the changeable variable of imperative languages with the fixed binding of functional ones
imperative-programming: defines imperative programming as sequences of commands built from assignment
functional-programming: defines a functional program as nested function calls

Execution order stops mattering

In imperative languages the order in which commands are carried out is usually crucial. Values travel between commands through shared variables, and one command may change a variable before the next uses it. Change the order and the behaviour of the whole program may change.

The swap, and two ways to get it wrong

To swap X and Y:

T := X;
X := Y;
Y := T

T’s value depends on X, X’s depends on Y, and Y’s depends on T. Any change in the sequence completely changes what happens. Permuting the same three assignments:

X := Y;
T := X;
Y := T

sets X to Y. And:

T := X;
Y := T;
X := Y

sets Y to X. Same three commands, three different programs.

Not every command sequence is order-dependent — if the expressions do not refer to each other’s names, the order does not matter. But most programs depend on precise sequencing.

Imperative languages have fixed execution orders.

The functional case

In functional languages, function calls cannot change the values associated with shared names. So the order in which nested calls are carried out does not matter, because the calls cannot interact.

Suppose we have functions written in a Pascalish style:

FUNCTION F( X,Y,Z:INTEGER):INTEGER ;
BEGIN ... END
FUNCTION A(P:INTEGER):INTEGER ;
BEGIN ... END
FUNCTION B(Q:INTEGER):INTEGER ;
BEGIN ... END
FUNCTION C(R:INTEGER):INTEGER ;
BEGIN ... END

Then in the call

\[F(A(D),\ B(D),\ C(D))\]

the order in which A(D), B(D) and C(D) are carried out does not matter, because A, B and C cannot change their common actual parameter D.

In functional languages, there is no necessary execution order.

Functional programs must of course be executed in some order — all programs are — but the order does not affect the final result. This is execution order independence, and it is one of the real strengths of the approach: it is what allows parts of a program to be reordered, or run in parallel, with no extra machinery, because there is no shared state to protect.

A caveat to plant now

Order does not affect the result. It can affect whether evaluation terminates, and how much work is done. We will meet that properly in unit 2 as normal versus applicative order, and it becomes decisive in unit 4.

Learning outcomes

explain-order-independence: Explain why the order of evaluation does not change a functional program’s result.

Concepts

execution-order-independence: explains why nested functional calls have no necessary execution order
imperative-programming: illustrates how command sequences depend on their order

Repetition without loops

In imperative languages a name can take new values, so repeating a computation does not require duplicating the commands. The same commands run again.

To sum the N elements of array A, we do not write:

SUM1 := A[1];
SUM2 := SUM1 + A[2];
SUM3 := SUM2 + A[3];
...

Instead we reuse one name for the sum and another for the index, and loop:

I := 0;
SUM := 0;
WHILE I < N DO
BEGIN
    I := I + 1;
    SUM := SUM + A[I]
END

In imperative languages, new values may be associated with the same name through command repetition.

The functional version

Because the same name cannot be reused with different values, nested function calls create new versions of names for new values. And because command repetition is unavailable, recursion does the repeating: a function calls itself, creating new versions of its formal parameters bound to new actual parameter values.

FUNCTION SUM(A:ARRAY [1..N] OF INTEGER; I,N:INTEGER):INTEGER;
BEGIN
    IF I > N THEN
    SUM := 0
    ELSE
    SUM := A[I] + SUM(A,I+1,N)
END

For the call SUM(B,1,M) the sum is found through successive recursive calls:

B[1] + SUM(B,2,M) =
B[1] + B[2] + SUM(B,3,M)
...
B[1] + B[2] + ... + B[M] + SUM(B, M+1, M)
B[1] + B[2] + ... + B[M] + 0

Each recursive call creates new local versions of A, I and N, and the previous versions become inaccessible. At the end of each call the new locals are lost, the partial sum returns to the previous call, and the previous locals come back into use.

In functional languages, new values are associated with new names through recursive function call nesting.

Line the two up and the correspondence is exact:

the loop’s index becomes an argument, different on each call rather than updated
the loop’s accumulator becomes a returned value, built as the calls return
the loop’s termination test becomes the base case, I > N

The variable that “changes” in the loop is really a sequence of values. Recursion makes that sequence explicit.

A harder question, deferred

This works because SUM can refer to itself by name. In unit 4 we will find that in the pure λ calculus a name is an abbreviation, not a reference — so a definition mentioning its own name expands forever. Getting recursion back takes real work.

Learning outcomes

write-repetition-as-recursion: Express repetition as recursion rather than as a loop.

Concepts

recursion: explains how functional languages achieve repetition through recursive call nesting
imperative-programming: explains repetition by command loops over reused names

Data structures, and functions as values

Two apparently separate ideas, which will turn out to be one.

Data is written whole

In imperative languages, array elements and record fields are changed by successive assignments. With no assignment, sub-structures cannot be changed one at a time. Instead you write down a whole structure with explicit changes to the appropriate sub-structure.

Functional languages provide explicit representations for data structures.

Functional languages do not provide arrays, because without assignment there is no easy way to access an arbitrary element — and writing out an entire array to change one element would be unwieldy. Instead they provide nested structures like lists, based on recursive notations where operations on a whole structure are described in terms of recursive operations on sub-structures.

The representation for nested data often looks very like the nested function call notation. In LISP, the same representation is used for both.

This has real advantages:

one standard format for displaying structures, so no per-type printing routines
one standard format for storing them, so no per-type file I/O
no global structures, so every structure a function touches is passed in and passed back explicitly

The last point makes function calls larger than their imperative equivalents. In exchange, the flow of data is visible in the definitions and calls rather than hidden in shared state.

Functions are values

In many imperative languages a sub-program can be passed in as a parameter, but it is rare to be able to pass one back as a result. Functional languages allow both — functions may construct new functions and pass them on.

Functional languages allow functions to be treated as values.

The book’s example is deliberately illegal Pascal, which is the point:

TYPE OPTYPE = (ADD, SUB, MULT, QUOT);

FUNCTION ARITH(OP:OPTYPE):FUNCTION;
FUNCTION SUM(X,Y:INTEGER):INTEGER; BEGIN SUM := X+Y END;
FUNCTION DIFF(X,Y:INTEGER):INTEGER; BEGIN DIFF := X-Y END;
FUNCTION TIMES(X,Y:INTEGER):INTEGER; BEGIN TIMES := X*Y END;
FUNCTION DIVIDE(X,Y:INTEGER):INTEGER; BEGIN DIVIDE := X DIV Y END;
BEGIN
    CASE OP OF
    ADD: ARITH := SUM;
    SUB: ARITH := DIFF;
    MULT: ARITH := TIMES;
    QUOT: ARITH := DIVIDE;
    END
END

So ARITH(ADD) returns the function SUM, ARITH(SUB) returns DIFF, and we can add two numbers with:

ARITH(ADD)(3, 4)

This is illegal in many imperative languages because you cannot construct a function of type “function”.

Notice the double application: ARITH(ADD) produces a function, and (3, 4) applies it. Reading expressions like this fluently matters from unit 2 onward, where everything is a function applied to a function.

Why these are the same idea

If functions are values, then a structure holding two things can be a function that, given a selector, returns one of them. Data stops needing its own mechanism.

That sounds like a curiosity now. It is the entire content of unit 3, where booleans and natural numbers are built from nothing but functions.

Learning outcomes

describe-explicit-data-structures: Describe how functional languages build data explicitly from nested structures.
use-functions-as-values: Pass a function as an argument and return a function as a result.

Concepts

recursion: notes that nested functional data structures are defined recursively
functional-programming: explains explicit parameter passing of whole structures
functions-as-values: demonstrates passing and returning functions as first-class values

Where these ideas came from

Functional programming has its roots in mathematical logic, and it is older than imperative programming.

The logical background

Propositional calculus (Hamilton, De Morgan, Boole, mid-19th century) — true and false as basic values, with and, or, not as basic operations, and names standing for arbitrary truth values. Theorems are built from axioms by rules of inference.
Predicate calculus — extends this to non-logical values like numbers, sets and strings, adding predicates, functions, and quantifiers (universal and existential).
Peano’s number theory (late 19th century) — introduced numbers in terms of 0 and the successor function, so any number is that many successors of 0, with proofs by induction.

Two of these will reappear almost verbatim. Unit 3 builds the natural numbers exactly as Peano did — zero and a successor — and unit 4’s recursion is the computational face of induction.

Note also that within these calculi, associations between names and values are unchanging and expressions have no necessary evaluation order. The two properties we met earlier were inherited, not invented.

1931, and then 1936

Russell and Whitehead’s Principia Mathematica attempted to derive mathematics from logic. Hilbert’s Program then asked for a proof that this description was consistent and complete. In 1931 Gödel showed that any system powerful enough to describe arithmetic is necessarily incomplete.

The Program failed, but it had provoked serious investigation into the theory of computability. In 1936, three distinct formal approaches appeared:

Turing’s Turing machines
Kleene’s recursive function theory
Church’s λ calculus

Each is defined by a simple set of primitive operations and a simple set of rules for structuring them, and — most importantly — each has a proof theory.

All three have been shown formally to be equivalent to each other, and to digital computers. A result in one has an equivalent in the others, and any one may be used to model any other. Church hypothesised that all descriptions of computability are equivalent; Church’s thesis cannot be proved formally, but every subsequent description has turned out to be equivalent to the existing ones.

A difference of emphasis

The Turing machine treats computation as mechanised symbol manipulation based on assignment and time-ordered evaluation. Recursive function theory and the λ calculus treat it as structured function application, and both are evaluation order independent.

Two models of the same class of functions, each of which looks like one of our two programming styles.

Halting, and Church–Rosser

Turing showed that it is impossible to tell whether an arbitrary Turing machine will halt. The halting problem is unsolvable, and this applies equally to the λ calculus: there is no way of telling whether evaluation of an arbitrary λ expression will terminate.

But Church and Rosser showed something important about the λ calculus. The Church–Rosser theorem: if different evaluation orders do terminate, the results will be the same. They also showed that one particular evaluation order is more likely to lead to termination than any other.

This is the formal version of the order-independence we saw earlier, and it has practical weight: it may be more efficient to carry out some parts of a program in one order and other parts in another, and an evaluation-order-independent language can run parts in parallel.

From theory to languages

ALGOL 60 had recursion and a λ-calculus-based call-by-name parameter mechanism.
LISP (McCarthy, 1963) — recursive functions manipulating lists, untyped, with no necessary distinction between programs and data, since a LISP program is a list. Not purely functional, but hugely influential.
The SECD machine (Landin, mid-1960s) — an abstract interpreter giving the λ calculus an operational description, showing the calculus could actually be executed. Landin then used it to build an interpreter for ALGOL 60, an approach that became the Vienna Definition Language. He also developed ISWIM, a pure functional language.
Denotational semantics (Strachey, with Scott’s lattice-theoretic description) — describing imperative languages so that every construct has an equivalent function denotation. Still how programming languages are formally defined.
Later languages: POP-2, SASL, KRC, Miranda, Hope, and ML.
Backus’s 1977 paper argued computing was restricted by the structure of digital computers and imperative languages, proposing FP systems built from atomic objects, operations, and rules for structuring them.

The point of the history is not the dates. It is that the λ calculus was a model of computation before it was a programming language, which is exactly why it can be minimal and still be enough.

Learning outcomes

place-functional-programming-historically: Place functional programming among the 1936 computability results and the systems that followed.

Concepts

lambda-calculus: introduces Church’s λ calculus as one of the three 1936 foundations, and traces its use in language design
church-rosser-theorem: describes the guarantee that terminating evaluation orders agree on the result
denotational-semantics: describes Strachey’s approach of giving each construct an equivalent function denotation

The λ calculus underneath

We can now name what the rest of the module is about.

The λ calculus is a surprisingly simple yet powerful system, based on two mechanisms:

abstraction — generalising an expression through the introduction of names
application — evaluating a generalised expression by giving names particular values

There are no numbers, no booleans, no data structures, no control flow and no recursion. Two mechanisms, and nothing else.

Four properties make it suitable for describing programming languages:

It is universal. Abstraction and application are all that are needed to develop representations for arbitrary programming language constructs. The λ calculus can be treated as a universal machine code for programming languages.
It is evaluation order independent, so it can be used to describe and investigate the implications of different evaluation orders in different languages.
It has well developed proof techniques, which can be applied to λ calculus descriptions of other languages.
It is very simple, so it is relatively easy to implement — a λ calculus description of a language can be run as a prototype.

The useful way to hold it: real languages are notation on top of this core. Each addition — numbers, conditionals, data, recursion — can be explained by translating it back down into pure λ terms. That translation is what units 2 to 4 actually do.

Learning outcomes

say-why-lambda-calculus-is-the-core: Say why the λ calculus is treated as the machine code of functional programming.

Concepts

lambda-calculus: outlines the mechanics of abstraction and application, and why they suffice
execution-order-independence: identifies order independence as one of the calculus’s useful properties

What you now have, and where we go

Pure λ calculus does not look much like a programming language. All it provides are names, function abstraction and function application. But it is straightforward to develop new language constructs from this basis, and that is what the module does: use the λ calculus to construct, step by step, a compact general-purpose functional programming notation.

The three units ahead:

Lambda Calculus — the pure calculus: its syntax and evaluation rules, and functions for representing pairs of objects, which become building blocks later. Simplified notations for λ expressions and function definitions are introduced here too.
Conditions, Booleans and Integers — representations for boolean values and operations, numbers, and conditional expressions.
Recursion and Arithmetic — representations for recursive functions, used to construct the arithmetic operations.

Each unit builds only from what the ones before it established. Nothing is assumed and nothing is imported.

Learning outcomes

say-what-functional-programming-is: Say what functional programming is, in terms of what a program is made of.
contrast-names-and-values: Contrast how imperative and functional languages associate names with values.
explain-order-independence: Explain why the order of evaluation does not change a functional program’s result.
write-repetition-as-recursion: Express repetition as recursion rather than as a loop.
use-functions-as-values: Pass a function as an argument and return a function as a result.
describe-explicit-data-structures: Describe how functional languages build data explicitly from nested structures.
place-functional-programming-historically: Place functional programming among the 1936 computability results and the systems that followed.
say-why-lambda-calculus-is-the-core: Say why the λ calculus is treated as the machine code of functional programming.

Concepts

lambda-calculus: summarises how the module will use the λ calculus to build a programming notation step by step
recursion: outlines the final unit’s focus on recursive functions and arithmetic

Conclusion

Functional and imperative programming differ fundamentally, and every difference follows from one decision about names.

An imperative name is a place whose contents change; a functional name is a label fixed once. Order-dependence, loops and mutable data structures are all consequences of the first choice.
Execution order does not affect the result of a functional program.

Nested calls cannot interact through shared names, so there is nothing for order to change. Church and Rosser made this formal: terminating evaluation orders agree.
Repetition is recursion, and data is written whole.

A loop’s index becomes an argument and its accumulator becomes a returned value. Structures are passed and rebuilt explicitly rather than mutated in place.
First-class functions are what make the rest possible.

A function that returns a function lets one definition cover a family of operations — and lets a data structure be a function that hands you the component you ask for.
Functional programming is rooted in 20th-century computability theory.

Church’s λ calculus, Turing’s machines and Kleene’s recursive functions all appeared in 1936 and define the same class of computable functions. The λ calculus is the one that became a programming style.
The λ calculus is a minimal, universal foundation.

Abstraction and application are enough for every programming language construct, which is why it is worth learning as the machine code beneath functional languages.

Where next

The next unit, Elements of Lambda Calculus, stops motivating and starts defining. You will get the grammar for λ expressions, the reduction rules that evaluate them, and your first functions built from nothing at all — ending with selectors and pairs, the building blocks the two units after it depend on.

← Introduction Elements of Lambda Calculus →

--- title: Lecture notes — Introduction keywords: - ver. 1.0.1 date: '2026-08-19' --- [← Introduction](index.qmd){.hg-back} ## Where we are This is the first unit of the module, so nothing is assumed from an earlier one. What we do assume is that you have written programs in an imperative language — Pascal, C, Java, Python — and are comfortable with variables, assignment, loops and arrays. That experience is exactly what this unit works against. We are going to remove the assignment statement and see what is left. ## What you will be able to do 1. `say-what-functional-programming-is` — Say what functional programming is, in terms of what a program is made of. 2. `contrast-names-and-values` — Contrast how imperative and functional languages associate names with values. 3. `explain-order-independence` — Explain why the order of evaluation does not change a functional program's result. 4. `write-repetition-as-recursion` — Express repetition as recursion rather than as a loop. 5. `use-functions-as-values` — Pass a function as an argument and return a function as a result. 6. `describe-explicit-data-structures` — Describe how functional languages build data explicitly from nested structures. 7. `place-functional-programming-historically` — Place functional programming among the 1936 computability results and the systems that followed. 8. `say-why-lambda-calculus-is-the-core` — Say why the λ calculus is treated as the machine code of functional programming. ## What we will cover - **Functional programming** — an approach based on function calls as the primary programming construct. - **Imperative programming** — programming as a sequence of commands that change variables. - **Name–value association** — the rule governing what a name stands for, and whether it can change. - **Execution order independence** — the property that evaluation order does not affect the result. - **Recursion** — repetition through nested function calls rather than command repetition. - **Functions as values** — functions that can be passed as arguments and returned as results. - **λ calculus** — Church's system of function abstraction and application. - **Church–Rosser theorem** — if different evaluation orders terminate, they give the same result. - **Denotational semantics** — describing language constructs by giving each an equivalent function. ## Why another way to program Most of the programming you have done treats a program as a sequence of commands that change a store. Read a variable, compute, write it back, repeat. This module asks what happens if you remove that entirely. No assignment. No statement order. No mutable variables. What is left? The answer is that nothing is lost. Every computable function can still be expressed. Making that case is what this unit is for, and it takes the rest of the module to carry out in full. We will work through the differences one at a time: - what a **name** means, which is where the two styles first part company - why **execution order** stops mattering once names cannot be reassigned - how **repetition** happens without a loop - how **data** is built, and why functions can be values like any other Then we turn to where these ideas came from. Functional programming is not a recent style. It is the programming face of results proved in 1936, at the same time as the Turing machine and shown equivalent to it. Finally we name the object the rest of the module is about: the λ calculus. This unit motivates it and does not yet teach it. ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "say-what-functional-programming-is" >}}: Say what functional programming is, in terms of what a program is made of. - {{< badge outcome "contrast-names-and-values" >}}: Contrast how imperative and functional languages associate names with values. ::: ## What functional programming is Here is the definition the book works from: > Functional programming is an approach to programming based on function calls as the primary programming construct. **Functional programming** provides practical approaches to problem solving, and — with its roots in the theory of computing — it forms a bridge between formal methods in computing and their application. That bridge is worth keeping in view. The reason this style has such a clean theory is that it *started* as theory. Set against it is **imperative programming**, which we will use as the contrast throughout: programming as a sequence of commands, each typically changing the value of a variable. The rest of the unit works through four differences in turn — names, execution order, repetition, and data — and then turns to the history and to the λ calculus itself. One framing to carry with you. Every difference we meet follows from a single decision about what a name is allowed to mean. The next section makes that decision explicit, and everything after it is a consequence. ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "say-what-functional-programming-is" >}}: Say what functional programming is, in terms of what a program is made of. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "functional-programming" >}}: defines functional programming and states its bridge role between formal methods and practice - {{< badge concept "imperative-programming" >}}: sets up the contrast this unit works against ::: ## Names and values Start somewhere simpler than a programming language: an electronic calculator. A calculator does arithmetic on numbers, and its limitation is that there is no way to *generalise* a calculation. To do the same calculation with different values, you re-enter the whole thing. Programming languages fix this with **names**. We write a program using names to stand for values in general, then run it with the names taking particular values from the input. The program does not change; only the input does. So far both styles agree. They part company over what the association between a name and a value is allowed to do. ### The imperative rule Traditional languages are built around a **variable**: a *changeable* association between a name and values. They are called imperative because a program is a sequence of commands: ```text <command1> ; <command2> ; <command3> ; ... ``` Each command is typically an **assignment**, which works out the value of an expression and associates the result with a name: ```text <name> := <expression> ``` Each command's expression may refer to variables that earlier commands changed. That is how values travel from command to command. > **In imperative languages, the same name may be associated with different values.** ### The functional rule Functional languages are built around structured function calls. A program is an expression: a function call that calls other functions in turn. ```text <function1>(<function2>(<function3> ... ) ... )) ``` Each function receives values from its caller and passes new values back. This is **function composition**, or nesting. Names are only introduced as the **formal parameters** of functions, and are given values by function calls supplying **actual parameters**. Once a formal parameter is associated with an actual parameter value, there is no way for it to be associated with a new one. There is no assignment, so there is no command sequence and no command repetition. > **In functional languages, a name is only ever associated with one value.** ::: {.callout-note title="Why this one difference matters so much"} To know what a name means in an imperative program, you must know *when* you are asking — which commands have already run. To know what a name means in a functional program, you look at where it was bound. Time does not enter. The next three sections are all consequences of this. ::: ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "contrast-names-and-values" >}}: Contrast how imperative and functional languages associate names with values. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "name-value-association" >}}: contrasts the changeable variable of imperative languages with the fixed binding of functional ones - {{< badge concept "imperative-programming" >}}: defines imperative programming as sequences of commands built from assignment - {{< badge concept "functional-programming" >}}: defines a functional program as nested function calls ::: ## Execution order stops mattering In imperative languages the order in which commands are carried out is usually crucial. Values travel between commands through shared variables, and one command may change a variable before the next uses it. Change the order and the behaviour of the whole program may change. ### The swap, and two ways to get it wrong To swap `X` and `Y`: ```text T := X; X := Y; Y := T ``` `T`'s value depends on `X`, `X`'s depends on `Y`, and `Y`'s depends on `T`. Any change in the sequence completely changes what happens. Permuting the same three assignments: ```text X := Y; T := X; Y := T ``` sets `X` to `Y`. And: ```text T := X; Y := T; X := Y ``` sets `Y` to `X`. Same three commands, three different programs. Not every command sequence is order-dependent — if the expressions do not refer to each other's names, the order does not matter. But most programs depend on precise sequencing. > **Imperative languages have fixed execution orders.** ### The functional case In functional languages, function calls cannot change the values associated with shared names. So the order in which nested calls are carried out does not matter, because the calls cannot interact. Suppose we have functions written in a Pascalish style: ```text FUNCTION F( X,Y,Z:INTEGER):INTEGER ; BEGIN ... END FUNCTION A(P:INTEGER):INTEGER ; BEGIN ... END FUNCTION B(Q:INTEGER):INTEGER ; BEGIN ... END FUNCTION C(R:INTEGER):INTEGER ; BEGIN ... END ``` Then in the call $$F(A(D),\ B(D),\ C(D))$$ the order in which `A(D)`, `B(D)` and `C(D)` are carried out does not matter, because `A`, `B` and `C` cannot change their common actual parameter `D`. > **In functional languages, there is no necessary execution order.** Functional programs must of course be executed in *some* order — all programs are — but the order does not affect the final result. This is **execution order independence**, and it is one of the real strengths of the approach: it is what allows parts of a program to be reordered, or run in parallel, with no extra machinery, because there is no shared state to protect. ::: {.callout-important title="A caveat to plant now"} Order does not affect the *result*. It can affect whether evaluation **terminates**, and how much work is done. We will meet that properly in unit 2 as normal versus applicative order, and it becomes decisive in unit 4. ::: ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "explain-order-independence" >}}: Explain why the order of evaluation does not change a functional program's result. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "execution-order-independence" >}}: explains why nested functional calls have no necessary execution order - {{< badge concept "imperative-programming" >}}: illustrates how command sequences depend on their order ::: ## Repetition without loops In imperative languages a name can take new values, so repeating a computation does not require duplicating the commands. The same commands run again. To sum the `N` elements of array `A`, we do not write: ```text SUM1 := A[1]; SUM2 := SUM1 + A[2]; SUM3 := SUM2 + A[3]; ... ``` Instead we reuse one name for the sum and another for the index, and loop: ```text I := 0; SUM := 0; WHILE I < N DO BEGIN I := I + 1; SUM := SUM + A[I] END ``` > **In imperative languages, new values may be associated with the same name through command repetition.** ### The functional version Because the same name cannot be reused with different values, nested function calls create *new versions* of names for new values. And because command repetition is unavailable, **recursion** does the repeating: a function calls itself, creating new versions of its formal parameters bound to new actual parameter values. ```text FUNCTION SUM(A:ARRAY [1..N] OF INTEGER; I,N:INTEGER):INTEGER; BEGIN IF I > N THEN SUM := 0 ELSE SUM := A[I] + SUM(A,I+1,N) END ``` For the call `SUM(B,1,M)` the sum is found through successive recursive calls: ```text B[1] + SUM(B,2,M) = B[1] + B[2] + SUM(B,3,M) ... B[1] + B[2] + ... + B[M] + SUM(B, M+1, M) B[1] + B[2] + ... + B[M] + 0 ``` Each recursive call creates new local versions of `A`, `I` and `N`, and the previous versions become inaccessible. At the end of each call the new locals are lost, the partial sum returns to the previous call, and the previous locals come back into use. > **In functional languages, new values are associated with new names through recursive function call nesting.** Line the two up and the correspondence is exact: - the loop's **index** becomes an argument, different on each call rather than updated - the loop's **accumulator** becomes a returned value, built as the calls return - the loop's **termination test** becomes the base case, `I > N` The variable that "changes" in the loop is really a sequence of values. Recursion makes that sequence explicit. ::: {.callout-note title="A harder question, deferred"} This works because `SUM` can refer to itself by name. In unit 4 we will find that in the pure λ calculus a name is an *abbreviation*, not a reference — so a definition mentioning its own name expands forever. Getting recursion back takes real work. ::: ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "write-repetition-as-recursion" >}}: Express repetition as recursion rather than as a loop. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "recursion" >}}: explains how functional languages achieve repetition through recursive call nesting - {{< badge concept "imperative-programming" >}}: explains repetition by command loops over reused names ::: ## Data structures, and functions as values Two apparently separate ideas, which will turn out to be one. ### Data is written whole In imperative languages, array elements and record fields are changed by successive assignments. With no assignment, sub-structures cannot be changed one at a time. Instead you write down a whole structure with explicit changes to the appropriate sub-structure. > **Functional languages provide explicit representations for data structures.** Functional languages do not provide arrays, because without assignment there is no easy way to access an arbitrary element — and writing out an entire array to change one element would be unwieldy. Instead they provide nested structures like **lists**, based on recursive notations where operations on a whole structure are described in terms of recursive operations on sub-structures. The representation for nested data often looks very like the nested function call notation. In LISP, the same representation is used for both. This has real advantages: - one standard format for **displaying** structures, so no per-type printing routines - one standard format for **storing** them, so no per-type file I/O - no **global** structures, so every structure a function touches is passed in and passed back explicitly The last point makes function calls larger than their imperative equivalents. In exchange, the flow of data is visible in the definitions and calls rather than hidden in shared state. ### Functions are values In many imperative languages a sub-program can be passed *in* as a parameter, but it is rare to be able to pass one back as a result. Functional languages allow both — functions may construct new functions and pass them on. > **Functional languages allow functions to be treated as values.** The book's example is deliberately illegal Pascal, which is the point: ```text TYPE OPTYPE = (ADD, SUB, MULT, QUOT); FUNCTION ARITH(OP:OPTYPE):FUNCTION; FUNCTION SUM(X,Y:INTEGER):INTEGER; BEGIN SUM := X+Y END; FUNCTION DIFF(X,Y:INTEGER):INTEGER; BEGIN DIFF := X-Y END; FUNCTION TIMES(X,Y:INTEGER):INTEGER; BEGIN TIMES := X*Y END; FUNCTION DIVIDE(X,Y:INTEGER):INTEGER; BEGIN DIVIDE := X DIV Y END; BEGIN CASE OP OF ADD: ARITH := SUM; SUB: ARITH := DIFF; MULT: ARITH := TIMES; QUOT: ARITH := DIVIDE; END END ``` So `ARITH(ADD)` returns the function `SUM`, `ARITH(SUB)` returns `DIFF`, and we can add two numbers with: ```text ARITH(ADD)(3, 4) ``` This is illegal in many imperative languages because you cannot construct a function of type "function". ::: {.column-margin} Notice the double application: `ARITH(ADD)` produces a function, and `(3, 4)` applies it. Reading expressions like this fluently matters from unit 2 onward, where *everything* is a function applied to a function. ::: ### Why these are the same idea If functions are values, then a structure holding two things can be a **function** that, given a selector, returns one of them. Data stops needing its own mechanism. That sounds like a curiosity now. It is the entire content of unit 3, where booleans and natural numbers are built from nothing but functions. ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "describe-explicit-data-structures" >}}: Describe how functional languages build data explicitly from nested structures. - {{< badge outcome "use-functions-as-values" >}}: Pass a function as an argument and return a function as a result. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "recursion" >}}: notes that nested functional data structures are defined recursively - {{< badge concept "functional-programming" >}}: explains explicit parameter passing of whole structures - {{< badge concept "functions-as-values" >}}: demonstrates passing and returning functions as first-class values ::: ## Where these ideas came from Functional programming has its roots in mathematical logic, and it is older than imperative programming. ### The logical background - **Propositional calculus** (Hamilton, De Morgan, Boole, mid-19th century) — `true` and `false` as basic values, with `and`, `or`, `not` as basic operations, and names standing for arbitrary truth values. Theorems are built from axioms by rules of inference. - **Predicate calculus** — extends this to non-logical values like numbers, sets and strings, adding predicates, functions, and **quantifiers** (universal and existential). - **Peano's number theory** (late 19th century) — introduced numbers in terms of `0` and the **successor** function, so any number is that many successors of `0`, with proofs by induction. Two of these will reappear almost verbatim. Unit 3 builds the natural numbers exactly as Peano did — zero and a successor — and unit 4's recursion is the computational face of induction. Note also that within these calculi, associations between names and values are unchanging and expressions have no necessary evaluation order. The two properties we met earlier were inherited, not invented. ### 1931, and then 1936 Russell and Whitehead's *Principia Mathematica* attempted to derive mathematics from logic. Hilbert's Program then asked for a proof that this description was **consistent** and **complete**. In 1931 Gödel showed that any system powerful enough to describe arithmetic is necessarily incomplete. The Program failed, but it had provoked serious investigation into the **theory of computability**. In 1936, three distinct formal approaches appeared: - Turing's **Turing machines** - Kleene's **recursive function theory** - Church's **λ calculus** Each is defined by a simple set of primitive operations and a simple set of rules for structuring them, and — most importantly — each has a proof theory. All three have been shown formally to be **equivalent** to each other, and to digital computers. A result in one has an equivalent in the others, and any one may be used to model any other. Church hypothesised that all descriptions of computability are equivalent; **Church's thesis** cannot be proved formally, but every subsequent description has turned out to be equivalent to the existing ones. ::: {.callout-note title="A difference of emphasis"} The Turing machine treats computation as mechanised symbol manipulation based on assignment and time-ordered evaluation. Recursive function theory and the λ calculus treat it as structured function application, and both are evaluation order independent. Two models of the same class of functions, each of which looks like one of our two programming styles. ::: ### Halting, and Church–Rosser Turing showed that it is impossible to tell whether an arbitrary Turing machine will halt. The **halting problem** is unsolvable, and this applies equally to the λ calculus: there is no way of telling whether evaluation of an arbitrary λ expression will terminate. But Church and Rosser showed something important about the λ calculus. The **Church–Rosser theorem**: if different evaluation orders do terminate, the results will be the same. They also showed that one particular evaluation order is more likely to lead to termination than any other. This is the formal version of the order-independence we saw earlier, and it has practical weight: it may be more efficient to carry out some parts of a program in one order and other parts in another, and an evaluation-order-independent language can run parts in parallel. ### From theory to languages - **ALGOL 60** had recursion and a λ-calculus-based call-by-name parameter mechanism. - **LISP** (McCarthy, 1963) — recursive functions manipulating lists, untyped, with no necessary distinction between programs and data, since a LISP program *is* a list. Not purely functional, but hugely influential. - **The SECD machine** (Landin, mid-1960s) — an abstract interpreter giving the λ calculus an *operational* description, showing the calculus could actually be executed. Landin then used it to build an interpreter for ALGOL 60, an approach that became the Vienna Definition Language. He also developed **ISWIM**, a pure functional language. - **Denotational semantics** (Strachey, with Scott's lattice-theoretic description) — describing imperative languages so that every construct has an equivalent function **denotation**. Still how programming languages are formally defined. - Later languages: POP-2, SASL, KRC, **Miranda**, Hope, and **ML**. - **Backus's 1977 paper** argued computing was restricted by the structure of digital computers and imperative languages, proposing **FP** systems built from atomic objects, operations, and rules for structuring them. The point of the history is not the dates. It is that the λ calculus was a model of computation before it was a programming language, which is exactly why it can be minimal and still be enough. ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "place-functional-programming-historically" >}}: Place functional programming among the 1936 computability results and the systems that followed. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "lambda-calculus" >}}: introduces Church's λ calculus as one of the three 1936 foundations, and traces its use in language design - {{< badge concept "church-rosser-theorem" >}}: describes the guarantee that terminating evaluation orders agree on the result - {{< badge concept "denotational-semantics" >}}: describes Strachey's approach of giving each construct an equivalent function denotation ::: ## The λ calculus underneath We can now name what the rest of the module is about. The λ calculus is a surprisingly simple yet powerful system, based on two mechanisms: - **abstraction** — generalising an expression through the introduction of names - **application** — evaluating a generalised expression by giving names particular values There are no numbers, no booleans, no data structures, no control flow and no recursion. Two mechanisms, and nothing else. Four properties make it suitable for describing programming languages: - **It is universal.** Abstraction and application are all that are needed to develop representations for arbitrary programming language constructs. The λ calculus can be treated as a **universal machine code for programming languages**. - **It is evaluation order independent**, so it can be used to describe and investigate the implications of different evaluation orders in different languages. - **It has well developed proof techniques**, which can be applied to λ calculus descriptions of other languages. - **It is very simple**, so it is relatively easy to implement — a λ calculus description of a language can be run as a prototype. [The useful way to hold it: real languages are notation on top of this core.]{.hg-key} Each addition — numbers, conditionals, data, recursion — can be *explained* by translating it back down into pure λ terms. That translation is what units 2 to 4 actually do. ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "say-why-lambda-calculus-is-the-core" >}}: Say why the λ calculus is treated as the machine code of functional programming. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "lambda-calculus" >}}: outlines the mechanics of abstraction and application, and why they suffice - {{< badge concept "execution-order-independence" >}}: identifies order independence as one of the calculus's useful properties ::: ## What you now have, and where we go Pure λ calculus does not look much like a programming language. All it provides are names, function abstraction and function application. But it is straightforward to develop new language constructs from this basis, and that is what the module does: use the λ calculus to construct, step by step, a compact general-purpose functional programming notation. The three units ahead: - **Lambda Calculus** — the pure calculus: its syntax and evaluation rules, and functions for representing pairs of objects, which become building blocks later. Simplified notations for λ expressions and function definitions are introduced here too. - **Conditions, Booleans and Integers** — representations for boolean values and operations, numbers, and conditional expressions. - **Recursion and Arithmetic** — representations for recursive functions, used to construct the arithmetic operations. Each unit builds only from what the ones before it established. Nothing is assumed and nothing is imported. ::: {.hypergen-refs .outcomes} <h1>Learning outcomes</h1> - {{< badge outcome "say-what-functional-programming-is" >}}: Say what functional programming is, in terms of what a program is made of. - {{< badge outcome "contrast-names-and-values" >}}: Contrast how imperative and functional languages associate names with values. - {{< badge outcome "explain-order-independence" >}}: Explain why the order of evaluation does not change a functional program's result. - {{< badge outcome "write-repetition-as-recursion" >}}: Express repetition as recursion rather than as a loop. - {{< badge outcome "use-functions-as-values" >}}: Pass a function as an argument and return a function as a result. - {{< badge outcome "describe-explicit-data-structures" >}}: Describe how functional languages build data explicitly from nested structures. - {{< badge outcome "place-functional-programming-historically" >}}: Place functional programming among the 1936 computability results and the systems that followed. - {{< badge outcome "say-why-lambda-calculus-is-the-core" >}}: Say why the λ calculus is treated as the machine code of functional programming. ::: ::: {.hypergen-refs .concepts} <h1>Concepts</h1> - {{< badge concept "lambda-calculus" >}}: summarises how the module will use the λ calculus to build a programming notation step by step - {{< badge concept "recursion" >}}: outlines the final unit's focus on recursive functions and arithmetic ::: ## Conclusion - Functional and imperative programming differ fundamentally, and every difference follows from one decision about names. > An imperative name is a place whose contents change; a functional name is a label fixed once. Order-dependence, loops and mutable data structures are all consequences of the first choice. - Execution order does not affect the result of a functional program. > Nested calls cannot interact through shared names, so there is nothing for order to change. Church and Rosser made this formal: terminating evaluation orders agree. - Repetition is recursion, and data is written whole. > A loop's index becomes an argument and its accumulator becomes a returned value. Structures are passed and rebuilt explicitly rather than mutated in place. - First-class functions are what make the rest possible. > A function that returns a function lets one definition cover a family of operations — and lets a data structure *be* a function that hands you the component you ask for. - Functional programming is rooted in 20th-century computability theory. > Church's λ calculus, Turing's machines and Kleene's recursive functions all appeared in 1936 and define the same class of computable functions. The λ calculus is the one that became a programming style. - The λ calculus is a minimal, universal foundation. > Abstraction and application are enough for every programming language construct, which is why it is worth learning as the machine code beneath functional languages. ### Where next The next unit, **Elements of Lambda Calculus**, stops motivating and starts defining. You will get the grammar for λ expressions, the reduction rules that evaluate them, and your first functions built from nothing at all — ending with selectors and pairs, the building blocks the two units after it depend on. ::: {.hg-nav} [← Introduction](index.qmd){.hg-prev} [Elements of Lambda Calculus →](../2_lambda_calculus/index.qmd){.hg-next} :::