A simple bytecode compiler with a fast vm.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Examples
Source
.DS_Store
LICENSE
README.md
TutorialSource.txt

README.md

BytecodeVM

A simple bytecode compiler with a fast vm.

codebeat badge

Design

This was implemented in Swift from the original CPython tutorial (link here). I recommend taking a look at that as it can be easily implemented in many languages and offers a good explanation of how compilers work.

Usage

We will define a simple factorial function.

/*
 func fact(x: Int) -> Int {
     if x == 0 { return 1 }
         return x * fact(x-1)
     }
 }
 fact(5)
 */
let code: Any = [
    ["func", "fact", ["x"],
     ["if", ["==", "x", 0],
      1,
      ["*", "x", ["fact", ["-", "x", 1]]]]
    ],
    ["fact", 5]
]

This is the IR that the compiler will convert to bytecode.

Next we define the helping functions.

func dif(args: [Any]) throws -> Any {
    let vals = args.compactMap { $0 as? Int }
    assert(vals.count == 2)
    return vals[0] - vals[1]
}
func mul(args: [Any]) throws -> Any {
    return args.compactMap { $0 as? Int }.reduce(1, *)
}
func eq(args: [Any]) throws -> Any {
    let vals = args.compactMap { $0 as? CustomStringConvertible }
    assert(vals.count == 2)
    return vals[0].description == vals[1].description ? 1 : 0
}

We can put those functions in an environment.

let environment = Environment(table: [:])
environment.defineFnWithReturn(name: "-", block: dif)
environment.defineFnWithReturn(name: "*", block: mul)
environment.defineFnWithReturn(name: "==", block: eq)

Now we can perform the compilation.

do {
    let compiler = Compiler()
    let bytecode = try compiler.compile(exp: code)
}
catch {
    print((error as! Error).localizedDescription)
}

Finally, add this code to the do block in order to execute.

    let vm = VM()
    if let val = try vm.evaluate(bytecodeInstructions: bytecode, env: environment) {
        print("Result: \(val)")
    }
    print("Environment: \(environment.table)")

Here is the result:

Result: 120
Environment: ["fact": __lldb_expr_10.Function(params: ["x"], body: [loadName("=="), loadName("x"), loadConst(0), callFunction(2), relativeJumpIfTrue(10), loadName("*"), loadName("x"), loadName("fact"), loadName("-"), loadName("x"), loadConst(1), callFunction(2), callFunction(1), callFunction(2), relativeJump(1), loadConst(1)], vm: __lldb_expr_10.VM, env: __lldb_expr_10.Environment), "-": (Function), "==": (Function), "*": (Function)]

Outside Uses

  • Swizzle uses a modified version of this compiler to execute Swizzle code.