In the previous post, I announced my implementation of Writing an Interpreter in GO (plus the Lost Chapter (Macros)) and Writing a Compiler in GO: the MonkeyLang.jl package.
Now, I want to announce some advancements I have made in the past few days.
Performance
When I first finished the compiler part, the traditional fib(35) benchmark shows that the VM version ran 3x slower than the evaluator version, which was surprising.
After some invaluable discussion with @jdad and @c42f, I found out the main cause was the use of abstract Ref{Int}. After refactoring them to mutable struct + Int, the VM version was 3x faster than the evaluator version, which was about the same as GO.
Some minor performance improvements have also been made, which I will not cover here.
The CLI
By using PackageCompiler.jl, MonkeyLang.jl can now be compiled to a standalone CLI executable monkey. Hope you will enjoy it.
New Features
More inspiring are the new features, which are not implemented in the original GO version.
At first, my main goal was to implement a while loop. The lexer + parser part was not so hard. But after that, I realized that to make a while loop useful, I need to implement one more thing: mutable variables.
I refactored the parser to support two different types of LetStatements (maybe I should have renamed it to AssignStatement), one with let (define a new variable), and the other without let (modify an existing variable).
On the evaluator side, things were easy since the scopes were handled elegantly by nested Environments. However, on the compiler side, the current design cannot fully support my requirements. I wanted a while statement to create a new scope, while it could modify the variables in outer scopes (so that the condition might evaluate to false after some loops). But we only had OpSetLocal and OpSetGlobal, which were not sufficient. Implementing OpSetFree on basis of the current OpGetFree was not hard, but that still could not meet my need.
In the final design, I made a while statement whose body is a special Closure and is called repeatedly if the condition remains true. This special Closure is different from normal Closures in that it does not capture free variables in a FreeScope and stores them, instead, it captures free variables in an OuterScope and stores the pointers to them. Here, a pointer (called SymbolPointer in my implementation) has three properties, the nested level, the scope of the original symbol, and the index of the original symbol. I further implemented OpGetOuter and OpSetOuter, which have three operands each. When we need to get or set an outer symbol, we use the level information to go back to the end - level-th frame, and fetch the information there.
And my final achievement can be revealed in the following example:
The Julia version:
x = 5
y = 0
while x > 0
global x, y
x = x - 1
z = 5
function f()
w = 1
while z > 0
w = w * 2
y = y + z * w
z = z - 1
f()
end
end
f()
end
println(y)
And the Monkey version:
let x = 5;
let y = 0;
while (x > 0) {
x = x - 1;
let z = 5;
let f = fn() {
let w = 1;
while (z > 0) {
w = w * 2;
y = y + z * w;
z = z - 1;
f();
}
}
f();
}
puts(y);
They both output 150. Amazing!
The Monkey version can be run with the CLI with:
./monkey run test.mo --vm(VM version) or./monkey run test.mo(evaluator version)