Lambda the Ultimate

I was thinking about this problem the other day and came up with what I think is a tenable solution. It's quite possible someone else has thought of this before but I haven't seen it.

The idea is very simple: provide the programmer with a function random(x), which deterministically maps real numbers to random values (e.g. a white noise function). Within any function definition (or other code unit), the programmer obtains random numbers by calling the function with different arguments, e.g.:

let my_random_data = [random(0), random(1), random(2)]
-> [0.53, 0.12, 0.79]

Because random(x) is deterministic, these expressions can be reused at will, returning their original results:

let my_random_data = [random(0), random(1), random(2), random(0), random(1), random(2)]
-> [0.53, 0.12, 0.79, 0.53, 0.12, 0.79]

Now, to enable modular use of this function, we can simply derive from it a new function, random'(y), whose domain is again the real numbers, but maps to an interval in the domain of random(x), say 0<x<1:

let random'(y) = random(atan(y) / pi + 0.5)

Now another function or module can use random'(y) in the same manner as the main code used random(x), without fear of duplicating the random sequence. A new derived function can be created for each module which requires its own random function, simply by choosing a different interval of random(x) to map into:

let random''(z) = random(atan(z) / pi + 1.5)
let random'''(a) = random(atan(a) / pi + 2.5)

This process can be repeated within sub-modules, etc.

Of course, you can simplify this pattern using a higher-order function, which I will call "delve":

let delve(random, index) = (x) -> random(atan(x) / pi + index + 0.5)

So an example program might look like:

let create_random_data(random') = [random'(0), random'(1), random'(2)]

let my_random_data =
create_random_data(delve(random, 0)) ::
create_random_data(delve(random, 1)) ::
create_random_data(delve(random, 2))

-> [0.53, 0.12, 0.79, 0.16, 0.08, 0.92, 0.65, 0.50, 0.01]

I wrote an OCaml module implementing roughly this interface, albeit over integers, which is available here (interface). It reuses the built-in sequential random number generator, and is optimized for the case when the random function is accessed sequentially. (It must "replay" the random sequence if it is accessed otherwise.) The "delve" function is implemented by using the value from the given random sequence as a seed for a new random sequence.

Thoughts? Improvements?

See fig. 3.38 in SICP, where the authors show a model of a joint bank account shared by two people, Paul and Peter. The bank account can be modeled as a process that operates on a stream of transactions and generates a stream of responses. But the difficulty is merging the individual streams of transactions by Paul and Peter in a purely functional style. They argue that one can't get away from explicit synchronization. They end this this chapter by pointing out the essential difference between the two views of modeling of the world: as a set of interacting stateful objects vs a single timeless stateless entity. They say "A grand unification has yet to emerge". IIRC this part has not changed between the first and second edition of SICP. [This is probably confusing so you might wish to read this last section of chapter 3 in the online copy of SICP, or view the very excellent video lecture 6B from MIT opencourseware @ about 52 minutes. The Q&A at the end is also relevant]

I am wondering if things have changed since then. I doubt FPLs can allow modeling such a merge but how far have we come? Can we express synchronization in some way in FPLs? Is there a grand unification of something like CSP and FPL? Are SICP authors looking at this the wrong way?

Now that's a really cool effort, I'm just saying : A haskell interpreter in Javascript.

Well, yes : if only for possibly inspiring other folks (and... forks ;) from there.

Bravo, Mattis and the team. :)