3 ms·

That does sort of make sense; what I was missing is the following idea: If you have a universal data structure at your disposal at runtime (that is, Lisp's lis

That does sort of make sense; what I was missing is the following idea: If you have a universal data structure at your disposal at runtime (that is, Lisp's list), then why not use that data structure to put function addresses into it, after function names had been looked up, to save additional look-ups in the future? So that makes sense! But -- was that idea really implemented in the absolute first version of Lisp? Wikipedia: https://en.wikipedia.org/wiki/Lisp_(programming_language) https://en.wikipedia.org/wiki/Lisp_(programming_language) >"Lisp was first implemented by Steve Russell on an IBM 704 computer using punched cards.[12] Russell had read McCarthy's paper and realized (to McCarthy's surprise) that the Lisp eval function could be implemented in machine code.[13] The result was a working Lisp interpreter which could be used to run Lisp programs, or more properly, "evaluate Lisp expressions"." When Steve Russell wrote this first version of Lisp -- did it really do that? Surely this idea wasn't present in McCarthy's paper -- so when/where and how in Lisp's early history -- did this idea come about? The idea would come about as the realization that continual table lookups are costly in terms of time -- so that would be early in lisp's history -- but that would not have been present in Steve Russell first version -- because this would have been the simplest implementation of Lisp possible... >"You're speculating without knowledge both about how early versions of Lisp worked and, I suspect, about how to teach an introductory CS class." Both Isaac Newton and Leibniz -- invented Calculus independent of the other at roughly the same point in time in history... Did one of them steal it from the other? Probably not; both had great minds capable of inductive and deductive reasoning; both had the ability to derive a body of unknown things that logically had to be true -- based on a body of known ones. Now, did they speculate about how things should be done when doing the work that would become Calculus? They probably did! But they also checked their speculations thoroughly, against existing knowledge, time and time again! Speculation is not evil, in and of itself, provided there is accompanying "due dilligence" to reconcile such speculation with a body of known information. If I "speculate" -- it's only one step, one small step, on the greater path of deriving. What you are calling speculation -- I call "the process of deriving". What I do is no different than a binary search for a bug in a codebase. "Can we eliminate this half of the code? Yes? OK, well then the problem must be in the other half." And Lather, Rinse, Repeat... In this case here, I'm trying to figure out when/where/why and how Lisp would have evolved from it's initial "do-the-lookup-every-single-time" version (or so I "speculate" <g>), to the "these lookups are time consuming, let's just put the address into the list and be done with it", later version, probably a few versions down the line. A comment which pointed to a source on the Internet where this information might be gleaned -- would be helpful. Telling me that I am without knowledge (and it might be true -- I might resemble that remark! <g>) -- is a lot like saying that there are uneducated people out there (and there are!) -- but then not doing one simple thing to help them out in their ignorance -- like giving them a book or manual -- or something else they can read -- to help educate them! At least give me a book or manual or web link or something! <g>

kazinator 6y ago
I've never seen any references to any Lisp work without symbol interning. I suspect MacCarthy had this idea before any code had been written. I also suspect that property lists came into being organically as part of incremental development, as follows. Initially, symbols would have had some built-in storage fields, such as a place to store a function or value. As development went on, the researchers wanted to attach more information to symbols pervasively. In the system itself, they waned to indicate whether a function is in machine language or in Lisp. Plus, likely, there were situations in which it was desirable to attach application-specific data to a symbol (that is not simply its value). At that point, the idea would have been obvious: let's not make symbols any larger with more fixed fields that waste memory, in order to represent rare properties that only a subset of the symbols have. Let's attach a dynamic list to them with variable properties. Since not all symbols have all properties, the properties cannot have fixed positions in these lists, which requires associative lookup. A symbol with no properties at all wastes only one storage cell to represent the empty list, which is the last such cost that has to be paid to support any number of properties.
- peter_d_sherman 6y ago
  Makes sense!
kragen 6y ago
Oh hey, sorry to go silent! I didn't mean to say you were evil, just mistaken! As far as I know, yes, symbol interning was in the very first version of Lisp (though at the time symbols were called "literal atoms"). McCarthy wrote a HOPL paper which is worth reading; one of the source links in the Wikipedia article you linked is the relevant part of McCarthy's 1979 "History of Lisp" paper for HOPL. The comment thread at https://news.ycombinator.com/item?id=26218426 https://news.ycombinator.com/item?id=26218426 points at some relevant papers from that epoch, as well as a runnable version of 7094 LISP, though of course not the very first version. Reading the Project MAC memos from that time (later retconned as AI Lab memos) is also very helpful, more for what they assume as implicit shared context rather than what they say explicitly. It might be worthwhile to dig into the documentation on the earlier versions of IPL, which were the inspiration for LISP, even more than the λ-calculus: http://bitsavers.org/pdf/rand/ipl/ http://bitsavers.org/pdf/rand/ipl/ — IIRC my friend Norm learned the concept of linked lists from these documents. It wasn't something that was obvious at the time. Also, there's an interview with McCarthy at https://www.infoq.com/interviews/Steele-Interviews-John-McCarthy/ https://www.infoq.com/interviews/Steele-Interviews-John-McCa... covering some of this time.

kazinator 6y ago

I've never seen any references to any Lisp work without symbol interning. I suspect MacCarthy had this idea before any code had been written. I also suspect that property lists came into being organically as part of incremental development, as follows. Initially, symbols would have had some built-in storage fields, such as a place to store a function or value. As development went on, the researchers wanted to attach more information to symbols pervasively. In the system itself, they waned to indicate whether a function is in machine language or in Lisp. Plus, likely, there were situations in which it was desirable to attach application-specific data to a symbol (that is not simply its value). At that point, the idea would have been obvious: let's not make symbols any larger with more fixed fields that waste memory, in order to represent rare properties that only a subset of the symbols have. Let's attach a dynamic list to them with variable properties. Since not all symbols have all properties, the properties cannot have fixed positions in these lists, which requires associative lookup. A symbol with no properties at all wastes only one storage cell to represent the empty list, which is the last such cost that has to be paid to support any number of properties.

peter_d_sherman 6y ago
Makes sense!

kragen 6y ago

Oh hey, sorry to go silent! I didn't mean to say you were evil, just mistaken! As far as I know, yes, symbol interning was in the very first version of Lisp (though at the time symbols were called "literal atoms"). McCarthy wrote a HOPL paper which is worth reading; one of the source links in the Wikipedia article you linked is the relevant part of McCarthy's 1979 "History of Lisp" paper for HOPL. The comment thread at https://news.ycombinator.com/item?id=26218426 https://news.ycombinator.com/item?id=26218426 points at some relevant papers from that epoch, as well as a runnable version of 7094 LISP, though of course not the very first version. Reading the Project MAC memos from that time (later retconned as AI Lab memos) is also very helpful, more for what they assume as implicit shared context rather than what they say explicitly. It might be worthwhile to dig into the documentation on the earlier versions of IPL, which were the inspiration for LISP, even more than the λ-calculus: http://bitsavers.org/pdf/rand/ipl/ http://bitsavers.org/pdf/rand/ipl/ — IIRC my friend Norm learned the concept of linked lists from these documents. It wasn't something that was obvious at the time. Also, there's an interview with McCarthy at https://www.infoq.com/interviews/Steele-Interviews-John-McCarthy/ https://www.infoq.com/interviews/Steele-Interviews-John-McCa... covering some of this time.