Two Guys Arguing

subtraction

Posted in bf by youngnh on 04.18.09

in bf, subtracting one element’s value from another is dead simple. to subtract the value of y in cell 1 from the value of x in cell 0, starting from cell 0:

>[<->-]

this type of subtraction is useful for dealing with numerical values, but doesn’t help much when we need to compare numbers. I’d like to be able to tell if x is greater than y. Subtraction seems to be the natural operation for this. Just subtract y from x and loop if x is positive. This, however, only works when we can be assured that y is less than or equal to x, in which case, our comparison is probably moot. Negative numbers, of course are considered boolean true, so what we really want is a separate subtraction operation that won’t make x any less than 0.

this isn’t too hard to write in C:

while(x && y) {
  x--; y--;
}

there is no && statement in bf, but a pair of nested whiles would do as well:

while(x) {
  while(y) {
    x--; y--;
  }
}

which very easily translates into bf:

[>[-<-]]

There is a problem with this loop, though. It doesn’t have a consistent exit point. If x is greater than y, the loop will exit with the pointer at y’s location. If y is greater than x, then the loop will exit with the pointer at x’s location. To remedy this, we need to establish a fixed point to “rewind” to.

If we establish a 0 in cell 0 as our “anchor”, then put x in cell 1 and y in cell 2, after we finish subtracting y from x, we can “rewind” back to our anchor cell for a consistent starting and end point.

>[>[-<-]]<[<]>

bookkeeping

Posted in bf by youngnh on 04.16.09

bf has a tendency to push the maximum limit of Things I Can Hold In My Head At One Time.

Keeping track of where a variable\’s value is located takes up the bulk of a bf programmer\’s mental bookkeeping. Heck, a quarter of the language\’s syntax ( < and >) is devoted to updating what the current pointer is looking at. bf doesn\’t have any syntactic notion of variables, but it is impossible for me not to assign a cell\’s location some \”reason\” for existing in my program. Variables, in my head, are usually named along the lines of that reason.

Another note, cells in bf hold only numbers, much like every computer; it is simply how you choose to interpret those numbers that makes reasoning about computation simpler or harder. For the most part, I\’ve interpreted bf numbers as one of only three distinct types:

integers, which need no conversion and are usually 8 bits in size and signed
characters, in which the number actually corresponds to an ASCII value
booleans, where the number 0 represents false and any other integer, true

Lets look at some code. A succinct bit of bf is doubling a number. In bf, it might look like this:

++++++  initialize cell 0 to 6
[       while cell 0 is not 0
>++     move to cell 1 and add 2
<-]     move back to cell 0 and decrement

Notice that since bf code only consists of 8 distinct characters, any others including whitespace are considered comments and thrown away, so you can mix plain text comments anywhere in a bf program that you\'d like.

Here cell 0 acts both as the value we are doubling and the index counter for the loop. We decrement it once each time through the loop until it is zero. The doubled result now resides in cell 1, NOT cell 0 where it began life. This is a universally common pattern in bf. Data is its own counter. Unlike the way that most programmers think about memory references — esp. array elements — data is always moving around in bf.

There are two ways to deal with this, accept that data moves around and update where your program will thenceforth look for that variable\'s value, or copy the doubled value back to its original cell. The second approach takes another seven characters of bf, minimum, to achieve, while the first approach takes no extra characters, but diligent and correct bookkeeping on the part of the programmer.

Or, if you are a programmer, then, inevitably, the program you\'ve created to do this for you.

pathological programming

Posted in bf by youngnh on 04.10.09

My post count is slipping.  I’m too worried about writing long, polished entries with a point to them, when what I’m generally working on is short, scatterbrained and only interesting to me for short periods of time.  So, who wants to ride bikes?

The shiny object of my current attention is the brainfuck language.  That’s actually its name, but I’ll be referring to it in polite company as bf.  A few weeks ago, while lamenting to myself the fact that I haven’t entered a horse in the Lambda Lounge Shootout race, I decided that its far too easy to write readable code in a well-established, if not widely used language.  Nevermind that this was the entire spirit of the shootout — to expose developers to how real software is written in other languages — I decided that I was going to attempt to write it in a pathological language.

How pathological?  bf is based around a 30,000 element array and 8 operators.

+ – > < . , [ ]

+ increments the value of the current array element
- decrements the value of the current arrayelement
> increments the current array index pointer
< decrements the current array index pointer
. prints out the value of the current array element
, stores one character of input in the current array element
[ marks the start of a loop
] marks the end of a loop

Loops can be arbitrarily nested and start execution of their bodies if the current array element is zero. When the ending ] is reached, the execution will loop only if the current array element is non-zero.

That’s it.  No strings, no if statements, no methods, no threads, no concurrency, no objects.  It has zero of the features that language presentations at Lambda Lounge have focused on. The language is Turing complete though, so theoretically, any computable function can be expressed in bf.  I intend to put that assumption to the test this coming month.

Follow

Get every new post delivered to your Inbox.