History of Functional Programming
From lambda calculus and Lisp to ML, Scheme, and Haskell: programming with functions, values, and controlled effects.
Functional programming treats computation as the evaluation and combination of functions. Instead of describing a sequence of changes to memory, a program builds values from other values. The important questions become: what goes in, what comes out, and what can change along the way?
input → function → output
The idea is older than electronic computers. Its path into programming came through mathematical logic, symbolic AI, theorem proving, and programming-language research.
Lambda Calculus — Functions as the Whole Machine
Alonzo Church developed lambda calculus in the 1930s while studying what it means for a function to be computable. It has only three basic forms:
x a variable
λx. body a function that takes x
f x applying f to x
λx. x + 1 is a function. Applying it to 4 gives 5. From variable binding and application alone, lambda calculus can express numbers, data structures, conditionals, recursion, and computation itself.
The notation was never meant as a convenient industrial programming language. Its value was that programs could be treated as mathematical expressions. Replacing an expression with an equal expression did not change its meaning. That property became the foundation for reasoning about functional programs.
Lisp — The First Working Family
John McCarthy’s 1960 Lisp paper turned symbolic functions into a programming system for the IBM 704. Lisp represented both programs and data as lists. A program could construct, inspect, and evaluate the same kind of symbolic structure.
(define (square x)
(* x x))
(square 5)
Lisp made recursion, higher-order functions, garbage collection, and symbolic manipulation practical. It was not purely functional: mutation was available from the beginning. But Lisp showed that functions and lists were enough to make a real language expressive, interactive, and useful for AI research.
The Lisp family later split into Common Lisp, Scheme, Clojure, Racket, and many smaller dialects. Their shared habit is treating code as data and functions as ordinary values that can be stored, passed, and returned.
The Critique of State
Most early programming followed the structure of the machine: named memory locations, assignment, loops, and instructions that changed state. This model maps naturally to hardware, but it makes a program’s meaning depend on the order of updates.
total = total + price
The right side reads the old total; the left side replaces it. Reordering similar lines can change the result. Shared mutable state makes this harder again, especially when several parts of a program run at once.
In 1977, John Backus used his Turing Award lecture to argue against this “von Neumann style.” His proposed alternative built programs by composing functions rather than by naming and updating intermediate storage. The argument did not remove state from computing, but it made state something to isolate rather than spread through every calculation.
ML — Types Meet Functions
Robin Milner developed ML in the 1970s for the Edinburgh LCF theorem prover. The language needed functions, recursion, symbolic data, and a type system strong enough to catch mistakes in proof programs.
fun length [] = 0
| length (_ :: rest) = 1 + length rest
ML introduced a durable combination: algebraic data types, pattern matching, parametric polymorphism, and type inference. The compiler can infer that length works on a list of any element type without being told what that type is.
length : 'a list -> int
This made static types feel less like annotation overhead and more like information recovered from the program. Standard ML and OCaml carried the design into teaching, compilers, proof systems, and production software.
Scheme — Small Lisp, Clear Semantics
Scheme appeared in 1975 as a small Lisp dialect based closely on lambda calculus. It kept lexical scope and first-class functions at the centre, while reducing the language to a compact core.
(map (lambda (x) (* x x)) '(1 2 3 4))
; => (1 4 9 16)
map receives a function as a value. The lambda has no name because it is needed only once. This is one of the everyday forms functional programming took: operations over collections described by composing small functions rather than writing explicit loops and mutable counters.
Scheme also made continuations, tail calls, interpreters, and evaluation order visible subjects of language design. Its small size made it important in programming-language education even when larger Lisp dialects were used elsewhere.
Haskell — Purity as a Language Boundary
By 1987, more than a dozen non-strict, purely functional languages existed. A committee formed at the Functional Programming Languages and Computer Architecture conference to consolidate that work. Haskell was the result.
Haskell made a sharp distinction between pure expressions and effects. A pure function has no hidden input, does not mutate external state, and always returns the same result for the same arguments.
double x = x * 2
double 4 is always 8. Reading a file, printing text, generating randomness, and changing a database cannot fit that rule, so Haskell represents them in types such as IO. Effects still happen; they are kept in explicit parts of the program.
Lazy evaluation, type classes, and monads became closely associated with Haskell. The terminology is dense, but the underlying aim is direct: preserve simple reasoning about ordinary expressions while giving effects a visible structure.
Functional Ideas in Ordinary Languages
Pure functional languages remained a smaller part of industry than Java, C, C++, Python, or JavaScript. Their ideas did not remain separate. Garbage collection, closures, immutable data, map, filter, reduce, pattern matching, async composition, and type inference spread into mainstream languages.
const names = users
.filter(user => user.active)
.map(user => user.name)
The code describes a transformation from one collection to another. It avoids exposing the temporary index, accumulator, and mutation that an equivalent loop would need. This does not make the surrounding program pure, but it makes one part of it easier to test and rearrange.
Functional programming did not replace imperative programming. Operating systems, graphics engines, databases, and user interfaces all must change state. The lasting contribution is the boundary: keep calculations as functions where possible, make state and effects explicit where they are necessary, and let types describe the shapes of values moving through the program.