Lambda calculus to Javascript source-to-source filter

(If you don't know what lambda calculus is, see Chris Barker's excellent tutorial.)

The naive way to do this is to let

transform(λx.y) = function(x){return transform(y)}

The problem is that Javascript is eager: in a function call like f(x), it evaluates x first. However, this is very bad news in lambda-land. Consider these lambda terms:

ω = λx.xx
Ω = ω(ω)

Ω has no normal form. It's an infinite loop. On the other hand,

KXΩ = (λxy.x)XΩ = X.

But look what happens in Javascript:

K = function(x){return function(y){return x}}; 
omega = function(x){return x(x)};
K(X)(omega(omega));

To make Javascript behave, we have to suspend the evaluation. We can do this by wrapping the definition in a function with no arguments; when it comes time to apply the function, we evaluate it explicitly.

The replacements that work are:

transform(λx.y) = function(){return function(x){return transform(y)()}}
transform(x(y)) = function(){return transform(x)()(transform(y))}

Unlambda introduced the backtick (`) as a prefix application operator: The term `xy means x(y). Functions of multiple arguments get curried: ``xa`bc means x(a)(b(c)). Terms have the form of a preorder traversal of the binary tree of applications, where ` is a node and any other symbol is a leaf.

Since λ is an operator that takes a variable, a body, and a replacement pattern, it makes sense to represent it in the same way. In this filter,

(λ<var>.<body>)(<replacement>)

is expressed as

```^<var> <body> <replacement>

In particular,

K = ``^x ``^y x

and

Ω = ```^x `x x ``^x `x x

I allow arbitrary Javascript identifiers as variables. Terms of the form `xy are ambiguous once multi-character identifiers are allowed, so all identifiers must be terminated with a single space character. For example,

Pair = ``^left ``^right ``^which ``which left right

For convenience, I provide two functions _(x) and __(x) (single and double underscore). The first evaluates x, then suspends it; the second takes a lambda-calculus term x, transforms it, and evaluates it, returning a Javascript function with the same behavior (modulo explicit evaluation).

Try it out now! The combinators S,K,I, omega and Pair have been predefined for you. The identifiers X and Y are the strings 'X' and 'Y', so don't try to apply them to anything!

The same technique works for nearly every other eager language with first-class functions, like Perl.