Alonzo Church: Architect of computer intelligence | Hacker News Reader

Alonzo Church: Architect of computer intelligence

onepercentrule.substack.com

329 pointsdrcwpl89 comments

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.

Great tidbit, (thanks for the Paradigms share) - in the footnote I mention about CS folks awareness.

But wait, who ever first coined the term 'lambda calculus' ? was it before or after McCarthy started lisp ?

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...

BTW the PAIP book, independent of AI topics (where it did not age so good) is an excellent book overall, covering many programming topics, and opening some paradigms, that for people who had little exposure to FP might be unknown.

>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.

"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.

"usually" probably means at the time of writing this book. lambda, car and cdr are from the 50s/60s when short names were preferred for various reasons (small memory, input on cards, output on paper, small screens, ...).

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.

The names CAR and CDR weren't invented for Lisp or FLPL. They came from assembly language mnemonics on the IBM 704, where the first Lisp interpreter was implemented.

The original Lisp CAR and CDR operations used the machine-level instructions with those names on the IBM 704.

Cons cells were stored in single words of the 36-bit memory and 36/38-bit registers, and the CAR and CDR operations accessed the "address" and "decrement" 15-bit parts of a word, respectively.

That's the legend, but they're actually no such instruction mnemonics.

The Address and Decrement terms and the fields of the 36-bit word they denote do come from the architecture.

There are instructions like LXA and LXD -- load index from address, load index from decrement.

probably there were no such machine-level instructions, but assembler macros

https://en.wikipedia.org/wiki/CAR_and_CDR

I felt it simplified the description to not mention they were assembler macros, but in retrospect, that was begging for a correction :-)

The linked page with details was interesting, thanks!

The page doesn't say that these were predefined assembler macros provided by IBM. I'm tending toward the interpretation that the Lisp guys themselves (likely Russel) wrote these macros as part of the assembly language implementation of the interpreter. Which means they specified them to the assembler, rather than the other way around.

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]

[1] http://catb.org/%7Eesr/writings/taoup/html/ch15s04.html

Yes, but after you get used to it, CADR, CADDR, etc are just a lot easier (and logical!) than SECOND, THIRD, ...

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.

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’odyssée de l’é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!

"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"

That is such a great quote - classic programming humor, but no idea of the original

Just like Niklaus Wirth's quote about how people used to call him, or the joke about there being 10 kinds of people.

Those are the ones that make me wish people knew just enough Computer Science to get them :)

"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 need more of these ...

https://news.ycombinator.com/item?id=42054476

> 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"

It's just as funny today as when I first heard it in 2002/2003... to which my professor at the time would add:

"But really, naming things is colouring. And cache invalidation is colouring. So really there's only one problem in computer science, colouring and counting... which doesn't sound so hard after all".

I made a UDP joke once.

You may get it.

I'm sorry, but this joke is out of order here!

Heh.

Are you sure you got it? ;)

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.

I think it is from Peter Norvig, look the sister comment.

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/...

Perfect! Thanks for the source.

>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). ]

from:

https://en.m.wikiquote.org/wiki/Niklaus_Wirth

So sayeth the wise Alonzo.

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....

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)

That is brilliant, thank you - I added the Rota one as an addendum under the further reading at the end.

This was entertaining, thanks for the link.

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.

[1] https://dl.acm.org/doi/pdf/10.1145/68127.68139

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 ’

thanks, and apologies if i came across harshly, I really enjoyed the article.

It is solid advice, I will be much more careful in future. Thank you

If you search for a picture of alonzo church now on google, the image from your article is near the top.

"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.

Oh yes, that's fair. I was thinking about that, but somehow dismissed it.

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.

This is a strong point, "the latter cared about ways we could actually think, and cared not for implementation, but articulation and the furthering of abstraction." I will look into this more. Thank you

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.

One of Church's big contributions was his students; an amazing collection of thinkers coming out of one place...

First edition of Probabalistic Models, uses a lisp-like language called Church as a teaching tool. Obviously named after Alonzo Church.

http://v1.probmods.org/

Excellent! Looks like a very cool book, and this comment very nearly passed me by. Thank you for sharing!

I'm going for a browse of the book now and realise they've a newer second edition, for anyone interested, it's here:

https://probmods.org/

Which doesn’t use church. Second edition uses a more JavaScript like language.

the real challenge of understanding lamba calculus is realizing its simplicity

it is a sacred idea by the fact that executing it does not really help understand the fact that it is equivalent to any and all computation

I don't know. You don't have to do much bootstrapping to get from lambda calculus primitives all the way up to if-elses, pattern matching, higher-order functions, etc.

[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.

People's conception of Turing is massively skewed by the ending. His persona is now defined by his sexuality and treatment more than his contributions to maths and computer science. Andrew Hodges book is great. I had the fortune to go to his author tour the year it came out, he was doing the compsci departments of the UK and it was a really nice seminar.

Benedic Cumbersome was a good actor, but it's important to remember Michelangelo actually didn't look like Kirk Douglas.

Also his contribution to the war might be one of the biggest reason he is well known.

I like that you called Benedict 'Cumbersome'. He is indeed cumbersome in so many roles.

I read a review in the Guardian [1] which used a series of malapropisms for his name, and riffed on the concept.

[1] https://www.theguardian.com/tv-and-radio/article/2024/may/29...

Right - For every Newton, who (rightly) gets credit for his immense contributions, there are people like Euler, who are relatively unknown outside the field in spite of significant contributions[1].

[1] Massive in the case of Euler obviously.

Agreed - what I tried to highlight through a series about people that have contributed significantly, but are not so well known outside of the fields they impacted, there is always cooperation to a large extent and others involved - rarely a lone individual as the Turing movie and much of the press in the UK likes to portray. And many people, who should be known, get lost in the complexity of history. It's worth bringing the attention of this to a wider audience - people are genuinely inquisitive. Plus as another example, on an intro course to AI 45 out of 52 bachelor students had never heard of Church!

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

As evidence, I've been programming for 25 years now but never actually studied CS. Yet throughout that duration I feel like I see/read Turing's name every week somewhere. I've never heard of Church until now.

Great point - thanks for that.

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!

It's ironic that you reference a paper by Turing here but not one by Church himself.

I also add the Turing one at the end of the post also because of the discussions at the beginning - especially "Church had certainly obtained the result before Turing"

Forgotten by whom? Certainly not by me.

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!

Reply on news.ycombinator.com