How Factor implements closures

The recent blog post from the Clozure CL team on Clozure CL's implementation of closures inspired me to do a similar writeup about Factor's implementation. It is often said that "closures are a poor man's objects", or "objects are a poor man's closures". Factor takes the former view, because as you will see they are largely implemented within the object system itself.

Quotations

First, let us look at quotations, and what happens internally when a quotation is called. A quotation is a sequence of literals and words. Quotations do not close over any lexical environment; they are entirely self-contained, and their evaluation semantics only depend on their elements, not any state from the time they were constructed. So quotations are anonymous functions but not closures.

Internally, a quotation is a pair, consisting of an array and a machine code entry point. The array stores the quotation's elements, and when you print a quotation with the prettyprinter, this is how Factor knows what its elements are:

( scrachpad ) [ "out.txt" utf8 [ "Hi" print ] with-file-writer ] .
[ "out.txt" utf8 [ "Hi" print ] with-file-writer ]

The machine code entry point refers to a code block in the code heap containing the quotation's compiled definition.

The call generic word calls quotations. This word can take any callable, not just a quotation, and has a method for each type of callable. The callable class includes quotations, as well as curry and compose which are discussed below. This means that closure invocation is implemented on top of method dispatch in Factor.

For reasons that will become clear in the last section on compiler optimizations, most quotations never have their entry points called directly, and so it would be a waste of time to compile all quotations as they are read by the parser.

Instead, all freshly-parsed quotations have their entry points set to the lazy-jit-compile primitive from the kernel.private vocabulary.

The call generic word has a method on the quotation class. This method invokes the (call) primitive from the kernel.private vocabulary. The (call) primitive does not type check, since by the time it is called it is known that the input is in fact a quotation. This primitive has a very simple machine code definition:

mov eax,[esi]    ! Pop datastack
sub esi,4
jmp [eax+13]     ! Jump to quotation's entry point

Note that the quotation is stored in the EAX register; this is important. Recall that initially, a quotation's entry point is set to the lazy-jit-compile word, and that all quotations initially share this entry point.

This word, which is not meant to be invoked directly, compiles quotations the first time they are called. Since all quotations share the same initial entry point, it needs to know which quotation invoked it. This is done by passing the quotation to this word in the EAX register. The lazy-jit-compile word compiles this quotation, sets its entry point to the new compiled code block, and then calls it again. On subsequent calls of the same quotation, the new compiled definition will be jumped to directly, and the lazy-jit-compile entry point is not involved.

If you're interested in the definition of lazy-jit-compile, search for it in these files:

• basis/cpu/x86/32/bootstrap.factor
• basis/cpu/x86/64/bootstrap.factor
• basis/cpu/ppc/bootstrap.factor

The curry and compose words

curry

The curry word is the fundamental constructor for making closures. It takes a value and a callable, and returns something that prints out as if it were a new quotation:

( scratchpad ) 5 [ + 2 * ] curry .
[ 5 + 2 * ]

This is not a quotation though, but rather an instance of the curry class. Instances of this class are pairs of elements: an object, and another callable.

Instances of curry are callable, because the call generic word has a method on curry. This method pushes the first element of the pair on the data stack, then recursively calls call on the second element.

Calls to curry can be chained together:

( scratchpad ) { "a" "b" "c" } 1 2 [ 3array ] curry curry map .
{ { "a" 1 2 } { "b" 1 2 } { "c" 1 2 } }

Note that using curry, many callables can be constructed which share the same compiled definition; only the data value differes.

Technically, curry is just an optimization -- it would be possible to simulate it by using sequence words to construct a new quotation with the desired value prepended, but this would be extremely inefficient. Prepending an element would take O(n) time, and furthermore, result in the new quotation being compiled the first time the result was called. Indeed, in some simpler concatenative languages such as Joy, quotations are just linked lists, and they execute in the interpreter, so partial application can be done by using the cons primitive for creating a new linked list.

compose

The compose word takes two callables and returns a new instance of the compose class. Instances of this class are pairs of callables.

( scratchpad ) [ 3 + ] [ sqrt ] compose .
[ 3 + sqrt ]

As with curry, the call generic word has a method on the compose class. This method recursively applies call to both elements.

It is possible to express the effect of compose using curry and dip:

: my-compose ( quot1 quot2 -- compose )
    [ [ call ] dip call ] curry curry ; inline

The main reason compose exists as a distinct type is to make the result prettyprint better. Were it defined as above, the result would not prettyprint in a nice way:

( scratchpad ) [ 3 + ] [ sqrt ] [ [ call ] dip call ] curry curry .
[ [ 3 + ] [ sqrt ] [ call ] dip call ]

The curry and compose constructors are sufficient to express all higher-level forms of closures.

