What type of interpreter were most 8-bit BASIC implementations?

Question

I’m a big fan of early/mid 1980s personal computers like the Amstrad CPC, Commodore 64 and the Sinclair Spectrum. One thing these computers all had was a version of BASIC. Well known ones being MS-BASIC, Locomotive BASIC, etc.

As a language hacker myself I’m curious: were these interpreters implemented as tree-walker interpreters (simply traversing the parse tree) or bytecode interpreters? I can’t find a lot of information on how they were implemented. It’s fascinating to me how they were built given the limitations of the hardware at the time.

Answer 1

[W]ere these interpreters implemented as tree-walker interpreters or bytecode interpreters?

Neither, or both. They are kind of source code interpreters - much like (classic) shell scripts - except they used a tokenized storage format (*1). Their structure was dictated by balancing lack of memory, lack of interpreter code and desired optimization for speed (*2,3)

Almost all (*4) were simple two-part systems consisting of

1. an editor to fetch a line entered, parse it into tokens (*5) and store it, as line structure, at its desired position (*6) and
2. an interpreter swinging along the tokenized program when executed.

So in modern terms it's like a combination of shell, editor and lexer for part 1 while part 2 combines parser and evaluator.

So, categorized by today's standards, they are somewhat like byte code interpreters - except, byte code implies usually some kind of virtual machine (*7), which isn't the case for back then interpreters, as the code used is literally translated BASIC source text.

Keep in mind, memory was scary rare. There is no room to store a source code and some byte code. Even less parsing trees or other fancy constructions. There was only room for one representation, which must be able to be put back into a readable text without any difference (*8) to the statements entered.

---

I can’t find a lot of information on how they were implemented.

They are quite well documented and information is to be found all over the web. But note that such documentation may use terminology that has changed since back then - or leave out information that was considered well known to everyone - like the very basic process of how they worked. It was so ubiquitously used that no further explanation seems to be needed. It's almost as if reading a book from another century. Interesting, isn't it?

---

*1 - The use of the term token differs a bit from today's usage (as pointed out later) and is tied to a way more basic concept to save on storage and simplify interpretation compared to an interpreter running over full source.

While most contemporary documents usually call it tokenization, comments in the original 8080 Microsoft BASIC source, rather call the process crunching. That part was, BTW, written by Paul Allen, as part of what they called 'non-runtime' functions, e.g. Line insertion, line editing, NEW, RUN, LIST, etc.

*2 - Most differences between BASIC interpreters are based thereon, especially with their optimization in tokenization and data storage - which are of course needed to fit more (or better) code into ROM.

*3 - There are almost endless variations in detail across BASIC implementations. Mentioning these would go way overboard for an explanation. If there is anything you need to know for a specific BASIC/solution, please feel invited to write up separate questions regarding them.

*4 - Well, with the exception of Dartmouth BASIC and Tiny BASIC that is. Both did interpret the otherwise unprepared source code text.

*5 - These tokens are always single-byte values - not strings or token-name/token-value pairs like with modern parsers. Data is usually represented as itself in ASCII (Sinclair being quite different here).

*6 - Or hand it to (direct) interpretation if not preceded by a line number.

*7 - Well, unless we take BASIC as the machine code of this virtual CPU. But that's quite far-fetched, isn't it?

*8 - Beside formatting that is.

Answer 2

The Sinclair systems were tokenised directly at the keyboard, so there was almost no lexical analysis. Keys were inputs to a state machine that implemented the BASIC language structure in a ROM table.

The first keystroke would have a label on it -- maybe the P key was also labelled Print, G was Goto, and the L key was Let. After that was hit, the state machine went to "expecting variable name" or "label" or whatever the syntax called for.

State machine contents included "what do I do with this value" and "what state do I got to next".

Some of the byte codes were off the wall. For example, the keystrokes also coded into strings directly, to give the words Let, Print, Goto. The "newline" was chosen to be the same as an interrupt instruction (far as i recall) so that the line display would wake up the z80, which is why the ZX80 flickered on every keystroke.

Answer 3

Most early 8-bit personal computer Basic interpreters were tokenized recursive descent interpreters. Tokenized to reduce the size of the program text, as well as speed up the interpreter by not have to parse text at runtime, and runtime recursive descent, trading off stack space usage versus having to build a parse tree in memory beforehand. Very few (if any?) built any sort of parse tree, or generated bytecodes for a run-time VM.

Also, the Basic programs as saved on disk were saved in tokenized form to reduce disk storage use.

You can detect tokenization in some interpreters from the fact that the LIST listing of program text is slightly different from the input text in formatting, as the output is re-generated from tokens on the fly, and the original text formatting information was not saved in the token record.

Most implementations used 8-bit tokens (much smaller than uncompressed ASCII keywords), but IIRC Woz further compressed the tokens down to 6 bits for Apple I integer Basic. Many of the Tiny Basic's (Palo Alto, et.al.) did not tokenize, thus trading off larger Basic program text size (full ASCII text in memory), versus smaller interpreter code size (no separate token table and token decoder needed).

Answer 4

were these interpreters implemented as tree-walker interpreters (simply traversing the parse tree) or bytecode interpreters?

I have been looking at various BASICs for the last while. The answer is "all of the above".

