For the description of the eight elementary BF commands, read the introduction page.
[-](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:
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(a)[ next(a) = to(a)-] 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.
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.
times(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,t3) = to(d) + for(p) copy(x,t1) times(d,t1,t2,t3) move(t2,d) next(p) zero(x)Dividing however, is a whole different story, far beyond an introductionary course.
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) ]
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)
subtractMinimum(x1,x2,t1,t2,t3) = copy(x1,t1,t3) copy(x2,t2,t3) and(t1,t2,t3) to(t3) [ zero(t3) dec(x1) dec(x2) copy(x1,t1,t3) copy(x2,t2,t3) and(t1,t2,t3) to(t3) ](Note that the above definition does return the results in x1 and x2.) With this we can define all the comparison operations, as follows:
notEqual(x1,x2,d,t1,t2) = subtractMinimum(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) = subtractMinimum(x1,x2,d,t1,t2) zero(x2) move(x1,d) Less(x1,x2,d,t1,t2) = subtractMinimum(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 subtractMinimum looks rather short, it is not very sort when expanded completely. The following variant is shorter:
subtractMinimum(x1,x2,t1,t2,t3) = for(x1) copy(x2,t1,t2) ifelse(t1,t2) dec(x2) else(t1,t2) inc(t3) endelse(t2) next(x1) move(t3,x1)
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) ....
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:
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.