Named local variables and lexical closures in Factor

I previously wrote about adding named parameters to Factor as an extension library. Well, now I've beefed up this code with support for lexical closures, and threw it in extra/locals.

Hopefully, this module can now replace the less efficient rewrite-closures library by Eduardo Cavazos.

Here is an example word using locals:

:: add-test | x y z | x y + z + ;
1 2 3 add-test .
  6

The syntax is simple; to define a word which uses locals, you use :: instead of :. Then you follow the word name with a list of locals enclosed in | characters, and use these locals anywhere in the body of the word.

Closure conversion is performed:

:: map-test | seq inc | seq [ inc + ] map ;
{ 10 20 } 5 map-test .
  { 15 25 }

Here, we're using the "inc" local inside the quotation passed to map. The :: word performs all the necessary rewriting to make this work. The key to making this efficient is compiled curry.

You can also define lambdas, which are like quotations except inputs are placed in local variables:

:: map-test | seq inc | seq [| elt | elt inc + ] map ;
{ 10 20 } 5 map-test .
  { 15 25 }

The lambda [| elt | elt inc + ] is equivalent to the quotation [ inc + ], and in both cases closure conversion is performed by the :: word.

Lambdas can be used in normal colon definitions, too:

: foo-bar 1 2 [| x y | x y * ] lambda call ;
foo-bar .
  3

The lambda word converts a lambda into code for producing a quotation. If the input to lambda is literal, the code transformation is done at compile time.

So how does the closure conversion actually work? Consider the following code:

[| a b | a [| c | c b + ] map ]

The inner quotation refers to the free variable b. We can rewrite it as follows:

[| a b | a b [| c b | c b + ] curry map ]

That is, we add all free variables to the list of inputs, then fetch these free variables right before pushing the quotation; after the quotation is pushed, we use curry to partially apply the quotation to the free variables. All lambdas and quotations are rewritten this way, as we lift free variables up. In the above example, we have already arrived at a form with no free variables anywhere. Now, we convert to point-free form. This is done in a brute-force way; within a lambda, all locals are stored on the retain stack. Here is the final result of closure conversion applied to the above example:

[
    >r
    >r r>
    r>
    dup
    >r
    >r r>
    dup
    >r
    [ >r >r r> r> dup >r >r r> dup >r + r> drop r> drop ] curry
    map r>
    drop r>
    drop
]

Looks rather complicated, but most of the stack shuffling is optimized away by the compiler.

This vocabulary is not in the darcs repository yet, because it depends on compiled curry, which I'm still in the process of debugging. However, it should work with the latest code from darcs, except words using closures won't compile. I put the code up on LispPaste.

In only 121 lines, I was able to add efficient lexical scoping to Factor. Even though I encourage people to try to express everything in a clean way using the stack only, sometimes locals are handy (complex math formulas, bizarro native APIs taking 11 parameters each, etc). Having more options is always good. Plus, this library makes a great demo of how to extend the language in a radical way without altering the core implementation!