Forty Years of Personal Computing - "Compilative" BASIC Interpreter

Notebook containing the BASIC
interpreter source code

In June of 1977, Kilobaud (later Kilobaud Microcomputing and still later Microcomputing) magazine published an article by Tom Rugg and Phil Feldman entitled "BASIC Timing Comparisons"(page 66). A few months later, they revised this article in the October 1977 issue, with a follow up "BASIC Timing Comparisons - Revised and Updated" (page 20).

In the late 1970s, there weren't many computer languages available for small computer use. One either wrote BASIC or assembly language programs. Microsoft got their start this way --  selling BASIC interpreters to a variety of small computer manufacturers.

Assembly language is difficult. Having a high-level language, even one as, well, basic as BASIC made programming more accessible. I used Robert Uterwyk's 8K BASIC interpreter, sold as SWTPc 8K BASIC. When the Kilobaud articles came out, I was shocked to find the SWTPc 6800 Computer system ranked near the very bottom.

No way! The Motorola MC6800 was capable a spot near the top of the list, once you adjusted for relative clock speed -- a 2 MHz Z-80 or 8080 is equivalent to a 1 MHz 6800 or 6502. Something wasn't right. The problem wasn't the machine, it was the software.

The Problem(s)

My experience with SWTPc 8K BASIC showed there were three issues. First, it did no syntax checking on entry. This told me statements weren't parsed until the program was run. Second, each line had to be re-parsed during execution, which slowed things down further. The third wasn't really a bug. All the other BASIC interpreters used 32-bit floating point numbers for their calculations. SWTPc 8K BASIC floating point numbers used Binary Code Decimal (BCD), and supported nine-digits of precision and exponents of plus or minus 99. These numbers took six bytes to store, and many more instructions to calculate, but covered a larger numeric range and precision.

Math Routines

I decided I would write a BASIC interpreter. I started with math routines. My floating point format was straightforward. One byte was the exponent, and the next four bytes were the mantissa. Both were two's complement binary numbers. I worked on these routines hard, and manage to test them to the point I believed they were complete. 

The math routines used a sixteen level expression stack, all in page zero. The bottom of the stack held the X and Y registers -- where all math operations took place. This meant the basic math operations where coded directly on X and Y using zero-page addressing modes -- which was very fast. In retrospect, this meant a lot of shuffling values around in memory. Given the MC6800's lack of registers, perhaps this was a reasonable choice. 

Science Fair Project

At some point, this became a science fair project that got me to the International Science and Engineering Fair (ISEF) in San Antonio, TX. I'll tell that side of the story in a separate article.

The Interpreter

Flowchart of edit / command
mode

With the math routines in place, I focused on the editor/interpreter. 

My editor parsed input on entry, storing keywords with one-byte tokens, where the high bit was set. This took less memory to store, plus it was faster to interpret. For this reason, I dubbed it a "compilative" interpreter -- due to the pre-parsed statements in memory.

I had decided my BASIC would replace SWTPc BASIC. It would support the same statements, functions and language. From the start, I allotted for every statement, function, and expression.

I continued to work on the interpreter in the spring, even as I was showing my exhibit at various science fairs. I was nowhere near done. 

My style of working in those days was simple. I hand-wrote assembly language in notebooks, later typing it into the computer to build. Then I would write out the source and object to cassette tape. My terminal had only 16 lines, so hard copy in a notebook was easier to study. It also allowed me to write code when I wasn't at my computer -- like when I was at school. 

The project grew a lot, and the source exceeded the capacity of my small system. There was more code than would fit in my 20 KB system with the co-resident assembler/editor loaded. I worked on it in sections.

As things moved faster, my coding sessions got longer and longer into the evening. Then, one evening, I screwed up. I had just finished a programming session, and went to write the source out to cassette tape. But I had the wrong tape in the cassette recorder. I over-write dozens of hours of work. I didn't have time to re-do this work, and ended up going to the ISEF with an incomplete project. 

My code had run into a problem in any case. I made clever use of tables to deal with different aspects of parsing. I used three different tables for different situations. The tables had grown to the point where the code exceeded 8 KB. By the time of my late-night coding accident, I had decided to consolidate the three parsing tables into one large one, which should have solved some of the memory problems.

Looking Back

"Compilative" Interpreter 

After the ISEF, I never took up the project again. I was dismayed at losing work, plus I was busy that summer -- a trip to Spain, and getting ready for college. 

Writing a BASIC interpreter was a huge project. After forty years as a software development professional, it's clear I'd gone about this all wrong. My strategy was to build all the components of a full-fledged BASIC -- math routines, transcendental functions, editor, parser, execution, variable handling, and then stick them all together into a working program. I had a lot of pieces, but very little of it was actually working.

In retrospect, I should have started small -- focus on a simple subset of BASIC and gotten that working. Then incrementally add features to it. This would result in a working solution sooner. Plus, I would have had something to exhibit. I'd learn this later, with experience.

In this alternate path, at some point there would have been enough of an interpreter to run the Kilobaud timing programs. Once I could measure what performance was like, I would know if my solutions would work, or if it needed something more clever. 

Even so, I'm impressed with how much I wrote. Looking back at the two hundred notebook pages of assembly code and notes I've kept, there's much I'd forgotten I'd written. 

Epilogue

I wasn't the only one to react to those Kilobaud articles. Technical Systems Consultants (TSC) read them as well. TSC had a Micro BASIC Plus product in 1976 - a BASIC that fit in 3 KB. It supported integer arithmetic only, and no string operations. 

TSC developed a full-featured 8 KB BASIC for the MC6800. When they delivered it in March/April of 1979, it outperformed everything else on the market -- including Microsoft BASIC. 

This was about the same time as my late-night programming sessions. Had I only known.