Birth of BASIC (2014) [video]

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

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.