An introduction to programming in BF

Writing a program in BF requires some planning, just as it used to be with machine language programming, but with the help of some macros it is not that hard. We will see that values will be copied arround between memory locations a lot, so some bookkeeping of which values are stored where and which memory locations are free, is needed.

For the description of the eight elementary BF commands, read the introduction page.

Moving, copying, and adding

The most simple program is the program zero, which makes a positive value in the current memory location zero, and it looks like: 
  [-]
(Of course, it is rather arbritrary what you call most simple. A program consisting of just a single BF command is even simpler than the above program. But in some way, I feel you can hardly call such a program a program.) The next "most simple" program consist of "moving" a positive or zero value from a memory location to the next memory location. With "moving" we mean that afterwards, the current location has become zero, and the next is increased with the original value from the current location. It looks like: 
  [ > + < - ]
(While the value in the current memory location is still larger than zero, move to the next memory location, increment this one, move back, and decrement the current location.)

To move a value from a given source location to a given destination location, the program consists of:

Lets to(m) stand for moving the memory pointer to location m, and move(s,d) for the above program, then we can write: 
  move(s,d) = to(s) [ to(d) + to(s) - ]
We can even make this more readable if we would define for(a) and next(a) as follows: 
  for(a) = to(s)[
  next(a) = to(s)-]
  move(s,d) 
  = for(s) 
      to(d) + 
    next(s)
Likewise, we could define a program which moves the value from one location to two locations, as follows: 
  move2(s,d1,d2) 
  = for(s)
      to(d1) +
      to(d2) +
    next(s)-]
Now what if we would like to copy the value from a location into another location? The solution is simple, just move it to that location and some temporary location, and then move the value from the temporary location back to its original location. The copy program can be described with: 
  copy(s,d,t) = move2(s,d,t) move(t,s)
You can think yourself of a smart way of copying a value from one location to two other locations. In all the above examples we have silently assumed that the destination location contained the value zero. What if it did not? Exactly, then we would not have been moving and copying, but adding to the value already present.

Multiplying and powers

The simplest form of multiplying, is multiplying with two, which is just adding a number with its self. The program which moves and doubles a value from a given location into another is simply: 
  double(s,d) = move2(s,d,d)
This program assumes that the destination location d contains zero at the start of the program, and causes the source location s to become zero. Many of the following programs will follow this convention that the output locations are considered to be zero, and that the input locations are zeroed.

If the notation constant(n) stands for the program which addes the constant n to the current memory location, that we can describe multiplying with a constant as: 

  multiplyconst(s,d,n)
  = for(s)
      to(d) constant(n)
    next(s)
As multiplying can be seen as repeated adding, it is also very simply to see, how two numbers can be multiplied. 
  multiply(s1,s2,d,t)
  = for(s1)
      copy(s2,d,t)
    next(s1)
    zero(s2)
To raise a number to a certain power, is not so complicated, as raising to a certain power, is nothing else than repeated multiplication: 
  power(x,p,d,t1,t2)
  = to(d) +
     for(p)
        times(x,d,t1,t2)
        move(t1,d)
     next(p)
     zero(x)
Dividing however, is a whole different story, far beyond an introductionary course.

If-then-else

A program without control structures is not a real program. So, now lets focus on control structures. One important control structure, the for-next loop, we already introduced above. An if-statement can be seen as a for statement that is being executed once. We introduce the following macros for representing the if and the endif (together with the zero operation, which sets a memory location to zero): 
  zero(a) = to(a) [-]
  if(a) = to(a) [
  endif(a) = zero(a) ]
In principle each if-then-else statement can be written as two if-statements where the condition for the second if-statement is whether the first condition was not true. To implement this, we need an temporary memory location, which is set to one on for hand, and set to zero in the then part of the statement. The idea is used in the following set of macros for the if-then-else statement: 
  ifelse(a,t) = inc(t) if(a) dec(t)
  else(a,t) = endif(a) if(t)
  endelse(t) = endif(t)
Note that the last macro can also be defined as: 
  endelse(t) = dec(t) ]

The logical operations

For logical values, we will used the same assumption as the C programming language: zero means false, all values larger than zero mean true. The logical-or operations is really simple with our definition of logicals, because it can be implemented using the move operation. It is defined with the following macro: 
  or(s1,s2,d) = move(s1,d) move(s2,d)
To implement the logical-and operation we need an if-statement. It is defined with the following macro: 
  and(s1,s2,d) = if(s1) move(s2,d) endif(s1) zero(s2)
