Monday, June 30, 2008

An interesting use-case for the spread combinator

The spread combinator is the least frequently used of any of the cleave family.

Recall that it takes a sequence of quotations, and applies the nth quotation to the nth stack element. So for example,
1 2 3 4 { [ 1 + ] [ 1 - ] [ 2 / ] [ 2 * ] } spread

Leaves us with the following stack:
2 1 1+1/2 8

It is easy to see why it is not used frequently; very rarely do we have 4 items on the stack, and then decide to manipulate each one individually. The bi* and tri* combinators special-case spread for 2 or 3 stack items, respectively; bi* is used pretty often, tri* not so much.

However, it turns out cleave is very useful when meta-programming. Consider this code from the FFI implementation:
: (param-prep-quot) ( parameters -- )
dup empty? [
drop
] [
unclip c-type c-type-unboxer-quot %
\ >r , (param-prep-quot) \ r> ,
] if ;

: param-prep-quot ( node -- quot )
parameters>> [ <reversed> (param-prep-quot) ] [ ] make ;

We traverse a sequence recursively, stopping if it is empty, otherwise we use unclip to break it down into the first element and the of the sequence. We surround the result of the recursive call in a >r/r> pair.

Given something like { "float" "int" "char*" }, this generates code like the following:
utf8 string>alien >r >r >float r> r>

This code was written before spread, and I just discovered that it is a perfect use-case for it:
: (param-prep-quot) ( parameters -- )
c-type c-type-unboxer-quot ;

: param-prep-quot ( node -- quot )
parameters>> [ (param-prep-quot) ] map [ spread ] curry ;

Much more elegant.

This pattern came up in the FFI twice, and I refactored both usages. It also came up in something I'm working on; type declarations for tuple slots. I will blog in detail when this is done, but the basic idea is that you can assert that a tuple slot has a certain type when declaring the tuple class. Storing into the slot will check the type at runtime; the compiler will elide these checks when necessary, and make assumptions about the slot value's type when the slot is read. The boa word, which makes a tuple and fills in the slots from the stack, needs to check that the values on the stack satisfy the type declartions. It does this using a similar technique to the above; mapping over a sequence to make an array of quotations, and then applies to to spread.

3 comments:

Anonymous said...

Slava, if the third element on the stack is 3, and the quote is [ 2 / ], what is 1+1/2 ?

Thanks,
James

Anonymous said...

IOW, why not just say 1.5?

James

Slava Pestov said...

James,

1+1/2 is an exact ratio.

1.5 is a floating point value.

Factor has both arbitrary precision ratios and inexact floats; both have different use-cases.

Compare

1 3 /

1 3 /f

The former is exact, the latter is inexact.