An aside: compose and dip

It is possible to express compose using curry and dip. Conversely, it is also possible to express dip using compose and curry.

: my-dip ( a quot -- ) swap [ ] curry compose call ;

Here is an example of how this works. Suppose we have the following code:

123 321 [ number>string ] my-dip

Using the above definition of my-dip, we get

123 321 [ number>string ] swap [ ] curry compose call  ! substitute definition of 'my-dip'
123 [ number>string ] 321 [ ] curry compose call       ! evaluate swap
123 [ number>string ] [ 321 ] compose call             ! evaluate curry
123 [ number>string 321 ] call                         ! evaluate compose
123 number>string 321                                  ! evaluate call
"123" 321                                              ! evaluate number>string

Fry syntax

The fry syntax provides nicer syntax sugar for more complicated usages of curry and compose. Beginners learning Factor should start with fry syntax, and probably don't need to know about curry and compose at all; but this syntax desugars trivially into curry and compose, as explained in the documentation.

Lexical variables

Code written with the locals vocabulary can create closures by referencing lexical variables from nested quotations. For example, here is a word from the compiler which computes the breadth-first order on a control-flow graph:

:: breadth-first-order ( cfg -- bfo )
    <dlist> :> work-list
    cfg post-order length  :> accum
    cfg entry>> work-list push-front
    work-list [
        [ accum push ]
        [ dom-children work-list push-all-front ] bi
    ] slurp-deque
    accum ;

In the body of the word, three lexical variables are used; the input parameter cfg, and the two local bindings work-list and accum.

When the parser reads the above definition, it creates several quotations whose bodies reference local variables, for example, [ accum push ]. Before defining the new word, however, the :: parsing word rewrites this into concatenative code.

Suppose we were doing this rewrite by hand. The first step would be to make closed-over variables explicit. We can do this by currying the values of accum and work-list onto the two quotations passed to bi:

:: breadth-first-order ( cfg -- bfo )
    <dlist> :> work-list
    cfg post-order length  :> accum
    cfg entry>> work-list push-front
    work-list [
        accum [ push ] curry
        work-list [ [ dom-children ] dip push-all-front ] curry bi
    ] slurp-deque
    accum ;

And now, we can do the same transformation on the quotation passed to slurp-deque:

:: breadth-first-order ( cfg -- bfo )
    <dlist> :> work-list
    cfg post-order length  :> accum
    cfg entry>> work-list push-front
    work-list accum work-list [
        [ [ push ] curry ] dip
        [ [ dom-children ] dip push-all-front ] curry bi
    ] curry curry slurp-deque
    accum ;

Note how three usages of curry have appeared, and all lexical variable usage now only occurs at the same level where the variable is actually defined. The final rewrite into concatenative code is trivial, and involves some tricks with dup and dip.

A lexical closure closing over many variables will be rewritten into code which builds a long chain of curry instances, essentially a linked list. This is less efficient than closure representations used in Lisp implementations, where typically all closed-over values are stored in a single array. However in practice this is not usually a problem, because of optimizations outlined below.

Mutable local variables

Mutable local variables are denoted by suffixing their name with !. Here is an example of a loop that counts a mutable variable up to 100:

:: counted-loop-test ( -- )
    0 :> i!
    100 [ i 1 + i! ] times ;

Factor distinguishes between binding (done with :>) and assignment (done with foo! where foo is a local previously declared to be mutable). At a fundamental level, all bindings and closures are immutable; code using mutable locals is rewritten to close over a mutable heap-allocated box instead, and reads and writes involve an extra indirection. The previous example is roughly equivalent to the following, where we use an immutable local variable holding a mutable one-element array:

:: counted-loop-test ( -- )
    { 0 } clone :> i
    100 [ i first 1 + i set-first ] times ;

For this reason, code that uses mutable locals does not optimize as well, and iterative loops that uses mutable local variables can run slower than tail-recursive functions which uses immutable local variables. This might be addressed in the future with improved compiler optimizations.

Optimizations

Quotation inlining

If after inlining, the compiler sees that call is applied to a literal quotation, it inlines the quotation's body at the call site. This optimization works very well when quotations are used as "downward closures", and this is why most quotations never have their dynamic entry point invoked at all.

Escape analysis

Since curry and compose are ordinary tuple classes, any time some code constructs instances of curry and compose, and immediately unpacks them, the compiler's escape analysis pass can eliminate the allocations entirely.

The escape analysis pass has no special knowledge of curry and compose; it applies an optimization intended for object-oriented code.

Again, this helps optimize code with "downward closures", with the result that most usages of curry and compose will never allocate any memory at run time.

For more details, see my blog post about Factor's escape analysis algorithm.