bf #
A programming language that is reminiscent of a Turning machine.
There is a tape and a pointer to that tape. The tape holds data, and its infinite to right. Each position on the tape is initialized to a 0.
00000000000000000...
^
Each position holds a single byte. The tapehead starts at the very most left position.
The program is a sequence of characters. The legal characters are
+ // ++*ptr
- // --*ptr
> // ++ptr
< // --ptr
[ // while(ptr) {
] // }
, // scanf(" %c", ptr)
. // putchar(*ptr)
where ptr is current pointer to the tape in C.
An example program may look like
[.>.<,>,]
Note: Square braces must be properly nested.
Each position on the tape is a char in C, so values may overflow from 127 to -128 if incremented.
When you use the , command, the values read from stdin are ASCII values.
The language is considered Turing complete, because it has the same expressive power as a Turing machine.
Input/output #
If your program is the input symbol followed by the output symbol:
,.
and you input the 1 key, the tape will look like
49 0 0 0 0 0 ...
^
and a 1 will be printed.
Looping #
The [] characters essentially construct a while loop where the pointer is the check.
This looks like a while loop in C:
while (*ptr) // [
{
} // ]
The loop can be optimized by checking the boolean on the end bracket ], and either go back to the [ symbol, or just move forward and be done.
A program to calculate a sum #
If we want to add \( 2 + 3 \) , we can read in each value to a tape cell, so our tape looks like this:
2 3 0 0 ...
So lets start by reading the 2 characters in from input:
. read
> move right
. read
[ while not 0
- decrement c0
> move right
+ increment c1
< move left
]
< move left
. print result
After this runs, the tape will look like
5 0 0 ...
So if we run this program with the input $% and the tape will be
36 37 0 0 ...
and after the program complete it will look like this:
73 0 0 0 ...
and an I will print out.
A bf interpreter in Java
#
import java.nio.file.Files;
import java.nio.file.Paths;
import java.io.IOException;
public class Bf {
public static void main(String[] args) throws IOException {
String program;
byte[] data = new byte[30000];
int didx = 0;
int pidx = 0;
try {
program = Files.readString(Paths.get("bf.txt"));
program = program.replaceAll("[^-+<>,\\.\\[\\]]","");
}
catch (Exception e) {
System.out.println("Could not read bf.txt.");
return;
}
while (pidx < program.length()) {
char pc = program.charAt(pidx);
if (pc=='+')
data[didx] += 1;
else if (pc=='-')
data[didx] -= 1;
else if (pc=='>')
didx += 1;
else if (pc=='<')
didx -= 1;
else if (pc=='.')
System.out.print((char)data[didx]);
else if (pc==',')
data[didx] = (byte)System.in.read();
else if (pc==']' && data[didx]!=0) {
int balance=1;
do {
pidx -= 1;
if (program.charAt(pidx)=='[')
balance -= 1;
if (program.charAt(pidx)==']')
balance += 1;
} while (program.charAt(pidx)!='[' || balance!=0);
} else if (pc=='[' && data[didx]==0) {
int balance=1;
do {
pidx += 1;
if (program.charAt(pidx)=='[')
balance += 1;
if (program.charAt(pidx)==']')
balance -= 1;
} while (program.charAt(pidx)!=']' || balance!=0);
}
pidx += 1;
}
System.out.println();
System.out.println("Program complete!");
for (int i=0; i<10; i++)
System.out.print(data[i] + " ");
System.out.println();
System.out.println("didx=" + didx);
}
}
It is traditional to have the tape be 30,000 cells long, all initialized to 0.
didx is the data pointer.
pidx is a pointer to the source program.