A JS -> λ transpiler

⚠️This project is a WIP ⚠️

I have seen transpilers that convert λ-calculus to javascript, and was intrigued enough to do the opposite. The challenge here is that, although in theory any turing-complete computation can be expressed with λ-calulus, things get really complicated really quickly. Nonetheless, it'll be fun to see how far this can be taken.

Given the complex scope of this problem, it seems most reasonable to begin by supressing parts of the Javascript language and incrementally adding them in. See the "strategy" section below:

But....why??

This would fall in the "exploration" category of the exploration vs exploitation paradigm. Why would the ability to convert between two computational models be useful to me?

I don't know. But there's a chance that it could be beneficial.

If this project interests you, I'd love to collaborate:

rkotcher [at] gmail [dot] com

Strategy

The following sections outline the sub-challenges that I plan to work through. Assume that anything not explicitly mentioned is not considered by the transpiler. A green checkmark next to a list item means that it is tentatively (not exhaustively tested) finished.

1 - Functions, arguments, currying

• A function can be expressed via either the "var" or "function" keywords ✅
• Functions can take 1 or more arguments ✅
• functions can only return 1 argument ✅
• Functions with greater than 1 argument will be curried, i.e. ✅
• No shorthand notation will be applied, i.e. no λab. ✅

function f(a, b) { ... } -> function f(a) { return function g(b) { ... }} -> λa.λb.?

Church encodings enabled

With this functionality, we can already create a number of more primitive Church encodings, for example:

Kestrel (const)

• function f(a, b) { return a; } -> λa.λb.a

Kite (Kestrel of Identity)

• function f(a, b) { return b; } -> λa.λb.b

Coincidentally, the Kestrel and Kite can be used functionally as True and False encodings, and these uses will be revealed once the transpiler functionality includes function evaluation.

2 - Parsing functions as tokens

• A function is a first-class citizen ✅

function f(a, b) { return function g(c) { return c; }} -> λa.λb.λc.c (f is curried)

• Function parameters must not be bound to any parent scopes ✅

I propose throwing an error if this is not the case, for example, var f = function(a) { return function(a) { return a; }}; should throw the following error:

"Variable 'a' at position X is already bound to a parent scope."

3 - Evaluations

function f(h) { return function g(a) { return h(a); }} -> λh.λa.ha

Church encodings enabled

By enabling functions to be passed as

Mockingbird

• function(f) { return f(f); } -> λf.ff

Bluebird

• function(f, g) { return function(a) { return f(g(a)) } } or equivalently: -> function(f) { return function(g) { return function(a) { return f(g(a)) }}} -> λfga.f(ga)