3 ms·
maybe also worth mentioning is that lisp was commonly stored as s-expressions instead of plain text, for example in interlisp and i think its predecessor bbn li
by kragen 3y ago
maybe also worth mentioning is that lisp was commonly stored as s-expressions instead of plain text, for example in interlisp and i think its predecessor bbn lisp; this is a practical representation for direct interpretation and one that they did in fact use, but even on a 16-bit machine it lacked the great compression of forth indirect threaded code or tokenized basic
Consider this Lisp program, which will run in SBCL or Emacs Lisp today
and I think in virtually any LISP of the 01960s and 70s:
123456789 123456789 123456789 123456789 123456789 1
(DEFUN FACT (N) (IF (< N 2) 1 (* N (FACT (1- N)))))
0 1 23 45 67 8 9 a bc d ef gh i
That’s 51 characters long; in a SIXBIT code it would be 306 bits,
while on a machine using one 8-bit byte per character, it’s 408 bits.
The letters below are base-36 indices into a list structure made out
of 19 conses:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| CAR | DEFUN | FACT | 3 | N | 5 | IF | 7 | < | N | #2 |
| CDR | 1 | 2 | 4 | NIL | NIL | 6 | a | 8 | 9 | NIL |
| | a | b | c | d | e | f | g | h | i |
| CAR | #1 | c | * | N | f | FACT | h | 1- | N |
| CDR | b | NIL | d | e | NIL | g | NIL | i | NIL |
Some of these pointers are tagged integers (marked as `#` here), some
point to interned symbols (the capital letters), and some point to
other conses. On a 36-bit machine like a PDP-6 or PDP-10 each cons
would be a 36-bit word, so 19 conses would occupy 684 bits. On a
16-bit machine like a PDP-11 or a NOVA each cons would be two 16-bit
words, so 19 conses would occupy 608 bits. It's fairly easy to write
an interpreter that just directly walks this list structure, and it
was commonly done in the 01960s and 01970s, but it’s kind of slow.
In theory this kind of thing can give you source code compression,
because you don’t need to store long symbol names every time you use
them; most symbols are already defined before you load your program
and therefore don't occupy any space at all. But usually the list
structure occupies more memory than the source text, rather than less.
In this case you can see that the expansion is by a factor from 1.49
to 2.24, depending on the implementation in question.
Forth does better; here’s a Forth implementation of the same
algorithm:
123456789 123456789 123456789 123456789 123456789 123
: fact dup 2 < if drop 1 else dup 1- recurse * then ;
It’s virtually the same amount of code, 53 bytes instead of 51; in a
classic 16-bit indirect threaded Forth, the colon definition might
look something like this:
| 0 | 4 F | Length, flags, first letter |
| 1 | A C | other two letters |
| 2 | DOCOL | cfa to interpret this definition |
| 3 | DUP | pointer to the primitive |
| 4 | (2) | pointer to a subroutine pushing 2 |
| 5 | < | another primitive pointer |
| 6 | (IF) | conditional jump if nonzero |
| 7 | 12 | jump destination |
| 8 | DROP | more pointers to definitions |
| 9 | (1) | |
| 10 | (ELSE) | unconditional jump |
| 11 | 16 | jump destination |
| 12 | DUP | more pointers to definitions |
| 13 | 1- | |
| 14 | FACT | |
| 15 | * | |
| 16 | EXIT | pointer to subroutine-exiting primitive |
So this works out to be 17 Forth cells, including the two-cell header
and the one-cell cfa, which is 272 bits on a 16-bit Forth. This is
not only smaller than the LISP list structure, it’s considerably
smaller than the source code, which is 424 bits on an 8-bit-byte
machine, but you can reconstitute a reasonable simulacrum of the
source code from it (try typing SEE FACT to GForth after entering the
above definition). It’s also considerably faster to interpret.
This is fairly similar to a bytecode interpreter, the way Smalltalk
since at least Smalltalk-76 are implemented, not to mention many Lisps
like Emacs Lisp and its imitator Python. But Smalltalk bytecode
wasn’t the first stack-oriented bytecode; those go back to probably
the 01950s. Unix `bc` was implemented by compiling its C-like input
language to a human-readable bytecode that could be interpreted by the
`dc` arbitrary-precision calculator program, Unix’s first real
application. Pascal was commonly explained by reference to a bytecode
interpreter for a similar stack bytecode, as was Wirth and Weber’s
Euler in 01965, though I'm not certain whether they abstained from the
final step of compiling Euler’s bytecode to Burroughs 5500 machine
code. Ken Thompson’s implementation of his `B` language, the
predecessor to C, similarly interpreted a stack-oriented bytecode,
using a machine-code interpreter copied into the executable along with
the bytecode.
The differences between
such a bytecode and Forth indirect threaded code are small:
1. Like pointers in Lisp list structure, the items in the “bytecode”
were direct pointers to what they referred to, rather than indices
into a tiny table; this reduced the time overhead of
interpretation.
2. That meant that the items in the “bytecode” were bigger, typically
16 bits instead of 8, so the same amount of code would generally
require more space unless it consisted almost entirely of
subroutine calls, as Forth code does. Bytecodes like Smalltalk and
Emacs Lisp bytecode typically allocate much of the bytecode space
to common primitive subroutines like `car` and `+`.
Chuck Moore’s first Forths, like the one he documented in the
“Problem-Oriented Language” article, didn’t use indirect threaded code
this way; they were text interpreters like Bash. But he switched over
to the threaded-code approach sometime in the 01970s. Did he invent
it? I’m not sure. [Wikipedia doesn’t know][0].
[0]: https://en.wikipedia.org/wiki/Threaded_code#History https://en.wikipedia.org/wiki/Threaded_code#History
But it should be apparent that, when Gates, Allen, and Davidoff were
writing BASIC-80 in 01975, bytecode was already a well-established
technique; they didn’t have to invent it. As far as I know, though,
the BASIC tokenization approach they used, where as I understand it
the bytecode tokens were in the same order as the BASIC source
language, was new.