Sunday, June 4, 2017

The ∞ levels of programming

At the 0th level are functions. Functions operate on data. Data like 1 or 2 or "three".

def f(x):
    return x + 1

At the 1th level are meta-functions, what you might call macros. Meta-functions operate on code.

def reapply(c):
    return apply(c.func, c)

reapply(f(2))f(f(2))4

There is of course meta-data as well, and a meta-function can operate on meta-data:

map(reapply, [f(2), f(3), f(4)])

At the 2th level are meta-meta-functions, that operate on meta-functions and meta-meta-data.

def reapply(c):
    return apply(c.func, c)

reapply(reapply(f(2)))reapply(reapply(f(2)))reapply(f(f(2))f(f(f(2)))5

And so on.

What the ∞ levels of programming give you is precision. Remember Scala continuations? Remember how you couldn't use shift inside a map or a foreach? Well that was because shift was a meta-function, and map was a function, and functions can't operate on meta-functions.

Or more concretely, shift tears apart the code itself. But when shift is mapped, you don't know yet--at compile time--where it will land. So you can't pull the code apart.

But with a meta-meta-map, and a meta-meta-list, you could meta-meta-map your shift over your meta-meta-list.

There's some analogy to universes in type systems, that the way to clarify statements about statements is to separate them by levels. When code may only refer to the level below it, a multitude of paradoxes go away.

And then the puzzle is how to compile it efficiently.