Introduction to Functional Programming

Lambda Calculus · v1.0.2

2026-09-28 02:12:33

Overview

The restrictions

Start from Python, and take three things away:

• no assignment — a name is bound once and never rebound
• no statement order — no sequence of commands to run in turn
• no mutable variables — nothing is updated in place

Everything else in this module is a consequence of those three.

Is it still a useful language?

Nothing is lost. Every computable function can still be expressed.

• Making that case is what this unit is for
• Carrying it out in full takes the rest of the module

The claim is not that the restricted language is convenient. It is that it is complete: anything computable at all remains expressible. That is a result, not a matter of taste, and the rest of the module is the demonstration.

What the restrictions buy

• Function calls cannot change values shared with other calls
• So parts of a program can be reordered, or run in parallel, with no extra machinery
• There is no shared state to protect

The restriction that looks like a loss is what makes concurrency safe.

The four differences

• what a name means — 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

What functional programming is

Definition — functional programming

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

• Its roots are in the theory of computing
• It forms a bridge between formal methods and their application

The theory is clean because the style started as theory.

The contrast — imperative programming

Imperative

A sequence of commands, each typically changing the value of a variable.

t = x
x = y
y = t

Functional

An expression: a function call that calls other functions in turn.

f1(f2(f3(...)))

Definition over commands

• An imperative program does things, in order
• A functional program is an expression, evaluated
• Each function receives values from its caller and passes new values back

This is function composition, or nesting.

Symbols

Names generalise a calculation

A calculator cannot generalise: to repeat a calculation with different values, re-enter the whole thing.

• A name stands for a value in general
• The program does not change; only the input does

Both styles agree this far. They part over what a name is allowed to do.

The two rules

The imperative rule

A variable: a changeable association between a name and values.

\[\langle name \rangle = \langle expression \rangle\]

The same name may hold different values.

The functional rule

Names are introduced only as formal parameters, bound by actual parameters.

A name is only ever associated with one value.

Binding: declaration and invocation

def f(x, y):     # formal parameters
    return x + y

f(3, 4)          # actual parameters

• Declaration introduces the names
• Invocation binds them, once, for the duration of that call
• There is no assignment, so no way to rebind

When is a name’s meaning fixed?

• Imperative: to know what a name means, know when you are asking — which commands have run
• Functional: to know what a name means, look at where it was bound

Time does not enter.

Example: which x does f see?

x = 1

def f():
    return x     # which x?

def g():
    x = 2
    return f()

Two defensible answers, and languages differ on which they give.

Lexical and dynamic scoping

Lexical scoping

f sees the x where f was written.

g() is 1.

Dynamic scoping

f sees the x of whoever called it.

g() is 2.

Lexical scoping is what makes “look at where it was bound” a complete answer.

Evaluation

Imperative: order is everything

To swap x and y:

t = x
x = y
y = t

Permute the same three commands and the program changes:

• x = y; t = x; y = t sets x to y
• t = x; y = t; x = y sets y to x

Same three commands, three different programs.

Functional: order does not matter

def f(x, y, z): ...
def a(p): ...
def b(q): ...
def c(r): ...

\[f(a(d),\ b(d),\ c(d))\]

• a, b and c cannot change their common argument d
• So the order in which they run cannot change the result

Three orders, one result

Whichever order the arguments are evaluated in, f receives the same three values.

How do we know they agree?

The guarantee is a theorem, not an observation.

• Church–Rosser: if different evaluation orders terminate, the results are the same
• One particular order is more likely to terminate than any other

Order independence is proved, not assumed.

Repetition

No loops

• A loop needs a name that takes new values on each pass
• Without assignment, there is no such name
• Recursion does the repeating instead

A function calls itself, creating new versions of its parameters.

The imperative versions

for

s = 0
for i in range(len(a)):
    s = s + a[i]

while

i = 0
s = 0
while i < len(a):
    s = s + a[i]
    i = i + 1

Both reuse s and i, which is exactly what is unavailable.

The recursive version

def total(a, i):
    if i >= len(a):
        return 0
    else:
        return a[i] + total(a, i + 1)

For total(b, 0):

b[0] + total(b, 1) =
b[0] + b[1] + total(b, 2) = ...

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 >= len(a)

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

This works because total can refer to itself by name. Unit 4 finds 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.

Data structures in functional programming

Data is written whole

• With no assignment, sub-structures cannot be changed one at a time
• Instead a whole structure is written down, with explicit changes to the appropriate part

Functional languages provide explicit representations for data structures.

Transformation, not mutation

In place

a[0] = 99

The old list is gone. Anything else holding it sees the change.

Rebuilt

[99] + a[1:]

A new list. The original is untouched and still valid.

No arrays, but lists

• Without assignment there is no easy way to reach an arbitrary element
• Writing out a whole array to change one element would be unwieldy
• Lists and other nested structures are used instead, with recursive operations on sub-structures

The representation for nested data looks much like nested function calls. In LISP they are the same.

What explicit data buys

• one standard format for displaying structures — no per-type printing routines
• one standard format for storing them — no per-type file I/O
• no global structures — every structure is passed in and passed back

Calls get larger; the flow of data becomes visible rather than hidden in shared state.

Functions are values

Passing a function in is common. Returning one out is rare — and is the point.

FUNCTION arith(OpType op) {   // illegal return type
    switch (op) {
        case ADD:  return sum;
        case SUB:  return diff;
    }
}

arith(ADD) produces a function; (3, 4) applies it.

History of functional programming

The logical background

Functional programming is not a recent style.

• It is the programming face of results proved in 1936
• The same year as the Turing machine, and shown equivalent to it

From logic to the λ calculus

• 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
• Both of the latter are evaluation order independent

The λ calculus was a model of computation before it was a programming language.

Some results in lambda calculus

Halting

Turing showed it is impossible to tell whether an arbitrary Turing machine will halt.

• The halting problem is unsolvable
• This applies equally to the λ calculus: no way to tell whether evaluation of an arbitrary λ expression terminates

Church–Rosser

If different evaluation orders do terminate, the results will be the same.

• One particular evaluation order is more likely to terminate than any other
• This is the formal version of the order independence seen earlier

It may be efficient to run some parts in one order and others in another — or in parallel.

Conclusion

Summary

• A functional program is nested function calls, not a command sequence
• A name is bound once; time does not enter
• Order independence follows, and is guaranteed by Church–Rosser

• Repetition is recursion: the loop’s index becomes an argument
• Data is rebuilt whole rather than mutated
• Functions are values like any other

Where next

Elements of Lambda Calculus — the next unit in this module.

• The λ calculus is simpler still: names, abstraction, application, and nothing else
• It is the simplest language in which everything computable can be written

This unit motivates it. The next one defines it.