F0 · History · optional
The evolution of functional languages & runtimes
Everything Elixir leans on was argued out decades earlier. This module traces the line — from the λ-calculus to the immutable runtimes that made the idea ordinary.
This chapter is context, not a prerequisite: F1 stands on its own. Read it to see where each idea came from and why it survived. Three dives follow the overview, and each one pairs a historical idea with the exact place it reappears in Elixir.
One line, six steps
Functional programming is not a recent style; it is a sixty-year argument about how to compute without mutable state. Each step below kept what worked and dropped what did not. Select a step to read what it introduced and where that idea lands in Elixir.
The lineage · select a step
Computation as functions and substitution: no state, no steps, only rewriting a term until it can reduce no further.
Elixir did not invent these ideas. It is the current end of the line — a functional language on the BEAM that gathers what each step proved and aims it at concurrency.
From the λ-calculus to LISP
In 1936 Alonzo Church described a system in which every value is a function and the only act is application. A term is evaluated by β-reduction: find a function applied to an argument, and replace the function's parameter with that argument throughout the body. There is no assignment and no clock — a program is a term, and running it means rewriting the term until no reduction remains.
Twenty-two years later John McCarthy made the idea executable. LISP (1958) introduced code as data, the literal lambda, automatic memory management, and the interactive prompt. Almost every comfort a modern functional programmer expects starts here.
λ-calculus, 1936
A function is a rule: λx. x * x. Applying it substitutes the argument for x.
Elixir, today
The same rule, with a syntax: fn x -> x * x end, applied with .(3).
β-reduction · step through an evaluation
- α rename
- a bound name may be renamed; λx. x and λz. z are the same function.
- β apply
- a function applied to an argument reduces by substituting the argument for the parameter.
- δ arithmetic
- built-in operations on constants reduce in one step (an applied calculus extends the pure one).
- normal form
- a term with no remaining redex; the value the program computes.
Running a functional program is reduction: replace, never mutate. F1.02 turns this exact move into Elixir's substitution model, and F1.01 defines the function it acts on.
Types & laziness — the ML and Haskell branch
Robin Milner's ML (1973) added two ideas that Elixir uses every day. The first is pattern matching: code organised by the shape of its data rather than by conditionals. The second is Hindley–Milner type inference — types the compiler works out for itself.
Haskell (1990) pushed further: effects became explicit, and evaluation became lazy by
default — nothing is computed until a result depends on it. Elixir is pragmatic about effects, but it
keeps ML's pattern matching outright and offers Haskell's laziness as a deliberate choice through
Stream.
Haskell, lazy by default
take 3 (map f [1..]) — an endless list, yet only three results are forced.
Elixir, lazy on request
1.. |> Stream.map(f) |> Enum.take(3) — the same restraint, opted into.
Strict vs lazy · count the work
Same answer, different work. Laziness lets a pipeline touch only what the result needs; Haskell made that the default, and Elixir makes it a choice. F3.04 is where streams arrive in full.
The immutable turn — persistent data on the JVM & CLR
For a long time immutability was treated as a luxury: if you can never change a value, surely you copy it constantly. The answer arrived as persistent data structures — Okasaki's work in 1998, and Bagwell's hash array mapped tries in 2001. Updating a persistent structure copies only the path from the root to the change and shares everything else with the previous version. The cost is O(log n), not O(n).
Clojure (2007) brought these collections to the JVM and made them mainstream; Scala and F# carried the same idea across the JVM and the CLR. The BEAM had immutable data from the start — that runtime story is F0.2 — and Elixir's maps and lists work this way today.
Persistent structure
An update copies the path to the changed leaf and shares the untouched branches.
Elixir collections
Maps and lists are immutable; the runtime shares structure. F4.05–F4.07 build the HAMT, CHAMP, and branded keys.
Structural sharing · update one leaf
Immutability stopped being expensive once an update could share the parts it did not touch.
Elixir's collections work this way; F4 builds the HAMT and CHAMP that make it so, and F4.07 puts a branded
key such as TSK0KHTOWnGLuC at the front of each entry.
What this lands
Three threads run out of this history and into the rest of the course. Reduction without mutation
becomes the substitution model (F1.02) and, with it, purity. Pattern matching and
laziness from the ML and Haskell branch return as Elixir's function heads and its Stream
module (F3). Persistent, shared data turns immutability from a cost into a default, which F4 builds
explicitly as the HAMT and CHAMP.
One thread is missing here: the runtime. Immutability and lightweight processes were present in Erlang from 1986, and the machine that runs them — the BEAM — has its own history.
Next in this chapter: F0.2 — The evolution of Erlang, the BEAM & OTP (soon). Until it lands, the course proper begins at F1 · Algebra.