Lox

Implementation of the Lox language in OCaml, comprised of a front-end compiler and an interpreter, in roughly 1KLOC !

Big thanks to Bob Nystrom!! You're amazing.

No further work is expected to happen on this project as it is feature-complete. The implementation is not optimal but still useful as a learning material.

Quickstart

Assuming ocaml (version 4.08.1) and opam are installed and setup:

$ opam install .
$ lox run test/hello_world.lox
hello, world

$ printf 'print 4 * 3 - 1;' | lox run
11

$ lox repl
> 1+1;
2.
> ^C

# The last field of an AST node is an internal unique id
$ echo "print 1 + 2;" | lox dump ast
((Print (Binary (Literal (Number 1) 1) Plus (Literal (Number 2) 2) 3) 4))

Implemented

Numbers, strings, booleans, nil
Comments
Number arithmetic
Statements & print
Variables (scope based)
Conditions (if/else)
Boolean logic (and, or, not)
Loops (while, for)
All errors are reported with line and column number
Functions (including recursion, closures)
Object-oriented programming (classes, single inheritance)
Shebang
"Native" functions:
- clock()
- readLine()
- parseNumber()
Basic static analysis:
- Return statement outside of a function body e.g return 1;
- Variables assigned to themselves e.g var a = a;
- Same-scope variable shadowing e.g var a = 1; var a = 2;
- Unused variables, functions, and function arguments

Example:

fun fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 2) + fibonacci(n - 1);
}
for (var i = 0; i < 20; i = i + 1) {
  print fibonacci(i);
}

Example of objects:

class Breakfast {}

class BreakfastBuilder {
    init() {
        this.breakfast = Breakfast();
    }

    withEggs(eggNumber) {
        this.breakfast.eggNumber = eggNumber;
        return this;
    }

    withToasts(toastNumber) {
        this.breakfast.toastNumber = toastNumber;
        return this;
    }

    build() {
        return this.breakfast;
    }
}

var breakfast = BreakfastBuilder().withEggs(2).withToasts(5).build();
print breakfast.eggNumber;
print breakfast.toastNumber;

Test

Requires GNU parallel

make test

You can opam install patdiff for a better output, by default it uses diff.

Docker

$ make docker
$ docker run -it lox

Better REPL experience

lox repl works out of the box with the GNU Readline library if you have it installed:

rlwrap lox repl will provide command history for free.

Major differences with the official implementation

Variable resolution does not distinguish between local/global variables. In practices it means that mutally recursive functions in the global scope are not allowed
Stricter static analysis, e.g referring to undefined variables (will fail at compile time in some cases instead of at runtime)