This article has been a fascinating read, by the way. Kudos to the maintainer of the Gist post. I am also sharing these corrections as comments on the Gist post.
EDIT #1: Downloaded a copy of the original Scientific American article from https://www.jstor.org/stable/24968822 and confirmed that indeed the functions "oval" and "snot" are misspellings of "eval" and "snoc".
EDIT #2: Fixed typo in this comment highlighted by @fuzztester below.
This article simply reinforces that the primary problem with the popularity of Lisp was people explaining Lisp.
This article, like every other Lisp article, tells pre-teen me nothing that he could use. Nobody ever demonstrated how much easier task X is in Lisp over asm/C/Pascal/etc.
By contrast, current me could have told pre-teen me "Hey, that spell checker that took you 7 months to write in assembly? Yeah, it's damn near trivial in Lisp on a microcomputer with bank switched memory that nobody every knew how to utilize (it makes garbage collection completely deterministic even on a woefully underpowered CPU). Watch."
I want to weep over the time I wasted doing programming with the equivalent of tweezers, rice grains and glue because every Lisp article and textbook repeated the same worn out lists, recursion and AI crap without ever demonstrating how to do anything useful.
Hofstadter's followup article had a more interesting example.
When I first got a Byte magazine as a pre-teen, one of the articles was Lisp code for symbolic differentiation and algebraic simplification. I really couldn't follow it but felt there was something intriguing there. Certainly it wouldn't have been easier in Basic.
(Byte September 1981, AI theme issue. Later I was able to tell the code was not so hot...)
I didn't really get into Lisp until the late 80s with XLisp on a PC, and SICP. Worth the wait!
I just love his writing so much -- he captures what I felt when I discovered Lisp. As a kid learning programming in the 80s, I had already done some BASIC, Fortran, Pascal and COBOL in high school and early college. There were differences, of course, but they had some fundamental commonality.
At UC Berkeley, however, the first computer science class was taught in Scheme (a dialect of Lisp)...and it absolutely blew me away. Hofstadter is right: it feels the closest to math (reminding me a ton of my math theory classes). It was the first beautiful language I discovered.
(edit: I forgot to paste in the quote I loved!)
"...Lisp and Algol, are built around a kernel that seems as natural as a branch of mathematics. The kernel of Lisp has a crystalline purity that not only appeals to the esthetic sense, but also makes Lisp a far more flexible language than most others."
At the risk of diverging off from the original post, I also think that calling it "math" might make things a bit murky (and this is coming from someone who wanted to be algebraic topologist!)
It _is_ an elegant and minimal expression of a style of programming that is ubiquitous among dynamically-typed, garbage-collected languages. And it's a "theory" in the sense that it seems complete, and that you can think of ways to solve problems into Scheme and translate that into other dynamically-typed languages and still end with an elegant solution. Emphasis on the elegant (since minimal, wart-free, consistent and orthogonal, etc.).
Scheme was a simplification and a "cleaning up" compared to conventional Lisps of the time (lexical scoping, single shared namespace for functions and variables etc.)
> IN previous columns I have written quite often about the field of artificial intelligence - the search for ways to program computers so that they might come to behave with flexibility, common sense, insight, creativity, self awareness, humor, and so on.
This is very amusing to me because it reads like a list of things LLMs truly stink at. Though at least they finally represent some nonzero amount of movement in that direction.
You must interact with more interesting people than I because to me LLMs have demonstrated as much "common sense, insight, creativity, self awareness, humor" as the average person I run into (actually maybe more but that makes me sound crazy to myself).
This article, and the two companion articles it mentions, can be found in the book "Metamagical Themas" [0] in chapters 17-19, as well as all of his other articles that appeared in this series of Scientific American.
(the book's title is the article series, which originated as an anagram of the article series that Martin Gardner authored, "Mathematical Games," also published in Scientific American and which Hofstadter then took over)
> Attempting to take the car or cdr of nil causes (or should cause) the Lisp genie to cough out an error message, just as attempting to divide by zero should evoke an error message.
Interestingly, this is no longer the case. Modern Lisps now evaluate (car nil) and (cdr nil) to nil. In the original Lisp defined by John McCarthy, indeed CAR and CDR were undefined for NIL. Quoting from <https://dl.acm.org/doi/pdf/10.1145/367177.367199>:
> Here NIL is an atomic symbol used to terminate lists.
> car [x] is defined if and only if x is not atomic.
> Function: car cons-cell ... As a special case, if cons-cell is nil, this function returns nil. Therefore, any list is a valid argument. An error is signaled if the argument is not a cons cell or nil.
> Function: cdr cons-cell ... As a special case, if cons-cell is nil, this function returns nil; therefore, any list is a valid argument. An error is signaled if the argument is not a cons cell or nil.
I was curious what it is like on Maclisp. Here is a complete telnet session with Lars Brinkhoff's public ITS:
$ telnet its.pdp10.se 10003
Trying 88.99.191.74...
Connected to pdp10.se.
Escape character is '^]'.
Connected to the KA-10 simulator MTY device, line 0
^Z
TT ITS.1652. DDT.1548.
TTY 21
3. Lusers, Fair Share = 99%
Welcome to ITS!
For brief information, type ?
For a list of colon commands, type :? and press Enter.
For the full info system, type :INFO and Enter.
Happy hacking!
:LOGIN SUSAM
TT: SUSAM; SUSAM MAIL - NON-EXISTENT DIRECTORY
:LISP
LISP 2156
Alloc? n
*
(status lispversion)
/2156
(car nil)
NIL
(cdr nil)
NIL
^Z
50107) XCT 11 :LOGOUT
TT ITS 1652 Console 21 Free. 19:55:07
^]
telnet> ^D Connection closed.
$
The use of car and cdr are such a surprisingly concrete implementation detail in the birth of a language that was designed to be mathematical. The most basic and famous operators of "List Processor" were created to operate not on lists but on conses, an element in a particular machine representation that Lisp uses to build data structures! Not only are conses not always interpreted as lists, but a very very important list, the base case for recursive functions on lists, is not represented by a cons.
Sixty years later, most Lisp programs are still full of operations on conses. A more accurate name for the language would be "Cons Processor!" It's a reminder that Lisp was born in an era when a language and its implementation had to fit hand in glove. I think that makes the achievement of grounding a computer language in mathematical logic all the more remarkable.
is there a term to describe the language design choice (reminds me of SQL, btw, where it is equally bad IMHO) where doing things to nil just returns nil without erroring? I want to call it "bleeding nils/NULLs" if there isn't another term yet.
As stated, I think this design choice is terrible, especially if nil isn't equivalent to false in boolean comparisons (as it is in Ruby and Elixir- with Elixir actually providing two types of boolean operators with slightly different but significant behavior; "and" will only take pure booleans while "&&" will equate nil with false). It might mean cleaner-written code upfront but it's going to result in massively-harder-to-debug code because the actual error (a mishandled nil result) might only create a visible problem many stack levels away in some completely different part of the code.
There really should be two different kinds of cons cells, one for "proper" linked lists and another for general purpose consing. The difference is that the cdr of the first kind of cons cell (I'll call it a PL-cons) can only be NIL or another PL-cons, not anything else. This would eliminate vast categories of bugs. It would also make the predicate for determining is something was a proper list run in constant time rather than O(n). (There would still be edge cases with circular lists, but those are much less common than non-proper lists.)
I certainly know the Lisp information in this article already, but it's still a fun read. Hofstadter just has a charming way with words.
I found this bit extra amusing:
>It would be nice as well as useful if we could create an inverse operation to readers-digest-condensed-version called rejoyce that, given any two words, would create a novel beginning and ending with them, respectively - and such that James Joyce would have written it (had he thought of it). Thus execution of the Lisp statement (rejoyce 'Stately 'Yes) would result in the Lisp genie generating from scratch the entire novel Ulysses. Writing this function is left as an exercise for the reader.
It took a while, but we got there. I don't think 2024's AI is quite what he had in mind in 1983, but you have to admit that reproducing text given a little seeding is a task that quite suits the AI of today.
I do think LISP remains the major language that can encompass the strange loop idea he explored in his work. I know LISP is not the only homoiconic language, but it is the biggest that people know how to use where the "eval" function doesn't take in a string that has to be parsed.
I hate that people are convinced LISP == functional programming, writ large. Not that I dislike functional programming, but the symbolic nature of it is far more interesting to me. And it amuses me to no end that I can easily make a section of code that is driven by (go tag) sections, such that I can get GOTO programming in it very easily.
I loved Hofstadter's writing on Lisp in Metamagical Themas and adapted the code in the last article of the series to Clojure for a study group at work, written up here[1].
> As you might expect, the value of the atom 1729 is the integer 1729, and this is permanent. (I am distinguishing here between the atom whose print name or pname is the four-digit string 1729, and the eternal Platonic essence that happens to be the sum of two cubes in two different ways - i.e., the number 1729.)
> Every computer language has arbitrary features, and most languages are in fact overloaded with them. A few, however, such as Lisp and Algol, are built around a kernel that seems as natural as a branch of mathematics.
Algol? The kernel of Algol seems as natural as a branch of mathematics? Can anyone who has used Algol give their opinion of this statement?
I read that article when it came out, as my parents subscribed to Scientific American. Even though I had learned BASIC and Pascal, the concepts in the article were just way over my head. Also, I had no access (that I was aware of at least) to a machine where I could try my hand at Lisp programming. Alas, I wish I had taken it more seriously.
At least Hofstadter was successful at getting me interested in math beyond high school.
I find this article to be quaint -- remember reading it decades ago and feeling more receptive to its perspective. Ironically, I prefer using Clojure (though some here challenge its status as a Lisp lol) to interface with Large Language Models rather than Python. Clojure in particular is much better suited, for some reasons that Hofstadter details, and if you can interact with an LLM over a wire, you are not beholden to Python. But what we use to interface to these massive digital minds we are building, including the Bayesian sampling mathematics we use to plumb them, may have their elegance, but they are orthogonal to the nearly ineffable chaos of these deeply interconnected neural networks -- and it is in this chaotic interconnectedness where artificial intelligence is actually engendered.
That’s changed, of course, but it remained true for at least another 15 or 20 years after this article was written and then changed rather quickly, perhaps cemented with deep neural networks and GPUs.
Other than running the emacs ecosystem, what else is Lisp being used for commonly these days?
I remember reading GEB and being shocked that he never mentions Lisp. He _does_ wade into CompSci topics, but it's something half-hearted about how compilers are programs that read and generate programs. This really should've been integrated into a revised edition of the book.
In case anyone else is confused by what the functions named "oval" and "snot" mean in the following example:
I realised after a few seconds that they are meant to be "eval" and "snoc" instead. The above code should be written as the following instead: This article has been a fascinating read, by the way. Kudos to the maintainer of the Gist post. I am also sharing these corrections as comments on the Gist post.EDIT #1: Downloaded a copy of the original Scientific American article from https://www.jstor.org/stable/24968822 and confirmed that indeed the functions "oval" and "snot" are misspellings of "eval" and "snoc".
EDIT #2: Fixed typo in this comment highlighted by @fuzztester below.
>confirmed that indeed the functions "oval" and "snot" are misspellings of "eval" and "snot".
Correction of your correction:
confirmed that indeed the functions "oval" and "snot" are misspellings of "eval" and "snoc".
And I guess snoc is cons reversed and rac is car reversed.
OCR maybe?
This article simply reinforces that the primary problem with the popularity of Lisp was people explaining Lisp.
This article, like every other Lisp article, tells pre-teen me nothing that he could use. Nobody ever demonstrated how much easier task X is in Lisp over asm/C/Pascal/etc.
By contrast, current me could have told pre-teen me "Hey, that spell checker that took you 7 months to write in assembly? Yeah, it's damn near trivial in Lisp on a microcomputer with bank switched memory that nobody every knew how to utilize (it makes garbage collection completely deterministic even on a woefully underpowered CPU). Watch."
I want to weep over the time I wasted doing programming with the equivalent of tweezers, rice grains and glue because every Lisp article and textbook repeated the same worn out lists, recursion and AI crap without ever demonstrating how to do anything useful.
Common Lisp: A Gentle Introduction to Symbolic Computation might be useful for the context you are describing. https://www.cs.cmu.edu/~dst/LispBook/
Practical Common Lisp https://gigamonkeys.com/book/
Hofstadter's followup article had a more interesting example.
When I first got a Byte magazine as a pre-teen, one of the articles was Lisp code for symbolic differentiation and algebraic simplification. I really couldn't follow it but felt there was something intriguing there. Certainly it wouldn't have been easier in Basic.
(Byte September 1981, AI theme issue. Later I was able to tell the code was not so hot...)
I didn't really get into Lisp until the late 80s with XLisp on a PC, and SICP. Worth the wait!
I just love his writing so much -- he captures what I felt when I discovered Lisp. As a kid learning programming in the 80s, I had already done some BASIC, Fortran, Pascal and COBOL in high school and early college. There were differences, of course, but they had some fundamental commonality.
At UC Berkeley, however, the first computer science class was taught in Scheme (a dialect of Lisp)...and it absolutely blew me away. Hofstadter is right: it feels the closest to math (reminding me a ton of my math theory classes). It was the first beautiful language I discovered.
(edit: I forgot to paste in the quote I loved!)
"...Lisp and Algol, are built around a kernel that seems as natural as a branch of mathematics. The kernel of Lisp has a crystalline purity that not only appeals to the esthetic sense, but also makes Lisp a far more flexible language than most others."
Have you tried Haskell? It feels much closer to math to me. Definitions, not procedures. It even looks like math.
At the risk of diverging off from the original post, I also think that calling it "math" might make things a bit murky (and this is coming from someone who wanted to be algebraic topologist!)
It _is_ an elegant and minimal expression of a style of programming that is ubiquitous among dynamically-typed, garbage-collected languages. And it's a "theory" in the sense that it seems complete, and that you can think of ways to solve problems into Scheme and translate that into other dynamically-typed languages and still end with an elegant solution. Emphasis on the elegant (since minimal, wart-free, consistent and orthogonal, etc.).
Scheme was a simplification and a "cleaning up" compared to conventional Lisps of the time (lexical scoping, single shared namespace for functions and variables etc.)
40 years ago, and 20 years into the field:
> February, 1983
> IN previous columns I have written quite often about the field of artificial intelligence - the search for ways to program computers so that they might come to behave with flexibility, common sense, insight, creativity, self awareness, humor, and so on.
This is very amusing to me because it reads like a list of things LLMs truly stink at. Though at least they finally represent some nonzero amount of movement in that direction.
You must interact with more interesting people than I because to me LLMs have demonstrated as much "common sense, insight, creativity, self awareness, humor" as the average person I run into (actually maybe more but that makes me sound crazy to myself).
His research group has a long history of trying to tackle these problems. Some interesting reading , even if much of it hasn’t (yet?) panned out .
This article, and the two companion articles it mentions, can be found in the book "Metamagical Themas" [0] in chapters 17-19, as well as all of his other articles that appeared in this series of Scientific American.
[0]: https://www.goodreads.com/book/show/181239.Metamagical_Thema...
(the book's title is the article series, which originated as an anagram of the article series that Martin Gardner authored, "Mathematical Games," also published in Scientific American and which Hofstadter then took over)
I love this book. Highly recommended for all lovers of Godel Escher Bach (his classic).
This book is indeed very beautiful to read and look at, it has a lot of fascinating illustrations.
> Attempting to take the car or cdr of nil causes (or should cause) the Lisp genie to cough out an error message, just as attempting to divide by zero should evoke an error message.
Interestingly, this is no longer the case. Modern Lisps now evaluate (car nil) and (cdr nil) to nil. In the original Lisp defined by John McCarthy, indeed CAR and CDR were undefined for NIL. Quoting from <https://dl.acm.org/doi/pdf/10.1145/367177.367199>:
> Here NIL is an atomic symbol used to terminate lists.
> car [x] is defined if and only if x is not atomic.
> cdr [x] is also defined when x is not atomic.
However, both Common Lisp and Emacs Lisp define (car nil) and (cdr nil) to be nil. Quoting from <https://www.lispworks.com/documentation/HyperSpec/Body/f_car...>:
> If x is a cons, car returns the car of that cons. If x is nil, car returns nil.
> If x is a cons, cdr returns the cdr of that cons. If x is nil, cdr returns nil.
Also, quoting from <https://www.gnu.org/software/emacs/manual/html_node/elisp/Li...>:
> Function: car cons-cell ... As a special case, if cons-cell is nil, this function returns nil. Therefore, any list is a valid argument. An error is signaled if the argument is not a cons cell or nil.
> Function: cdr cons-cell ... As a special case, if cons-cell is nil, this function returns nil; therefore, any list is a valid argument. An error is signaled if the argument is not a cons cell or nil.
I was curious what it is like on Maclisp. Here is a complete telnet session with Lars Brinkhoff's public ITS:
The use of car and cdr are such a surprisingly concrete implementation detail in the birth of a language that was designed to be mathematical. The most basic and famous operators of "List Processor" were created to operate not on lists but on conses, an element in a particular machine representation that Lisp uses to build data structures! Not only are conses not always interpreted as lists, but a very very important list, the base case for recursive functions on lists, is not represented by a cons.
Sixty years later, most Lisp programs are still full of operations on conses. A more accurate name for the language would be "Cons Processor!" It's a reminder that Lisp was born in an era when a language and its implementation had to fit hand in glove. I think that makes the achievement of grounding a computer language in mathematical logic all the more remarkable.
> Modern Lisps now evaluate (car nil) and (cdr nil) to nil.
Scheme doesn't. Taking the CAR or CDR of nil is an error.
Sadly this is not the case with Scheme and it makes for very unergonomic code, especially for a newbie like me.
Which is a shame, because I prefer (Guile) Scheme to Common Lisp.
is there a term to describe the language design choice (reminds me of SQL, btw, where it is equally bad IMHO) where doing things to nil just returns nil without erroring? I want to call it "bleeding nils/NULLs" if there isn't another term yet.
As stated, I think this design choice is terrible, especially if nil isn't equivalent to false in boolean comparisons (as it is in Ruby and Elixir- with Elixir actually providing two types of boolean operators with slightly different but significant behavior; "and" will only take pure booleans while "&&" will equate nil with false). It might mean cleaner-written code upfront but it's going to result in massively-harder-to-debug code because the actual error (a mishandled nil result) might only create a visible problem many stack levels away in some completely different part of the code.
There really should be two different kinds of cons cells, one for "proper" linked lists and another for general purpose consing. The difference is that the cdr of the first kind of cons cell (I'll call it a PL-cons) can only be NIL or another PL-cons, not anything else. This would eliminate vast categories of bugs. It would also make the predicate for determining is something was a proper list run in constant time rather than O(n). (There would still be edge cases with circular lists, but those are much less common than non-proper lists.)
I certainly know the Lisp information in this article already, but it's still a fun read. Hofstadter just has a charming way with words.
I found this bit extra amusing:
>It would be nice as well as useful if we could create an inverse operation to readers-digest-condensed-version called rejoyce that, given any two words, would create a novel beginning and ending with them, respectively - and such that James Joyce would have written it (had he thought of it). Thus execution of the Lisp statement (rejoyce 'Stately 'Yes) would result in the Lisp genie generating from scratch the entire novel Ulysses. Writing this function is left as an exercise for the reader.
It took a while, but we got there. I don't think 2024's AI is quite what he had in mind in 1983, but you have to admit that reproducing text given a little seeding is a task that quite suits the AI of today.
I do think LISP remains the major language that can encompass the strange loop idea he explored in his work. I know LISP is not the only homoiconic language, but it is the biggest that people know how to use where the "eval" function doesn't take in a string that has to be parsed.
I hate that people are convinced LISP == functional programming, writ large. Not that I dislike functional programming, but the symbolic nature of it is far more interesting to me. And it amuses me to no end that I can easily make a section of code that is driven by (go tag) sections, such that I can get GOTO programming in it very easily.
>Emacs defalias
On Common Lisp too, by defining defalias as a macro:
https://stackoverflow.com/questions/24252539/defining-aliase...
I loved Hofstadter's writing on Lisp in Metamagical Themas and adapted the code in the last article of the series to Clojure for a study group at work, written up here[1].
[1] http://johnj.com/posts/oodles/
edit: clarification
> As you might expect, the value of the atom 1729 is the integer 1729, and this is permanent. (I am distinguishing here between the atom whose print name or pname is the four-digit string 1729, and the eternal Platonic essence that happens to be the sum of two cubes in two different ways - i.e., the number 1729.)
He is? What is the distinguishment he is making?
This writing styling is....interesting.
> In a testament to the timelessness of Lisp, you can still run all the examples below in emacs if you install these aliases:
> (defalias 'plus #'+)
> (defalias 'quotient #'/)
> (defalias 'times #'*)*
> (defalias 'difference #'-)*
Looks like we also need a defmacro for def that is used much further in the article:
> > (def rac (lambda (lyst) (car (reverse lyst))))
I mean the above example fails in Emacs:
If we want the above example to work, we need to define def like this: Now the previous example, as presented in the article, works fine:> Every computer language has arbitrary features, and most languages are in fact overloaded with them. A few, however, such as Lisp and Algol, are built around a kernel that seems as natural as a branch of mathematics.
Algol? The kernel of Algol seems as natural as a branch of mathematics? Can anyone who has used Algol give their opinion of this statement?
I read that article when it came out, as my parents subscribed to Scientific American. Even though I had learned BASIC and Pascal, the concepts in the article were just way over my head. Also, I had no access (that I was aware of at least) to a machine where I could try my hand at Lisp programming. Alas, I wish I had taken it more seriously.
At least Hofstadter was successful at getting me interested in math beyond high school.
* After this "def wish" has been carried out, the rac function is as well understood by the genie as is car. *
Sometimes I wonder what non-programmers think about us when they hear us talk..
Maclisp goodness:
Elisp much improved:Any Shen people in the house?
Interesting article, I enjoyed following along - but I do hate the parentheses lol
What dialect is he using that has “plus” vs “+” and so on?
I find this article to be quaint -- remember reading it decades ago and feeling more receptive to its perspective. Ironically, I prefer using Clojure (though some here challenge its status as a Lisp lol) to interface with Large Language Models rather than Python. Clojure in particular is much better suited, for some reasons that Hofstadter details, and if you can interact with an LLM over a wire, you are not beholden to Python. But what we use to interface to these massive digital minds we are building, including the Bayesian sampling mathematics we use to plumb them, may have their elegance, but they are orthogonal to the nearly ineffable chaos of these deeply interconnected neural networks -- and it is in this chaotic interconnectedness where artificial intelligence is actually engendered.
> I hope you enjoyed Hofstadter's idiosyncratic tour of Lisp. You can find more like this re-printed in his book Metamagical Themas.
This seems like an interesting book.
> Why is most AI work done in Lisp?
That’s changed, of course, but it remained true for at least another 15 or 20 years after this article was written and then changed rather quickly, perhaps cemented with deep neural networks and GPUs.
Other than running the emacs ecosystem, what else is Lisp being used for commonly these days?
Regardless of your opinion on the utility of Lisp, this is an exemplary piece of writing. Crisp, engaging, informative.
God I miss old Scientific American. Today's SA isn't especially terrible, but old SA, like old BYTE, was reliably enlightening.
I remember reading GEB and being shocked that he never mentions Lisp. He _does_ wade into CompSci topics, but it's something half-hearted about how compilers are programs that read and generate programs. This really should've been integrated into a revised edition of the book.
Lisp aNeeds Braces