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.