26

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.

  • 5
    Check out the Atari BASIC Source Book (archive.org/details/ataribooks-the-atari-basic-source-book). It was written by the language authors and includes a walk-through of the design and a complete assembly listing. – Jim Nelson Nov 19 at 1:51
  • 1
    The Toolkit BASIC book on the C64 and VIC20 from Compute! (now at archive.org/details/… has some detailed chapters on the tokenization, statement evaluation, variable storage, and expression handling. – Joe Nov 19 at 4:15
  • 4
    Memory usage was really a premium. For instance the VIC-20 only had 5 Kb RAM. – Thorbjørn Ravn Andersen Nov 19 at 20:29
  • 2
    It's telling that we used to avoid comments and spaces as much as we could to improve run times and save memory. We also used really short variable names to save space and time (the ones I know had only two significant characters, anyway). – Fred Larson Nov 19 at 20:50
  • Limitations included being able to fit in 4k to 16k of memory, editor, interpreter, plus program text. – hotpaw2 Nov 20 at 20:16
43

[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 tokenised 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, categorised 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 literal 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 how they worked. It was so ubiquitously used that no further explanation seams 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 todays 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 tokenisation and data storage - which are of course needed to fit more more (or better) code into ROM.

*3 - There are almost endless variations in detail across BASIC implementations. Mentioning these would go way overboard for a 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.

  • 13
    Because numbers in ZX-81 Basic were stored in 6 bytes (iirc), while tokens like PI were only one byte, the programs were laced with gems like NOT PI (instead of 0), PI/PI (instead of 1) or $STR("42") (instead of 42). – Edheldil Nov 19 at 11:52
  • 2
    @Edheldil Jup, check here for more details. There are endless variations across all 8 bit BASICs. – Raffzahn Nov 19 at 14:21
  • 1
    @Edheldil SGN PI is the shortest code for 1 in ZX Basic, and I think you mean VAL "42". – Neil Nov 19 at 16:38
  • 3
    @RonJohn Not really. Tokens represent a source text element, while byte code is an instruction. While in practical use it may be a blurry line, and intheory some could argue here on a quite high level about similarities, the semantics are quite different. – Raffzahn Nov 19 at 20:55
  • 1
    @Edheldil, that made me wonder why they didn't also have tokens for one and zero, but then I suppose the token namespace might have been scarce too... – ilkkachu Nov 20 at 8:44
18

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.

  • 8
    Having cut my teeth on ZX Spectrum Basic (at age 10), I got used to a single keystroke generating an entire keyword (PRINT, longest was RANDOMIZE). When I moved to other "normal" implementations, It would seem quite strange and wasteful that I'd have to actually type PRINT, and then have the computer parse that back... – Jonathan Nov 19 at 15:01
  • 5
    The ZX80 and ZX81 use the HALT opcode as newline because the program counter is reused as a display counter (thanks to some external subterfuge) and HALT therefore allows for a compact display — white space to the right isn't stored in memory. The ZX80 flickers upon keypresses because the processor momentarily stops doing that and does some processing instead. I've no idea what carried over in the Spectrum, but it is a direct code descendant so it wouldn't be surprising if the opcode for HALT were still end-of-line despite the entirely different video display. – Tommy Nov 19 at 15:35
  • @Tommy The Spectrum had a fixed size graphical display buffer so it didn't need newlines. – Neil Nov 19 at 16:40
  • @Neil RST $10 in the Spectrum ROM uses and understands newlines. Thankfully. – Rui F Ribeiro Nov 20 at 2:29
16

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 the 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).

  • Thank you for this. Really helpful. – Garry Pettet Nov 20 at 21:10
15

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.

  • Thanks for this. Fabulous info! – Garry Pettet Nov 20 at 21:10
  • QL BASIC operated similarly, with variables being tokenized into references to a variable table, making it important to get the casing right in a variable name the first time that one entered it, as that would be the spelling in all occurrences in the program entered thereafter. – JdeBP Nov 28 at 19:09
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".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.