Efficient partial function application (aka compiled curry)

Note: the code described here is not in darcs yet, but will make it there within the new few days after I fix a few residual bugs.

Ever since quotations became a first-class data type, Factor has had a curry word:

  3 [ + ] curry .
[ 3 + ]

This is essentially a partial function application. (I'm aware that currying and function application is not the same, but this word was named before I was aware of that fact, and anyway, curry reads better than papply or partial.)

Previously, this was an expensive word to use. Not only did it allocate a new quotation and copy the existing quotation's elements, but words which called quotations produced by curry did not compile, and had to run in the interpreter; this is due to the compiler's design, which "lifts" all quotations up to their call site.

Now, this has all changed. For interpreted code, curry now runs in constant time, not linear time proportional to the quotation's length, because it allocates a small object holding the object together with the quotation. These objects are instances of a curry class, but they print like quotations and are equal to quotations having the same elements, so they're essentially identical:

3 [ + ] curry [ 3 + ] = .
  t

When a curried quotation is called by call in the interpreter, the VM simply pushes the curried object first, then calls the quotation.

In compiled code, we can do even better now. The compiler knows about curry and applies a rewrite rule to the dataflow graph. Essentially, it replaces all occurrences of curry's output value with a pair of values, being the object and quotation; it also "widens" all stack shuffling from the point where the curry is created to where it is called. If the curry is passed to an ordinary word, the compiler inserts a real call to curry which allocates memory; however, the key idea behind this rewrite rule is that curry instantiation is "lazy", and is not done at all if the curry is simply passed downward to a combinator.

For example, consider this example:

: foo ( x y -- x' y' ) 3 [ + ] curry 2apply ;

This word adds 3 to the top two stack elements. The compiler first inlines the 2apply word:

: foo ( x y -- x' y' ) 3 [ + ] curry tuck >r >r call r> r> call ;

Now it applies the rewrite rule:

: foo ( x y -- x' y' ) 3 [ + ] abc--bcabc >r >r >r call r> r> r> call ;

The compiler represents stack shuffles in symbolic form, internally; I'm writing abc--bcabc to mean a shuffle with that effect, for which no word exists in the library.

Now, it lifts the quotation up to the call site:

: foo ( x y -- x' y' ) 3 [ + ] abc--bcabc >r >r >r drop + r> r> r> drop + ;

Finally, it removes the literal value [ + ], since it is now dead; it travels around the stack without ever being used for anything, and is dropped:

: foo ( x y -- x' y' ) 3 ab--bab >r >r + r> r> + ;

So in this case, the compiler will produce the exact same code for the following two snippets:

3 [ + ] curry 2apply
3 tuck >r >r + r> r> +

While [ + ] curry 2apply is not a useful thing to write, since the direct expansion is simpler, it does demonstrate how the compiler is able to remove the object allocation from this code.

So, curry is efficient now, both in the interpreter and compiler. But what does this mean?

The role played by curry here is somewhat like a Lisp lambda which closes over one free variable. We can use curry to package up a bunch of values, pass them to the combinator, and fiddle with them from inside a quotation. Until now, you either had to pay a performance penalty for using curry, or you would use stack juggling tricks. For example, consider the each and 2each combinators. Here is the current implementation:

: (each) ( seq quot i -- seq quot i )
    [ rot nth-unsafe swap call ] 3keep ; inline

: each ( seq quot -- )
    over length [ (each) ] repeat 2drop ; inline

: (2each) ( quot seq seq i -- quot seq seq i )
    [ 2nth-unsafe rot dup slip ] 3keep ; inline

: 2each ( seq1 seq2 quot -- )
    -rot 2dup min-length [ (2each) ] repeat 3drop ; inline

Here is an implementation using curry:

: (each) ( seq quot -- n quot' )
    >r [ length ] keep r>
    [ >r nth-unsafe r> call ] 2curry ; inline

: each ( seq quot -- )
    (each) each-integer ; inline

: (2each) ( seq1 seq2 quot -- n quot' )
    >r [ min-length ] 2keep r>
    [ >r 2nth-unsafe r> call ] 3curry ; inline

: 2each ( seq1 seq2 quot -- )
    (2each) each-integer ; inline

Note that each-integer is the new version of repeat, with a slightly altered stack effect.

In the old code, the quotation passed to repeat has to manually save and restore various values that it needs; now that curry is efficient, we just package those values up with the quotation before passing it along to each-integer.

It is somewhat ironic that while Factor is as "concatenative" language, until now concatenating quotations together was discouraged, at least where performance was important! But now, we can easily write an efficient compose word which takes a pair of quotations:

: compose [ >r call r> call ] 2curry ; inline

For example,

[ 2 2 ] [ + ] compose .
  [ [ 2 2 ] [ + ] >r call r> call ]

It is pretty clear that this quotation has the same effect when called as [ 2 2 + ]. The difference between compose, which only works on quotations and produces a funny result, and append, which works on all sequences, is that since compose is built from curry, it runs in O(1) time, and the compiler is able to eliminate its runtime cost altogether.

For example, consider the assoc-each combinator. It is implemented in terms of the assoc-find combinator, since assoc-find is the only primitive combinator each assoc instance must implement. On each iteration, we want to call the quotation, but always output f, forcing assoc-find to continue the iteration until the end. Formerly, assoc-each was implemented as follows. First, we had a utility word, assoc-find-with, which called assoc-find while retaining a parameter on the stack. It was in implemented using a assoc-with word which was also used for assoc-each-with, and so on:

: assoc-with 2swap [ >r -rot r> call ] 2keep ; inline

: assoc-find-with ( obj assoc quot -- key value ? )
    swap [ assoc-with rot ] assoc-find
    >r >r 2nip r> r> ; inline

: assoc-each ( assoc quot -- )
    swap [ rot call f ] assoc-find-with 3drop ; inline

This is ugly as hell, and essentially boilerplate. Here is the new way:

: assoc-each ( assoc quot -- )
    [ f ] compose assoc-find 3drop ; inline

That's it; no need to define -with words, and no unnecessary stack shuffling. We exploit the "concatenative" nature of Factor here -- composition of sequences is the same as composition of functions!

Which brings me to the next topic; all the "manually curried" combinators you know and love, such as each-with, map-with, and so forth, have been moved to a deprecated vocabulary. They're going away soon. Updating code is easy.

swap [ swap XYZ ] each-with  ===  [ XYZ ] curry each
[ XYZ ] each-with  ===  [ XYZ ] curry* each

Same for map-with, subset-with, and so on. The curry* word is just partial application on the second stack element; it is defined in terms of curry.

All the sequence and assoc combinators have been greatly simplified. In fact, I was able to move the 2swap word out of the core and into extra/shuffle; stack shuffling has been simplified by curry to such an extent that in particular, 2swap is simply not needed anymore. Other more complex shuffle words such as roll and pick are used less frequently now, as well.

By lowering the cost of an abstraction, I was able to simplify code by a non-trivial amount. There's a general theme here: the goal of a compiler is to make idiomatic code run fast. It is not good enough to only accelerate hand-unrolled, tuned code chock-full of irrelevant detail and declarations. Nobody wants to write unnecessarily complex code just to please the compiler.