4 ms·

Birth of BASIC (2014) [video]

63 points by nyc111 3y ago

nliang86 3y ago
https://www.videogist.co/videos/birth-of-basic-1720 https://www.videogist.co/videos/birth-of-basic-1720
pjmlp 3y ago
One interesting thing about original BASIC, is that it was JIT compiled. 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.
nyc111 3y ago
They emphasize several times that “this was all before Bill Gates”.
whartung 3y ago
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.
- wvenable 3y ago
  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.
- crq-yml 3y ago
  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-compiler/557 https://retrocomputingforum.com/t/ibms-63-pass-fortran-compi...
  - 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.
lucb1e 3y ago
BASIC should be uppercased in the title, then everyone will instantly get the subject of the video and that's also the title used by the submission
- dang 3y ago
  Fixed now. Thanks!
dang 3y ago
Related: Birth of BASIC (2014) [video] - https://news.ycombinator.com/item?id=23830201 https://news.ycombinator.com/item?id=23830201 - July 2020 (36 comments)

63 points by nyc111 3y ago

https://www.videogist.co/videos/birth-of-basic-1720 https://www.videogist.co/videos/birth-of-basic-1720

One interesting thing about original BASIC, is that it was JIT compiled. 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.

nyc111 3y ago

They emphasize several times that “this was all before Bill Gates”.

whartung 3y ago

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.

wvenable 3y ago
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.
crq-yml 3y ago
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-compiler/557 https://retrocomputingforum.com/t/ibms-63-pass-fortran-compi...
- 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.

lucb1e 3y ago

BASIC should be uppercased in the title, then everyone will instantly get the subject of the video and that's also the title used by the submission

dang 3y ago
Fixed now. Thanks!

dang 3y ago

Related: Birth of BASIC (2014) [video] - https://news.ycombinator.com/item?id=23830201 https://news.ycombinator.com/item?id=23830201 - July 2020 (36 comments)