Bfmacro: a bf macro-interpreter

Bf (which I prefer to call "BrainFried" because I would really like to keep my job as a professor:) is one of the world's simplest Turing-complete languages, consisting of 8 operators: "+-<>[].,". At the time of this writing, many excellent resources have been made available for people wishing to program in bf... for a start, see Frans Faase's excellent introduction to programming in bf. That page inspired this page, because I decided that his macro language was worthy of implementation. Thus bfmacro was born.

Installation and Use

Bfmacro is a Perl 5.8 script that implements Faase's macro-interpreter. It is freely available and you are encouraged to modify it for your needs and redistribute it as you wish. It is available for download here. You can learn most of what you need to know about bfmacro at Faase's site. The things I will document here are the builtins that Faase does not use, as well as the unusual features of bfmacro that Faase did not describe in his pages.

To use bfmacro, download the script from the above link and edit the first line to point to the pathname of a copy of Perl (5.6 and above). Then, in UNIX/Linux/MacOSX/Cygwin, one types:

 
bfmacro file.bfm >file.bf
to process the file file.bfm (consisting of macros, comments, and bf code) and produce the file file.bf. When invoking bfmacro this way, macros are expanded with comments describing the expansion. To remove those comments, type
 
bfmacro -na file.bfm >file.bf
to produce a pretty-printed version of bf code without annotations (-na). The generated code will be identical in either case, and comments will be copied through to file.bf in both cases.

Subtleties of bfmacro builtins

The best possible introduction to the macros in bfmacro has already been written in Faase's pages. However, there are some subtleties of the macro interpreter that are documented here.

  1. Macro arguments can be constant symbols or numeric constants in decimal, hexadecimal, or ASCII. Constant symbols can have explicitly defined values or will default to cell offsets that are not the value of any other constant.
     
    A=5; 
    
    will set the constant A to 5, which has the side effect of not setting any other undefined constant to that value. Likewise, one can say
     
    B=0xf; 
    
    to set the constant B to hexadecimal 0xf (decimal 15) or say
     
    C='C'; 
    
    to set the constant C to ASCII 'C'. For example, to print "hello", one can write:
     
    plus('h').>plus('e').>plus('l')..>plus('o')
    
    where the builtin plus(X) appends X +'s to the output and > selects a new data cell (initialized to 0).
  2. Unbound symbolic constants are automatically bound to non-conflicting values greater than zero, so that unbound constants point to unique memory locations. Binding is done in lexical order of appearance of the unbound symbols. For example, in the code:
     
    A=1; B=3; set(C,'a') set(D,E) 
    
    the following bindings will be made automatically:
     
    C=2; D=4; E=5; 
    
    Of course, you may always utilize numeric constants or explicitly define all symbolic constants in order to override this behavior.
  3. Expressions of constants, e.g., 2*X+5, are not supported in this version of bfmacro; sorry.
  4. As on Faase's pages, the macro to(X) (where X is a symbolic constant or a value) moves the data pointer to data[X]. It is important to note, however, that it is easy for the programmer to make it impossible for to(X) to be properly interpreted, by any operation that potentially loses track of the location of the data pointer. This is true in any case where a loop is unbalanced, e.g.
     
    [>]
    
    where the number of '<'s and '>'s does not match within '[' and ']'. After such a loop, there is no way that the interpreter can reliably predict the current location of the data pointer (this is equivalent to the halting problem!) so that invocations of to(X) are treated as syntax errors, until the next invocation of at(X) to tell the interpreter where the data pointer is.
  5. at(X) informs the interpreter (after an unbalanced loop) of the true location of the data pointer. Often, the programmer knows this location, but the interpreter cannot infer it. For example, consider the following bfm code:
     
    to(1)+++>++>+[<]
    
    After this fragment, data has values 0,3,2,1 and the pointer is at data[0], but bfmacro does not know this. To resume use of to(X), one must tell the interpreter this fact via at(0). After that, to(X) can be used again.
  6. Four builtins save typing of long strings of symbols:
    1. plus(X) appends X +'s to the output.
    2. minus(X) appends X -'s to the output.
    3. left(X) appends X <'s to the output.
    4. right(X) appends X >'s to the output.
    In all cases, X can be 0, resulting in no output.
  7. Note that in this version, it is an error to utilize a non-argument symbolic constant in a macro. All symbols used in contained macros must be arguments, and argument strings must exactly match in length between macro and invocation. This is done to promote good programming style.

