Lambda Calculus Interpreter

Syntax

Lambda abstractions can be defined using a backslash. \x.x, for example, denotes the identity function, where x is a variable. Note, that, since dropping the additional backslashes for multi-argument functions is allowed, \fx.fx is equivalent to \f.\x.fx.

Variables are usually single characters, but multi-character variables can be used by enclosing them in backquotes: `func`x

Lowercase and uppercase letters, as well as digits are allowed in variable names.

Let-bindings

The interpreter allows for variables to be defined through let-bindings, such as let `id` = \x.x. These bindings all have to occupy their own line, but they don't necessarily have to be in order. The let-bindings can reference any other variables, as long as the definition doesn't end up being recursive.

These bindings are evaluated by detecting the free variables in a line and passing in the relevant bindings through a lambda. For example:

let `succ` = \nfx.f(nfx)

`succ`(\fx.x)

will result in

(\`succ`.`succ`(\fx.x))(\nfx.f(nfx))

being passed to the interpreter.