About Archive Tags RSS Feed


Monkeying around with intepreters

16 June 2018 14:01

Recently I've had an overwhelming desire to write a BASIC intepreter. I can't think why, but the idea popped into my mind, and wouldn't go away.

So I challenged myself to spend the weekend looking at it.

Writing an intepreter is pretty well-understood problem:

  • Parse the input into tokens, such as "LET", "GOTO", "INT:3"
    • This is called lexical analysis / lexing.
  • Taking those tokens and building an abstract syntax tree.
    • The AST
  • Walking the tree, evaluating as you go.
    • Hey ho.

Of course BASIC is annoying because a program is prefixed by line-numbers, for example:

 20 GOTO 10

The naive way of approaching this is to repeat the whole process for each line. So a program would consist of an array of input-strings each line being treated independently.

Anyway reminding myself of all this fun took a few hours, and during the course of that time I came across Writing an intepreter in Go which seems to be well-regarded. The book walks you through creating an interpreter for a language called "Monkey".

I found a bunch of implementations, which were nice and clean. So to give myself something to do I started by adding a new built-in function rnd(). Then I tested this:

let r = 0;
let c = 0;

for( r != 50 ) {
   let r = rnd();
   let c = c + 1;

puts "It took ";
puts c;
puts " attempts to find a random-number equalling 50!";

Unfortunately this crashed. It crashed inside the body of the loop, and it seemed that the projects I looked at each handled the let statement in a slightly-odd way - the statement wouldn't return a value, and would instead fall-through a case statement, hitting the next implementation.

For example in monkey-intepreter we see that happen in this section. (Notice how there's no return after the env.Set call?)

So I reported this as a meta-bug to the book author. It might be the master source is wrong, or might be that the unrelated individuals all made the same error - meaning the text is unclear.

Anyway the end result is I have a language, in go, that I think I understand and have been able to modify. Now I'll have to find some time to go back to BASIC-work.

I found a bunch of basic-intepreters, including ubasic, but unfortunately almost all of them were missing many many features - such as implementing operations like RND(), ABS(), COS().

Perhaps room for another interpreter after all!



Comments on this entry

icon Ian at 11:32 on 16 June 2018

the statement wouldn't return a value, and would instead fall-through a case statement, hitting the next implementation.

A Go case doesn't fall through like a C one would (so no need for break or return to avoid falling through, there's an explicit fallthrough statement if you actually want to do so). I guess it is just exiting the switch and hitting the return nil at the end of the function which is confusing something further up the call chain.

icon Steve Kemp at 11:38 on 16 June 2018

You're quite correct Ian, thank-you!

icon DDD at 05:55 on 17 June 2018

LEX/AST? Nah - you've only got 2k

The way basic used to work was that the text editor stored your program into (including line numbers) as you typed it in. LIST did the opposite.

Some implementations even did GOTO by scanning through your entire program from the top...

icon Steve Kemp at 05:55 on 21 June 2018

DDD: So very true! But I figure we're in modern times now, and even the ESP8266 chips I develop on have more than 2k of RAM these days.

If I'm going to do it I should do it "properly".

Though I admit I got side-tracked by updating the monkey-sample intepreter, and that's kinda killed my interest in BASIC for the moment.