Pure interpreters - Tiny BASIC

TinyBASIC parsed the line to the extent of converting the line number to an 8-bit value to see if the line already existed. If it did, it put it in the proper place and then stored the rest of the line behind it, unchanged in its original text form. Lines were separated by carriage returns, which is nice. You can read a discussion of the storage strategy on page 11 of the volume 1 collection.

The goal of Tiny BASIC was to be as small as possible. Machines of the era often shipped with only 4k of RAM, which had to fit both the interpreter AND the user's program. As such, there was so little room left over that a single byte for the line number was not a real limitation.

So this means that the interpreter has to re-parse every line during run-time. It used a simple recursive descent system for this. As it parsed the line it converted the resulting tokens into an abstract syntax tree in the intermediary language and then ran the resulting AST through the IL interpreter.

Other versions of the language, notably Palo Alto TB, replaced the last step with one that ran the AST directly in assembly. This made the evaluation run much faster, although it still had the same overhead of parsing the line repeatedly.

Semi-tokenized - MS

UPDATE: I found a good description of CB so I've made some edits.

Next up is the MS series, as typified (numerically if no other way) by Commodore BASIC. It started off like TB in that it would convert the line number from ASCII to binary, but in this case used a 16-bit value. It then continued scanning the line, converting keywords like PRINT and FOR into single-byte tokens. Everything else, variable names, numbers and strings, it left as-in in the code. To indicate that a given byte was a token vs. data, they set the high bit, meaning that you only had a total of 128 possible tokens.

At runtime, anything with the high bit triggered a jump through a vector table into the parser for that function. For instance, the FOR code would begin reading the following data to parse out the I=1 TO 10. Because this was performance-critical, this code was placed in the zero page in the 6502, and I assume similar places on other CPUs.

Note that when it sees a variable it has to go look it up in a table. That table had two bytes of name, so that's why variables were only two letters long (you could type more, but they did nothing). Likewise, numbers were in ASCII format, so it had to convert them - over and over - into the 40-bit internal format to put it on the evaluation stack.

Fully tokenized - Atari

Finally, we come to Atari BASIC. AB tokenized everything, not just the statements. So in the case of FOR I=1 TO 10 it would not only convert the FOR and TO into tokens, but also the 1 and 10 would be converted from ASCII to the 40-bit internal format right then. Likewise, the I variable had space set aside for it and its index in the table became its token, with the high-bit set to indicate this.

So in AB, a simple line like this:

10 PRINT "HELLO WORLD"

would result in something like

0A 0F 00 20 0F 0B HELLO WORLD 13

The 0F indicates a string literal follows 0B long, 13 is EOL. I'm going by memory here so always compare to De Re Atari.

At runtime, there's nothing to convert or look up. The variable is an index pointing to its value so it's one operation to put its value onto the stack, the 1 and 10 are already converted so you just copy them onto the stack, etc. In theory, you can see that this should run much faster than either MS or TB, and this was indeed the case for some BASICs like BASIC09, that used this strategy. However, AB managed to throw this out the window with some truly horrible code in places that made it one of the slowest BASICs ever.

Upsides and downsides: most programs are small, so line numbers generally might be 3 chars on average. In AB these get expanded to 40 bits, whereas in MS they remain 3 bytes. So AB will take up more room for the same program in some cases. On the other hand, large numbers become smaller, 1.23456E-17 goes from 88 bits to 40 on AB. Other things are pretty much the same, so I am very curious which is ultimately smaller. I suspect MS would be smaller on average simply because of the small-number rule.

With a little extra work one could have a second numeric constant type for small numbers, using a single byte to store two BDC digits. During the tokenization you start by assuming it's small and only change to the long token if need be. That would encode something like 75% of all numbers found in actual programs and expand the number only one byte (the token header) in the case of single-digit numbers.

So you can see there are a range of solutions and all of them were used in production systems.

Answer 5

Dartmouth Basic wasn't an interpreter at all — it compiled directly into machine code when the user typed RUN. It was designed so that the program appeared to start executing almost immediately, and there were a number of tricks that made this possible.

1. Speed of compilation was a design criterion. The compiler only needed a single pass over the input, and did almost no optimization.

2. The compiler and the standard runtime library were generated at the same time and had matched versions, so the compiler knew where in memory the called library routines would be. This meant that no separate linker was needed for the standard library.

3. The command shell (it wasn't called that, but I'll use the Unix/Linux name for clarity) printed out a header (the program name and current date/time) before running the program. At 10 char/sec, this took about 3 seconds, so any compilation < 3 seconds appeared "instantaneous".

Answer 6

Microsoft BASICs did very minimal tokenization. Keywords were replaced by their one-byte tokens (except in later versions with so many keywords that some required two bytes), but everything else was left alone. Even numeric literals weren't parsed into the way they lived in memory in variables, but were left as sequences of ASCII (or PETSCII or whatever) digits, which led to plenty of speedup tricks like using π or . (which parsed as 0 but faster). Formatting was also preserved, other than leading whitespace on a line (an initial colon was helpful if you wanted indentation). Literal strings were referenced directly from the source code (using copy-on-write, so changes to the string variables later didn't overwrite the source).