So I wrote a basic BASIC

Saturday, 20 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:

I had fun. Worth it.

I even "wrote" a "game":

| No comments

 

Pulling back

Saturday, 29 September 2018

I've updated my fork of the monkey programming language to allow object-based method calls.

That's allowed me to move some of my "standard-library" code into Monkey, and out of Go which is neat. This is a simple example:

 //
 // Reverse a string,
 //
 function string.reverse() {
   let r= "";
   let l = len(self);

   for( l > 0 ) {
      r += self[l-1];
      l--;
   }
   return r;
 }

Usage is the obvious:

  puts( "Steve".reverse() );

Or:

  let s = "Input";
  s = s.reverse();
  puts( s + "\n" );

Most of the pain here was updating the parser to recognize that "." meant a method-call was happening, once that was done it was otherwise only a matter of passing the implicit self object to the appropriate functions.

This work was done in a couple of 30-60 minute chunks. I find that I'm only really able to commit to that amount of work these days, so I've started to pull back from other projects.

Oiva is now 21 months old and he sucks up all my time & energy. I can't complain, but equally I can't really start concentrating on longer-projects even when he's gone to sleep.

And that concludes my news for the day.

Goodnight dune..

| No comments

 

PAM HaveIBeenPwned module

Monday, 17 September 2018

So the PAM module which I pondered about in my previous post now exists:

I did mention "sponsorship" in my post which lead to a couple of emails, and the end result of that was that a couple of folk donated to charity in my/its name. Good enough.

Perhaps in the future I'll explore patreon/similar, but I don't feel very in-demand so I'll avoid it for the moment.

Anyway I guess it should be Debian-packaged for neatness, but I'll resist for the moment.

| No comments

 

Recommendations for software?

Saturday, 15 September 2018

A quick post with two questions:

  • What spam-filtering software do you recommend?
  • Is there a PAM module for testing with HaveIBeenPwnd?
    • If not would you sponsor me to write it? ;)

So I've been using crm114 to perform spam-filtering on my incoming mail, via procmail, for the past few years.

Today I discovered it had archived about 12Gb of my email history, because I'd never pruned it. (Beneath ~/.crm/.)

So I wonder if there are better/simpler/different Bayesian-filters out there at that I should be switching to? Recommendations welcome - but don't say "SpamAssassin", thanks!

Secondly the excellent Have I Been Pwned site provides an API which allows you to test if a password has been previously included in a leak. This is great, and I've integrated their API in a couple of my own applications, but I was thinking on the bus home tonight it might be worth tying into PAM.

Sure in the interests of security people should use key-based authentication for SSH, but .. most people don't. Even so, if keys are used exclusively, a PAM module would allow you to validate the password which is used for sudo hasn't previously been leaked.

So it seems like there is value in a PAM module to do a lookup at authentication-time, via libcurl.

| 4 comments.

 

Improving my release process

Tuesday, 4 September 2018

I have written a lot of software which I deploy upon my own systems. Typically I deploy these things via puppet, but some things are more ad-hoc. For the ad-hoc deployments I tend to rely upon ssh to deploy them.

I have a bunch of shell-scripts, each called .deploy, which carries out the necessary steps. Here is an example script which deploys my puppet-summary service upon a host:

  #!/bin/sh

  HOST=master.steve.org.uk
  RELEASE=1.2

   # download
  ssh -t ${HOST} "wget --quiet -O /srv/puppet-summary/puppet-summary-linux-amd64-${RELEASE} https://github.com/skx/puppet-summary/releases/download/release-${RELEASE}/puppet-summary-linux-amd64"

   # symlink
   ssh -t ${HOST} "ln -sf /srv/puppet-summary/puppet-summary-linux-amd64-${RELEASE}  /srv/puppet-summary/puppet-summary"

   # make executable
   ssh -t ${HOST} "chmod 755 /srv/puppet-summary/puppet-summary*"

   # restart
   ssh -t ${HOST} "systemctl restart puppet-summary.service"

