The Mendicant Bug

I mentioned the esoteric programming language brainfuck a little while back. It consists of 8 operations and was created in order to make the smallest compiler in the world (I think the current best is 174 bytes). I was reading a post over on Good Math, Bad Math that defines arithmetic in terms of sets. Pretty basic if you’ve done anything with set theory, but Mark has a clear way of explaining things so I usually try to read all of his posts. I’ve been playing catch-up today.  It struck me immediately how closely the set form that Mark describes matches the syntax/logical structure of brainfuck.  So I decided to play around a little.  Read on for more.

Anyhow, his explanation for the construction of addition is as follows. Given that we have ordered pairs of the form (x,y) — see his post for a more formal definition of this — we can define the function of addition as a mapping of the ordered pair (x,y) to z according to the following rules:

1. if x = 0, z = y
2. if y = 0, z = x
3. else, let x’ = successor(x) and let y’ = predecessor(y). z = Add(x’, y’)

This is arithmetic for the natural numbers and in a previous post he showed that every number except 0 has a predecessor and every number has a successor. So basically addition is the process of decrementing y until it reaches zero while incrementing x. For example, Add(3,4) =

• Add(4,3)
• Add(5,2)
• Add(6,1)
• Add(7,0)

At which point rule 2 fires and z = x = 7. So in brainfuck, we would have the following program for adding two numbers:

,>,[-<+>]<.

This reads in two numbers (,>,), decrements the second until it reaches zero while incrementing the first ([->+<]) and then outputs the first number(<.).

Multiplication is similarly defined, with the rules being:

• if x = 0, z = 0
• if y = 0, z = 0
• else z = Add(y, Mult(predecessor(x),y))

This is more complicated because we have a nested function and brainfuck lives up to its name. So the solution I came up with was to copy the value of x into another variable and then decrement the temp variable for x while incrementing the solution and the original variable again. Then loop over this y times.

,>,[<[->>+<<]>>[->+<<<+>>]<-]>>.

The pseudocode for this is

1. read in x and y
2. while y > 0:
   1. while x > 0:
      1. decrement x
      2. increment temp_x
   2. while temp_x > 0:
      1. decrement temp_x
      2. increment z
      3. increment x
   3. decrement y
3. output z