[Project] Compiling Amy to Brainfuck

Project Overview

This project was developed as part of the university course CS-320: Computer Language Processing at EPFL, taught by Viktor Kuncak. The Amy compiler skeleton was provided by the course staff.

This was a group project, with the following members:

• Vincentas Antanas Danys
• Yann Gaspoz
• Alain Sinzig

This is a blog post about the parts I personally found the most interesting about our project, and an overview of the project rather than a full write-up.

In the first guided labs of the course we built a compiler for Amy. Amy is a small functional language designed for this course that looks like Scala.

The last lab wasn’t guided and we decided to replace the WebAssembly backend to now compile to the language of Brainfuck. Brainfuck only has a tape of bytes and a pointer, so every language feature had to be rebuilt on top of that.

To make the translation possible, we had to change Amy itself:

• Int(32) became Int(8), because a Brainfuck cell holds one byte.
• Functions and user-defined types were removed. A call stack would need a runtime written in Brainfuck itself.
• while loops and a reassignment operator reassign_to were added. They replace the functions and recursion that we removed.
• Strings got a fixed size, written as String(n). There is also a resize operator [n, s].

What is Brainfuck?

Brainfuck is a minimal language. It has an infinite tape of byte-sized cells, all set to 0, and one pointer that sits on one cell.

A program is a sequence of only eight commands:

The pipeline

The pipeline itself was given to us by the course and we adapted it in the following way:

The front of the pipeline is almost unchanged. Only the last phase was replaced. Everything before it just had to learn the new syntax and the new types.

Our test runner works in three steps. It compiles Amy to Brainfuck, runs the Brainfuck, and compares the output with an expected file. Some tests are slow, because a loop in Brainfuck is just a lot of +.

The stack

Brainfuck has no stack and no variables, so we built one in the compiler. The tape plays the role of the stack. Everything that is currently in scope sits in consecutive cells to the left of the pointer.

For each variable the compiler stores three things: its depth on the tape, its type, and its length. It also stores where we currently are, which we call the current depth. Every expression evaluates to the cell under the pointer at the time we started evaluating it.

Reading a variable means walking to its cell and copying it back. Copying is needed because reading a cell in Brainfuck destroys it. The copy loop we use turns one cell into two equal cells, so the original can be consumed safely:

[-       decrement cell 1
>+>+     increment cells 2 and 3
<<]      repeat until cell 1 is 0
>>       go to cell 3
[-<<+>>] move the contents of cell 3 back to cell 1

A worked example

Take this program:

object StackTest
  val x : Int(8) = 5;
  val y : Int(8) = 10;
  y + x
end StackTest

We start with an empty tape. The pointer, marked with ^, sits on the cell where the result of the whole program will end up.

The literal 5 is evaluated and lands in that cell.

Then x is pushed. The value stays where it is and the pointer moves one cell to the right. We remember that x lives at depth 0. The same thing happens for y.

Now y + x is evaluated. Both operands are copied to temporary cells, then added. The result lands under the pointer, which is 15.

When a val expression closes, the pointer moves back one cell. So the program returns 15 at the depth where it started, and the pointer is home again.

Scoping comes for free from this. A variable exists only while the pointer is to the right of it.

if (val a : Int(8) = 1; true) then
   a   // ERROR: not found
end if

Here a is only in scope while the condition is evaluated, so the body cannot see it.

The stack cannot grow or shrink inside a while body. The body is generated for one specific depth. If it moved the pointer, the compiler would lose track of the variables above it, this leads to the necessity of having fixed size strings, more on that below.

Strings and concatenation

Layout

A string is a run of cells with ASCII values. It ends with a delimiter of 00, and the unused cells after it are filled with 1.

The 00 marks the end of the text. The 1 cells mark space that was reserved but not used. With this convention, printing a string is easy: output cells until you reach a 0.

The size is part of the type:

val s : String(10) = "hello"

It can also be inferred from the literal, so val s : String = "abc" becomes String(3).

Why fixed sizes?

We need to know the size of every string at compile time. The tape layout is decided by the compiler, so it must know how many cells each variable takes. If a string could grow at runtime, its position on the tape would change and all the offsets we computed would break.

The alternative is a heap, where memory is allocated at runtime. A heap needs bookkeeping to know which cells are free, and writing that in Brainfuck would be far too complicated for the time we had. So we kept strings at a fixed size.

The type checker follows the same idea. It infers sizes where it can, and it rejects an assignment when the source string is larger than the destination. The tricky case is concatenation, because its size depends on both operands. We solve this by keeping a list of unresolved size constraints and re-visiting them until every size is known.

Concatenation

Concatenation happens at runtime, in pure Brainfuck. We allocate as many cells as both strings need together, minus two, because the result only needs one delimiter. Then we copy the second string into the first.

This program concatenates two strings and writes the result back into s:

object ConcatTest
  val s : String(10) = "hello";
  s reassign_to [10, s ++ "world"];
  s
end ConcatTest

The three tapes below show what happens. First hello and world sit next to each other. Then ++ joins them into one long string. Finally the resize operator [10, ...] cuts the result back to the size of s, so it fits into the variable again.

The joining itself runs in a loop over the cells. Between the two strings we keep a few control cells. One of them says whether the copy is finished. The others say whether we are in the middle of a character or starting a new one. The loop walks through the second string, overwrites the delimiter of the first one with the next character, and writes a new delimiter after it. When there is nothing left to copy, the loop stops.

Resizing is simpler. Resizing to a larger size appends 1 cells. Resizing to a smaller size looks for the first 00 and sets everything behind it to 1. If the size does not change, nothing happens.

Macros

Most operators are not generated directly. Before code generation, the compiler rewrites them into small Amy programs that only use the core language. These rewrites are what we call macros. They introduce temporary variables with names that the user never sees, and they happen before the Brainfuck backend is involved at all.

Before we get to them, it helps to see what the backend does on its own. In the end it only knows the eight Brainfuck commands, so some operations are written as plain Brainfuck. Addition is the simplest example. Put the two values into two neighbouring cells, then move one into the other while adding:

evaluate left     // cell 1 holds the left hand side
>                 // move to the next cell
evaluate right    // cell 2 holds the right hand side
[<+>-]            // take one from cell 2 and add it to cell 1
<                 // pointer back on the result

Every macro is built on primitives like this one. The further we go up, the more of this hand written Brainfuck becomes Amy code that the compiler generates for us.

Here is a example for multiplication:

// x * y becomes:
val result : Int(8) = 0;
val left   : Int(8) = x;   // copies, the originals stay untouched
val right  : Int(8) = y;

while (!(right == 0)) {
  result reassign_to result + left;
  right  reassign_to right - 1
};
result

Wrapping up

The challenge of only having 8 commands was a restriction that looked scary at first, but it ended up making the whole process much more fun. Translating Amy into Brainfuck turned out to be a genuinely fun challenge.

To my surprise, I had a blast writing code in pure Brainfuck, and it even helped me get better at designing Turing machines for another course.

References

• Brainfuck on Wikipedia
• Brainfuck visual debugger
• CS-320: Computer Language Processing
• Python interpreter we used to run the tests

A big thank you to Vincentas Antanas Danys and Yann Gaspoz for a great collaboration on this project. Thanks to Viktor Kuncak for teaching the course, and to the course team for the compiler skeleton and the guided parts of the lab.