2008-10-11
Revisiting the Linear recursion combinator in Factor four years on
The Joy programming language has a linrec combinator for performing linear recursion. Some time ago I took a stab at implementing linrec in Factor. Slava also posted his version that was originally a part of Factor.
As can be seen from Slava's version, juggling the stack when four quotations are involved can be problematic. I thought I'd revisit linrec using Factor's locals library and see how it compares. This is my attempt at an implementation using locals:
:: linrec
( if-quot: ( -- ? )
then-quot: ( -- )
else1-quot: ( -- )
else2-quot: ( -- )
-- )
if-quot call [
then-quot call
] [
else1-quot call
if-quot then-quot else1-quot else2-quot linrec
else2-quot call
] if ; inline recursive
This is pretty readable compared to the solutions in the prior posts. Because linrec is a combinator it needs to be declared 'inline'. It recursively calls itself so needs to be declared 'inline recursive' to enable calls of linrec to be compiled. More details about this can be found in the Factor documentation. Usage of the linrec word looks like:
5 [ dup 1 = ] [ ] [ dup 1- ] [ * ] linrec .
=> 120
[ 5 [ dup 1 = ] [ ] [ dup 1- ] [ * ] linrec ] infer.
=> ( -- object )
{ 1 2 3 } [ dup rest empty? ] [ first ] [ rest ] [ ] linrec
=> 3
[ { 1 2 3 } [ dup rest empty? ] [ first ] [ rest ] [ ] linrec ] infer.
=> ( -- object )
[ 1000 [ dup 1 = ] [ ] [ dup 1- ] [ * ] linrec drop ] time
=> 22ms
: fac ( n -- n ) dup 1 = [ dup 1- fac * ] unless ;
[ 1000 fac drop ] time
=> 19ms
It's nice that the 'fac' word and the linrec definition seem to compile down to the same code:
[ [ dup 1 = ] [ ] [ dup 1- ] [ * ] linrec ] optimized.
=> [
\ ( gensym ) [
dup 1 dupd eq?
[ drop t ]
[ dup 1 swap tag eq? [ 1 bignum= ] [ drop f ] if ] if
[ ] [ dup 1 - ( gensym ) * ] if
] label
]
\ fac optimized.
=> [
dup 1 dupd eq?
[ drop t ]
[ dup 1 swap tag eq? [ 1 bignum= ] [ drop f ] if ] if
[ ] [ dup 1 - fac * ] if
]
One confusing aspect of this linrec definition is having to declare the stack effects of the quotations passed to linrec. Depending on the linear recursion task the stack effects may be different. Compare factorial vs finding the last element of a sequence:
{ [ dup 1 = ]
[ ]
[ dup 1- ]
[ * ]
} [ infer. ] each
=> ( object -- object object )
( -- )
( object -- object object )
( object object -- object)
{
[ dup rest empty? ]
[ first ]
[ rest ]
[ ]
} [ infer. ] each
=> ( object -- object object )
( object -- object )
( object -- object )
( -- )
Both usages of linrec still infer and compile so I guess the fact that the stack effects balance out allows this. I'm not sure whether it's just a side effect of implementation or intended.
Working on this example I can say that, for me, Factor programming has become easier compared to four years ago.
