Fernando Meyer

Reading my daily incoming links I faced with this interesting link http://worrydream.com/AlligatorEggs/ someone had a great idea about a nice puzzle, the alligator game.

This game represents the untyped lambda calculus. A hungry alligator is a lambda abstraction, an old alligator is parentheses, and eggs are variables. The eating rule corresponds to beta-reduction. The color rule corresponds to (over-cautious) alpha-conversion. The old age rule says that if a pair of parentheses contains a single term, the parentheses can be removed.

Schematic Form

I’ve found that a schematic form of alligator calculus is actually rather handy for calculating lambda terms by hand. We draw a lambda as a line with a mouth. Parentheses are a line without a mouth. Here’s the identity function:

Here are some Church numerals:

Here are boolean AND and OR (assuming the standard definitions for TRUE and FALSE):

The Y combinator:

I don’t know if these are any easier to read than the standard notation, but I’ve found them to be easier to work with, using pencil and paper. I imagine the terms eating one another and hatching below. I don’t get lost in a long chain of symbols, losing track of what’s applying to what.

I’m sure that after 4.0 drools release I’m going to implement this game as a drools DRL.

Unfortunately I didn’t wrote this while drooling with Mark, maybe someday I do it with a few scheme code.