As you can see this script is very obvious:

  • Download a binary release from a github-page.
  • Symlinks a fixed name to point to this numbered-release.
  • Ensures the download is executable.
  • Then restarts a service.

This whole process is pretty painless, but it assumes prior-setup. For example it assumes that the systemd unit-file is in-place, and any corresponding users, directories, and configuration-files.

I wanted to replace it with something simple to understand, and that replacement system had to have the ability to do two things:

  • Copy a file from my local system to the remote host.
  • Run a command upon the remote host.

That would let me have a local tree of configuration-files, and allow them to be uploaded, and then carry out similar steps to the example above.

Obviously the simplest way to go would be to use fabric, ansible, salt, or even puppet. That would be too easy.

So I wondered could I write a script like this:

   # Copy the service-file into place
   CopyFile puppet-summary.service /lib/systemd/system/puppet-summary.service
   IfChanged "systemctl daemon-reload"
   IfChanged "systemctl enable puppet-summary.service"

   # Fetch the binary
   Run "wget --quiet -O /srv/puppet-summary/puppet-summary-linux-amd64-${RELEASE} https://github.com/skx/puppet-summary/releases/download/release-${RELEASE}/puppet-summary-linux-amd64"

   # Run the rest here ..
   Run "ln -sf .."

   ..
   Run "systemctl restart puppet-summary.service"

Turns out that connecting to a remote-host, via SSH, and using that single connection to either upload/download files or run commands is very simple in golang. So I'm quite placed with that.

I've only added three primitives, and the ability to set/expand variables:

  • CopyFile [local-file-name] [remote-file-name]
    • This sets a flag if the remote file was missing, or the contents changed.
  • IfChanged
    • Run a command only if the file-copy flag was set.
  • Run
    • Run a command. Unconditionally.

I suspect if I needed much more than that I should use something else. But having dealt with Ansible deployments in the past I'm very glad I didn't use that.

(It makes a lot of sense to have the repositories for deploying application A inside the repository of project A. Another reason to not use ansible, etc. Though I guess fabric would work well with that, as recipes are typically contained in ./fabfile.py. Of course .. python.)

| 1 comment.

 

Project cleanup

Friday, 27 July 2018

For the past couple of days I've gone back over my golang projects, and updated each of them to have zero golint/govet warnings.

Nothing significant has changed, but it's nice to be cleaner.

I did publish a new project, which is a webmail client implemented in golang. Using it you can view the contents of a remote IMAP server in your browser:

  • View folders.
  • View messages.
  • View attachments
  • etc.

The (huge) omission is the ability to reply to messages, compose new mails, or forward/delete messages. Still as a "read only webmail" it does the job.

Not a bad hack, but I do have the problem that my own mailserver presents ~/Maildir over IMAP and I have ~1000 folders. Retrieving that list of folders is near-instant - but retrieving that list of folders and the unread-mail count of each folder takes over a minute.

For the moment I've just not handled folders-with-new-mail specially, but it is a glaring usability hole. There are solutions, the two most obvious:

  • Use an AJAX call to get/update the unread-counts in the background.
    • Causes regressions as soon as you navigate to a new page though.
  • Have some kind of open proxy-process to maintain state and avoid accessing IMAP directly.
    • That complicates the design, but would allow "instant" fetches of "stuff".

Anyway check it out if you like. Bug reports welcome.

| No comments

 

Automating builds via CI

Sunday, 15 July 2018

Gitlab is something I've no interest in self-hosting, and Jenkins is an abomination, so I figured I'd write down what kind of things I did and explore options again. My use-cases are generally very simple:

  • I trigger some before-steps
    • Which mostly mean pulling a remote git repository to the local system.
  • I then start a build.
    • This means running debuild, hugo, or similar.
    • This happens in an isolated Docker container.
  • Once the build is complete I upload the results somehere.
    • Either to a Debian package-pool, or to a remote host via rsync.

