Entries posted in October 2018

So back in June I challenged myself to write a BASIC interpreter in a weekend. The next time I mentioned it was to admit defeat. I didn't really explain in any detail, because I thought I'd wait a few days and try again and I was distracted at the time I wrote my post.

As it happened that was over four months ago, so clearly it didn't work out. The reason for this was because I was getting too bogged down in the wrong kind of details. I'd got my heart set on doing this the "modern" way:

• Write a lexer to spit the input into tokens
  • LINE-NUMBER:10, PRINT, "Hello, World"
• Then I'd take those tokens and form an abstract syntax tree.
• Finally I'd walk the tree evaluating as I went.

The problem is that almost immediately I ran into problems, my naive approach didn't have a good solution for identifying line-numbers. So I was too paralysed to proceed much further.

I sidestepped the initial problem and figured maybe I should just have a series of tokens, somehow, which would be keyed off line-number. Obviously when you're interpreting "traditional" BASIC you need to care about lines, and treat them as important because you need to handle fun-things like this:

10 PRINT "STEVE ROCKS"
20 GOTO 10

Anyway I'd parse each line, assuming only a single statement upon a line (ha!) you can divide it into:

• Number - i.e. line-number.
• Statement.
• Newline to terminate.

Then you could have:

code{blah} ..
code[10] = "PRINT STEVE ROCKS"
code[20] = "GOTO 10"

Obviously you spot the problem there, if you think it through. Anyway. I've been thinking about it off and on since then, and the end result is that for the past two evenings I've been mostly writing a BASIC interpreter, in golang, in 20-30 minute chunks.

The way it works is as you'd expect (don't make me laugh ,bitterly):

• Parse the input into tokens.
• Store those as an array.
• Interpet each token.
  • No AST
  • No complicated structures.
  • Your program is literally an array of tokens.

I cheated, horribly, in parsing line-numbers which turned out to be exactly the right thing to do. The output of my naive lexer was:

INT:10, PRINT, STRING:"Hello World", NEWLINE, INT:20, GOTO, INT:10

Guess what? If you (secretly) prefix a newline to the program you're given you can identify line-numbers just by keeping track of your previous token in the lexer. A line-number is any number that follows a newline. You don't even have to care if they sequential. (Hrm. Bug-report?)

Once you have an array of tokens it becomes almost insanely easy to process the stream and run your interpreter:

 program[] = { LINE_NUMBER:10, PRINT, "Hello", NEWLINE, LINE_NUMBER:20 ..}

 let offset := 0
 for( offset < len(program) ) {
    token = program[offset]

    if ( token == GOTO ) { handle_goto() ; }
    if ( token == PRINT ) { handle_print() ; }
    .. handlers for every other statement
    offset++
 }

Make offset a global. And suddenly GOTO 10 becomes:

• Scan the array, again, looking for "LINE_NUMBER:10".
• Set offset to that index.

Magically it all just works. Add a stack, and GOSUB/RETURN are handled with ease too by pushing/popping the offset to it.

In fact even the FOR-loop is handled in only a few lines of code - most of the magic happening in the handler for the "NEXT" statement (because that's the part that needs to decide if it needs to jump-back to the body of the loop, or continue running.

OK this is a basic-BASIC as it is missing primtives (CHR(), LEN,etc) and it only cares about integers. But the code is wonderfully simple to understand, and the test-case coverage is pretty high.

I'll leave with an example:

10 REM This is a program
00 REM
 01 REM This program should produce 126 * 126 * 10
 02 REM  = 158760
 03 REM
 05 GOSUB 100
 10 FOR i = 0 TO 126
 20  FOR j = 0 TO 126 STEP 1
 30   FOR k = 0 TO 10
 40    LET a = i * j * k
 50   NEXT k
 60  NEXT j
 70 NEXT i
 75 PRINT a, "\n"
 80 END
100 PRINT "Hello, I'm multiplying your integers"
110 RETURN

Loops indented for clarity. Tokens in upper-case only for retro-nostalgia.

Find it here, if you care:

• https://github.com/skx/gobasic

I had fun. Worth it.

I even "wrote" a "game":

• 99-game.bas

Tags: basic, golang, interpreter | 2 comments

So my previous post described a BASIC interpreter I'd written.

Before the previous release I decided to ensure that it was easy to embed, and that it was possible to extend the BASIC environment such that it could call functions implemented in golang.

One of the first things that came to mind was to allow a BASIC script to plot pixels in a PNG. So I made that possible by adding "PLOT x,y" and "SAVE" primitives.

Taking that step further I then wrote a HTTP-server which would allow you to enter a BASIC program and view the image it created. It's a little cute at least.

Install it from source, or fetch a binary if you prefer, via:

$ go get -u github.com/skx/gobasic/goserver

Then launch it and point your browser at http://localhost:8080, and you'll be presented with something like this:

Fun times.

Tags: basic, golang, interpreter | 2 comments

I've talked about making bread in the past on this blog, here's my typical recipe - this recipe requires only two bowls, a spatula, a dutch-oven, oven-gloves, and some scales.

Ingredients:

• 1kg flour
• 950g water.
  • If you want to keep it simple you could use 1kg of water instead. It simplifies the measuring if you're using a balance-scale
• 1.5 teaspoon salt.
• 1 teaspoon instant/dried yeast.

Here is the flour, water, & yeast - not pictured salt!

Mix all ingredients together. It will be sticky, and your hands will become messy. Embrace it. (ProTip: Take off your watch and wedding-ring(s) if applicable.) Expect it to take 2-5 minutes to do a decent job. Ensure you scoop your hand right into the bottom of the mixture, to make sure there is no flour clumped together at the bottom of the bowl which is not fully mixed in.

The end result is a sticky mess which will look something like this, perhaps your bowl will be cleaner and you'll have done a better job at mixing all the flour!

Cover the bowl with cling-film, and stick in the fridge overnight. (I tend to mix stuff at 6PM in the evening, then come back to it around 9AM the following morning, which means the bowl sits in the fridge for 14 hours or so.)

Take the bowl out of the fridge and you should see it has "grown", and it will have a lot of bubbles on the top, as growth of the yeast emitted CO².

You'll also see that it is significantly more gloopy, as chains of gluten have formed

Anyway now your bowl is on the counter, out of the fridge, you want turn on your oven and set it to 250°C, with the dutch oven inside it. While you're waiting for the oven to heat up transfer the sticky mess to a new bowl, lined with baking-paper. This will make it easier to add to the pot when we're ready to actually cook it.

As per the previous video the mixture will be very sticky, but you should be able to manage it. Don't worry too much about the shape, it'll become a "loaf-shape" when it cooks, the only reason we're moving it is because it is much easier to lift the mixture into the pot by holding the paper, than trying to scrape it from your cold bowl to your very hot dutch-oven. Anyway once you've moved it to a new bowl you'll have something like this:

When your oven has reached the right temperature carefully transfer the mixture, in its paper, to the dutch oven which you'll then return to the oven.

• Cook for 40 minutes at 250°C
• Cook for an additional 20 minutes at 200°C
  • Just turn down the temperature-dial.
• Finally open the oven, remove the lid from the pot, and cook for a further 15 minutes (still at 200°C)

The end result will be something similar to this:

Enjoy!

Notes:

• You can see vestiages of the paper-wrapper in the final result.
• I like my bread dark.
• Let it cool down before you eat it, something like 45-60 minutes once you've removed from the oven.

Tags: baking, bread, recipe | 7 comments