Poor Man's Time Machine · Irfan Ali

Poor Man's Time Machine: Lazy Evaluation in JavaScript and Haskell

Here is a simpler version of the famous repmin puzzle from Richard Bird's arsenal of functional tricks: Given a<br>non-empty array of numbers a, you have to find the smallest number m and replace every element of a with m<br>in a single traversal .

Naive Non-Solution

It is straightforward to build a naive non-solution which calculates the minimum value of a in one pass and then<br>mutates a in another pass:

function findMin(a) {<br>let m = a[0]<br>for (let i = 0; i<br>The question is: how do we perform these temporally dependent tasks in a single pass? That is, how do we go through<br>a to replace all its elements with m but somehow also calculate m at the same time?

Basically, we need to traverse a to calculate m and simultaneously replace it with some value x which we can<br>guarantee is going to be the minimum value?

But wait, won't that require sending a message to the present from the future?

So, is it necessary to invent a time-machine to solve this puzzle? Or could we do with something more modest: say, a<br>simple function and a tiny leap of faith .

Unevaluated Value is Function

To see how a simple function can help us, please note that the seemingly temporal dependency arises only because<br>replaceMin(a, findMin (a)) forces the traversal in findMin before replacement in replaceMin.

If we could just find a way to represent the minimum value not as a Number in JavaScript but a function instead, the<br>temporal dependency would vanish because a function doesn't need to be evaluated immediately. We can just replace<br>every element of a with a function which would evaluate to the minimum value later in the future. This function is<br>then a proxy for m which delays the need to actually calculate m when we enter replaceMin.

Let's do this with a function findAndReplaceMin which calculates m but also replaces the elements of a by some<br>as-of-yet unrelated function xf in a single pass:

function findAndReplaceMin(a, xf) {<br>let m = a[0]<br>for (let i = 0; i<br>Note that xf is a function which is passed to findAndReplaceMin which replaces every element of the list a by<br>xf. We still need to choose xf so that every occurrence of xf eventually yields the minimum value, even though<br>that minimum has not yet been computed.

This seems like a problem. We're still stuck in a situation where evaluation of m requires xf be passed to<br>findAndReplaceMin but findAndReplaceMin itself needs xf to be passed before m has evaluated.

Make Evidence for Faith

This seems like real problem until we realise that we can bootstrap the evidence for our faith by saying this:

let m = findAndReplaceMin(a, () => m)

This seems paradoxical: how can m be used in its own definition?

The answer is subtle: we are NOT using m to calculate m but only denoting m in a function which calculates m<br>independently of the denotation.

More precisely, the closure () => m captures the undefined variable m without forcing the evaluation which would<br>happen only when we say xf(). And if you look carefully, we take care not to do that anywhere inside<br>findAndReplaceMin (more on this in a bit).

When the line let m = findAndReplaceMin(a, () => m) is executed in code, it would do two separate tasks in one<br>single pass:

Calculate the minimum value by traversing a and bind it to m

Replace every element of a with the function () => m (without evaluating the function)

Contrast the line above with the obviously invalid declaration: let m = m which immediately attempts to read the value<br>of m before it has been initialized.

By comparison, let m = findAndReplaceMin(a, () => m) never reads m during the construction of the closure. The<br>expression () => m merely records how to obtain m in the future. The actual lookup is postponed until the function<br>is called.

Note that after findAndReplaceMin has run, a is populated by functions and not Numbers. So, when any element of<br>a is needed, we get it by calling a[i]() which would try to access the value bound to m. But note that that<br>doesn't need to run findAndReplaceMin again because m is already bound to the minimum value from Step 1.

In functional parlance, writing this self-referential declaration is close to what is called "tying the knot" . It<br>refers to the circular reference to m, which we fill from findAndReplaceMin in the future, but which we can still<br>use inside findAndReplaceMin in the present if we care not to inspect or evaluate it.

The key to this illusion of time-travel is the assignment a[i] = xf without inspecting xf. We can not afford to poke<br>xf (say by doing xf()) inside findAndReplaceMin because that would just force the evaluation of m ... inside the<br>evaluation of m ... I think you get where that would lead.

I should reiterate that no law of physics is being broken here and no information is actually travelling backwards in<br>time. We instinctively think of computation as a sequence of steps: first compute the minimum, then replace...