However, the word "binding", in Computer Science, is higher on the abstraction totem pole than say, words like "Compile Time" and "Runtime" -- which are more easily understood to new people...
When you add "early" and "late" to the word "binding", you are talking about things which are highly interpreter and compiler specific, that is, different compilers and interpreters which contain compilers and interpreters and bytecode compilers -- will all do things slightly different from one another...
Now, I should have amended what I said by talking about the earliest versions of Forth and Lisp.
The earliest versions of Forth and Lisp.
In those versions, they would not have bound ("binded", early or late) functions the way say a C compiler does, that is, by sticking the address of a function into machine code -- effectively removing all table lookups at that point.
No, those earliest versions of Forth and Lisp (and especially Forth) -- would have looked up (from a symbol table), the same symbol, each and every time that it was seen/invoked.
Would that have been slower than hell, compared to what a compiler can do?
Absolutely!
But that is how the earliest (AKA, "simplest"/"least complex") versions of these programs would have operated...
So, I stand corrected (as I said, all of what you've said is true, I acknowledge that) -- but the thing is, if you were teaching an introductory CS class, you wouldn't want to teach what you've said to new students on the first day, because many would not have the background necessary in compilers and interpreters to understand it...
So we're not arguing, you are correct, but while you are correct, please understand that what I search for is the most general, most broadest, simplest, unifying principles (maybe you would call them "axioms" or "first truths") from which all else (including all that you've explained) can be derived.
The idea of a symbol is that one does only do a lookup when the symbol is read. During execution the symbol is not read again. After reading the symbol is a reference to a symbol object in memory. That's why early Lisp has symbols for identifiers and not strings. Early on the data structure to find or intern a symbol might have been not very efficient, but finding a symbol was thought to be done mostly at read time.
Lisp then used a memory image which was loaded on startup (and possibly written on exit) - which contained the pre-interned symbols.
You're still wrong in the case of Lisp. The first runnable versions were interpreted, but even the earliest interpreter didn't do symbol-table lookups from the textual name on every function call. The symbols ("atoms") were absolutely stuck into the parsed code as addresses, removing all table lookups at that point. (But the interpreter still had to walk the atom's property list to find a property that would allow it to invoke the atom as a function, either EXPR, FEXPR, SUBR, or FSUBR.)
You're speculating without knowledge both about how early versions of Lisp worked and, I suspect, about how to teach an introductory CS class.
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?
>"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>
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 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/ — IIRC my friend Norm learned the concept of linked lists from these documents. It wasn't something that was obvious at the time.
>"IPL was first utilized to demonstrate that the theorems in Principia Mathematica which were proven laboriously by hand, by Bertrand Russell and Alfred North Whitehead, could in fact be proven by computation. According to Simon's autobiography Models of My Life, this application was originally developed first by hand simulation, using his children as the computing elements, while writing on and holding up note cards as the registers which contained the state variables of the program."
Fascinating!
Makes me want to go back into the history of that Math and those theorems, and who proved what, when...
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.
However, the word "binding", in Computer Science, is higher on the abstraction totem pole than say, words like "Compile Time" and "Runtime" -- which are more easily understood to new people...
When you add "early" and "late" to the word "binding", you are talking about things which are highly interpreter and compiler specific, that is, different compilers and interpreters which contain compilers and interpreters and bytecode compilers -- will all do things slightly different from one another...
Now, I should have amended what I said by talking about the earliest versions of Forth and Lisp.
The earliest versions of Forth and Lisp.
In those versions, they would not have bound ("binded", early or late) functions the way say a C compiler does, that is, by sticking the address of a function into machine code -- effectively removing all table lookups at that point.
No, those earliest versions of Forth and Lisp (and especially Forth) -- would have looked up (from a symbol table), the same symbol, each and every time that it was seen/invoked.
Would that have been slower than hell, compared to what a compiler can do?
Absolutely!
But that is how the earliest (AKA, "simplest"/"least complex") versions of these programs would have operated...
So, I stand corrected (as I said, all of what you've said is true, I acknowledge that) -- but the thing is, if you were teaching an introductory CS class, you wouldn't want to teach what you've said to new students on the first day, because many would not have the background necessary in compilers and interpreters to understand it...
So we're not arguing, you are correct, but while you are correct, please understand that what I search for is the most general, most broadest, simplest, unifying principles (maybe you would call them "axioms" or "first truths") from which all else (including all that you've explained) can be derived.
But all of that being said... you are correct!