Running all these steps inside a container is well-understood, but I cheat. It is significantly easier to run the before/after steps on your host - because that way you don't need to setup SSH keys in your containers, and that is required when you clone (private) remote repositories, or wish to upload to hosts via rsync over SSH.

Anyway I wrote more thoughts here:

Then I made it work. So that was nice.

To complete the process I also implemented a simple HTTP-server which will list all available jobs, and allow you to launch one via a click. The output of the build is streamed to your client in real-time. I didn't bother persisting output and success/failure to a database, but that would be trivial enough.

It'll tide me over until I try ick again, anyway. :)

| No comments

 

Odroid-go initial impressions

Friday, 13 July 2018

Recently I came across a hacker news post about the Odroid-go, which is a tiny hand-held console, somewhat resembling a gameboy.

In terms of hardware this is powered by an ESP32 chip, which is something I'm familiar with due to my work on Arduino, ESP8266, and other simple hardware projects.

Anyway the Odroid device costs about $40, can be programmed via the Arduino-studio, and comes by default with a series of emulators for "retro" hardware:

  • Game Boy (GB)
  • Game Boy Color (GBC)
  • Game Gear (GG)
  • Nintendo Entertainment System (NES)
  • Sega Master System (SMS)

I figured it was cheap, and because of its programmable nature it might be fun to experiment with. Though in all honesty my intentions were mostly to play NES games upon it. The fact that it is programmable means I can pretend I'm doing more interesting things than I probably would be!

Most of the documentation is available on this wiki:

The arduino setup describes how to install the libraries required to support the hardware, but then makes no mention of the board-support required to connect to an ESP32 device.

So to get a working setup you need to do two things:

  • Install the libraries & sample-code.
  • Install the board-support.

The first is documented, but here it is again:

 git clone https://github.com/hardkernel/ODROID-GO.git \
     ~/Arduino/libraries/ODROID-GO

The second is not documented. In short you need to download the esp32 hardware support via this incantation:

    mkdir -p ~/Arduino/hardware/espressif && \
     cd ~/Arduino/hardware/espressif && \
     git clone https://github.com/espressif/arduino-esp32.git esp32 && \
     cd esp32 && \
     git submodule update --init --recursive && \
     cd tools && \
     python2 get.py

