Sade – Infinitely Optimizable Brainfuck-to-Lisp Compiler

Sade ([sad], as in Marquis de Sade) follows the suit of April, APL-to-Lisp compiler, in compiling a non-Lisp language to Lisp with the goal of getting more interactive of a development workflow, better error inspection and possibly faster code (yet to be optimized and benchmarked). Be not afraid of “Lisp” in the title – it’s all compilable to an executable binary, so that you don’t have to worry about the Lisp compiler after you compiled it.

What it is not:

• It’s not the fastest Brainfuck compiler, but it can be. If you have an idea for an optimization, contribute a code snippet with your primitive and optimization in primitives.lisp and optimizations.lisp. The pattern is pretty simple. I can help you with the Lisp primitive side, if you don’t feel confident enough in Lisp writing – just open a PR with the optimization pattern and be clear about what you want to express :)
• It’s not yet the most configurable Brainfuck compiler, but it has all the potential to be one. Right now the cell size and memory length are configurable on the Lisp side, not on the CLI side. Give me some time and I’ll abstract away all the commands and add a way to dynamically generate dialects, be it pbrain, abrainfuck, bf++, or whatever else you fancy. Feel free to open an issue with what you want the compiler options to be!
• It’s not yet the most CLI-usable compiler, but this can change. I’ve been quite lazy about CLI options parsing in cli.lisp on the prototype stage. However, it doesn’t mean that the bulky API is there to stay. I’ll be glad to accept any contribution improving on the status quo.

Getting Started

The dependencies are extremely minimal – a working Lisp compiler with a recent enough ASDF (most modern Lisp compilers have it). I’ve tested SBCL 2.2.2, CCL 1.12.1, ECL 21.2.1, they worked just fine. Those (especially SBCL) should be easily available on your system, just search for it.

To build Sade, simply do

make all

in the directory you cloned Sade to. If you use CCL instead of (implied) SBCL, add LISP=ccl in the end.

You’ll have the sade executable right in this directory. You can use it as

./sade h # print help
./sade c assets/hello.bf hello # compile a Brainfuck file to an executable
./hello # run the compiled file
# => Hello, World!

or install it with make install.

How it Works

Sade takes a Brainfuck input and produces Lisp code doing exactly what Brainfuck one does. The initial code is lengthy and slow. After that, this code goes through a set of optimizations (see optimizations.lisp) that turn recognized patterns (like the ones from brainfuck optimization strategies by Mats Linander) into the simpler and faster Lisp code. This Lisp code is then compiled with the strongest typing and optimizations possible, resulting in quite fast final executables. Not the level of more sophisticated compilers or Assembly-level interpreters, but good enough, and recompiling Sade with new optimizations will allow you to produce even faster code!

Writing Optimizations

It’s mostly a matter of understanding the syntax of ~destructuring-bind~ and having an &aux binding for the match? variable.

Let us try an example. Suppose we want to optimize the absurd [+] loop. The purpose of this look is clearly zeroing the cell content, yet doing it the hard way – through the cell value wrapping. Why not just set is to zero when we see the pattern? This code does it:

(defoptimization zero-hard-way
  ((lop (plus x))
   &rest forms
   &aux (match?
         (and (eq plus 'plus)
              (eq lop 'lop))))
  `((setc 0) ,@forms))

The match pattern is saying “find a loop that only contains plus primitive, no matter how much, and take it from the surrounding code, no matter what the code is.” If this pattern is matched, it’s being replaced by the (setc 0). Note the grave accent before the setc expression – the code after the match pattern is valid Lisp code, so you can do arbitrary Lisp computations there, given that you return the valid literal sequence of primitives afterwards. For example, copying loops and multiplication loops are being discerned like this:

(defoptimization copy-right
  ((lop (right x) (plus y) (left x) (minus one))
   &rest forms
   &aux (match? (and (= one 1)
                     (eq lop 'lop)
                     (eq right 'right)
                     (eq plus 'plus)
                     (eq left 'left)
                     (eq minus 'minus))))
  (if (= y 1)
      `((copy ,x) ,@forms)
      `((mult ,x ,y) ,@forms)))

In other words, “If the number that’s being added to the destination cell is one, it’s copying. Otherwise it’s multiplication.”