burn / docs

The Burn VM

Building a language on bvm

examples/bvm/ember/ember.bn is a complete language on top of bvm, written in Burn: a lexer, a parser, a type checker and a code generator in one file, which builds a bvm module and runs it with the bvm written in Burn (embedding bvm). It shows the pieces every front end needs.

fn fib(n) {
    if n < 2 { return n }
    return fib(n - 1) + fib(n - 2)
}

fn sum(xs: arr) {
    let total = 0
    let i = 0
    while i < len(xs) {
        total = total + xs[i]
        i = i + 1
    }
    return total
}

let squares = []
let i = 0
while i < 10 {
    push(squares, square(i))   # square is a host function provided by the program that runs Ember
    i = i + 1
}
print("squares:", squares, "sum:", sum(squares), "fib(20) =", fib(20))
burn build examples/bvm/ember/ember.bn -o ember
./ember examples/bvm/ember/demo.em
./ember examples/bvm/ember/demo.em --emit-asm demo.bvm -o demo.bvmc

Ember is built as a native executable because bvm calls the C library directly. Hot Ember functions are compiled to machine code by the JIT like Burn's.

1. Decide how values map to words

Ember has three types: int is a 64-bit integer, str is a string object and arr is an [int] array (built-in type id 11). Since the checker knows the type of every expression, the generator can pick the right instruction: Op.IAdd for ints, Op.Rt("StrConcat") for strings, Op.Len for arrays and Op.Rt("StrLen") for strings. A dynamically typed language would instead box values into any with Op.Rt("Box") and use Op.Rt("IsType"), Op.Rt("Cast") and Op.Unbox.

2. Declare functions before generating code

Functions can call each other in any order, so Ember gives every function its index first and records its signature. Calls refer to that index (Op.Call(id)) before the function has any code:

for i in 0..len(funcs) {
    [Ty] tys = []
    for x in funcs[i].params {
        tys.push(x.ty)
    }
    sigs[funcs[i].name] = Sig { id: i, params: tys, ret: funcs[i].ret }
}

3. Variables: locals and globals

Parameters are the first locals, and every let inside a function adds one (Op.Store(slot), Op.Load(slot)). Top-level lets become globals, pushed to m.globals, so functions can read them with Op.GLoad(id).

4. Control flow with labels

Jumps name the index of the instruction they go to, which is not known yet while the code after them is generated. Ember's generator hands out labels, remembers each jump to a label, and fills in the indexes when the function is done (withJumpTarget from compiler/src/vm/module.bn changes the target of a jump):

var start = label()
bind(start)
var end = label()
expectTy(s.cond, Ty.Int)
jump(Op.Jz(0), end)
block(s.body)
jump(Op.Jmp(0), start)
bind(end)

&& and || use Op.JzKeep and Op.JnzKeep, which leave the tested value on the stack as the result when they jump.

5. Keep the stack balanced

The verifier checks that every path reaches an instruction with the same stack height. Expression statements pop their value, and calls to functions without a result still return 0, which must be popped. Every function ends with a return on every path, so Ember appends Op.RetVoid (or Op.Const(0) and Op.Ret) at the end of each one.

6. Use the runtime and the host

Printing is Op.Rt("ToStr") with a type id followed by Op.Rt("Print"). Arrays grow with Op.Rt("ArrPush"). square is an import, added to m.imports as Import { name: "square", argc: 1 } and called with Op.Host(index). Ember provides it when it runs the module:

var square = fun(xs: [int]): int {
    return wrappingMul(xs[0], xs[0])
}
var prog = prepare(module, [HostFn { name: "square", argc: 1, call: square }])
if (prog.error != "") {
    eprint("error: ${prog.error}")
    exit(1)
}
runEntry(prog)

7. Point errors at the source

Ember adds a location for every instruction that can fail ("demo.em:12" pushed to m.locs, its index passed to Op.Index and Op.IDiv), so runtime errors name the Ember line:

runtime error: index 5 out of bounds (length 2)
  --> demo.em:3

From here

  • Records: add a Desc.Record type, then use Op.NewRecord, Op.GetField and Op.SetField.
  • Interfaces or virtual methods: add dispatch tables and call through Op.Dispatch.
  • First-class functions: push Op.FuncRef values and call them with Op.CallInd.
  • Concurrency: Op.Spawn with a future<T> type, then Op.Rt("Await").
  • Shipping: write .bvmc files with encode and run them with the bvm command.