Macro Syntax

Here's a simple EBNF declaration of macro syntax ('^' means the empty string):
 
program ::= statements | statements statement ; 
statement ::= macro | define | opcode | comment ; 
comment ::= ( '!' | '#' )  chars "\n" ; 
opcode ::= '+' | '-' | '<' | '>' | '.' | ',' | '[' | ']' ; 
macro ::= identifier '(' args ')' ; 
args ::= ^ | args ',' arg; 
arg ::= identifier | number ; 
define ::= macro '=' stream ';' | identifier '=' number ';'
stream ::= ^ | macro | stream macro ; 

Macro Definitions

The entire macro set for the current version is documented below.
 
! builtins

! to(X)
! preconditions:  X is a non-negative integer; 
!                 no unbalanced loops encountered in the code so far, 
!                 or at(X) used after last unbalanced loop to anchor pointer. 
! postconditions: data pointer points to X 
! notes: Interpreter does not allow use of to(X) after an unbalanced loop
!        (e.g., [<]) unless there is an at(X) statement between the loop
!        and the to(X) in lexical scope. 

! at(X)
! preconditions:  X is a non-negative integer. 
! postconditions: presumes that data pointer is currently X, even if it is not, 
!                 for purposes of to(X). Essentially an 'origin' statement. 
! notes: One can use this to 'lie' about the data pointer, for the purposes of 
!        choosing a new 'origin' (0) for data. 

! plus(X)
! preconditions:  X is a non-negative integer. 
! postconditions: X +'s are appended to code. 
! notes: One can use ascii by enclosing in '', e.g. 'A'. 
!        One program for printing "hi" is 
!        zero(X) plus('h') . zero(X) plus('i') .

! minus(X)
! preconditions: X is a non-negative integer. 
! postconditions: X -'s are appended to the code. 

! left(X)
! preconditions: X is a non-negative integer. 
! postconditions: X <'s are appended to the code. 
! notes: tracks location; does not interfere with use of to(X)

! right(X)
! preconditions: X is a non-negative integer. 
! postconditions: X >'s are appended to the code. 
! notes: tracks location; does not interfere with use of to(X)

! number constructors

zero(X)  = to(X)[-] ; 
! preconditions:  X is a non-negative integer. 
! postconditions: pointer at X, data[X] is 0. 

one(X)   = to(X)[-]+ ; 
! preconditions:  X is a non-negative integer. 
! postconditions: pointer at X, data[X] is 1. 

inc(X)   = to(X)+ ; 
! preconditions:  X is a non-negative integer. 
! postconditions: pointer at X, data[X] is 1 greater than before. 

dec(X)   = to(X)- ; 
! preconditions:  X is a non-negative integer. 
! postconditions: pointer at X, data[X] is 1 less than before. 

set(X,Y) = zero(X) plus(Y) ; 
! preconditions:  X,Y are non-negative integers. 
! postconditions: pointer at X, data[X] is Y%256

! simple iteration 
for(X)   = to(X)[ ;
next(X)  = to(X)-] ; 
! usage: for(X) ...text... next(X)
! preconditions:  X is a non-negative integer. 
! postconditions: text is executed for decreasing values of X, not 
!                 including 0. 

! while 
while(X) = to(X)[ ;
wend(X)  = to(X)] ;
! usage: while(X) ...text... wend(X)
! preconditions:  X is a non-negative integer. 
! postconditions: text is executed while X remains non-zero. 

! moving and copying 
move(X,Y)      = for(X) to(Y) + next(X) ;
! preconditions:  X and Y are non-negative integers. 
! postconditions: data[Y]+=data[X]; data[X]=0.
! note: when unambiguous, I will identify each variable X with 
! a data location, writing Y+=X; X=0 instead of the above. 

move2(X,Y,Z)   = for(X) to(Y) + to(Z) + next(X) ; 
! preconditions:  X,Y,Z are non-negative integers. 
! postconditions: Y+=X; Z+=X; X=0; 

copy(S,D,T)    = move2(S,D,T) move(T,S) ;
! preconditions:  S,D,T are non-negative integers. 
! postconditions: D+=S; S+=T; T=0; 

! if-endif
if(X)          = to(X)[ ; 
endif(X)       = zero(X)] ; 
! usage: if(X) ...text... endif(X)
! preconditions:  X is non-negative integer
! postconditions: text between if and endif are executed if X != 0; X=0.