(This assumes that you're using ~/Arduino for your code, but since almost everybody does ..)

Anyway the upshot of this should be that you can:

  • Choose "Tools | Boards | ODROID ESP32" to select the hardware to build for.
  • Click "File | Examples |ODROID-Go | ...." to load a sample project.
    • This can now be compiled and uploaded, but read on for the flashing-caveat.

Another gap in the instructions is that uploading projects fails. Even when you choose the correct port (Tools | Ports | ttyUSB0). To correct this you need to put the device into flash-mode:

  • Turn it off.
  • Hold down "Volume"
  • Turn it on.
  • Click Upload in your Arduino IDE.

The end result is you'll have your own code running on the device, as per this video:

Enough said. Once you do this when you turn the device on you'll see the text scrolling around. So we've overwritten the flash with our program. Oops. No more emulation for us!

The process of getting the emulators running, or updated, is in two-parts:

  • First of all the system firmware must be updated.
  • Secondly you need to update the actual emulators.

Confusingly both of these updates are called "firmware" in various (mixed) documentation and references. The main bootloader which updates the system at boot-time is downloaded from here:

To be honest I expect you only need to do this part once, unless you're uploading your own code to it. The firmware pretty much just boots, and if it finds a magic file on the SD-card it'll copy it into flash. Then it'll either execute this new code, or execute the old/pre-existing code if no update was found.

Anyway get the tarball, extract it, and edit the two files if your serial device is not /dev/ttyUSB0:

  • eraseflash.sh
  • flashall.sh

One you've done that run them both, in order:

$ ./eraseflash.sh
$ ./flashall.sh

NOTE: Here again I had to turn the device off, hold down the volume button, turn it on, and only then execute ./eraseflash.sh. This puts the device into flashing-mode.

NOTE: Here again I had to turn the device off, hold down the volume button, turn it on, and only then execute ./flashall.sh. This puts the device into flashing-mode.

Anyway if that worked you'll see your blue LED flashing on the front of the device. It'll flash quickly to say "Hey there is no file on the SD-card". So we'll carry out the second step - Download and place firmware.bin into the root of your SD-card. This comes from here:

(firmware.bin contains the actual emulators.)

Insert the card. The contents of firmware.bin will be sucked into flash, and you're ready to go. Turn off your toy, remove the SD-card, load it up with games, and reinsert it.

Power on your toy and enjoy your games. Again a simple demo:

Games are laid out in a simple structure:

  ├── firmware.bin
  ├── odroid
  │   ├── data
  │   └── firmware
  └── roms
      ├── gb
      │   └── Tetris (World).gb
      ├── gbc
      ├── gg
      ├── nes
      │   ├── Lifeforce (U).nes
      │   ├── SMB-3.nes
      │   └── Super Bomberman 2 (E) [!].nes
      └── sms

You can find a template here:

| 6 comments.

 

Another golang port, this time a toy virtual machine.

Monday, 2 July 2018

I don't understand why my toy virtual machine has as much interest as it does. It is a simple project that compiles "assembly language" into a series of bytecodes, and then allows them to be executed.

Since I recently started messing around with interpreters more generally I figured I should revisit it. Initially I rewrote the part that interprets the bytecodes in golang, which was simple, but now I've rewritten the compiler too.

Much like the previous work with interpreters this uses a lexer and an evaluator to handle things properly - in the original implementation the compiler used a series of regular expressions to parse the input files. Oops.

Anyway the end result is that I can compile a source file to bytecodes, execute bytecodes, or do both at once:

I made a couple of minor tweaks in the port, because I wanted extra facilities. Rather than implement an opcode "STRING_LENGTH" I copied the idea of traps - so a program can call-back to the interpreter to run some operations:

int 0x00  -> Set register 0 with the length of the string in register 0.

int 0x01  -> Set register 0 with the contents of reading a string from the user

etc.

This notion of traps should allow complex operations to be implemented easily, in golang. I don't think I have the patience to do too much more, but it stands as a simple example of a "compiler" or an interpreter.

I think this program is the longest I've written. Remember how verbose assembly language is?

Otherwise: Helsinki Pride happened, Oiva learned to say his name (maybe?), and I finished reading all the James Bond novels (which were very different to the films, and have aged badly on the whole).

| No comments

 

Hosted monitoring

Tuesday, 26 June 2018

I don't run hosted monitoring as a service, I just happen to do some monitoring for a few (local) people, in exchange for money.

Setting up some new tests today I realised my monitoring software had an embarassingly bad bug:

  • The IMAP probe would connect to an IMAP/IMAPS server.
  • Optionally it would login with a username & password.
    • Thus it could test the service was functional

Unfortunately the IMAP probe would never logout after determining success/failure, which would lead to errors from the remote host after a few consecutive runs:

 dovecot: imap-login: Maximum number of connections from user+IP exceeded
          (mail_max_userip_connections=10)

Oops. Anyway that bug was fixed promptly once it manifested itself, and it also gained the ability to validate SMTP authentication as a result of a customer user-request.

Otherwise I think things have been mixed recently:

  • I updated the webserver of Charlie Stross
  • Did more geekery with hardware.
  • Had a fun time in a sauna, on a boat.
  • Reported yet another security issue in an online PDF generator/converter
    • If you read a remote URL and convert the contents to PDF then be damn sure you don't let people submit file:///etc/passwd.
    • I've talked about this previously.
  • Made plaited bread for the first time.
    • It didn't suck.

(Hosted monitoring is interesting; many people will give you ping/HTTP-fetch monitoring. If you want to remotely test your email service? Far far far fewer options. I guess firewalls get involved if you're testing self-hosted services, rather than cloud-based stuff. But still an interesting niche. Feel free to tell me your budget ;)

| No comments

 

Recent Posts

Recent Tags