Factor/Implementation history

Factor was originally implemented in Java. The first Java Factor versions were interpreted only. The interpreter would iterate over a Quotation, pushing literals on the stack and executing Words. The interpreter would invoke itself recursively and there was no Tail call optimization, Continuations or support for Reflection of the call stack.

JFactor was rewritten to use a Stack-less design. This enabled the interpreter to have continuations and tail call optimization but incurred a performance hit.

A Java bytecode Compiler was introduced for JFactor alongside the Interpreter. Only words with a static Stack effect were compiled; at the time, this excluded words which used continuations. The compiler supported self-tail-calls (like Clojure) but not general tail call optimization.

In mid-2004, a new runtime for Factor was developed, replacing the Java code with a mix of Factor and C. The first native Factor releases used a stack-less interpreter much like JFactor.

A simple compiler was added to native Factor. Initially it only did a few optimizations, such as inlining and Defunctionalization.

The Optimizing compiler grew more sophisticated over time, with new optimization passes and support for additional architectures added. At some point, Factor gained the ability to save compiled code in the image, instead of recompiling everything on startup.

Quotations became a first class type. Instead of traversing a list of Cons cells, the interpreter would iterate over an array.

The interpreter was replaced by a non-optimizing Subroutine-threading compiler. The Stack checker also learned about Continuations and so the Optimizing compiler began to able to compile code which used them. Effectively, the Stack-less philosophy was now applied to compiled code. The major challenge in implementing this was the reification of native call stack frames into a continuation object.

The Non-optimizing compiler subsequently went through several iterations. The latest improvement is that certain primitives are expanded inline. Since the only time when a large amount of non-optimized code runs is during bootstrap, further improvements to the non-optimizing compiler will be conservative and only considered if they improve bootstrap time.

Almost all implementation effort can now be focused on the Optimizing compiler.

More information:

This revision created on Tue, 23 Mar 2010 08:45:39 by slava