Please also refer to my blog posts related to this project.

Beautiful algorithms used in a compiler and a stack based virtual machine

• Part 1. Design of the Monkey compiler
• Part 2. How a pratt parser in Monkey compiler works
• Part 3. How to compile global bindings
• Part 4. How to compile functions
• Part 5. What Monkey does not have, but Java has

Monkey Compiler In Go

About this project

This is a compiler and a virtual machine of the Monkey programming language. The design overview of this project is described here.

As a guide of this project, I referenced these two books written by Thorsten Ball.

• Writing An Interpreter In Go
• Writing A Compiler In Go

(back to top)

Getting Started

How to build and run

$ go build .
$ go run .

How to test

$ go test ./...

(back to top)

Project History

In this project, Monkey was first implemented as an interpreter. Then, it has been updated to a compiler. Both of them are REPL style.

v1.0. Monkey Interpreter

The first version of Monkey was a tree walking interpreter.

PR#1 ~ PR#15 are the processes of implementation, where the lexer, the parser, and the evaluator are implemented. The algorithm used in the parser in documented here.

v2.0. Monkey Compiler

The second and the latest version of Monkey is a bytecode compiler and virtual machine. The previous version has been refactored and converted into this version in PR#16 and later.

The algorithms used for compiling and executing local variables are documented here, and those for functions are here.

(Appendix) Benchmarking of the interpreter vs. the compiler

Here is the benchmark testing of the interpreter version and the compiler version. The snippet below is executed by each of them.

let fibonacci = fn(x) {
  if (x == 0) {
    0
  } else {
    if (x == 1) {
      return 1;
    } else {
      fibonacci(x-1) + fibonacci(x-2)
    }
  }
}

fibonacci(35)

The result reveals that the compiler version is more than 3 times as performant as the interpreter version.

# the interpreter version
$ go run benchmark/main.go -engine=eval
engine=eval, result=9227465, duration=37.105657782s

# the compiler version
$ go run benchmark/main.go -engine=vm
engine=vm, result=9227465, duration=11.787990726s

(back to top)

Contributing

If you have a suggestion that would make this project better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Some possible improvements are listed here. Don't forget to give the project a star! Thanks again.

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

(back to top)