Brainf**k interpreter

[Ben Erlebach]

Hi,

Making games is hard, so instead, I decided to explore the computation power of Puzzlescript.

To this end, I wrote a Brainf**k interpreter. If you're unfamiliar with the language, you can find some information here:

https://en.wikipedia.org/wiki/Brainfuck

https://esolangs.org/wiki/Brainfuck

Here's a link to the interpreter, with a 'Hello World' program loaded in that I took from the wiki (I'm not masochistic enough to write programs in BF myself!):

http://www.puzzlescript.net/play.html?p=01cbfb3980dfb249921e

The screen's split into two parts - the array (top) and the code (bottom). Each column in the array is a cell, with the least significant bit at the bottom. The red arrow represents the pointer, and the blue line represents where in the code the interpreter is.

You can toggle the program running with the action key. It can be a little unreadable on a small screen - sorry!

I guess this is proof that Puzzlescript is Turing complete, although I remember seeing someone here post a turing machine so I think that question was already answered.

I'd like to thank Stephen Lavelle for making such a great tool, and all of you for making cool games - although I've not commented on any of them, I've been playing a lot of the games posted here and they're super neat. Keep up the good work!

The rest of this post is about design and implementation decisions, which should hopefully be interesting, but isn't required reading! If you have any questions, comments, criticism or have found any bugs, let me know.

Cheers,

Ben

=====

The main objective I had was to write an interpreter that wasn't bounded i.e. could run any length of code and support arbitrarily large arrays and cell sizes. I also wanted to work with (not against) Puzzlescript and make the most of its features. With the code, I tried to be concise but not to the point of obfuscation.

Sadly, because level size can't be changed at run-time, some manipulation to BF code is required - rows need to be placed above the code (for the array) and below the code (for indentation - see later). If an array larger than the length of the code is required, columns need to be placed to the right of the code, too.

I didn't write much code to check that the level was valid, because I don't think it's worth the effort. There is a nice benefit that the array can be pre-filled with values, to allow for easy debugging / testing of small snippets of code. However, I did check for valid BF.

Maybe I'm just not familiar enough with Puzzlescript yet, but I often found myself wanting to know whether an object was on an edge. I ended up writing a lot of code like

> right [ Object | ] -> [ | action Object ]

> [ stationary Object ] -> do stuff

> [ action Object ] -> [ Object ]

to move the object one to the right if possible, else run the code relevant for reaching the side of the screen (e.g. if the cursor moves the screen, stop execution). I know I could have a border around everything and then check if the object was next to the border, but that adds more complexity.

Another issue I fell afoul of is there currently isn't any way to have a rule run if none of an object (either in a certain direction or anywhere). Thus I had to write things things like:

> [ Foo ] -> [ action Foo ]

