Implementation of Lambda Calculus in Scala

Expr ::= Name(name: String) | Lmbd(param: Expr, body: Expr) | Appl(fn: Expr, arg: Expr)

Examples:
Name("x")
//-> "x"
Lmbd(Name("y"), Name("y"))
//-> "λy.y"
Lmbd(Name("f"), Lmbd(Name("x"), Name("x")))
//-> "λf.λx.x"
Appl(Name("f"), Name("a"))
//-> "(f a)"

The \ operator peforms function application. Using named variables for functions as well as \ leads to simpler code.

First, let's get some definitions out of the way:

val x = Name("x")
//-> "x"
val y = Name("y")
val f = Name("f")
val a = Name("a")
val b = Name("b")
val id = Lmbd(x, x)
//-> "λx.x"
val makePair = Lmbd(x, Lmbd(y, Lmbd(o, Appl(Appl(o, x), y))))
//-> "λx.λy.λo.((o x) y)"

Now, using those definitions, let's apply the \ operator:

id \ y
//-> "y"

makePair \ a \ b
//-> "λf.((f a) b)"

You can also use traditional argument passing:

id(y)
//-> "y"

makePair(a)(b)
//-> "λf.((f a) b)"