The zero(s2) is needed to clear s2 in case s1 is zero.

For the logical-not operation the same trick as with the if-then-else statement can be used. See the following macro: 

  not(s,d) = inc(d) if(s) dec(d) endif(s)

Comparing values

How to compare values? One way of comparing two number is to decrement both of them until one of them has become zero. If the other has become zero as well, than the numbers are equal, otherwise the non-zero number is the larger one. The following routine will decrement numbers until one of the two (or both) have become zero: 
  substractMinimum(x1,x2,t1,t2,t3) =
     copy(x1,t1) copy(x2,t2)
     and(t1,t2,t3)
     [
       zero(t3)
       dec(x1) dec(x2)
       copy(x1,t1) copy(x2,t2)
       and(t1,t2,t3)
     ]
(Note that the above definition does return the results in x1 and x1.) With this we can define all the comparison operations, as follows: 
  notEqual(x1,x2,d,t1,t2) = substractMinimum(x1,x2,d,t1,t2) or(x1,x2,d)     
  Equal(x1,x2,d,t1,t2) = NotEqual(x1,x2,t1,d,t2) not(t1,d)
  Greater(x1,x2,d,t1,t2) = substractMinimum(x1,x2,d,t1,t2) zero(x2) move(x1,d)     
  Less(x1,x2,d,t1,t2) = substractMinimum(x1,x2,d,t1,t2) zero(x1) move(x2,d)     
  GreaterOrEqual(x1,x2,d,t1,t2) = inc(x1) Greater(x1,x2,d,t1,t2)
  LessOrEqual(x1,x2,d,t1,t2) = inc(x2) Less(x1,x2,d,t1,t2)
Although the above substractMinimum looks rather short, it is not very sort when expanded completely. The following variant is shorter: 
  substractMinimum(x1,x2,t1,t2,t3) =
     for(x1)
        copy(x1,t1)
        ifelse(t1,t2)
          dec(x1)
        else(t1,t2)
          inc(t3)
        endelse(t2)
     next(x1)
     move(t3,x1)

Comparing with small constants

Of course, the above definitions can be used to compare a number with a small constant, but there is a more efficient way to do this. In order to test if a number is zero, the previously defined logical not-operation can be used. A number is equal to one, if it is larger than zero, and equal to zero when substracted with one. Likewise, a number is equal to two, if it is larger than zero, and equal to one when substracted with one. This leads to the following definitions: 
  isZero(s,d) = not(s,d)
  isOne(s,d) = if(s) dec(s) isZero(s,d) endif(s)
  isTwo(s,d) = if(s) dec(s) isOne(s,d) endif(s)
  isThree(s,d) = if(s) dec(s) isTwo(s,d) endif(s)
  ....

Constants

To add a constant to a certain memory location, one can simply use the required number of '+' symbols. However for large constants this results in very long programs. To avoid this one can make use of multiplication or powers. To read more about how to make big constants efficiently, read the page Big numbers in BF.

Arrays

There is no limit to the number of memory locations that can be used by BF programs using the constructs described above. There is only one more thing needed to be able to calculate whatever one would like to calculate, and that is arrays. An array is a collection of memory locations which can be addressed through an index stored in some other memory location. (Yes, arrays are needed to show that BF is Turing-complete.)

Below we show how a number of arrays with unlimited size can be realized. On forhand we have to decide how many of these arrays we need, and where they start. All memory locations above the one where they start are reserved for the arrays, and cannot used for any other usage. We basically, need two procedures: one for getting a value from an array, and one for setting a value in an array. Both procedures have five parameters:

Now the procedures for setting and getting a value, are defined as follows: 
  setarray(b,n,a,i,v)
  = copy(i,b+1,b)
    copy(v,b+2,b)
    for(b+1)
       move(b,b+n+3)
       move(b+1,b+n+4)
       move(b+2,b+n+5)
       right(n+3) 
       inc(b)
    next(b+1)
    zero(a)
    move(b+2,a)
    for(b)
       left(n+3)
       move(b+n+3,b)
    next(b)

  getarray(b,n,a,i,v)
  = copy(i,b+1,b)
    for(b+1)
       move(b,b+n+3)
       move(b+1,b+n+4)
       right(n+3) 
       inc(b)
    next(b+1)
    copy(a,b+1,b+2)
    for(b)
       left(n+3)
       move(b+n+3,b)
       move(b+n+4,b+1)
    next(b)
    move(b+1,v,b)
In which the expression right(n) represent n times the '>' symbol, and in which the expression left(n) represent n times the '<' symbol.