Comment by peter_d_sherman | Hacker News Reader

Comment by peter_d_sherman | Hacker News Reader

Parent Full thread

peter_d_sherman

Both Forth and Lisp (and Basic, and every other interpreted language) -- implement symbol lookup at runtime, that is, take an arbitrary text string like 'something', 'something else', 'FUNC1', 'bob', etc. -- and look up an address for that value, then CALL that address (make that function happen).

Modern programmers might understand this as a hash lookup, or a key/value lookup... The key is the function/functionality name (symbol, string, call it whatever you will), and the value is an integer, which is the address in memory that will be called to implement the functionality.

Forth doesn't hide anything from the programmer.

Lisp hides its implementation of its list structure (memory, dynamic memory allocation, dynamic memory deletion, etc.) as well as any and all stacks -- from the programmer.

Now lisp might have API's where that information is accessible to the programmer -- (in theory, any language can have an API which allows access to any and all memory, by definition this allows any language to play with all parts of the machine), but the way LISP was originally implemented, the programmer no longer has to deal with this, much in the same way that in Java/.NET, the programmer doesn't have to deal with deallocating memory for objects when they go out of scope...

But all interpreted languages, one way or another, boil down to 'look up a symbol/string/"key" -- representing a function name -- then call/goto/invoke that function in memory... sort of like a key/value lookup (or even just a variable name that gives you back an address -- a pointer in compiled languages), and then you just CALL (preserving where you came from (to later RET)) to that address"...

So in some ways similar, in some ways different...

Both Forth and Lisp (and Basic, and every other interpreted language) -- implement symbol lookup at runtime

False for both Forth and Lisp — for Lisp since the beginning, for Forth since the early 1970s.

Note that (a usual) Forth (here I'm centering on ANS Forth) uses early binding for most code, rather than late binding as you sound like you're talking about. The dictionary is indeed available at runtime, but runtime includes compile-time!—which is how a lot of the metaprogramming works, by interleaving the two with no strict phase separation. So it's while you're defining a word that calls other words that the other words are looked up, and not while you're executing it. This has some convenient implications for redefinitions:

    : foo ( something ) ;
    : bar 2dup foo 1+ * ; \ or whatever
    \ ... in something loaded later on ...
    : foo ( other thing entirely ) ;
    : xyzzy foo bar ; \ calls later foo, then earlier bar which calls earlier foo

… which means it's harder to run into problems with stepping on “internal” symbols even if you're using short names in the “same” dictionary. “Purely” interpreted Forth does happen at the top level, in which lookups happen just before execution, but the part of it that isn't being used for compilation tends to be small fragments to kick off execution or to enter commands interactively. (In colorForth, phase distinctions are made by color instead, but I believe it also does early-bound compilation.)

In (a usual) Lisp (here I'm centering on Common Lisp and Scheme), function and variable lookups default to late binding, but based on symbol objects rather than strings. The symbols themselves contain pointers to function objects and/or variable contents, so there's a level of indirection, but it's not a hash table lookup every time. (Indeed in CL you can have “uninterned” symbols which usually have a name but can't be looked up by that name.) Again the mapping from strings, that is, packages in CL, obarrays in Emacs Lisp, etc. generally remains available at runtime, so you can do (find-symbol "FOO"), but when processing definitions, the lookup from string to symbol happens at read time. Then in CL there's some restrictions on redefinitions (http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc...) that make it easier for compilers to do more localized early binding even between top-level definitions.

Traditional BASICs I vaguely recall being closer to “fully” interpreted than this, but I haven't studied those enough to say—and I wouldn't expect that to apply to later BASIC revivals after a certain point.

An interesting other example would be Lua, which uses late binding semantics for global and method lookups, and then (here I'm thinking of the mainline PUC implementation) makes them faster by interning all strings at the C level, in a way which isn't exposed to the Lua level. When all strings with the same contents have the same pointer, string equality is very cheap, which makes table lookups over the string objects cheap. But lexical locals are compiled into index lookups, which are even cheaper, and it's often considered good practice to write internal file-level definitions as locals, import external module tables as locals, etc. so in practice once again some of the late binding disappears along the way.

What you say is all true.

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!

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?

Wikipedia:

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>

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.

Makes sense!

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

Also, there's an interview with McCarthy at https://www.infoq.com/interviews/Steele-Interviews-John-McCa... covering some of this time.

Some excellent information, to be sure!

For example, I never knew that IPL (Information Processing Language) existed prior to, and influenced (or probably influenced) LISP...

That IPL uses lists for computation is clear, and apparently IPL predates LISP by at least two years...

In reading the Wikipedia page on IPL (https://en.wikipedia.org/wiki/Information_Processing_Languag...), I found the following quote fascinating:

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

Anyway, thanks for the excellent links!

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.

Reply on news.ycombinator.com