Running Hammurabi in Dart
One of the first computer games I played (back in the 80’s) was Hammurabi, after I found David Ahl’s classic book about BASIC computer games in my local public library. Line by line, I typed the source code into my home computer and had hours of fun. At least, this is how I remember it.
Some time ago, I wanted to experience the game again. It would have been easy to translate its source code into some modern programming language, like for example Dart, but I figured, it would be more fun to create a BASIC interpreter in Dart and let it run the original program.
This is my story of doing exactly this.
Analysing BASIC
The game consists of 120 lines of BASIC for the Altair 8800 and this is a very typical example for its time with line numbers, simple instructions, no other control structures than FOR and GOTO and with only global variables.
Here is an except from the start of the program:
10 PRINT TAB(32);"HAMURABI"
20 PRINT TAB(15);"CREATIVE COMPUTING MORRISTOWN, NEW JERSEY"
30 PRINT:PRINT:PRINT
80 PRINT "TRY YOUR HAND AT GOVERNING ANCIENT SUMERIA"
90 PRINT "FOR A TEN-YEAR TERM OF OFFICE.":PRINT
95 D1=0: P1=0
100 Z=0: P=95:S=2800: H=3000: E=H-S
110 Y=3: A=H/Y: I=5: Q=1
210 D=0
215 PRINT:PRINT:PRINT "HAMURABI: I BEG TO REPORT TO YOU,": Z=Z+1
217 PRINT "IN YEAR";Z;",";D;"PEOPLE STARVED,";I;"CAME TO THE CITY,"
218 P=P+I
227 IF Q>0 THEN 230
228 P=INT(P/2)You might want to follow the link to the original source code, since I refer to it by mentioning line numbers in the rest of this article.
Basically, I will create an interpreter which reads in the source, splits it into tokens (like numbers, operators, names, …) to make further processing easier and then parse and evaluate instructions until I see the END instruction. Each instruction (with the exception of LET for assignments) starts with a keyword and is terminated by either : or the end of line.
For evaluating expressions (stuff like H/Y or INT(P/2)) I will probably need to create a recursive descent parser for a very typical EBNF grammar like this:
expression = term {("+"|"-") term}
term = factor {("*"|"/" factor)}
factor = "-" factor | primary
primary = "(" expression ")" | number | string | variable | function
variable = name
function = name (" expression ")"As seen in line 227, there are also conditionals which follow this grammar:
conditional = expression ("<"|"<="|">"|">="|"="|"<>") expressionTo implement jumping to lines I will simply do a linear search on the list of tokens instead of implementing some internal representation which might be more efficient. Each line starts with a line number and (with the exception of the first line) each line number is preceded by an end of line token from the previous line.
Divide and Conquer
Let’s start simple.
I set up a new Dart project where I put by BASIC source code (see above) and then create a file called hammurabi.dart which will contain all source code shown in this article.
I’ll try to show the relevant parts so that you can read along.
The following Dart code reads the BASIC source code and prints it. It’s to make sure the project setup works and we can run it (I’m using Visual Studio Code plus its Dart plugin) from within the IDE.
import 'dart:io';void main() {
run(File("hammurabi.bas").readAsStringSync());
}void run(String source) {
print(source);
}
By the way, because of an 8-letter restriction on the length of the filename, the original misses an “m” in the king’s name. I added it back.
My standard approach when creating LL(1) parsers is to create a stream of tokens using a tokenize function that uses a more or less complex regular expression to detect tokens and do some minimal post processing.
Eyeballing the source code, I need to detect
- numbers:
\d+ - strings:
".*?" - names (variables and keywords of instructions):
\w+ - arithmetic operators (see grammar above):
[-+*/] - comparison operators (see grammar above):
<(>=)?|>=?|= - syntax like parentheses or the
:to separate instructions - the end of line
I also want to skip whitespace. Therefore, I group everything I want to detect, append an alternative to skip whitespace, and return the first capture group and not the whole expression.
Iterable<String> tokenize(String source) {
return RegExp(r'(...)|\s+')
.allMatches(source)
.map((m) => m[1])
.where((m) => m != null);
}This (instead of ...) is my regular expression:
(\d+|".*?"|\w+|[-+*/:;()]|[<>=]+|\n)Let’s test it by replacing the old run with this new code:
void run(String source) {
print(List.of(tokenize(source)));
}This prints something like this which doesn’t look too bad:
[10, PRINT, TAB, (, 32, ), ;, "HAMURABI",
, 20, PRINT, TAB, (, 15, ), ;, "CREATIVE COMPUTING MORRISTOWN, NEW JERSEY",
, 30, PRINT, :, PRINT, :, PRINT,
, 80, PRINT, "TRY YOUR HAND AT GOVERNING ANCIENT SUMERIA",
, 90, PRINT, "FOR A TEN-YEAR TERM OF OFFICE.", :, PRINT,
, 95, D1, =, 0, :, P1, =, 0,
, 100, Z, =, 0, :, P, =, 95, :, S, =, 2800, :, H, =, 3000, :, E, =, H, -, S,
, 110, Y, =, 3, :, A, =, H, /, Y, :, I, =, 5, :, Q, =, 1,
, 210, D, =, 0, ...This was almost too easy. To make sure, that I didn’t miss anything (spoiler: I did) I add another alternate group to the regular expression (.) that matches anything not matched before and prints it:
Iterable<String> tokenize(String source) {
return RegExp(r'(\d+|".*?"|\w+|[-+*/:;()]|[<>=]+|\n)|\s+|(.)')
.allMatches(source)
.map((m) {
if (m[2] != null) print(m[2]);
return m;
})
.map((m) => m[1])
.where((m) => m != null);
}Looks like I’m missing these characters: ?!',%. While , and . (as part of floating point numbers) are obvious mistakes and I have to modify my regular expression accordingly, I don’t think that BASIC ever had those other operators. Looking at the source, I notice that the REM statement for remarks is somewhat irregular.
418 REM *** TRYING TO USE MORE GRAIN THAN IS IN SILOS?
532 REM *** LET'S HAVE SOME BABIES
541 REM *** HORROR, A 15% CHANCE OF PLAGUESo I have to filter it, too. My first instinct was to make it whitespace but then I thought that empty lines might later irritate my interpreter. I decided to make it a normal instruction, just ignoring everything following the keyword up to the end of the line. Because Dart — like JavaScript — has no lookbehind operator, I have to add a bit of post processing using an additional capture group. Order matters here.
Iterable<String> tokenize(String source) {
return RegExp(r'(\d+(?:\.\d*)?|\.\d+|".*?"|(REM).*|\w+|'
r'[-+*/:;()]|[<>=]+|\n)|\s+')
.allMatches(source)
.map((m) => m[2] ?? m[1])
.where((m) => m != null);
}This correctly tokenizes the complete source code.
Parsing for Fun and Profit
Over the years, I learned how a create a tiny framework for writing LL(1) parsers by hand.
- The
tokenfunction returns the current token. Normally, I’d use some kind of stream (a.k.a.Iterable), but thinking about how to implementGOTOI knew I had to keep all tokens as the representation of the program around, so this implementation will use aListand anintindex. Later, I will call this index the instruction pointer. - The
advancefunction will consume the current token and advances the index to the next one to make it the new current token.
Both functions are the basic building block for all other functions:
at(t)tests whethertokenistand automatically consumes it if this is the case. This is very useful for testing for keywords and other syntax.expect(t)works likeatbut throws an error ifatwould returnfalse.- Throwing the error is done by the
expectedfunction which tries to give some context. In this implementation I’m printing the current token and the BASIC line number, which is nearest to the instruction pointer.
String get token => _tokens[_index];void advance() => _index++;bool at(String t) {
if (token == t) {
advance();
return true;
}
return false;
}void expect(String t) {
if (!at(t)) expected('$t');
}void expected(String message) {
var i = _index;
while (i >= 0 && _tokens[i] != '\n') --i;
var line = _tokens[i + 1];
throw 'expected $message but found $token in $line';
}List<String> _tokens;int _index;
Because it will be handy, the next two functions detect the end of an instruction and unify the two cases that there’s either a : or the end of line. In the latter case I also skip the next line number which must follow (this would crash if the program end with : which it doesn’t).
bool atEnd() {
if (at('\n')) {
advance();
return true;
}
return at(':');
}void expectEnd() {
if (!atEnd()) expected('end of instruction');
}
Let’s test this “framework” by printing all BASIC instructions like so:
void run(String source) {
_tokens = List.of(tokenize(source));
_index = 1;
while (!at('END')) {
print(token);
while (!atEnd()) advance();
}
}I can pipe this output to sort -u and removing the obvious variable names, I get an overview of all instructions I have to implement:
GOSUB
GOTO
IF
INPUT
PRINT
REM
RETURNFortunately, this is a very short list. Adding another function for processing assignments (because theLET keyword is optional) I shall be able to parse everything using this main loop:
void run(String source) {
_tokens = List.of(tokenize(source));
_index = 1;
while (!at('END')) {
if (at('GOSUB'))
doGosub();
else if (at('GOTO'))
doGoto();
else if (at('IF'))
doIf();
else if (at('INPUT'))
doInput();
else if (at('PRINT'))
doPrint();
else if (at('REM'))
doRem();
else if (at('RETURN'))
doReturn();
else
doLet();
}
}void doGosub() { expectEnd(); }
void doGoto() { expectEnd(); }
void doIf() { expectEnd(); }
void doInput() { expectEnd(); }
void doPrint() { expectEnd(); }
void doRem() { expectEnd(); }
void doReturn() { expectEnd(); }
void doLet() { expectEnd(); }
Running this obviously doesn’t work, but the error that occurs will help in implementing the needed functionality as we slowing proceed through the source:
"expected end of instruction but found TAB in 10"This refers to the very first line:
10 PRINT TAB(32);"HAMURABI"So let’s implement PRINT (which unfortunately is also the most complex instruction) and for this, let’s implement expression parsing first.
Express Yourself
Instead of incrementally developing those parsing functions, I’ll create a standard expression parser according to the EBNF grammar shown above because that’s straight forward (at least to me). You can translate EBNF grammars nearly directly into recursive function calls. There is just one minor problem: The above grammar cannot distinguish variable and function rules as written. But that’s easy to fix.
You will also notice that I have to use regular expressions again to detect numbers and names. I could omit this by introducing a Token class that holds this information which is more easily available in tokenize. That function would be the right place to create such tokens. I leave this as an exercise to the reader and keep using strings.
// expression = term {("+"|"-") expression}
expression() {
var v = term();
while (true) {
if (at('+'))
v += term();
else if (at('-'))
v -= term();
else
return v;
}
}// term = factor {("*"|"/") factor}
term() {
var v = factor();
while (true) {
if (at('*'))
v *= factor();
else if (at('/'))
v /= factor();
else
return v;
}
}// factor = "-" factor | primary
// primary = "(" expression ")"
// | number | string | variable | function
// variable = name
// function = name (" expression ")"
factor() {
if (at('-')) return -factor();
if (at('(')) {
var v = expression();
expect(')');
return v;
}
var t = token;
if (t[0] == '"') {
advance();
return t.substring(1, t.length - 1);
}
if (RegExp(r'\.?\d').matchAsPrefix(t) != null) {
advance();
return num.parse(t);
}
var n = name();
if (at('(')) {
var arg = expression();
expect(')');
if (n == 'TAB') return ' ' * arg;
expected('unknown function $n');
}
return _variables[n] ?? 0;
}String name() {
var t = token;
if (RegExp(r'[a-zA-Z]').matchAsPrefix(t) != null) {
advance();
return t;
}
throw expected('name');
}Map<String, num> _variables = {};
Because Dart cannot express union types like num | String which is what these functions will return, I don’t specify a return type at all (so it is dynamic). This could be omitted by creating a hierarchy of custom values types but I consider it overkill for this project.
Now, the doPrint function looks like this:
void doPrint() {
var s = "";
if (!atEnd()) {
s += '${expression()}';
while (at(';')) {
s += '${expression()}';
}
expectEnd();
}
stdout.writeln(s);
}Looking at line 30, PRINT could be empty. Therefore the first if. Otherwise, there’s at least one expression and probably more, which are then separated by ;. If you know BASIC, you’ll remember that there’s also a variant using , instead of ; but luckily, this isn’t used by this program. (And yes, the above implementation isn’t 100% correct. We’ll revisit it shortly.)
Let there be print!
We’re now making real progress. Running the interpreter prints something:
HAMURABI
CREATIVE COMPUTING MORRISTOWN, NEW JERSEY
TRY YOUR HAND AT GOVERNING ANCIENT SUMERIA
FOR A TEN-YEAR TERM OF OFFICE.Apropos LET
The next error is in line 95 which is the first assignment.
"expected end of instruction but found D1 in 95"Let’s implement LET. With everything we already written, it’s almost too easy. We expect a name and a = token followed by an expression. Then we create or update a global variable.
void doLet() {
var n = name();
expect('=');
_variables[n] = expression();
expectEnd();
}Let’s run the programm again.
Conditions
The next error is in line 227 which is the first IF statement:
227 IF Q>0 THEN 230Evaluating the conditional expression should be easy and will be achieved by a new function called condition.
bool condition() {
var e = expression();
if (at('=')) return e == expression();
if (at('<>')) return e != expression();
if (at('<')) return e < expression();
if (at('<=')) return e <= expression();
if (at('>')) return e > expression();
if (at('>=')) return e >= expression();
expected('comparison operator');
}(BTW, does anybody know how to tell the Dart compiler that expected is a function that never returns? In Swift, it’s the type Never. I thought, I have to use Null in Dart, but I still get a warning that condition might not return a Boolean value.)
With a Jump to the Left…
So let’s next have a look at how to implement the jump. First of all, I want to make sure, there is a valid number, which is checked by a function line which works like name shown before. The goto function then implements searching for right line number and moving the instruction pointer index right behind that number in the token stream.
String line() {
var t = token;
if (RegExp(r'\d+').matchAsPrefix(t) != null) {
advance();
return t;
}
throw expected('line number');
}...void goto(String line) {
for (var i = 0; i < _tokens.length;) {
if (_tokens[i++] == line) {
_index = i;
return;
}
for (; i < _tokens.length && _tokens[i] != '\n'; i++);
i++;
}
throw 'missing line $line';
}
The last throw should never occur in a program but better be safe than sorrow. I’m using a string as a cheap runtime exception. Don’t follow my example.
IF THEN
This instruction is again straight forward to implement. I just have to remember that I have to parse the whole instruction before jumping or otherwise not jumping would result in a parsing error (which of course happened when I wrote this initially).
void doIf() {
var c = condition();
expect('THEN');
var l = line();
expectEnd();
if (c) goto(l);
}More BASIC Functions
The next problem is a missing RND function in line 310:
310 C=INT(10*RND(1)): Y=C+17There’s also another function INT which I will implement simultaneously. For the random function, I have to import dart:math and initialize a random generator somewhere in my program. I will omit that code here and just show the implementation of the two BASIC functions by adding two lines to the existingfactor function:
factor() {
...
var n = name();
if (at('(')) {
var arg = expression();
expect(')');
if (n == 'TAB') return ' ' * arg;
if (n == 'RND') return _random.nextDouble();
if (n == 'INT') return arg.toInt();
expected('unknown function $n');
}
...
}Revisiting PRINT
The next error took me some time to understand.
"expected name but found \n in 321"Is the INPUT statement the problem? But then the error is wrong…!?
320 PRINT "HOW MANY ACRES DO YOU WISH TO BUY";
321 INPUT Q: IF Q<0 THEN 850
322 IF Y*Q<=S THEN 330No, the problem is the ; in line 320 which instructs BASIC to not add a line feed and carriage return to the printed line, so that INPUT will prompt the user in the same line. But I overlooked it for minutes even if I originally knew about that variant of PRINT.
And while at it and in the case you’re following along with your own implementation, you might have noticed that the output looks wrong:
POPULATION IS NOW100
THE CITY NOW OWNS 1000.0ACRES.
YOU HARVESTED3BUSHELS PER ACRE.
RATS ATE200BUSHELS.I think, we need to add spaces around the numbers where semicolons are used. The true semantics when to add space might be more sophisticated, but that should do the trick. And I should probably also omit to print decimal places for doubles that have none. To do all this argument processing, I introduce a local function str.
void doPrint() {
String str(v) {
if (v is String) return v;
if (v == v.toInt()) v = v.toInt();
return ' $v ';
} var s = "";
if (!atEnd()) {
s += str(expression());
while (at(';')) {
if (atEnd()) {
stdout.write(s);
return;
}
s += str(expression());
}
expectEnd();
}
stdout.writeln(s);
}
This should fix the PRINT statement for good.
INPUT
Now the next missing instruction is INPUT. Its implementation would look like this, but because Visual Studio Code doesn’t support reading from stdin I couldn’t continue to run and debug my code using this IDE. How annoying…
void doInput() {
var n = name();
expectEnd();
stdout.write('? ');
var i = stdin.readLineSync();
_variables[n] = num.tryParse(i) ?? 0;
}I need a better solution and for now, I will provide hard-coded values I read from a global variable called inputs. I feel clever that I came up with this trick ;-)
var inputs = ['0', '1', '1800', '1000'];void doInput() {
var n = name();
expectEnd();
stdout.write('? ');
var i;
if (inputs != null && inputs.isNotEmpty) {
i = inputs.removeAt(0);
stdout.writeln(i);
} else {
i = stdin.readLineSync();
}
_variables[n] = num.tryParse(i) ?? 0;
}
We’re almost there. The output looks promising:
HAMURABI
CREATIVE COMPUTING MORRISTOWN, NEW JERSEYTRY YOUR HAND AT GOVERNING ANCIENT SUMERIA
FOR A TEN-YEAR TERM OF OFFICE.HAMURABI: I BEG TO REPORT TO YOU,
IN YEAR 1 , 0 PEOPLE STARVED, 5 CAME TO THE CITY,
POPULATION IS NOW 100
THE CITY NOW OWNS 1000 ACRES.
YOU HARVESTED 3 BUSHELS PER ACRE.
RATS ATE 200 BUSHELS.
YOU NOW HAVE 2800 BUSHELS IN STORE.LAND IS TRADING AT 24 BUSHELS PER ACRE.
HOW MANY ACRES DO YOU WISH TO BUY? 0
HOW MANY ACRES DO YOU WISH TO SELL? 1HOW MANY BUSHELS DO YOU WISH TO FEED YOUR PEOPLE? 1800HOW MANY ACRES DO YOU WISH TO PLANT WITH SEED? 1000
HAMURABI: THINK AGAIN. YOU OWN ONLY 999 ACRES. NOW THEN,
GOTO, GOSUB and RETURN
These are the remaining instructions to implement.
The next error shown after NOW THEN is this:
"expected end of instruction but found 440 in 447"Looking at that line, this is a GOTO instruction. Easy.
Here is this unconditional jump:
void doGoto() {
var l = line();
expectEnd();
goto(l);
}For jumping to (and returning from) subroutines, I need to setup a stack to save the current instruction pointer before changing it like so:
void doGosub() {
var l = line();
expectEnd();
_stack.add(_index);
goto(l);
}void doReturn() {
expectEnd();
_index = _stack.removeLast();
}List<int> _stack = [];
The BASIC Has Landed
I think, that was all.
I can now, after an hour or two needing to implement my interpreter and multiple hours writing everything down and refactoring the code and fixing my writeup, finally play this rather boring game.
HAMURABI
CREATIVE COMPUTING MORRISTOWN, NEW JERSEYTRY YOUR HAND AT GOVERNING ANCIENT SUMERIA
FOR A TEN-YEAR TERM OF OFFICE.HAMURABI: I BEG TO REPORT TO YOU,
IN YEAR 1 , 0 PEOPLE STARVED, 5 CAME TO THE CITY,
POPULATION IS NOW 100
THE CITY NOW OWNS 1000 ACRES.
YOU HARVESTED 3 BUSHELS PER ACRE.
RATS ATE 200 BUSHELS.
YOU NOW HAVE 2800 BUSHELS IN STORE.LAND IS TRADING AT 18 BUSHELS PER ACRE.
HOW MANY ACRES DO YOU WISH TO BUY? 0
HOW MANY ACRES DO YOU WISH TO SELL? 0HOW MANY BUSHELS DO YOU WISH TO FEED YOUR PEOPLE? 1800HOW MANY ACRES DO YOU WISH TO PLANT WITH SEED? 990HAMURABI: I BEG TO REPORT TO YOU,
IN YEAR 2 , 10 PEOPLE STARVED, 13 CAME TO THE CITY,
POPULATION IS NOW 103
THE CITY NOW OWNS 1000 ACRES.
YOU HARVESTED 5 BUSHELS PER ACRE.
RATS ATE 0 BUSHELS.
YOU NOW HAVE 5455 BUSHELS IN STORE.LAND IS TRADING AT 17 BUSHELS PER ACRE.
HOW MANY ACRES DO YOU WISH TO BUY? _
Back in the early eighties, I found it much more fascinating. But David Ahl’s book contains a lot of other games. The game Super Star Trek, sounds promising, doesn’t it? Let’s try it:
,------*------,
,------------- '--- ------'
'-------- --' / /
,---' '-------/ /--,
'----------------' THE USS ENTERPRISE --- NCC-1701
Then, it crashes because I don’t support string variables or array variables… The bigger problem however is that the Star Trek source doesn’t use spaces to separate tokens so my tokenize function is too simplistic to split something like IFK9>T9THENT9=K9+1. Too bad. Perhaps another time.
Appendix
The complete source code for my interpreter.
I’m not sure whether I’m allowed to also include the BASIC source, but this guy thinks it’s okay to provide machine readable versions from the book.
