"informal and entertaining introduction to [lambda calculus]"

June 8, 2022 10:53 AM

To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus An attempt to place the lambda calculus on an even deeper foundation. Personally, I think people have found way better visualisations for lambda calculus (https://github.com/prathyvsh/lambda-calculus-visualizations) but what I find remarkable here is not the visualisation itself but the metaconcept being used.

For context: This picks up on ideas presented in Raymond Smullyan's 1985 book "To Mock a Mockingbird and Other Logic Puzzles".
What was "To Mock a Mockingbird" all about? Well, it was essentially an attempt to make combinatory logic (functionally equivalent to lambda calculus) more accessible to the average person. Smullyan did so by dumbing everything down into very simple concept metaphors, one of which was the "bird" (equivalent to a combinator) sitting in a forest and "talking" (representing function application) to other birds. The book is essentially 267 pages of logic puzzles that further explain and extend this analogy.

"As pointed out by Raymond Smullyan 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." That's where the magic happens. He gives them other properties, that turn them from abstract concepts into tangible objects (e.g. birds), so that their "other properties" explain how they "act upon each other."

posted by Burgers (10 comments total)

In the summer, I plan to read this again.
I tried in the past, but it just didn't click for me.
posted by Acari at 1:49 PM on June 8, 2022 [1 favorite]

For myself, I didn't find the metaphor very helpful. I felt like it was saying "Imagine a magical forest full of birds that sing to each other! Now imagine the birds are completely unlike real birds in every way, and also don't exist. Now just take out the magic forest and you've got combinatory logic!"

But you never know which metaphor will finally click for you or anyone else, so I'm in favor of experimenting with lots of them.
posted by echo target at 2:17 PM on June 8, 2022 [5 favorites]

Derail Derail Derail

I can't see the word Lambda without my brain saying Lambada.

Which always reminds me of my Army buddy, who liked to jump on the company radio network in the middle of the night and passionately whisper, "The Lambada, that's the forbidden dance. hushhhhh."

It was a line from 1990's The Forbidden Dance. Oh boy did the officers get mad, and as far as I know they never figured out it was him.

Ok, I'm going to end my lambda vs Lambada derail now.




Don't ask about my long running Nutria vs Nutella confusion.
posted by Abehammerb Lincoln at 3:02 PM on June 8, 2022 [4 favorites]

The lambada is indeed mentioned in TFA.

Put me in the column of those who found this confusing. In particular the whole "let's use bird names that clearly are meant to resemble descriptive terms, but let's not actually use those terms" bit is a form of Whimsical Hostility that I would like to see rolled up in an old carpet and hurled into a fire.
posted by phooky at 3:55 PM on June 8, 2022 [2 favorites]

It's surprisingly skimmable, basically I thought of the birds are just programs and songs are data, and each of those boxes is basically a program that can accept other programs.

So I think to those of us who weren't taught formal lambda calculus (I don't believe most modern CS courses focus on that anymore) it's tempting to just mentally translate everything to Turing machines and/or lambda expressions (which the essay eventually does anyways).
posted by polymodus at 4:05 PM on June 8, 2022

For myself, I didn't find the metaphor very helpful. I felt like it was saying "Imagine a magical forest full of birds that sing to each other! Now imagine the birds are completely unlike real birds in every way, and also don't exist. Now just take out the magic forest and you've got combinatory logic!"

I actually felt somewhat similar after the first read. I thought about it and I realized, that what the paper attempts to do is making combinatory logic understandable by describing it as communication between different agents, which everyone can basically relate to from everyday social interaction, and that it's probably still difficult to understand because there is nothing in the metaphor that implies a hierarchy between the agents. Which is the actual hard part, right? The difficulty lies not in understanding what an omega combinator or λx.x does, the hard part is keeping track of dozens of parenthesis in more complex expressions. What does it actually mean if there are "birds inside birds inside birds"? The text does not give any clear intuition.

I'm not entirely sure how exactly I'd go on about improving it tho, since the hard part seems finding a metaphor for a combinator that suits it regardless of where it stands in a term.
posted by Burgers at 4:21 AM on June 9, 2022 [2 favorites]

Ok, serious request: Would anybody here be interested in exploring this topic further and creating an improved version of this text?
posted by Burgers at 4:35 AM on June 9, 2022 [3 favorites]

I'm reminded of the "monads are burritos" situation:

After struggling to understand them for a week, looking at examples, writing code, reading things other people have written, he finally has an “aha!” moment: everything is suddenly clear, and Joe Understands Monads! … “Of course!” Joe thinks. “It’s all so simple now. The key to understanding monads is that they are Like Burritos. If only I had thought of this before!” The problem, of course, is that if Joe HAD thought of this before, it wouldn’t have helped: the week of struggling through details was a necessary and integral part of forming Joe’s Burrito intuition, not a sad consequence of his failure to hit upon the idea sooner.

I read the Smullyan article when I was younger and was baffled by it. Probably if I'd spent a week grappling with the ideas in it, I'd have gotten somewhere. Instead, eventually, I went to grad school for formal semantics, and spent a couple years grappling with lambda calculus, and now, coming back to the article, it's a fun game: "Here's someone else's big metaphor—here are these familiar concepts expressed in an alien way—try and recognize them with these costumes on."

But idk, that doesn't mean the article is useless for beginners. Like I said, probably if I'd spent a week grappling with the bird metaphor I'd have gotten somewhere. The point is, you have to grapple with it. You can't just read it and say "Oh! Combinators are birds! Now I get it!" and skip the work.
posted by nebulawindphone at 7:05 AM on June 9, 2022 [2 favorites]

I thought cool bit about the essay is that it tries to mention each the major theorems of recursive functions using the bird metaphor. Like the fixed point theorem birds, the smallest basis bird families, and Godel's incompleteness birdology.

The author does point out maybe unicellular life forms are a better metaphor. We could imagine a photosynthetic organelle being engulfed by a cell and that's a bit more literal.

You can't just read it and say "Oh! Combinators are birds! Now I get it!" and skip the work.

I think the problem is the metaphor eventually breaks down. The easiest way to learn lambda calculus today the modern way is through any college course in theoretical programming languages, but even with that you are better off learning your background through Turing machines because that is a lot more accessible with less mathematical formalism and training.
posted by polymodus at 2:10 PM on June 9, 2022

But idk, that doesn't mean the article is useless for beginners. Like I said, probably if I'd spent a week grappling with the bird metaphor I'd have gotten somewhere. The point is, you have to grapple with it. You can't just read it and say "Oh! Combinators are birds! Now I get it!" and skip the work.

Yeah, ime when you learn a piece of math, you learn a kind of fast internal representation that uh "feels" like something and at least heuristically preserves its representative properties through counterparts of the "true" transformations, but for me at least you only ever get there by doing. Like you say it takes time and work.

These inner structures are difficult or impossible to share, at least without an intensive grappling process. You can gesture metaphorically in their direction in the hope that it'll stimulate parallel growth in the student.

It's rewarding when it comes online though. Like you're no longer directly and explicitly applying definitions and it just feels like something when a set is open or whatever. Or there's some construct with multiple equivalent definitions that sound really different but suddenly you can feel that they mean the same thing. Etc.
posted by grobstein at 5:29 PM on June 9, 2022 [2 favorites]