Monkey

A Monkey language AST-walking interpreter and a bytecode-compiled version (running in a custom VM) written in Go. Built following the books Writing an Interpreter in Go and Writing a Compiler in Go.

The project features:

• a lexer with its own token definition and tokenization policies
• an AST producing parser implemented using the top-down Pratt approach
• a tree-walking evaluator with support for a syntactic macro system (Elixir-like).
• a compiler producing custom defined bytecode
• a custom stack-based VM capable of executing Monkey bytecode

All Monkey functionalities are available both in tree-walking and compiled mode. Compiled Monkey is 3 to 4 times faster than interpreted Monkey!!! You can run a sample benchmark (simply runs fib(35) and takes the execution time) typying go run .\benchmark\ -engine=x where x is either vm or eval

What Monkey looks like

Variables (integers/booleans/strings), Arrays and Hash maps

let x = (1 + 3) / 2 * 7  
let name = "Monkey"
let array = [x, name, true]
let dict = {name: 1, 2: x, true: array}

Functions

let fibonacci = fn(x) {
    if (x == 0) {
        0                // Monkey supports implicit returning of values
    } else {
        if (x == 1) {
            return 1;      // ... and explicit return statements
        } else {
            fibonacci(x - 1) + fibonacci(x - 2); // and recursion!
        }
    }
}

Higher-order functions

let map = fn(arr, f) {
    let iter = fn(arr, accumulated) {   // iter is a recursive closure!!
        if (len(arr) == 0) {
            accumulated
        } else {
            iter(rest(arr), push(accumulated, f(first(arr))));
        }
    };

    iter(arr, []);
};

function closures

let add = fn(x) {
    return fn(y) { x + y }
};

let addTwo = add(2);

addTwo(4); // Output : 6

and macros

let unless = macro(condition, consequence, alternative) {
    quote(if (!(unquote(condition))) {
            unquote(consequence);
        } else {
            unquote(alternative);
        });
};

unless(10 > 5, puts("not greater"), puts("greater")); // Output : "greater"

The purpose of this project

This implementation of Monkey is for solely didactic purposes. The implementation makes heavy use of already existing Go objects for language-internal representation without any particular attention paid for optimization. The lexer ignores most of basic things like line numbers, the parser and the evaluator could be much more extended and the syntactic macro system severly lacks in error handling. With that said Monkey is easily extendable and Go garbage collector handles Monkey's garbage too! A compiler and a VM has been added to the project. The shift from AST-walking to bytecode execution improved the performance by a factor from 3 to 4

Try Monkey in the REPL

Simply type go run .\main.go *

You can choose the evaluation engine by specifying the flag -engine=vm for the compiled version or -engine=eval for the AST-walking version

You can view executing timing for each line directly in the REPL and make some nice comparison benchmark between engines.

* REPL is currently implemented with no support for multiline statements/expressions. Might be added in future