Comment by sourcepluck

Comment by sourcepluck 10 days ago

26 replies

View on Hacker News

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.

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

Reply View 3 replies
  • sourcepluck 9 days 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?".

    Reply View 2 replies
    • psychoslave 9 days ago

      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

      Reply View 1 reply
      • sourcepluck 9 days ago

        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!

        Reply View 0 replies
Chinjut 9 days 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.

Reply View 10 replies
  • sourcepluck 9 days 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, 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.

    Reply View 7 replies
    • kazinator 9 days 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.

      Reply View 5 replies
      • jlokier 9 days 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.

        Reply View 4 replies
  • lispm 9 days 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, ...).

    Reply View 0 replies
  • kkylin 9 days ago

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

    Reply View 0 replies
f1shy 9 days 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.

Reply View 0 replies
Chinjut 9 days 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_... for other instances where Alonzo Church has suggested it was more of an arbitrary choice of Greek letter.

Reply View 1 reply
  • sourcepluck 9 days 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) 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.

    Reply View 0 replies
agumonkey 9 days ago

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

Reply View 2 replies
[removed] 9 days ago
[deleted]
Reply View 0 replies
drcwpl 10 days ago

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

Reply View 0 replies
CodeArtisan 9 days 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.

Reply View 2 replies
  • trenchgun 9 days 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

    Reply View 0 replies