> [ action Foo ] [ Bar ] -> [ Foo ] [ Bar ] (don't run if a Bar exists)

> [ action Foo ] -> do stuff

If anybody has any other suggestions on how to deal with these two problems, I'm all ears.

=====

I decided to have cells over/underflow naturally, instead of raising errors when decrementing a 0 cell or incrementing a 'full' (i.e. 111....1) cell. On the other hand, the interpreter will raise an error if the code tries to move the pointer out of the array.

I've implemented these this way, partially because it's easier, and also partially because most implementations of BF do this, so it allows for more pre-existing code to be ran (with the pointer error flagging whether the code requires a larger array than it's given). 

The cells are in binary because it's 'neater' than having them in decimal or unary. There's also the added benefit that as mentioned above, lots of pre-exisiting BF code assumes a certain cell size in bits, so it makes it easier to run code that does.

=====

One of the hardest things in making any BF interpreter/compiler is dealing with loops. Because Puzzlescript doesn't have any counters, I was worried that there wouldn't be a nice solution to this.

Luckily, I came up with something nice (and very much in the spirit of Puzzlescript) - indenting code inside loops. That way, whenever the interpreter has to jump forward/back, it just has to find the first bracket on the same (horizontal) line going forwards/backwards.

This has the added bonus that it's really easy to find mismatched brackets - if the interpreter doesn't finish on the same line that it started, there must be too many left brackets; and if the interpreter strays upwards into the array, there must be too many right brackets. There's no added difficulty in dealing with reading indented code, either: thanks to the way Puzzlescript rules work, having a vertical line of cursors is just as easy as having one. Also, there's the aesthetic benefit that it's easier to see how the brackets match.

Sadly this does mean that extra space needs to be assigned to the bottom of the level, but even the most loop-heavy BF code will only need length/2 lines of space, so it's not too bad. The interpreter will raise an error if not enough space has been given for the code.

=====

The Hello World program doesn't feature input, but I did include it: when a comma is executed, a small input cursor appears on the current cell. Press left to change the current digit to a 0, right to change it to a 1, and up/down to move up and down cell. When the final digit is changed or the input cursor is moved past the end of the cell, execution continues.

I think this solution is ok, because it deals with arbitrary size cells well, even if it is a bit tedious. The alternative that springs to mind is to have a seperate array with pre-loaded input and to read that cell-by-cell whenever input is read. I didn't implement this because it's unnecessary complication for a lot of programs, and it still isn't a fantastic way to pass data into a program.

Output is probably where I'm least happy with this program. Because there's no counters in Puzzlescript or 'dynamic' messages, it's very difficult to turn an arbitrarily long sequence of One and Zero objects into a message.

One option would be to have a message for each digit (so 11001011 would output eight messages, saying One, One, Zero, ..., One), but this is pretty useless in terms of human readability. What I went with in the end was a message for each number from 0 to 255 (and also outputting the relevant ASCII character for some small subset of those numbers) and just doing nothing for any number larger than that. Obviously, this requires 256 lines of code, so it's not a very nice solution. On top of that, because I didn't want to lose support for larger cell sizes, I ended up writing this:

> [ Cursor Period ] [ Execute ] -> [ Cursor action Period ] [ Execute ]

>

> up [ Pointer | One | One | One | One | One | One | One | One ] [ Cursor action Period ] [ Execute ] -> [ Pointer | One | One | One | One | One | One | One | One ] [ Cursor Period ] [ Execute ] message 255

> up [ Pointer | Zero | One | One | One | One | One | One | One ] [ Cursor action Period ] [ Execute ] -> [ Pointer | Zero | One | One | One | One | One | One | One ] [ Cursor Period ] [ Execute ] message 254

> ...

> up [ Pointer | One ] [ Cursor action Period ] [ Execute ] -> [ Pointer | One ] [ Cursor Period ] [ Execute ] message 1

> up [ Pointer | Zero ] [ Cursor action Period ] [ Execute ] -> [ Pointer | Zero ] [ Cursor Period ] [ Execute ] message 0

which is a huge mess. If anyone has any better ideas, I'm all ears.

=====

I picked Brainf**k because of its small and simple instruction set. There's definitely scope to implement interpreters for other languages, though: languages like Befunge are a great fit for Puzzlescript, although they'll be a lot more work.

Despite its flaws, I'm quite happy with how this turned out. Now, if only I could make interesting levels to put in my games...

Thanks for reading.

[anna anthropy]

when i ran it it just spelled "hell" and then stopped

[Ben Erlebach]

Works fine for me - you probably accidentally paused it - press action again and it should carry on running.

I guess using the action button for play/pause was not the greatest of ideas when that's also the button to finish reading messages.

[Hand-E-Food]

Nice work!

[Chris Pickel]

I’ll admit, I’m amused that the idea of writing an interpreter in Puzzlescript was more palatable than the idea of writing something in the language itself.

About some of your implementation details:

- Checking if a cell is at the edge

- Checking if there isn't any of an object

I think Puzzlescript doesn’t offer a better solution, and you’ve come across the standard workarounds.

- Indentation

You could also use a physical counter, probably?

- ASCII

You could write the rules more concisely as:

[0|0|1|1|0|0|0|1] -> message

Which doesn’t solve the problem of needing 256 lines, but makes it easier to scan through the list of them, at least.

On Fri, Sep 25, 2015 at 10:18 AM Hand-E-Food <hand_...@hotmail.com> wrote:

Nice work!

--
You received this message because you are subscribed to the Google Groups "PuzzleScript" group.
To unsubscribe from this group and stop receiving emails from it, send an email to puzzlescript...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Connorses]

I thought about maybe writing a Brainfuck program just to say I did it.

Then I looked it up on Wikipedia.

I'm not so excited about writing one anymore. :L