Monday, July 7, 2008

Problem in Interpretation

Just as a programming exercise, I've been trying to write an interpreter for the esoteric Brainfuck language in C++, and it is hands down my most unsuccessful and frustrating project ever. Taking my first far less competent attempt into consideration, I've probably been working on this for a half a year (though I should mention that the "work" was extremely sparse at best).

My first attempt, before I understood the goodness that is the STL string class, was to utilize arrays. To be fair this was (pre-Theory of Computation) how my mind felt the interpreter was MEANT to be implemented. I mean, it uses > and < to increment and decrement the pointer. And really, stripping it down to its core, all the language does is move a pointer up and down an "array" and increments and decrements the contents until it gets a command to "print". At that point it is assumed you're outputting an ASCII character; all that work just to create a string of ASCII characters from their number codes.

My next crack at it (meaning my current attempt) is involving an array, but only an int array in the main increment and decrement function. The actual input, as well as the final output, are both strings (so, if you want to get really technical, they're char arrays, but we're not going to worry about that because you don't have to treat them as such when you're actually using the string class. Because the string class is so wonderful).

The issue I'm running into again is the same issue I ran into with my last attempt: the while loop encased within the "[" and "]". The problem here is twofold: 1) figuring out how to recursively call the increment/decrement function so that I won't be re-writing the main chunk of code in my program and 2) dealing with the situation where the current index (ie the index the pointer is on at the point of the "[") will either be the number to be incremented/decremented, or the counter.

So during the while loop there are four essential pieces of information: the index to be incremented/decremented, the counter index, and the actual value at both these indexes. I have to keep track of this, while being able to throw everything back to the "main" program in which everything is just a straight line of incrementing/decrementing.

My friend suggested using a stack at this point, and my initial sketches involved pushing and popping the "+" with each run of the loop; after considering, I don't think this is at all effective. The first move will be to push each + found in the first run through (for the sake of simplicity I'm assuming the modified index will only be incremented); after the first run it will be obvious what the counter is and what the index being modified is. Keep pushing + until the counter runs down, then pop each + until there aren't anymore. Voila!

Hopefully I'll have a working interpreter by the end of the week; I'll post code once it's completed.

No comments: