BAK

BAK is an esoteric programming language created by Prfnoff (2000).

A BAK interpreter maintains a modifiable program space consisting of an array of bytes and a stack of program locations.

The program counter is initially at the first byte of the program. The program counter is incremented after each instructions. The entire 13 instructions are given here with a general explanation of their effect (but with no guarantee about the exact order of operands pulled from stack):

$  here   push current location to the stack
:  jump   a -> jump to a
<  min    a, b -> min(a,b)
>  max    a, b -> max(a,b)
;  arith  a, b, c -> a + c - b  
+  input  a, b -> if at EOF, jump to b, else *a = getchar()
-  out    a -> putchar(*a)
@  find   a, b, c -> first location of *a between b and c
=  copy   a, b -> *a := *b
*  dup
/  swap 
\  rot
!  drop

Any byte not among these 13 intruction is a no-op (the program counter is incremented). To end, the program must reach past the end of the data space with an empty stack.

Computational class

Despite the lack of details in the original specification, and despite the reference implementation being written in obfuscated C, actual experiments with the implementation show that the data space can extend past the original program. For instance the following program copies an "a" several bytes past the program end, and outputs it.

$a$$;$..............$*\;*\=-

Although the only non-trivial program ever written in BAK seems to be a version of 99 bottles of beer using nested loops, a direct reuse of techniques used in that program are deemed sufficient to implement small finite state machines such as the 4-state 6-character universal Turing machine described in utm.b. Together with the unbounded data space, this gives an indication that BAK is turing complete.

External resources

• BAK reference manual
• Fromage, BAK, and other Obfuscated Languages (from the Wayback Machine; retrieved on 15 August 2000)
• 99 bottles of beer implemented in BAK