! if-then-else 
ifelse(X,T)    = one(T) if(X) zero(T) ; 
else(X,T)      = endif(X) if(T) ;
endifelse(X,T) = endif(T) to(X) ;
! usage: ifelse(X,T) ...text1... else(X,T) ...text2... endifelse(X,T)
! preconditions:  X is non-negative integer, text1 does not change T
! postconditions: if X is nonzero, text1 is executed, else text2 is executed.
!                 X=0, T=0

! logic 
tobool(S,D)    = zero(D) if(S) one(D) endif(S) ;
! preconditions: S and D are non-negative integers. 
! postconditions D=bool(S), 1 if S>0, 0 if S==0. 
! notes: consistently, I have erred on the side of simplicity; 
!        boolean functions are 1 and 0, as in C. 

not(S,D)       = one(D) if(S) zero(D) endif(S) ;
! preconditions:  S and D are non-negative integers. 
! postconditions: D=!S, 1 if S==0, 0 if S>0. 

or(S1,S2,D)    = zero(D) if(S1) one(D) endif(S1) if(S2) one(D) endif(S2) ; 
! preconditions:  S1,S2,S are non-negative integers 
! postconditions: D=S1 || S2; 0 if both are 0, 1 if either is nonzero. 
!                 S1=0, S2=0, d=S2.

and(S1,S2,D)   = zero(D) if(S1) tobool(S2,D) endif(S1) zero(S2) ; 
! preconditions:  S1,S2,S are non-negative integers 
! postconditions: D=S1 && S2; 0 if either is 0, 1 if both are nonzero. 
!                 S1=0, S2=0, d=S2

! comparison 
subtractMinimum(X1,X2,T1,T2,T3) =
  zero(T3) copy(X1,T1,T3) copy(X2,T2,T3) and(T1,T2,T3) to(T3)
  [ dec(X1) dec(X2)
    zero(T3) copy(X1,T1,T3) copy(X2,T2,T3) and(T1,T2,T3) to(T3)
  ] ;
! preconditions:  X1,X2,T1,T2,T3 are non-negative integers. 
!                 T1,T2 are 0. 
! postconditions: if X1>X2 then X1=X1-X2, X2=0, T1=T2=T3=0 
!                 if X1<X2 then X1=0, X2=X2-X1, T1=T2=T3=0 
!                 if X1==X2 then X1=X2=T1=T2=T3=0 

notEqual(x1,x2,d,t1,t2) = subtractMinimum(x1,x2,d,t1,t2) or(x1,x2,d); 
! preconditions:  x1,x2,d,t1,t2 are non-negative integers 
! postconditions: d=(x1!=x2); x1=x2=t1=t2=0

Equal(x1,x2,d,t1,t2) = notEqual(x1,x2,t1,d,t2) not(t1,d); 
! preconditions:  x1,x2,d,t1,t2 are non-negative integers 
! postconditions: d=(x1==x2); x1=x2=t1=t2=0

Greater(x1,x2,d,t1,t2) = subtractMinimum(x1,x2,d,t1,t2) zero(x2) move(x1,d); 
! preconditions:  x1,x2,d,t1,t2 are non-negative integers 
! postconditions: d=(x1>x2); x1=x2=t1=t2=0

Less(x1,x2,d,t1,t2) = subtractMinimum(x1,x2,d,t1,t2) zero(x1) move(x2,d); 
! preconditions:  x1,x2,d,t1,t2 are non-negative integers 
! postconditions: d=(x1<x2); x1=x2=t1=t2=0

GreaterOrEqual(x1,x2,d,t1,t2) = inc(x1) Greater(x1,x2,d,t1,t2); 
! preconditions:  x1,x2,d,t1,t2 are non-negative integers 
! postconditions: d=(x1>=x2); x1=x2=t1=t2=0

LessOrEqual(x1,x2,d,t1,t2) = inc(x2) Less(x1,x2,d,t1,t2); 
! preconditions:  x1,x2,d,t1,t2 are non-negative integers 
! postconditions: d=(x1<=x2); x1=x2=t1=t2=0

! multiplication 
times(s1,s2,d,t) = for(s1) copy(s2,d,t) next(s1) zero(s2); 
! preconditions:  s1,s2,d,t are non-negative integers 
! postconditions: d=s1*s2; s1=s2=t=0

