GNU/Linux ◆ st-256color ◆ zsh 2023 views

It took me some fiddling to get Hillel Wayne’s original vim-macros-only Brainfuck interpreter running, so I figured I’d share an asciinema, in the spirit of reproducible shitposting!

Any mistakes are mine; The interpreter itself is Hillel’s.

Why was it so hard?

(If you’re not familiar with vim marks and macros, skip this section and jump right to the more verbose explanations below)

The tricky part was the [ operator: I figured his 'clF0`b needed to do something other than move. Looking at the brainfuck spec, [ behaves like jz end_of_loop. `bh%mbmb clearly moves the mark `b (that is, the program counter) to the matching ], so 'clF0 has to crash the macro if the mark 'c (that is, the position of the head on the tape) is on a 0. That’s super clever; I wouldn’t have thought to use the fact that vim stops running your macro if you make an impossible move.

Alright, so how do we do that? Well, l just moves us one left, and F0 tries to go back to the previous 0 on this line. Okay, so it normally fails immediately, since there’s nowhere left to go after the numbers on each line. The first thing I tried to do is add a space after each number, but the C-a/C-x increment/decrement operator deletes the trailing whitespace. The solution is to use one of my favorite vim options virtualedit (invaluable for asciiart! see the modeline at the top). Now, we can go left all we like, but F0 still fails if there’s no 0 to our left!

Huh? Sorry, I don’t speak linenoise…

Let’s break it down:

What’s Brainfuck?

Brainfuck is a small, Turing-complete, notoriously impenetrable, language. Here’s the semantics denoted into C, according to wikipedia:

Brainfuck command   C equivalent
------------------- ---------------------------------------------------------
(Program Start)     char array[INFINITELY_LARGE_SIZE] = {0}; char *ptr=array;
>                   ++ptr;
<                   --ptr;
+                   ++*ptr;
-                   --*ptr;
[                   while (*ptr) {
]                   )

That is, we have a pointer into an infinitely long tape, and we can move back and forth along the tape with < and >, increment and decrement the memory cell on the tape that we’re currently looking at with + and -, and finally, we can loop until our pointer ends on a 0, using [ and ].

How?

You’ll notice that the commands from the above table mirror the block of text at mark `a on lines 8-14. That’s no coincidence: this is where we keep a lookup table of commands to execute. Mark `b is our program counter, and mark `c is the location of our pointer in memory/the tape. So at every step, we want to read the symbol at the program counter, look up the meaning of that symbol in our table of meanings, and then run that meaning/command on our tape. We’ll come back to that macro at the end, but let’s start with the easier ones and move up:

  • + just needs to increment the tape cell by 1, and since we’re already on it, we just use vim’s built in command to increment the next number in the line, ^A
  • - similarly just decrements the number on the current line using ^X, the opposite of ^A
  • > moves to the next tape cell. Since we have one cell per line with the current position marked by `c, we just move down a line (j) and update `c (mc)
  • <, similarly moves to the previous cell, so we just move up a line (k) and update `c (mc)
  • ] is finally a little more complex. It ends a looping construct, so it needs to change the program counter. It goes to the location of the program counter (`b), jumps to the matching [ delimiter (%), and then decrements the program counter (hmbmb), so that the next instruction is the start of the loop. Note that we need to run mb twice to change the mark b to a different character on the same line. The first mb deletes the mark instead of moving it, since this same line was the old location of the mark.
  • [ is the companion to ] that’s a little more complex and trick since it needs to actually check a conditional. See the first section of this post for an explanation of how it works.

Our macro on line 3 does exactly that every time we call it, so each call to that macro is one step on the machine. This works by moving to mark `b (`b), yanking the character into register "a ("ayl), jumping to mark `a (`a), starting a search (/), and then pasting in register "a (^R^Ra^M)^[note that ^R means “hold down control and hit R”], going to the next word (W), yanking into register "a the rest of the line ("ay$) which contains the macro to run, then moves to the tape 'c, runs the relevant command @a, and then moves mark `b one character to the right (`blmbmb). Remember, if you couldn’t follow any of that, vim’s :h is very good!