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.
"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".
> "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.
"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, ...).
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.
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
"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"
"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".
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.
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 ’
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:
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.
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
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.
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.
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].
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!
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.
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!
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"
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.
"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.
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.
Yes, but after you get used to it, CADR, CADDR, etc are just a lot easier (and logical!) than SECOND, THIRD, ...
"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, ...).
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.
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.
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...
>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.
Great tidbit, (thanks for the Paradigms share) - in the footnote I mention about CS folks awareness.
"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/...
Perfect! Thanks for the source.
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 ...
I think it is from Peter Norvig, look the sister comment.
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.
This was entertaining, thanks for the link.
That is brilliant, thank you - I added the Rota one as an addendum under the further reading at the end.
The Alonzo programming language named after him [1] has mostly been forgotten.
[1] https://dl.acm.org/doi/pdf/10.1145/68127.68139
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
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.
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
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
[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.
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...
Also his contribution to the war might be one of the biggest reason he is well known.
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!