smlfuck

Brainfuck in Standard ML

I've got plenty of time on my hands this summer, so I decided that I wanted to
implement interpreters or compilers for a lot of different languages (using
different languages as well). The goal is to implement a compiler or interpreter
for 30 different languages in 30 days.

This is day 1.

Today I wish to implement Brainfuck in Standard ML. I am going to use Moscow ML,
but the code should be more or less portable to MLton, SML/NJ and so on.

Working with MosML in Emacs

How did it go?

I started out tokenizing the input string and simply matching over the list of
tokens. The result can be seen in commit 305c91.
However, this turned out to be impractical for implementing loops. Instead, I
decided to converted the source code into an actual AST. The Brainfuck syntax is
very simple to model, so I could make do with this simple datatype declaration:

datatype ast = Right
             | Left
             | Inc
             | Dec
             | Output
             | Input
             | Loop of ast list

I am also very happy with how the parser turned out. I'm abusing the >>=
operator bit; it's not equivalent to bind, but I think it makes the code easy to
work with.

The actual interpreter is a bit more messy: I'm using a mutable array, which in
itself isn't very idiomatic in Standard ML, but it also makes the code a bit
ugly in my opinion. I considered using a vector instead, but I was afraid it'd
be too inefficient (For what? No idea, I'm not going to do anything with it).

All in all, I am quite happy with the result. This was the first language I
wanted to implement an interpreter for, so it's taken a little bit longer than I
expected, around 3 hours. smlfuck could do with a bit more error handling,
bounds checking, I/O optimization and such but I guess it's alright for
now.

Created: <2015-06-27 Sat>

Last modified: 2017-02-08 Wed 09:20