Lambda the Ultimate

inactiveTopic To Dissect a Mockingbird
started 8/9/2002; 11:25:18 PM - last post 4/11/2003; 1:36:56 PM
jon fernquest - To Dissect a Mockingbird  blueArrow
8/9/2002; 11:25:18 PM (reads: 1792, responses: 3)
To Dissect a Mockingbird

Subtitled "A Graphical Notation for the Lambda Calculus with Animated Reduction." A visual introduction to the lambda calculus. Scroll slowly down the page and watch the animations. (Source: Lambda Calculus <-> Category Theory Discussion)

As pointed out by Raymond Smullyan the eminent logician and author of several puzzle books, the theory of combinators is an abstract science dealing with objects whose only important property is how they act upon each other. We are free to choose other properties of these objects in any way we like. In his delightful book "To mock a mockingbird", Smullyan (1985) chooses birds for his combinators, in memory of Haskell Curry, an early pioneer in the theory of combinators (1958) and an avid bird-watcher.

The story begins, "A certain enchanted forest is inhabited by talking birds. Given any birds A and B, if you call out the name of B to A, then A will respond by calling out the name of some bird to you; this bird we designate AB. Thus AB is the bird named by A upon hearing the name of B." ... In the hope of making it even easier I introduce the following graphical notation by extending Smullyan's bird metaphor. We will go inside the birds' heads and see how to draw diagrams of the internal plumbing which connects their ear to their throat in order to produce the correct song in response to each song that they hear.

Posted to LC by jon fernquest on 8/9/02; 11:31:41 PM

Michael Christopher Vanier - Re: To Dissect a Mockingbird  blueArrow
8/10/2002; 12:01:09 AM (reads: 1088, responses: 0)
I really enjoyed this article. I've been trying to get a hold of a copy of Smullyan's "To Mock A Mockingbird" for some time now, but it's out of print and seemingly completely unavailable. If anyone locates a copy and would be willing to sell it, please let me know -- I'll pay good money ;-)

I find combinators fascinating. They represent the most minimalistic example of universal computation that I've ever seen. It's a shame that most CS graduates will never hear of them in their courses, since most books on theoretical computer science don't even mention them (or lambda calculus itself, for that matter). Also, Haskell Curry's pioneering work on combinators is totally out of print as well (alas). Dover has reprinted his "Foundations of Mathematical Logic", which contains some stuff on combinators, but the real meat is in his two-volume set "Combinatory Logic" (co-written with Richard Feys and others). I wish Dover would reprint those volumes as well. The languages APL and J show a lot of the combinator influence, as does (less seriously) unlambda.

Ehud Lamm - Re: To Dissect a Mockingbird  blueArrow
8/10/2002; 3:07:05 AM (reads: 1107, responses: 0)
Previously on LtU .

Chris Rathman - Re: To Dissect a Mockingbird  blueArrow
4/11/2003; 1:36:56 PM (reads: 710, responses: 0)
I know it's been a while since this was posted, but being a slow reader... :-)

About two-thirds of the way through the article the author shifts the base combinators from SK to JI in the derivation of the common derivative combinators. Problem is that the author never describes J in terms of SK - thus leaving me in the lurch about the mapping. Perhaps he was leaving it as an academic exercise?

For those of us non-students, what is J when described in the base SK combinators where:

Jay => Jabcd = ab(adc)