Go with the flow: basic

For simplicity, our imple­men­ta­tion of BASIC will be a cut-down, ideal­ized version. It won’t contra­dict anything we might already know about how BASIC works. But it also won’t imple­ment all the features & details we’d need to run a serious BASIC game. (This tuto­rial could be the basis of a more thor­ough imple­men­ta­tion, however.)

Require­ments

Our version of BASIC will be able to run simple programs like this:

To do this, we need to imple­ment four state­ments:

We also have to observe a few more ground rules:

Of course, with goto, we can create infi­nite loops, so a program can also continue indef­i­nitely. Another side effect of goto is that not every line in a program will neces­sarily be executed.

Let’s step through our sample program and see how these rules play out:

Thus the full output is:

Design

We’ll use the same grammar-based approach to BASIC that we’ve used before. The reader for our language will use a tokenizer and parser to create a parse tree. In turn, this parse tree will be passed to the expander for our language, which will use a combi­na­tion of macros and func­tions to convert the parse tree into a working program.

The trick­iest part of BASIC will be imple­menting the logic of how the program is executed—what’s known as control flow.

First, let’s consider the lines. Each line of a BASIC program is iden­ti­fied by a unique line number, and contains a series of state­ments that needs to be avail­able to be executed on demand—perhaps once, multiple times, or never.

Sound familiar? As we did in wires, we’re going to model each line as a func­tion. So in pseudocode, our program above will be trans­formed into some­thing like this:

(Part of the pseudo- here is that numbers can’t be actu­ally used as func­tion names in Racket. But we can work around that.)

Then, our program still needs to be able to put these lines in numer­ical order so it knows where to start, and in which order to execute the lines (i.e., once it’s done with line X, it needs to be able to discover which line comes next). So we’ll create a hash table that maps line numbers to their asso­ci­ated func­tions. Our main program loop will look up func­tions in this table and run them.

Finally, we need to figure out goto and end. What makes these state­ments special is that they imme­di­ately short-circuit further eval­u­a­tion: goto jumps out of a line func­tion (even if there are state­ments remaining), and end jumps all the way out of the program. To imple­ment this behavior, we’ll model these state­ments as excep­tions, which are signals that prop­a­gate up through a chain of func­tions. Excep­tions are typi­cally used in Racket to flag errors. But we’ll see how they can also be used to create alter­na­tive control flows like this short-circuiting behavior.

Addi­tional modern conve­niences

Now that we know about using source loca­tions, we’ll work on adding better error reporting to our BASIC inter­preter. Errors will still be reported in the DrRacket REPL, but this time they’ll also be visu­ally high­lighted in the source code in our DrRacket window.

And now that we know about syntax coloring, we’ll make a single lexer that can be shared between our tokenizer and our colorer, instead of making sepa­rate ones. (Though we’ll post­pone writing the actual syntax colorer until the next tuto­rial.)

As for indenting—we lucked out. Every line in BASIC is set flush left. No indenter neces­sary.

Contracts & unit tests

We’ve already covered the core ideas of contracts and unit tests. To save some time, we’re not going to include them in the sample code for this tuto­rial. Instead, we’ll leave them as an extra-credit project for curious readers who want more prac­tice. But as a rule, all code should be tested—obvi­ously.

Setup

Follow the instruc­tions in the master recipe to make a basic project direc­tory and install it as a package:

We’ll add our source files into this direc­tory as we go.