My history with Forth and stack machines (2010)
yosefk.com
yosefk.com
By day, I'm an FPGA coder. (The ASIC situation rhymes, more or less.) From the perspective of implementing small CPU architectures: register files are not the problem in the way you'd expect. A modern FPGA has primitives that implement 32- or 64-register files with remarkable efficiency, in 2-, 4-, or 8-port varieties. Midrange FPGAs are now fast enough that a lightly pipelined RISC CPU performs well enough; there's no need to aggressively pipeline a CPU for normal clock rates (100 to 250 MHz) any more, and little motivation for exotic architectures. The MicroBlaze (Xilinx) or NIOS-II (Altera) soft core CPUs are so boringly effective they've forced ARM to license their designs for FPGAs for free. For smaller state-machine-class problems, the PicoBlaze is an interesting, minimal RISC. For most of us, CPUs are solved problems and the frontier has shifted towards cache-coherency, networking and other more interesting arenas.
I love the idea of stack machines in the right contexts (PostScript, FORTH, Java, you name it), but it's hard to disagree with the essay's conclusions.
For anyone who isn't familiar with the language, Thinking Forth[1] and Starting Forth[2] are (as far as I know) well-regarded books on the subject.
[1]: http://thinking-forth.sourceforge.net
[2]: https://www.forth.com/starting-forth/
Also, for anyone like me who dearly misses W. Richard Stevens, he wrote a Forth primer in the 70s. You can find it any several other documents on forth.org[3].
[3]: http://forth.org/tutorials.html
Previous discussions of this post over the years:
https://news.ycombinator.com/item?id=3963896
https://news.ycombinator.com/item?id=8146306
High level & easy: chat bots. I have implemented a forth interpreter in several bots I wrote (admins only, for obvious reasons ;). Since they are running within the bot's code, you have as much access to the client's state as you allow/implement.
https://re-factor.blogspot.com/
For example, here's a gopher server: https://re-factor.blogspot.com/2016/10/gopher-server.html
I wonder how much of the stack manipulation problem could be solved with say four register words A, B, C, D (and A!, B!, C!, and D!) that access registers understood not to be trashed by primitives (CODE words) but might be trashed by definitions (COLON words).
Otherwise, once you start trying to fix these problems, you end up with Scheme.
> being able to do what at least 3 people in their respective areas normally do, and concentrating on those 3 things at the same time. Doing the cross-layer global optimization.
I at least desire to be competent at that level, and think I'd enjoy having a go.
> Good Forth programmers arrange things so that they flow on the stack.
I think this concept of "flow" applies elsewhere, for example when creating tacit programs in J. But I haven't seen "flow" used like this anywhere except this article.
It is, isn't it?
Forth is sort of "the next level up" from assembler, in the language abstraction hierarchy...
First you have switches...
Then you have punched cards...
Then you have a simple assembler that converts files of numbers into machine code.
Then you have a simple assembler that converts files of instruction symbols (operands/mnemonics) and numbers into machine code.
From there, you might have assemblers that understand global variables and labels/addresses in memory (necessary for function calls), etc.
Forth starts to come into existence when you take a later (in evolution/time) assembler's symbol (aka "function name") address look-up table for functions -- and implement it dynamically (with the ability to add to it) at run-time.
That's because the initial Forth tokens/symbols (it's "primitives") -- are CALLs to static pre-defined assembler routines (or would have been in the first version of forth) -- with the ability to define new tokens/symbols -- in terms of combinations of executions the previous ones...
To make all of this magic happen, you need to separate the "CPU provided" single stack (well, at least if we're thinking Intel, which may have not been the case with early CPU's) -- into two stacks, one for data, one as a call (function return) stack, and this is exactly what Forth does.
Forth exposes the data stack to do whatever you want with, to you the programmer.
Now, when we get to Lisp (the next level up from Forth, in my opinion) -- Lisp does two additional things, which are
A) Takes the ability to monkey with any stack, away from the programmer.
B) Implements the management of LISTS -- whose management (memory management, pointers, etc.) the programmer no longer needs to worry about (think of this as a pattern from mathematics, N, that is, 'multiples', 'batches', 'vectors' ("more than one thing of") -- meets Forth's ability to work with single symbols -- well there has to be a convenient data structure to work with multiple symbols (and data, which now there is a demarcation of in LISP) at a time -- and that way LISP provides, with it's "I'll manage the stack and the lists (at least the memory/structure/pointers of the list) for you, so you the programmer don't need to worry about any of that!
So yes, Forth is brilliant and fascinating in its simplicity...
I wouldn't write million-line business applications in it, because as a programmer, I am not perfect, I make mistakes, and I tend to like type-checking, automatic stack management, and other things that modern compilers provide.
But Forth is utterly brilliant from a "how did Computer languages evolve" / "how could a computer 'pull itself up by its bootstraps' perspective"...
It's highly worthwhile for any programmer to learn about...
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...
: 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
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.
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 speculating without knowledge both about how early versions of Lisp worked and, I suspect, about how to teach an introductory CS class.
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 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.
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.
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!
Lisp then used a memory image which was loaded on startup (and possibly written on exit) - which contained the pre-interned symbols.
False for both Forth and Lisp — for Lisp since the beginning, for Forth since the early 1970s.