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
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
TO into tokens, but also the
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.