Lambda the Ultimate

Dissecting Unlambda Birds
started 4/19/2003; 1:38:55 PM - last post 4/21/2003; 4:49:10 PM

Chris Rathman - Dissecting Unlambda Birds

4/19/2003; 1:38:55 PM (reads: 1891, responses: 3)

Dissecting Unlambda Birds

This web page is actually a combination of three things. First, I tried to document the various Combinator Birds that I found in To Mock a Mockingbird and To Dissect a Mockingbird. Second, I made a revised Combinator Calculator that is lifted from the Combinatory Logic Tutorial with modifications to support the birds beyond the Starling and Kestrel. Finally, I wrote a Partial Unlambda Interpreter that is a stripped down version of the Unlambda Programming Language

Note: That the two programs do require that JavaScript be enabled. I'm in the process of moving my pages to a website that doesn't have the annoyance of popups, but you'll have to live with it for the time being.

BTW: Consider this punishment for not answering my question about the Jay Birds. :-)
Posted to fun by Chris Rathman on 4/19/03; 1:43:27 PM

Chris Rathman - Re: Dissecting Unlambda Birds

4/19/2003; 9:25:40 PM (reads: 1018, responses: 1)

In addition to tweaking the two programs, I want to create a third calculator function that takes the general form of the lambda equation, and calculates the SK-combinators necessary to produce the desired result. For example, just picking one at random, let's say that I took the lambda form of:

labc.((ac)b)

Now, from looking at the bird chart, I can see that this is the form of the Cardinal, and it can be defined with SK as ((S((S(K((S(KS))K)))S))(KK)). Or I can just do trial and error with the B, C, S, and I combinators until I came up with the desired SK-Combinator.

What I really want, though, is to input the form of the lambda equation, and have the computer calculate the necessary SK combinator to achieve the result. In chapter 18 of Smullyan's book, he describes a general method using an a-eliminate and 4 Principles. I suppose it might not be a bad exercise to convert his verbiage into a working algorithm for JavaScript. But I was kind of hoping that someone already has an available set of code to accomplish the chore.

Daniel Marlay - Re: Dissecting Unlambda Birds

4/21/2003; 4:49:10 PM (reads: 905, responses: 0)

There is a discussion on how to do this conversion in the documentation for Unlambda http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/#lambda_elim.

It takes you step by step through the process of converting a lambda calculus expression into an equivalent combinator expression.

Daniel Marlay

Ehud Lamm - Re: Dissecting Unlambda Birds

4/22/2003; 1:20:41 AM (reads: 935, responses: 0)

Compiling lc expressions to combinators is discussed in Hankin's lc book.