5 ms·

A historical tidbit which I loved in Paradigms of Artificial Intelligence Programming (available in PDF and EPUB here - https://github.com/norvig/paip-lisp http

A historical tidbit which I loved in Paradigms of Artificial Intelligence Programming (available in PDF and EPUB here - https://github.com/norvig/paip-lisp 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.

drcwpl 2y ago
Great tidbit, (thanks for the Paradigms share) - in the footnote I mention about CS folks awareness.
agumonkey 2y ago
But wait, who ever first coined the term 'lambda calculus' ? was it before or after McCarthy started lisp ?
- seanhunter 2y ago
  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/Church-%20A%20Set%20of%20Postulates%20for%20the%20Foundation%20of%20Logic.pdf https://raw.githubusercontent.com/emintham/Papers/master/Chu...
  - agumonkey 2y ago
    Yeah indeed no trace of the term 'lambda'. But this https://www.classes.cs.uchicago.edu/archive/2007/spring/32001-1/papers/church-1940.pdf 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.pdf#page=9 https://compcalc.github.io/public/church/church_calculi_1941...
f1shy 2y ago
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.
deleted 2y ago
[deleted]
CodeArtisan 2y ago
>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.
- trenchgun 2y ago
  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
- llm_trw 2y ago
  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.
Chinjut 2y ago
"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.
- lispm 2y ago
  "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, ...).
- sourcepluck 2y ago
  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 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.
  - kazinator 2y ago
    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.
    - jlokier 2y ago
      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.
Chinjut 2y ago
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_%CE%BB_symbol 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.
- sourcepluck 2y ago
  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 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.
psychoslave 2y 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-calculus-named-after-that-specific-greek-letter-why-not-rho-calc/64469#64469 https://math.stackexchange.com/questions/64468/why-is-lambda...
- sourcepluck 2y ago
  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?".

drcwpl 2y ago

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

agumonkey 2y ago

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

seanhunter 2y ago
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/Church-%20A%20Set%20of%20Postulates%20for%20the%20Foundation%20of%20Logic.pdf https://raw.githubusercontent.com/emintham/Papers/master/Chu...
- agumonkey 2y ago
  Yeah indeed no trace of the term 'lambda'. But this https://www.classes.cs.uchicago.edu/archive/2007/spring/32001-1/papers/church-1940.pdf 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.pdf#page=9 https://compcalc.github.io/public/church/church_calculi_1941...

f1shy 2y ago

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.

deleted 2y ago

[deleted]

CodeArtisan 2y ago

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

trenchgun 2y ago
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
llm_trw 2y ago
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.

Chinjut 2y ago

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

lispm 2y ago
"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, ...).
sourcepluck 2y ago
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 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.
- kazinator 2y ago
  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.
  - jlokier 2y ago
    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.

Chinjut 2y ago

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_%CE%BB_symbol 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.

sourcepluck 2y ago
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 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.

psychoslave 2y 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-calculus-named-after-that-specific-greek-letter-why-not-rho-calc/64469#64469 https://math.stackexchange.com/questions/64468/why-is-lambda...

sourcepluck 2y ago
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?".