© 2009, Lyle Kopnicky
I began Vintage BASIC as a class project at the Oregon Graduate Institute. My aim was to demonstrate advanced knowledge of monads in Haskell. It occurred to me that BASIC's dynamic control structures would be interesting to interpret using a custom monad. Soon, using a continuation-passing style monad as a basic, I was able to construct an advanced form of exception handler that was ideal for implementing the BASIC control structures in a new way.
What follows are notes on a few of the more notable aspects of the design.
Most languages, like C,
have lexical control structures. It can be determined statically where
the boundaries of a loop lie. But BASIC's control flow statements are
read and interpreted one by one at runtime. Traditionally, a GOSUB pushes a pointer to the next statement onto the stack, and RETURN pops that pointer off the stack to return to that position. Any RETURN in the program could be associated with any GOSUB, if the right GOTOs are sprinkled about.
Instead of using the traditional stack-based method of implementing GOSUB-RETURN, I implemented GOSUB as an exception handler, and RETURN raises an exception to be caught by the GOSUB. Similarly, FOR is an exception handler, and NEXT raises a special exception to be caught by the FOR.
This is not too different from the stack-based approach, because a
pointer stack has been replaced by a handler stack. However, the code
is higher-level and more generalizable. It flows well in Haskell's
monadic do notation.
Simple Java-like exceptions
will not suffice. For one thing, they require a nested block of code
from which exceptions will be caught. But BASIC has no lexical nesting.
In principle, we want to catch exceptions that occur later in
execution. In other words, we want to catch exceptions from the
continuation of the handler. My new exception handlers can be used in
either way: to catch exceptions from within an expression, or to trap exceptions from the handler's continuation. I refer to it as trapping because it works much like a trap statement in Bourne shell.
There
are three actions an exception handler may take. In case an exception
does not apply to the exception handler, it needs to pass on the exception to the next outer handler. When a NEXT exception occurs, the loop termination condition may or may not be met. If it is not met, control flow will continue following the handler (the interior of the loop). If it is met, control should resume with the statement following the NEXT.
There is one more behavior of a handler to consider: whether or not it remains in force. When a NEXT leads to another loop iteration, the handler should remain in force. When the FOR loop is complete, the handler should not remain in force. I refer to this feature as durability and say that in the first case, the handler endures, while in the second case it does not endure.
The exception handlers provided in Control.Monad.CPST.DurableTraps, catchC and trap, are used to catch or trap exceptions, respectively. Each one is passed, along with the exception, three functions called passOn, resume, and continue, corresponding to the three desired courses of action. Each of those functions takes a boolean parameter endure, which can be set to True to keep the handler in force or False to remove it from the handler stack.
Although I originally hand-rolled a parser, I eventually moved to Parsec for better performance and error handling. I chose to implement the parsing in three layers. The line scanner layer recognizes BASIC line numbers and allows the lines to be sorted by line number without parsing the rest of the line. The tokenizer locates and tokenizes keywords in each line, without tokenizing variable names. I did this so that BASIC code could be written without spaces between the keywords and variables, as the Commodore 64 allowed. Finally, the parser does the rest of the work, building up statements and expressions.
I took care to make the syntax errors look reasonably old-fashioned. However, they do provide a bit more information than the old BASICs would have. Because Parsec provides it, they detail the error position and the found/expected tokens.
Vintage BASIC is extensively covered with unit tests. These tests are written on top of the HUnit framework. Most of the tests are on parsing code or the interpreter. The interpreter tests are at more or less integration tests rather than unit tests. They test the interpretation of the BASIC language straight from the textual source. However they are still unit tests in the sense that they are focused on exercising the behavior of the interpreter proper.
The tests are arranged in a hierarchical directory structure parallel to the implementation: in the test directory rather than src. They are executed by a harness called run_tests.hs in the root directory. This custom-written script finds all of the modules named ending in _test, and the functions within those modules starting with test_. It builds a driver program that calls all the tests, and executes it.
The tests can be run by calling runhaskell run_tests.hs, or preferably via runhaskell Setup.hs test.