Birth of BASIC (2014) [video](youtube.com)
youtube.com
Birth of BASIC (2014) [video]
https://www.youtube.com/watch?v=WYPNjSoDrqw
11 comments
Here are my curiosities about BASIC history.
* When did the MS style tokenized, interpreted BASIC start?
By this I mean, in MS BASIC, you have tokens that are evaluated. You enter text, the system tokenizes it, then when you run it, the interpreter does a combination of parsing and executing the tokens. It also reconstructs the program listing from the tokenized form. Curious what the origin of this style of BASIC was. Gate et al were clever, but I don't think they were that clever. I think this was borrowed from something else.
* Why was the original BASIC-PLUS from DEC done the way it was?
Unlike MS BASIC, B+ was compiled into an intermediate code (a stack machine as I understand it), and then executed. But this was done incrementally. As lines were entered, they were compiled, and put into place within the overall program. The original source was retained for editing, so you inevitably had two copies of the program: the source, and the compiled code, which isn't particularly efficient on the small machines of the day, but it ostensibly executed faster.
You could "compile" B+, but that was more saving the runtime image to disk, without source code.
* When did the MS style tokenized, interpreted BASIC start?
By this I mean, in MS BASIC, you have tokens that are evaluated. You enter text, the system tokenizes it, then when you run it, the interpreter does a combination of parsing and executing the tokens. It also reconstructs the program listing from the tokenized form. Curious what the origin of this style of BASIC was. Gate et al were clever, but I don't think they were that clever. I think this was borrowed from something else.
* Why was the original BASIC-PLUS from DEC done the way it was?
Unlike MS BASIC, B+ was compiled into an intermediate code (a stack machine as I understand it), and then executed. But this was done incrementally. As lines were entered, they were compiled, and put into place within the overall program. The original source was retained for editing, so you inevitably had two copies of the program: the source, and the compiled code, which isn't particularly efficient on the small machines of the day, but it ostensibly executed faster.
You could "compile" B+, but that was more saving the runtime image to disk, without source code.
All my research seems to indicate that tokenizing BASIC code on input was first done for Altair BASIC written by Gates and Allen. I'm not sure why you think they wouldn't be clever enough to come up with it. It's probably the only way one could get BASIC to work in the 4K of RAM available on the Altair.
At the time, while there was a lot of developing theory around string parsing and tokenization, a lot of the formal theory being crafted led to impractical implementations. At the same time, interactive coding was relatively new: a lot of systems were still using punchcards. I think this combination of constraints is why you would see things like the IBM 63-pass Fortran compiler[0]. But at the same time, Chuck Moore was working on Forth systems and had the sense to go in the direction of tokenization at input time, so I would point to him as one of the originators of the style.
[0] https://retrocomputingforum.com/t/ibms-63-pass-fortran-compi...
[0] https://retrocomputingforum.com/t/ibms-63-pass-fortran-compi...
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:
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:
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.
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
| | 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 |
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 ;
| 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 |
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.
I actually wrote a rudimentary BASIC interpreter in Scheme that does something like the latter. I invented a BASIC "abstract machine" that could interpret BASIC lines as tree structures. Then when the user typed in program source, the interpreter would parse it, turn it into a BASIC line data structure, and insert it in the proper place in the program. A logical extension which I did not implement is to keep the source of each line (so LIST and SAVE work, for instance).
It's a neat, sensical way to implement BASIC if you have the memory to spare. Crunching everything through tokenization and interpreting the tokens directly makes more sense if you're on an 8-bit, 4k machine however.
It's a neat, sensical way to implement BASIC if you have the memory to spare. Crunching everything through tokenization and interpreting the tokens directly makes more sense if you're on an 8-bit, 4k machine however.
Related:
Birth of BASIC (2014) [video] - https://news.ycombinator.com/item?id=23830201 - July 2020 (36 comments)
Birth of BASIC (2014) [video] - https://news.ycombinator.com/item?id=23830201 - July 2020 (36 comments)
They emphasize several times that “this was all before Bill Gates”.
The REPL always compiled into native code before execution.
Interpreters only came later with the adoption on 8 bit computers, which naturally didn't had the hardware resources for that.