Beautiful Racket / tutorials
Go with the flow: basic
- 1 intro
- 2 specification and setup
- 3 the lexer
- 4 the tokenizer
- 5 the parser
- 6 the reader
- 7 the expander
- 8 testing the language
- 9 recap
- 10 source listing
For simplicity, our implementation of BASIC will be a cut-down, idealized version. It won’t contradict anything we might already know about how BASIC works. But it also won’t implement all the features & details we’d need to run a serious BASIC game. (This tutorial could be the basis of a more thorough implementation, however.)
Our version of BASIC will be able to run simple programs like this:
30 rem print 'ignored'
35
50 print "never gets here"
40 end
60 print 'three' : print 1.0 + 3
70 goto 11. + 18.5 + .5 rem ignored
10 print "o" ; "n" ; "e"
20 print : goto 60.0 : end
1 2 3 4 5 6 7 8 9 | #lang basic 30 rem print 'ignored' 35 50 print "never gets here" 40 end 60 print 'three' : print 1.0 + 3 70 goto 11. + 18.5 + .5 rem ignored 10 print "o" ; "n" ; "e" 20 print : goto 60.0 : end |
three
4
1 2 3 4 | one three 4 |
To do this, we need to implement four statements:
-
print takes a string, number, or numerical expression as input and displays it, followed by a newline. A list of printable items can be separated by semicolons ; and the results will be concatenated. If print gets no input, it displays a blank line.
-
goto takes a number or numerical expression as input, and immediately jumps to that line of the program.
-
rem starts a line comment. Anything between the rem and the next newline is ignored. Even if the rem is at the beginning, the line can still be the target of a goto.
-
end immediately aborts the program.
We also have to observe a few more ground rules:
-
Each line of the program is on a separate line of the file. Line numbers are positive integers. Every line number must be unique.
-
A line can contain one statement, multiple statements separated by :, or no statements.
-
The only valid types of input are integers, decimals, and strings.
-
The only valid numerical expression is a sum of numbers.
-
When our program starts, we’ll execute each line in numerical order—regardless of the order that the lines are listed.
-
After a line executes, we’ll move on to the next line in numerical order, unless a goto sends us elsewhere.
-
Our program ends when we either run out of lines, or encounter the end statement.
Of course, with goto, we can create infinite loops, so a program can also continue indefinitely. Another side effect of goto is that not every line in a program will necessarily be executed.
Let’s step through our sample program and see how these rules play out:
30 rem print 'ignored'
35
50 print "never gets here"
40 end
60 print 'three' : print 1.0 + 3
70 goto 11. + 18.5 + .5 rem ignored
10 print "o" ; "n" ; "e"
20 print : goto 60.0 : end
1 2 3 4 5 6 7 8 9 | #lang basic 30 rem print 'ignored' 35 50 print "never gets here" 40 end 60 print 'three' : print 1.0 + 3 70 goto 11. + 18.5 + .5 rem ignored 10 print "o" ; "n" ; "e" 20 print : goto 60.0 : end |
-
The program starts at line 10, because it’s the lowest-numbered line (not line 30, even though it appears first).
-
Line 10 concatenates its three arguments and prints one.
-
Line 20 contains three statements. The print statement has no arguments, so it prints a blank line. The goto statement immediately sends us to line 60. The last statement, end, is therefore ignored.
-
Line 60 prints three and then prints the result of 1.0 + 3, which is 4.
-
Line 70 sends us to line 30 (because the sum of 11. + 18.5 + .5 is 30).
-
Line 30 starts with rem, so the rest of the line is ignored.
-
Line 35 has no statements. Nothing happens.
-
The next line in numerical order is line 40, which ends the program.
-
Line 50 is never visited.
Thus the full output is:
three
4
1 2 3 4 | one three 4 |
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 combination of macros and functions to convert the parse tree into a working program.
The trickiest part of BASIC will be implementing 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 identified by a unique line number, and contains a series of statements that needs to be available 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 function. So in pseudocode, our program above will be transformed into something like this:
(define (35) (void))
(define (50) (print "never gets here"))
(define (40) (end))
(define (60) (print "three") (print (+ 1.0 3)))
(define (70) (goto (+ 11 18.5 0.5)) (rem "ignored"))
(define (10) (print "o" "n" "e"))
(define (20) (print) (goto 60) (end))
1 2 3 4 5 6 7 8 | (define (30) (rem print "'ignored'")) (define (35) (void)) (define (50) (print "never gets here")) (define (40) (end)) (define (60) (print "three") (print (+ 1.0 3))) (define (70) (goto (+ 11 18.5 0.5)) (rem "ignored")) (define (10) (print "o" "n" "e")) (define (20) (print) (goto 60) (end)) |
(Part of the pseudo- here is that numbers can’t be actually used as function names in Racket. But we can work around that.)
Then, our program still needs to be able to put these lines in numerical 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 associated functions. Our main program loop will look up functions in this table and run them.
Finally, we need to figure out goto and end. What makes these statements special is that they immediately short-circuit further evaluation: goto jumps out of a line function (even if there are statements remaining), and end jumps all the way out of the program. To implement this behavior, we’ll model these statements as exceptions, which are signals that propagate up through a chain of functions. Exceptions are typically used in Racket to flag errors. But we’ll see how they can also be used to create alternative control flows like this short-circuiting behavior.
Now that we know about using source locations, we’ll work on adding better error reporting to our BASIC interpreter. Errors will still be reported in the DrRacket REPL, but this time they’ll also be visually highlighted 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 separate ones. (Though we’ll postpone writing the actual syntax colorer until the next tutorial.)
As for indenting—we lucked out. Every line in BASIC is set flush left. No indenter necessary.
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 tutorial. Instead, we’ll leave them as an extra-credit project for curious readers who want more practice. But as a rule, all code should be tested—obviously.
Follow the instructions in the master recipe to make a basic project directory and install it as a package:
1 | > raco pkg install /path/to/basic |
We’ll add our source files into this directory as we go.