! powers 
power(x,p,d,t1,t2) =
  to(d) +
  for(p)
    times(x,d,t1,t2)
    move(t1,d)
  next(p)
  zero(x); 
! preconditions: x,p,d,t1,t2 are non-negative integers 
! postconditions: d=x^p, x=p=t1=t2=0 

double(S,D) = move2(S,D,D); 
! preconditions: S,D are non-negative integers 
! postconditions: D+=S*S, S=0

! I/O
input(X) = to(X) , ; 
output(X) = to(X) . ; 

An advanced example: divide

In Frans Faase's pages, divide is left as an advanced exercise. That it is, and I utilized bfmacro to code it, as follows:
 
! divide Numerator by Denominator, 
! produce Quotient and Remainder; 
! use and zero temporaries T1,T2,T3
divide(Numerator,Denominator,Quotient,Remainder,T1,T2,T3) = 
  zero(Quotient) zero(Remainder) 
  ! main loop: repeatedly subtract one from Remainder=Denominator  
  ! and Numerator until one is 0; stop when Numerator is 0
  copy(Denominator,Remainder,T1) 
  subtractMinimum(Numerator,Remainder,T1,T2,T3) 
  ! until nothing left in Numerator
  while(Numerator) 
    ! add one to Quotient 
    inc(Quotient)  
    ! try again to subtract Denominator from Numerator
    copy(Denominator,Remainder,T1) 
    subtractMinimum(Numerator,Remainder,T1,T2,T3) 
  wend(Numerator)
  ! at this point, there are two states 
  !  Remainder!=0: Quotient is ok, Remainder=Denominator-Remainder
  !  Remainder==0: need Quotient++, one extra increment.
  copy(Remainder,T1,T2) 
  ifelse(T1,T2) ! remainder nonzero
    for(Remainder) dec(Denominator) next(Remainder) 
    move(Denominator,Remainder) 
  else(T1,T2) 
    inc(Quotient)
    zero(Denominator) 
  endifelse(T1,T2) ; 

mod(Number,Modulus,Result,T1,T2,T3,T4) =
  divide(Number,Modulus,T1,Result,T2,T3,T4) 
  zero(T1) ; 

X=0; Y=1; result=2; remainder=3; 
set(X,20) set(Y,5) divide(X,Y,result,remainder,T1,T2,T3)
Putting this into divide.bfm and invoking
 
bfmacro -na divide.bfm >divide.bf
produces
[-]++++++++++++++++++++>
[-]+++++>
[-]>
[-]<<
[>>+>+<<<-]>>>
[<<<+>>>-]>>
[-]<<<<<<
[>>>>+>>+<<<<<<-]>>>>>>
[<<<<<<+>>>>>>-]<<<
[>>+>+<<<-]>>>
[<<<+>>>-]
[-]<<
[>>
 [-]<
 [>
  [-]+<
  [-]
 ]<
 [-]
]>
[-]>
[<<<<<<->>>->>>
 [-]<<<<<<
 [>>>>+>>+<<<<<<-]>>>>>>
 [<<<<<<+>>>>>>-]<<<
 [>>+>+<<<-]>>>
 [<<<+>>>-]
 [-]<<
 [>>
  [-]<
  [>
   [-]+<
   [-]
  ]<
  [-]
 ]>
 [-]>
]<<<<<<
[>>+<
 [>>+>+<<<-]>>>
 [<<<+>>>-]>>
 [-]<<<<<<
 [>>>>+>>+<<<<<<-]>>>>>>
 [<<<<<<+>>>>>>-]<<<
 [>>+>+<<<-]>>>
 [<<<+>>>-]
 [-]<<
 [>>
  [-]<
  [>
   [-]+<
   [-]
  ]<
  [-]
 ]>
 [-]>
 [<<<<<<->>>->>>
  [-]<<<<<<
  [>>>>+>>+<<<<<<-]>>>>>>
  [<<<<<<+>>>>>>-]<<<
  [>>+>+<<<-]>>>
  [<<<+>>>-]
  [-]<<
  [>>
   [-]<
   [>
    [-]+<
    [-]
   ]<
   [-]
  ]>
  [-]>
 ]<<<<<<
]>>>
[>+>+<<-]>>
[<<+>>-]
[-]+<
[>
 [-]<<
 [<<->>-]<<
 [>>+<<-]>>>
 [-]
]>
[<<<+<
 [-]>>>>
 [-]
]<