Alonzo Church: Architect of computer intelligence
(onepercentrule.substack.com)329 points by drcwpl 9 days ago
329 points by drcwpl 9 days ago
I wish that it was at least of some significant beyond the esoteric symbol but apparently no, see[1]:
> Dana Scott, who was a PhD student of Church, addressed this question. He said that, in Church's words, the reasoning was "eeny, meeny, miny, moe" — in other words, an arbitrary choice for no reason. He specifically debunked Barendregt's version in a recent talk at the University of Birmingham.
As a French native, I like to rely on the expression "personne lambda", which is a way to say a layman, that is an anonymous person, which matches pretty well anonymous functions. More generally in French as an adjective lambda means "usual/common", and you might know the lambda letter is at the middle of the Greek alphabet, so it does make sense to represent a mean thing, like common sense.
[1] https://math.stackexchange.com/questions/64468/why-is-lambda...
Very interesting, thanks for sharing.
I followed the two links from the comment on SE making the claim that Church's choice of lambda was completely arbitrary (pun intended). The first one doesn't seem to work, and the second one is a 2m youtube clip of Dana Scott talking about the subject.
I watched the video, the audio is a bit hard to make out in parts, and I'm left thinking the SE commenter interpreting Dana Scott, who you quote fully there, is overstating the case somewhat. Perhaps the claim should be moved from "likely true" to "somewhat uncertain", but not in any way "debunked" as the commenter says. Debunking means providing conclusive evidence against a claim, that any reasonable person would be obliged to agree with. Here we have an interesting and relevant anecdote, but it's still anecdotal, unfortunately.
Scott says a couple of things which are clearly audible that are relevant:
1. He asked John McCarthy personally why Church chose lambda, and McCarthy said he'd no idea,
2. Church never talked about the lambda calculus when he (Scott) was at Princeton, and
3. John Addison, Church's son-in-law, told Scott that he (Addison) wrote Church a postcard in which he asked him where he got lambda from, and that Church sent the whole postcard back to him with "eeny, meeny, miny, moe" written in the margins.
So I'm very happy you shared some more information on the subject, but I feel a conscientious biographer, for example, would be forced to include Scott's and Barendregt's theories and say that without confirmation from Church himself the matter is hard to decide. If anyone has a relevant quote from Church, I'd love to see it, but I presume it mustn't exist if Scott is so convinced there's no link.
I'm tempted to also point out more generally that all symbols are esoteric if you go back far enough, so I don't know if your particular quest could ever have been satisfied. In any case, I learned French beore Lisp, so I did have the experience of going, "oh, like in French? Why is that, I wonder?".
Only on HN will I find people pickier than myself I guess. ^^
>I'm tempted to also point out more generally that all symbols are esoteric if you go back far enough
It certainly all depends on what we put as definition of esoteric and what is far enough. :) Here what I was meaning was in contrast of a choice like "anonymously".
Since you speak French, you might be interested to watch "L’odyssée de l’écriture - Les origines ": https://www.youtube.com/watch?v=8P2nAj50LdY
Isn't that what it is - a place where we don't have to pretend we don't care about details.
I see the point of the documentary, it would have absolutely floored me a couple of months ago. However, I have very recently spent a month learning Serbian, which included learning (Serbian) Cyrillic, which led to me finally asking some obvious questions - where does Cyrillic come from, where does Greek come from, where does the Latin alphabet come from, etc. So I've binged similar information of the sort that documentary describes, I think.
I still might watch it later though and see if there's more juice in there, thank you very much!
"Lisp usually prefers expressive names". In addition to the exception of "lambda", there are also "car" and "cdr", which, while not Greek, are hardly transparent.
If it is any consolation, Steve Russell, who implemented the first Lisp interpreter on the IBM 704 and came up with CAR (Contents of the Address Register) and CDR (Contents of the Decrement Register) wanted to change them to "first" and "rest" after a few months in to teaching and thinking "Hmm, maybe we could have had more direct names here".
See the full email from Steve Russell on the topic on this page https://www.iwriteiam.nl/HaCAR_CDR.html, and here's the relevant quote:
> "After several months and giving a few classes in LISP, we realized that "first" and "rest" were better names, and we (John McCarthy, I and some of the rest of the AI Project) tried to get people to use them instead.
Alas, it was too late! We couldn't make it stick at all. So we have CAR and CDR."
Personally I don't mind them, they're nicely introduced in "A Gentle Introduction to Symbolic Computation" and they stuck easily enough for me.
The Fortran-compiled List Programming Language (FLPL) had the functions XCARF and XCDRF. It doesn't look like MacCarthy and Russel invented CAR and CDR; they just stripped X...F from FLPL's notation.
IPL also used the same list structure; it used the terms SYMB and LINK.
Ahh the perils of the installed base. It brings to mind the use of tab in make files.
> And then a few weeks later I had a user population of about a dozen, most of them friends, and I didn't want to screw up my embedded base. The rest, sadly, is history.[1]
It's not clear that this oft-repeated story of the origin of Alonzo Church's lambda notation is true. See https://en.wikipedia.org/wiki/Lambda_calculus#Origin_of_the_... for other instances where Alonzo Church has suggested it was more of an arbitrary choice of Greek letter.
Excellent, thank you for the link! Another commenter and I above have at greater length come to similar conclusions as in this Wikipedia subsection. I'll be more careful throwing this quote from Norvig around in future, the matter does seem uncertain.
In the short video from Scott dicussing it (https://inv.nadeko.net/watch?v=juXwu0Nqc3I) he says clearly that Church never discussed the lambda calculus while he was at Princeton, and that he thought Church was bitterly disappointed that his system was proven to be in some way inconsistent.
I wonder if Church named it after the Russell and Whitehead notation, and later wanted to distance himself from the whole thing so dismissed the notion. I had a quick look for the "unpublished letter to Harald Dickson" mentioned in the wikipedia there and can't find anything. Hmm.
Well before. The original paper[1] introducing the lambda calculus was in the 1930s, but it wasn't called "lambda calculus" until a bit later.
[1] https://raw.githubusercontent.com/emintham/Papers/master/Chu...
Yeah indeed no trace of the term 'lambda'.
But this https://www.classes.cs.uchicago.edu/archive/2007/spring/3200... mentions "THE CALCULI OF LAMBDA-CONVERSION" linked here https://compcalc.github.io/public/church/church_calculi_1941...
>There were no Greek letters on the keypunches of that era, so McCarthy used (lambda (x) (+ x x)), and it has survived to this day.
I have a memory of a paper by McCarthy himself where he tells that the first implemented Lisp had a notation close to FORTRAN. S-expressions were only intended for the theory.
This does not seem correct. There was a vision of using M-expressions, (Metalanguage) but it never happened.
>In computer programming, M-expressions (or meta-expressions) were an early proposed syntax for the Lisp programming language, inspired by contemporary languages such as Fortran and ALGOL. The notation was never implemented into the language and, as such, it was never finalized https://en.wikipedia.org/wiki/M-expression
https://en.wikipedia.org/wiki/M-expression
It was never implemented.
It was M-expressions which users were to interact with, and S-expressions were what the machine would use.
"Church’s lambda calculus and the Turing machine are equally powerful but differ in the fact that Turing machines use mutable state. To this day, there is a rift between functional and imperative programming languages, because of the separation of Church and state."
[I have known the above quote forever, but I can't find an original source]
edit: might be from Guy Steele: "And some people prefer not to commingle the functional, lambda-calculus part of a language with the parts that do side effects. It seems they believe in the separation of Church and state"
Guy's quote there came from a mailing list at MIT that was formed out of the 2001 Lightweight Languages Workshop. Archive of the original post here:
https://people.csail.mit.edu/gregs/ll1-discuss-archive-html/...
>seems they believe in the separation of Church and state"
ha, good one.
remind me of the joke about niklaus wirth's name.
[ Quotes about Niklaus Wirth
Whereas Europeans generally pronounce his name the right way ('Nick-louse Veert'), Americans invariably mangle it into 'Nickel's Worth.' This is to say that Europeans call him by name, but Americans call him by value.
Introduction by Adriaan van Wijngaarden at the IFIP Congress (1965). ]
"There's two hard problems in computer science: we only have one joke and it's not funny" which I've seen credited to Phillip Scott Bowden
Which is a reference to the "two hard problems" jokes, the most used is "There are two hard problems in Computer Science: Cache invalidation, naming things, and off-by-one errors"
But there is also "Two hard problems in distributed systems: Exactly-once delivery, guaranteed order of messages, and exactly-once delivery".
I didn't see your comment before I posted mine, because I was reading the thread linearly, but anyway, I'll expand upon yours:
1: >Niklaus Wirth's quote
https://news.ycombinator.com/item?id=42054371
2: >the joke about there being 10 kinds of people.
those who understand binary and those who don't.
If you want to read something incredible about Church, read Rota's reminiscence. It's the first section of https://www34.homepage.villanova.edu/robert.jantzen/princeto....
Related:
Alonzo Church, 92, Theorist of the Limits of Mathematics(1995) - https://news.ycombinator.com/item?id=12240815 - Aug 2016 (1 comment)
Gian-Carlo Rota on Alonzo Church (2008) - https://news.ycombinator.com/item?id=9073466 - Feb 2015 (2 comments)
Rota's reminiscence (not just the part about Church but the entire webpage, namely "Fine Hall in its golden age: Remembrances of Princeton in the early fifties") is, as the asterisked footnote alludes to, a chapter of his book Indiscrete Thoughts. The whole book is great reading.
Very enjoyable reading! I've noted the book too now, and hope to get to it.
The Alonzo programming language named after him [1] has mostly been forgotten.
Especially his philosophy of logic and sense/reference (a continuation of the work of Frege and Russell) is mostly forgotten. He published many papers on this topic, yet they aren't discussed e.g. in Wikipedia. At least the SEP entry is better:
https://plato.stanford.edu/entries/church/
Though I heard that it also neglects some major parts of his work. I assume it was too philosophical for mathematicians and too technical for philosophers.
Related: E.J. Lemmon, in his book Beginning Logic, lists some important logic books and says that Chapter 0 of Church's Introduction to Mathematical logic ``deserves to be read several times by /all/ philosophers''.
Not really the point BUT... I really wish people would refrain from using AI illustrations on blog posts. There are actual pictures of Church in the public domain, this illustration doesn't particularly look like him and is already appearing in image search results for the man thanks to the blog post's popularity. If the illustration has so little value that you can't be bothered to spend more than 5 minutes generating it then perhaps just leave it out?
[edit] ... and if you really must use "AI" generated imagery then at least caption it as such.
Thank you. Noted and sorry - I was loathe to take an online photo … this one was actually 7th effort as I did not want the ‘fake’ likeness, I felt it captured a resemblance… I managed a good one of JvN but you are right to address this. I think in future I will use a symbol rather than a ‘character (un) likeness ’
"Architect of computer intelligence" - I'm sure Church was an accomplished logician, but his contribution to "computer intelligence", which I imagine is supposed to mean AI/ML, is absolutely nil.
On a separate note, I don't think lambda calculus is really maths. It's more like clever notation. The merits of any notation are subjective. It's interesting how Church never cared about how that particular idea of his inspired the design of certain programming languages - which are ultimately notations, and therefore subjective in their merits.
"Lambda calculus" is sometimes used to mean "simply typed lambda calculus", which is mainly used to refer to simple type theory (STT), which is also called "Church's type theory". STT is also often identified with higher-order logic, since just two primitive types (basic "entities" like chairs and the "truth values" T/F) and the function type (a --> b) suffice to express arbitrary logical objects. STT is indeed an invention of Church, and it has had a major influence on other modern type theories, which are often described as extensions of simple type theory. These also influenced some programming languages with complex type system, like Haskell.
I can't fully argue for this, but my gut says that Turing and all he represents is ultimately valorized by AI-stuff, but Church is the opposite. The former started from the point of view of purity, minimum possible conditions/possibilities, and abstraction/"pure" computation; the latter cared about ways we could actually think, and cared not for implementation, but articulation and the furthering of abstraction.
One point of view for this is that Turing built practical computers during the war effort and then was forbidden by his own government to continue to build computers so had to retreat to theory. Church had no practical experience with computers and was looking as much to expand the theory of Mathematics itself. In their collaborations together and communications across an ocean they married a lot of the practical and the theory and solidified core parts of the theory (imperative/functional dualism [the Church-Turing Theorem often shortened to the Turing Theorem ignoring the contributions of both]; the Halting Problem [and its relationship to Church's Theorem]; more).
I think it's wrong to see it as a competition, because their collaboration did so much together. Computer Science has "two dads" and that feels appropriate for several reasons, including how Turing died. It is somewhat important to Computer Science that Church and Turing met in the middle, one with the deep raw mathematical theory background and the other with the practical (but at the time unacknowledged) background.
Also, it would be somewhat remiss to ignore that Turing did care about implementation and wanted to get back to practical implementation but wasn't allowed. There's a deep tragedy there and lot of questions about what would have been different if things hadn't been classified in the same way by the UK government. Though also in that case perhaps it would have cost us the Church collaboration that helped firm up the theory so well in our timeline.
I was lucky enough to meet Alonzo Church and Haskell Curry at the ACM Symposium on LISP and Functional Programming at CMU in August 1982. Curry was clearly not well and only lived about two weeks after the conference, but Church was in good form and lived about 13 more years. Gerry Sussman was very excited while he went around the room at the reception introducing them, and of course it was a great thrill for us to meet them.
First edition of Probabalistic Models, uses a lisp-like language called Church as a teaching tool. Obviously named after Alonzo Church.
I'm going for a browse of the book now and realise they've a newer second edition, for anyone interested, it's here:
Which doesn’t use church. Second edition uses a more JavaScript like language.
Excellent! Looks like a very cool book, and this comment very nearly passed me by. Thank you for sharing!
[stub for offtopicness]
Side remark: "Please don't take the bait" is a good analogue to "please don't feed the trolls".
We've taken the bait out of the title now, but when a thread has already filled up with comments reacting to it, rather than anything interesting, that's bad for HN threads.
"Forgotten" in the sense that everyone who knows anything about CS knows who he is because of the Church-Turing hypothesis, Church numerals, lambda calculus etc, and anyone who reads "On Computable Numbers" (only the most famous paper in all of computer science) knows that Turing actually quotes and credits Church and his work in that paper.
Here's a link to "On Computable Numbers" for easy reference for anyone who wants to read it/read it again. It's a cracker https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Forgotten not in the sense of lost knowledge, but more that the individual is not known proportionally to the importance of his work, or perhaps consistently when compared to his peers.
While specialists in his field know his work and his name (but not even everyone in software does), the public do not.
While your parents and friends see the dramatised exploits of Turing in films like The Imitation Game, or his face on the currency, the same is not said for Church.
Every field has it's public heroes, usually related to the stature of their work - Fleming and Jenner, Marconi, Ford, Bell. Turing.
Anyone will at least recognise these names, but not so for Church.
Ok, and if I asked a random member of the public for the name of a mathematician (excepting Turing, for clarity) what name do you think they would come up with? Pythagoras? Euler? Erdős?
I think the reality is that only a very small number of scientists, mathematicians, and similar are household names.
Isn't that just because they haven't made a blockbuster feature film about him yet?
Oh so maybe 0.01% of the population will even recognize his name
Dammit! Did I forget to forget him? Seems pretty memorable to me, and I'm just a regular dev.
The main theme of the essay is his work which helped the foundation of AI, In their book Artificial Intelligence A Modern Approach (Third Edition), Russell and Norvig give limited (cursory) commentary about A. Church, but Turing gets the foundational credites, I think that is an oversight - and this book has sold in the hundreds of thousands and is used on AI courses extensively!
The point is about a wider audience - I believe it is good to highlight people that have contributed significantly, yet overlooked by society at large - agreed about the CS sector, but then again on my intro to AI course less than 7% of bachelor students have heard of him in this context!
A historical tidbit which I loved in Paradigms of Artificial Intelligence Programming (available in PDF and EPUB here - https://github.com/norvig/paip-lisp):
> The name lambda comes from the mathematician Alonzo Church's notation for functions (Church 1941). Lisp usually prefers expressive names over terse Greek letters, but lambda is an exception. A better name would be make-function. Lambda derives from the notation in Russell and Whitehead's Principia Mathematica, which used a caret over bound variables: x̂(x + x). Church wanted a one-dimensional string, so he moved the caret in front: ^x(x + x). The caret looked funny with nothing below it, so Church switched to the closest thing, an uppercase lambda, Λx(x + x) . The Λ was easily confused with other symbols, so eventually the lowercase lambda was substituted: λx(x + x). John McCarthy was a student of Church's at Princeton, so when McCarthy invented Lisp in 1958, he adopted the lambda notation. There were no Greek letters on the keypunches of that era, so McCarthy used (lambda (x) (+ x x)), and it has survived to this day.
So, yes, on the topic of this post - Church pops up in loads of Lisp retrospectives. Maybe he's "forgotten" by people with very little engagement in the history of computing.