Thursday, March 31, 2011

Scala Internal DSL for Lambda Calculus

I've been playing with the untyped lambda calculus recently, and come up with this notation for it in Scala:

'x ^: 'y ^: 'x ! 'y
'x ^: 'y ^: 'x ! ('x ! 'y)
'x ^: 'y ^: 'x ! ('x ! ('x ! 'y))

which translates to:


(You might recognize these as the Church numerals one through three.)

To digest this, you first have to imagine abstraction as an infix operator rather than a prefix operator. If you squint a little, you can see a caret as a lambda (the colon is necessary to get Scala to make the operator right-associative, as is conventional).

The exclamation point is the application operator by analogy with the notation used in Scala Actors. It takes only a wee bit of mental squinting to see passing an argument to a function as sending a message to an actor.

The single quote prefix in Scala turns an identifier into a Symbol, which is like a String but with only half the quoting. Scala Symbols are intended for purposes that are, uh, symbolic—I think a lambda calculus variable qualifies.

As cute as dancing kittens? You be the judge.