brainfuck
A Brainfuck compiler: it turns a program into the bytecode of the Vader VM and runs it, in memory.
examples/brainfuck in the repository.
// Brainfuck → Vader VM compiler.
//
// Reads a `.bf` source file, writes the program as `.virt` text (the bytecode's
// textual form, with named labels for its loops), reads it back into a module
// with `parse_virt_bc`, and runs it through `exec_fn()`, all in memory: no
// intermediate file, no subprocess.
//
// Memory model :
// - One i32[] local holds the cell tape, grown lazily : it starts as a
// single zero cell and `>` appends a fresh zero whenever the pointer
// walks past the current end. BF's tape is conceptually infinite, so
// there's no point materialising a fixed 30000 cells up front: only the
// cells a program actually visits get allocated.
// - One i32 local holds the data pointer (cell index).
// - BF cells are bytes: `+` and `-` wrap at 256, which programs written for
// the classic implementation count on.
//
// I/O goes through the C library, which the VM reaches by FFI: `.` calls
// `putchar` then `fflush`, and `,` calls `getchar`, all `extern` imports of the
// generated module. Output appears as the program runs, ahead of anything the
// host prints after it, and an interactive program reads its input as it
// arrives (a terminal hands it over a line at a time). At end of input, `,`
// stores 0.
//
// Usage :
// vader run examples/brainfuck path/to.bf # runs a BF program
// vader run examples/brainfuck --dump path/to.bf # prints the `.virt`, runs nothing
// vader run examples/brainfuck --help # lists the options
// vader build --out=bf examples/brainfuck # then ./bf path/to.bf
//
// Programs to run sit in `programs/`
//
// The folder is a project: its `vader.json` reaches the compiler's own modules
// (`vader/vm`, `vader/front/virt`) at the root of the checkout.
//
// Built natively or run by `vader run`, this program embeds the VM : the
// Brainfuck module always runs on it.
module "main"
Cli :: import "cli"
import "std/io"
import "std/iter"
import "std/string"
import "std/string_builder"
import "std/testing"
import "vader/front/virt"
import "vader/vm"
// ---- BF lexer ------------------------------------------------------------
// True for the eight Brainfuck characters. UTF-8 codepoints outside this
// set count as comments and get filtered away by `tokenize_bf`.
is_bf_char :: fn(c: char) -> bool {
return c == '>' || c == '<' ||
c == '+' || c == '-' ||
c == '.' || c == ',' ||
c == '[' || c == ']'
}
// Decode codepoints from `source` and keep the eight BF characters.
tokenize_bf :: fn(source: string) -> char[] = source.chars().filter(is_bf_char).collect()
// ---- bracket matcher -----------------------------------------------------
// For every `[` / `]` token, partner[i] is the index of its match.
// Non-bracket tokens get -1. Mismatched brackets return an empty array
// (caller detects and bails). One linear pass: each entry is pushed as
// `-1` then overwritten on the matching `]`.
match_brackets :: fn(tokens: char[]) -> i32[] {
partner: i32[]: []
open_stack: i64[]: [] // grow-only ; `sp` is the logical top
sp: i64 = 0
for j in 0..<tokens.len() {
partner.push(-1)
if tokens[j] == '[' {
if sp == open_stack.len() {
open_stack.push(j)
} else {
open_stack[sp] = j
}
sp += 1
} else if tokens[j] == ']' {
if sp == 0 {
return []
}
sp -= 1
open_idx :: open_stack[sp]
partner[open_idx] = i32(j)
partner[j] = i32(open_idx)
}
}
if sp != 0 {
return []
}
return partner
}
// ---- module emitter ------------------------------------------------------
// The program is written as `.virt` text : the module declares the cell type
// (`type 0`, an `i32`) and the tape type (`type 1`, an array of it), imports
// `putchar` (import 0), `getchar` (import 1) and `fflush` (import 2), and holds
// one function `bf_main` whose locals are
// 0 = mem (the lazily-grown cell tape)
// 1 = ptr (the current data pointer / cell index)
// 2 = byte (what the last `,` read)
//
// Each instruction's text block closes two columns left of its lines, which
// keeps them indented as the body of `bf_main`.
// Append the `.virt` lines of one Brainfuck instruction, the `idx`-th of the
// program, to `sb`. `partner` pairs each bracket with its match.
emit_bf_char :: fn(sb: StringBuilder, c: char, idx: i64, partner: i32[]) -> void {
match c {
// Move right, and grow the tape when the pointer steps past its end. The
// pointer moves one cell at a time, so it reaches the end exactly when a
// new cell is due : while ptr < the tape length the cell exists already.
'>' -> {
sb.append(move_pointer(1))
sb.append("""
block \$grow_${idx} void
local.get 1
local.get 0
array.len
i32.lt
br_if \$grow_${idx}
local.get 0
i32.const 0
array.push 1
end \$grow_${idx}
""")
}
'<' -> sb.append(move_pointer(-1))
'+' -> sb.append(add_to_cell(1))
'-' -> sb.append(add_to_cell(-1))
// Write the cell under the pointer, which `fflush(NULL)` sends on at once.
'.' -> sb.append("""
local.get 0
local.get 1
array.get 1
call.import 0
drop
i64.const 0
call.import 2
drop
""")
// Read a byte into the cell. `getchar` answers a negative value at end
// of input, which the cell reads as 0.
',' -> sb.append("""
call.import 1
local.tee 2
i32.const 0
i32.lt
if \$eof_${idx} void
i32.const 0
local.set 2
end \$eof_${idx}
local.get 0
local.get 1
local.get 2
array.set 1
""")
// Open a loop, left at once when the cell is zero.
'[' -> sb.append("""
block \$exit_${idx} void
loop \$back_${idx} void
local.get 0
local.get 1
array.get 1
i32.const 0
i32.eq
br_if \$exit_${idx}
""")
// Jump back to the matching `[`.
']' -> {
open_idx :: partner[idx]
sb.append("""
br \$back_${open_idx}
end \$back_${open_idx}
end \$exit_${open_idx}
""")
}
// Any other char : not a BF instruction (tokenize_bf already filters
// these out, so reaching this arm signals a contract violation).
_ -> assert(false, "char '${c}' not handled by emit_bf_char")
}
}
// The lines that move the data pointer by `delta` cells.
move_pointer :: fn(delta: i32) -> string = """
local.get 1
i32.const ${delta}
i32.add
local.set 1
"""
// The lines that add `delta` to the cell under the pointer, wrapping at 256.
add_to_cell :: fn(delta: i32) -> string = """
local.get 0
local.get 1
local.get 0
local.get 1
array.get 1
i32.const ${delta}
i32.add
i32.const 255
i32.bitand
array.set 1
"""
// Compile a Brainfuck program into the `.virt` text of a runnable module.
//
// `tokens` are the program's instructions and `partner` their bracket pairing
// (`match_brackets`), which must be complete.
compile_brainfuck :: fn(tokens: char[], partner: i32[]) -> string {
sb :: StringBuilder {}
// mem = [0] : the tape starts as a single zero cell and grows on demand as
// `>` walks past its end (see emit_bf_char), so only the cells a program
// touches are ever allocated. ptr = 0.
sb.append("""
module brainfuck
type 0 scalar i32
type 1 array 0
import 0 extern putchar bf\$putchar (i32) -> i32
import 1 extern getchar bf\$getchar () -> i32
import 2 extern fflush bf\$fflush (i64) -> i32
export main 0
fn 0 bf_main () -> void
local mem ref
local ptr i32
local byte i32
array.new 1 0
local.set 0
local.get 0
i32.const 0
array.push 1
i32.const 0
local.set 1
""")
for idx in 0..<tokens.len() {
emit_bf_char(sb, tokens[idx], idx, partner)
}
sb.append("""
return
end
""")
return sb.to_string()
}
// The compiled program, prepared for a run, or the message saying why it cannot
// run. `compile_brainfuck` writes every line, so either failure is its bug.
load_program :: fn(text: string) -> VmState | string {
module :: parse_virt_bc(text)
if module is VirtParseError {
return display_virt_parse_error(module, "brainfuck", "<compiled program>")
}
state :: prepare(module)
if state is VerifyError {
return "brainfuck: the compiled program is malformed: ${display_verify_error(state)}"
}
return state
}
// ---- entry point ---------------------------------------------------------
// The one-line description `--help` opens with.
SUMMARY :: "run a Brainfuck program on the Vader VM"
// The flags the command line accepts, ahead of the program's path.
FLAGS :: [
Cli.FlagSpec {
.name = "dump",
.help = "print the compiled `.virt` instead of running it",
.kind = .Bool,
},
Cli.FlagSpec {
.name = "help",
.help = "print this help",
.alias = "h",
.kind = .Bool,
},
]
// What `--help` prints, and what a command line naming no program gets.
help_text :: fn() -> string =
Cli.render_program_help("brainfuck", "[options] <program.bf>", SUMMARY, FLAGS)
main :: fn(argv: string[]) -> i32 {
args :: Cli.parse(argv[1..<argv.len()], FLAGS)
// `--help` outranks a mistyped flag next to it.
if Cli.bool_flag(args, "help") {
print(help_text())
return 0
}
if args.errors.len() > 0 {
for e in args.errors {
eprintln("brainfuck: ${e}")
}
return 1
}
if args.positionals.len() == 0 {
eprint(help_text())
return 1
}
path :: args.positionals[0]
src :: read_file_string(path)
if src is Error {
eprintln("brainfuck: cannot read ${path}")
return 1
}
tokens :: tokenize_bf(src)
partner :: match_brackets(tokens)
if tokens.len() > 0 && partner.len() == 0 {
eprintln("brainfuck: ${path} has unmatched `[` or `]`")
return 1
}
text :: compile_brainfuck(tokens, partner)
// Printed before it is read back, so a program that does not parse shows.
if Cli.bool_flag(args, "dump") {
print(text)
return 0
}
state :: load_program(text)
if state is string {
eprintln(state)
return 1
}
result :: exec_fn(state, "bf_main")
if result is Trap {
eprintln("brainfuck: vm trap: ${result.message}")
return 1
}
return 0
}
// ---- tests ----------------------------------------------------------------
@test
test_compile_brainfuck_passes_the_verifier :: fn() -> void {
tokens :: tokenize_bf("+[>,.<-]")
state :: load_program(compile_brainfuck(tokens, match_brackets(tokens)))
if state is string {
fail(state)
}
}Hello World!