Reusability and Closures: Turning Memoization into a Component
Functions that build and return functions — how JavaScript closures capture private state, and the design of a memoizer whose initial values and recurrence are both pluggable
Reusability as a design goal
The memoized Fibonacci from the previous page (Functional Programming 101) had one shortcoming: the table and the rule were written specifically for fib. To handle a different sequence, you would have to write nearly the same code again — even though the memoization machinery itself is identical for any sequence.
Program reusability means separating what stays the same from what varies. What stays the same is the memoization machinery. What varies is the sequence's initial values and its recurrence. If the former becomes an independent component and the latter can be plugged in from outside, the same component can build any sequence of this kind (one whose recurrence looks back at the terms just before it).
The tool: closures
The tool for this is the JavaScript closure. A closure is a function that keeps remembering the variables of the place where it was born. Write a function that builds and returns a function, and the returned function can refer to the outer function's variables indefinitely.
const makeCounter = () => { let count = 0 // only the returned function can touch this return () => ++count } const next = makeCounter() next() // 1 next() // 2 — count lives on inside the closure
Nothing outside makeCounter can touch count. It is private state that only the returned function can reach. With closures you can lock state inside a function and expose only the intended operations.
memoizer: memoization as a component
With that tool in hand, here is the previous page's memoization turned into an independent component — the memoizer.
const memoizer = inits => rule => { const memo = [...inits] // copy the initial values into a private table const elem = n => (n >= memo.length) ? memo[n] = rule(elem)(n) : memo[n] // if it is in the table, return it return elem }
Read it in three layers. First, the shape inits => rule => ...: a chain of functions each taking one argument, called currying. The moment you call memoizer(inits), you get back "a function that has remembered the initial values and is waiting for a rule".
Second, const memo = [...inits]: copy the initial values into a private table. This memo is exactly the state the closure locks in — only the returned elem can touch it.
Third, elem itself. If n is still within the table's range, return the stored value (a memoized read); otherwise compute rule(elem)(n) and write the result into the table (in JavaScript an assignment expression memo[n] = ... yields the assigned value, which is why this fits in a single expression). Note what is passed to rule: elem itself. The "self" that the recurrence refers to is injected from outside the component.
In action: swapping both the initial values and the recurrence
To use it, pass an array of initial values and a recurrence rule — nothing more.
// Fibonacci: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) const fibo = memoizer( [0, 1] )( a => n => a(n-1) + a(n-2) ) // different initial values AND a different recurrence — same memoizer const newFibo = memoizer( [2, 1, 5] )( a => n => a(n-1) + a(n-2) + a(n-3) ) fibo(10) // 55 newFibo(10) // 561
fibo and newFibo are different sequences, with different initial values and different recurrences. Yet not a single character of memoizer itself was rewritten. The varying parts (initial values, recurrence) are passed as arguments; the unchanging part (the memoization machinery) is reused as a component — the design goal we set at the start, realized.
One more property matters: fibo and newFibo each hold their own memo. Each completed call memoizer(inits)(rule) creates a fresh table, locked into its own closure. Two functions built from the same component do not interfere with each other — that separation, too, is guaranteed by closures.
Tracing the execution
How newFibo(4) runs (starting from memo = [2, 1, 5]): elem(4): 4 >= 3, so compute via rule elem(3): 3 >= 3, so compute via rule elem(2) -> 5 (from the table) elem(1) -> 1 (from the table) elem(0) -> 2 (from the table) memo[3] = 5 + 1 + 2 = 8 elem(2) -> 5 (from the table) elem(1) -> 1 (from the table) memo[4] = 8 + 5 + 1 = 14 The table has grown to [2, 1, 5, 8, 14] A second newFibo(4) returns 14 straight from the table
Trace newFibo(4) and you can watch the table grow. From the second call on, results come straight out of the grown table.
Summary
Reusability is the separation of what stays the same from what varies: make the unchanging machinery a component, and the varying values its arguments.
A closure is a function that remembers the variables of its birthplace — it creates private state (here, the memo table) that nothing outside can touch.
The curried memoizer(inits)(rule) gives the two varying parts — initial values and recurrence — their own argument slots.
Passing elem itself to rule lets the recurrence receive its own "self" from outside. Functions built from the same component hold separate tables and never interfere.