For a retro boot-to-basic computer, I’d need an actual Basic interpreter. My first idea was to just grab an open-source implementation online somewhere and just port it over to my system, rather than reinvent the wheel myself. There had to be something suitable out there already, right?
After a bit of searching, I decided to use Tony Wang’s MY-BASIC. This seemed idea –lightweight, packaged in a single code and header file, and easy to expand with hardware-specific commands. I copied it into my project, ported it over to deal with the idiosyncrasies of the MPLAB compiler, and added a handful of commands to make it work with the USB keyboard and text display. The trickiest part was converting it into a retro style line number dependent Basic instead of its more modern structured text style.
This seemed to work great at first. I tried a few simple “Hello World” programs, and then coded a simple text mode Game of Life engine as a demo. This ran, but it was a lot slower than I expected, taking several seconds to calculate a single frame of the simulation. Well, that’s to be expected, I thought. Interpreted basic is slow, even on a modern 32 bit 200mhz CPU.
The real problem came when I tried to write more complex programs. When I got to about 100 lines of code, the interpreter ran out of memory and crashed, even though most of the MCU’s 512KB of memory was set aside for it.
It turned out that MY-BASIC is just not very memory-efficient. From looking through the code, there’s a lot of overhead to everything it does. It’s just not all that well optimized for microcontrollers with limited memory space like the one I was using.
I looked at a few other options, but ultimately decided that I’d have to code my own Basic interpreter. One that was optimized for a lightweight memory footprint and high speed. It would turn out to be be my own unique dialog of Basic, as I looked at Commodore and Microsoft Basic for guidance but ended up reworking a few aspects of the language as I saw fit.
The main guideline of my Basic interpreter would be to pre-calculate everything as much as possible. I was inspired by the tokenization pass that was performed by the Basic interpreter on Commodore machines, as well as the way that Python interpreters pre-process scripts into an easier to execute form. My Basic interpreter would scan every line of the program, first tokenizing them, and then processing them into a simple stack-orientated byte code, which would be what the actual execution process then ran.
The first step taken after the user types the RUN command, is actually to save the user’s entered program onto the attached SD card, clearing the memory space that would be taken up by the raw text. That file is then read back a line at a time, each line being processed by the tokenizer and parser.
The tokenizer skims through each line, and breaks it down into a list of tokens. This is the part of the code that recognizes commands and functions, creates variable names and allocates space for variables as needed, and also recognizes strings and data and places those in specialized memory spaces.
For example, the Basic line:
b = 2*a*b+cbwill be broken down into the following list of tokens:
[Index of variable b] [Assignment] [Integer 2] [Multiply operator] [Index of variable a] [Multiply operator] [Index of variable b] [Addition operator] [Index of variable cb]
Each token is a 32 bit value, broken up into individual fields that can indicate token type (such as operator, variable, syntax, etc) and type within that token (such as type of operator, index of the variable, etc.). There is some complex logic in the tokenizer to distinguish different uses of syntax characters like equals signs and parentheses. The tokenizer will also catch many basic syntax errors and halt the process with an error message.
After tokenizing, the list of tokens is handed to the parser. This code takes the list of tokens and converts it into a list of commands, which will be run by a virtual machine during runtime. This command language was chosen to be run as fast as I can get it to run, and also to take up minimal space in memory. Each command in the command list is a 32 bit value, which can have additional data for immediate parameters stored as part of the 32 bit command. Commands can also be followed by physical addresses in memory, as during the parsing process the addresses of variables, procedures, and operators are looked up and stored directly in the command list.
Our previous Basic line, after going through the tokenizer and parser, will result in the following command list:
[Push variable contents to stack] [Address of variable a]
[Operation with immediate value 2] [Address of multiplication operator]
[Push variable contents to stack] [Address of variable b]
[Operation on top two values of stack] [Address of multiplication operator]
[Push variable contents to stack] [Address of variable ab]
[Operation on top two values of stack] [Address of addition operator]
[Pop top of stack to variable] [Address of variable b]
This list of 14 instructions takes up 56 bytes. This is admittedly more than the 12 bytes of the raw Basic text, but it is much faster to execute than parsing the Basic itself every time that line needs to be run.
As an additional optimization, there is a final sweep through the code that identifies GOTO and GOSUB statements and replaces the associated line number with the address of that line in memory. This eliminated the need to search through the program list for the actual address every time a GOTO or GOSUB is encountered, although there still needs to be that capability for jumping to a line number that’s calculated at runtime.
The resulting Basic interpreter is fast, running my Game of Life demo about 30 times faster than Tony Wang’s MY-BASIC. And it’s much more memory-efficient, I’ve written programs over 600 lines long without getting close to the memory limitations. I’d call it a success, for a part of the project that I never intended to develop from the start it’s working really well.
The source code for the project can be found here.
No comments:
Post a Comment