A brainf*ck interpreter in Prolog

It’s pretty easy to define an interpreter in Prolog. How this can be done is shown in this paper.

The language brainfuck is extremely minimalistic, consists of only eight commands and is Turing complete. Writing an interpreter for it in Prolog is a breeze.

You can download my interpreter here. It takes a slightly different approach than described in the paper to allow for tail recursion. Without this optimization, running any brainfuck program more complex than ‘hello world’, would result in a Prolog ‘Out of Stack’ error. For some tips on writing efficient Prolog programs check out this document. The Prolog environment I used is SWI-Prolog.

I’ve included some brainfuck programs I found at ‘The brainfuck archive’.

To start a brainfuck program from Prolog do the following:

It’s not the fastest interpreter around, but it’s a nice example of how to build one in Prolog.

Tic-tac-toe

tictactoe.gifComputer programs playing two-persons games like Chess, or Go usually use a search algorithm like minimax possibly with alpha-beta pruning. The simplicity of the game Tic-tac-toe however, makes a search algorithm unnecessary. The number of possible board situations is very limited and a better option in this case is to use a lookup table.

I started by generating all possible board situations and placing them all in a database. After that, calculating for every position the best possible move or moves that should follow to minimize the chance of losing and maximize the chance of winning was straightforward. I used the result to make a lookup table to be used in a C++ program that plays Tic-tac-toe perfectly. Because of the 8-fold symmetry of  the board the lookup table does not include too many elements.