Functional Programming 101: Programming Without Side Effects
"Same input, always the same output" — the power of referential transparency, Lisp (the oldest functional language), and recurrences and memoization taught through Fibonacci numbers
What functional languages are
Most programming languages are imperative: commands — "assign to this variable", "repeat this" — run from top to bottom, mutating state as they go. Functional languages take a different view. A program is built by evaluating expressions, out of functions that behave like mathematical functions: they take an input and return an output, and do nothing else.
In a functional language, functions are themselves values. They can be stored in variables, passed as arguments, and returned as results (this is called having first-class functions). "A function that takes a function" or "a function that builds and returns a function" are perfectly ordinary tools.
What "no side effects" means: referential transparency
Here comes the core concept. A side effect is any work a function does besides returning its value — mutating a global variable, printing to the screen, writing to a file. A function with no side effects — one that also depends on nothing outside its own inputs — returns the same output for the same input, no matter when, how often, or where it is called. This property is called referential transparency.
The benefits are tangible. First, testing is easy — you only look at inputs and outputs, and never ask what state must be set up beforehand. Second, understanding stays local — the world does not change across a function call, so code can be read piece by piece. Third, concurrency is safe — nothing shared is mutated, so computations can run side by side without stepping on each other.
"A function's meaning is determined by nothing but the relation between its input and its output" — if you have read the formal-methods content on this site, this should sound familiar: it is the same idea as writing contracts with pre- and postconditions. The fewer the side effects, the easier the input/output contract is to write and to verify.
Lisp: the oldest functional language
The ancestor of functional languages is Lisp. Devised by John McCarthy in 1958, it is — among high-level languages still in use today — second only to FORTRAN in age, and its dialects (Common Lisp, Scheme, Clojure) remain in active use.
Lisp's syntax is astonishingly small: nothing but S-expressions — parenthesized forms of (function argument argument ...). And that shape is itself the list data structure, so code and data share the same form, which makes "programs that generate programs" feel natural.
;; An S-expression: (function arg1 arg2 ...) — that is the whole syntax (+ 1 2) ; => 3 (* (+ 1 2) 4) ; => 12 (if (< 1 2) "yes" "no") ; => "yes"
The code examples below use one of the dialects, Common Lisp.
Worked example: the n-th Fibonacci number
The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, … is the sequence where each term is the sum of the previous two. Mathematically it is defined by a recurrence relation: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2).
Here the appeal of functional languages shows itself: the mathematical definition becomes code almost verbatim.
;; The recurrence relation transcribed as-is (Common Lisp) ;; F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (fib 10) ; => 55
The if mirrors the case split, and the recursive calls mirror the right-hand side of the recurrence. The distance between the specification (the mathematical definition) and the implementation could hardly be smaller. But a serious problem hides in this naive definition.
The problem: an explosion of repeated work
The call tree of (fib 5): (fib 5) ├─ (fib 4) │ ├─ (fib 3) │ │ ├─ (fib 2) ... │ │ └─ (fib 1) │ └─ (fib 2) ... └─ (fib 3) ├─ (fib 2) ... └─ (fib 1) (fib 3) twice, (fib 2) three times — the same work done over and over
Draw the call tree and you will find (fib 3) computed twice and (fib 2) three times — the same work done over and over. As n grows the duplication explodes exponentially, with a cost of roughly O(1.62ⁿ). Around fib 40, it becomes too slow to wait for.
Memoization: remembering what you computed
The fix is simple: store each computed result in a table, and when the same argument comes again, return it from the table instead of recomputing — this is memoization.
;; Memoized version: remember computed results in a hash table (Common Lisp) (let ((table (make-hash-table))) (defun fib-memo (n) (or (gethash n table) ; if it is in the table, return it (setf (gethash n table) ; otherwise compute and store it (if (< n 2) n (+ (fib-memo (- n 1)) (fib-memo (- n 2)))))))) (fib-memo 100) ; => 354224848179261915075 — returns instantly
Each n is now computed exactly once, and the cost drops from O(1.62ⁿ) to O(n). Even fib 100 is instant.
Memoization is safe precisely because fib has no side effects: the same input always yields the same output. Whether the answer comes from the table or from recomputation, it is the same — referential transparency is what guarantees that results may be reused. With a function whose result changes between calls, this would not work.
One honest note: writing into the table is, internally, a state change — a side effect. But since the input/output behavior seen from outside does not change, memoization is widely used in the functional world as an optimization that preserves apparent purity. Clojure even ships a standard memoize that memoizes a function in one line.
Summary
Functional languages build programs by evaluating expressions. The core is the absence of side effects — referential transparency (same input, always the same output).
Benefits: easy testing, local understanding, safe concurrency.
Lisp, born in 1958, is the oldest functional language. One syntax — the S-expression — and code and data share the same shape.
A recurrence relation becomes code almost verbatim. The naive recursion explodes exponentially — but memoization, justified by referential transparency, brings it down to O(n).