Using Factor I thought I'd work through some of the Joy papers and I
came across the 'linrec' combinator which Factor doesn't have. A while
back Slava sent me an implementation of linrec but I've misplaced it so
I thought I'd have a go at implementing it in Factor.
To keep the four quotations (if, then, rec1, rec2) readily accessible I
store them
in a vector:
: make-linrec-state ( if then rec1 rec2 -- state )
#! Given the four quotations for linrec, return a state
#! object that keeps the values.
4 <vector>
tuck vector-push tuck vector-push tuck vector-push tuck vector-push ;
And I use some helper functions to retrieve the values:
: linrec-if ( state -- state )
#! Retrieve the 'if' quotation from the linrec state
#! and call it, leaving the state on the top of the stack.
dup >r 3 swap vector-nth call r> ;
: linrec-then ( state -- state )
#! Retrieve the 'then' quotation from the linrec state
#! and call it, leaving the state on the top of the stack.
dup >r 2 swap vector-nth call r> ;
: linrec-rec1 ( state -- state )
#! Retrieve the 'rec1' quotation from the linrec state
#! and call it, leaving the state on the top of the stack.
dup >r 1 swap vector-nth call r> ;
: linrec-rec2 ( state -- state )
#! Retrieve the 'rec2' quotation from the linrec state
#! and call it, leaving the state on the top of the stack.
dup >r 0 swap vector-nth call r> ;
These call the requested quotation given the state on the stack and
leave the state on the stack with the quotations effect underneath it.
This cut down on return stack manipulations as that's the other place I
thought of keeping them.
The actual linrec implementation is then quite easy and readable:
: (linrec) ( v state -- state )
#! Implementation of linrec given the state rather than the
#! four quotations.
linrec-if swap [
linrec-then
] [
linrec-rec1
(linrec)
linrec-rec2
] ifte ;
: linrec ( if then rec1 rec2 -- )
#! The four quotations are saved. The 'if' quotation is called.
#! If that returns true then the 'then' quotation is called and
#! the combinator exists. Otherwise the 'rec1' quotation is called,
#! the combinator calls itself recursively and the 'rec2' quotation
#! is called.
make-linrec-state (linrec) drop ;
Testing with a factorial function works:
5 [ dup 1 = ] [ ] [ dup pred ] [ * ] linrec
=> 120
Note that I had to do a 'dup' in the if test to save the item on the
stack. The Joy linrec combinator doesn't require this as after the 'if'
quotation is called the stack is restored so any changes it made (apart
from the result that was put on the stack) are ignored. I think anyway.
I don't have Joy installed to try it but it seems this way from the
examples in the papers. To do the same thing in Factor I wrote a 'call+'
word that does this:
: call+ ( v quot -- v )
#! Call a quotation. The quotation can manipulate the
#! stack in any way but after the call the stack is
#! restored to how it was before the quotation was
#! called, with the quotation removed from the stack,
#! and the result of the quotation added to the stack.
#! The quotation must have stack effect ( anything -- X ).
datastack slip swap >r set-datastack drop r> ;
And then modified linrec-if to use it:
: linrec-if ( state -- state )
#! Retrieve the 'if' quotation from the linrec state
#! and call it. Restores the datastack to the way it was
#! before the quotation was called but with the quotation
#! removed and the result of the call aliong with the state
#! on the stack.
dup >r 3 swap vector-nth call+ r> ;
Now the following works:
5 [ 1 = ] [ ] [ dup pred ] [ * ] linrec
=> 120
For a timing comparison with a standard recursive version of factorial I
used:
: facr ( n -- n )
dup 1 = [ ] [ dup pred facr * ] ifte ;
I get the following times:
[ 10000 [ 20 facr drop ] times ] time
=> 878 ms
[ 10000 [ 20 [ 1 = ] [ ] [ dup pred ] [ * ] linrec drop ] times ]
time
=> 1426 ms
That's not too bad an overhead given that the implementation is in
Factor rather than as a C primitive. If I use the version that doesn't
do the datastack manipulation and requires you to manually save the
state in the 'if' quotation I get:
[ 10000 [ 20 [ dup 1 = ] [ ] [ dup pred ] [ * ] linrec drop ] times ]
time
=> 1230 ms
I tried to implement a version without using the 'state' in a vector but
got lossed in a mass of stack manipulations. The code above ends up
being quite readable I think for not too much overhead. Any thoughts on
other possible approaches?
Chris.
--
Chris Double
chris.double@...
For comparison rather than any suggestion of virture, here's the
implementation of linrec from the Monkey library. I'm afraid I don't
have the detailed derivation, but as per the comment in the code, it's
not actually recursive.
The only non-obvious word is 'pcon' which is Monkey's only iterative
word:
<< Synthesized pcon: {Body} {Test} -> ...
Executes {Test} if True is left on the ToS, executes {Body} and
loops. >>
pcon ==
{{
{ dip swapdup { swapif } dip unmove swap { dup unmove swap move swap
move move 0 } if drop }
cons cons
dup move move
}}
<< Linear recursive combinator. Executes P, if true executes T, else
R1, recurse, R2.
... {P} {T} {R1} {R2} -> ?
### This is implemented by counting the "downs" then calling an
### appropriate number of "ups" i.e. it's not /really/ recursive at
### all. There are two possible deductions from this: (1) this is
### not a correct implementation of linrec, or (2) the absence of
### lambda allows greater flexibility of recursion mechanisms.
>>linrec ==
{{
[ 1 ] cons cons cons cons
{ << body: >>
dup
{ rest rest first i } dip
}
{ << test: >>
dup first swap
{ i } dip swap
unit programise
{ dup { rest first i } dip false }
{ uncons uncons uncons uncons first 1 + unit cons cons cons cons
true }
ifte
}
pcon
rest rest rest
unswons swap first
repeat
}}
On Sat, 2004-11-20 at 04:46, Chris Double wrote:
> Using Factor I thought I'd work through some of the Joy papers and I
> came across the 'linrec' combinator which Factor doesn't have. A while
> back Slava sent me an implementation of linrec but I've misplaced it so
> I thought I'd have a go at implementing it in Factor.
--
Martin Young, at home.
in XY:
; linrec { [c t r s] c i c t r s _x linrec. } ;
; linrec. { [b c t r s x] x <- b t [r i c t r s linrec s i] if } ;
linrec expects c t r s on the stack. it evaluates c, pushes c t r s
and the stack _x up to but not including c t r s, calls linrec.
linrec. expects b (i.e. c i) c t r s and x (i.e. _x). it resets
the stack to x. if b is true, it evaluates t, else it evaluates r,
pushes c t r s, calls linrec, evaluates s.
inefficient? yer durn tootin'.
----- Original Message -----
From: "Martin Young" <martin@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, November 20, 2004 6:57 AM
Subject: Re: [stack] linrec in Factor
>
> For comparison rather than any suggestion of virture, here's the
> implementation of linrec from the Monkey library. I'm afraid I don't
> have the detailed derivation, but as per the comment in the code, it's
> not actually recursive.
>
> The only non-obvious word is 'pcon' which is Monkey's only iterative
> word:
>
> << Synthesized pcon: {Body} {Test} -> ...
> Executes {Test} if True is left on the ToS, executes {Body} and
> loops. >>
> pcon ==
> {{
> { dip swapdup { swapif } dip unmove swap { dup unmove swap move swap
> move move 0 } if drop }
> cons cons
> dup move move
> }}
>
>
>
>
> << Linear recursive combinator. Executes P, if true executes T, else
> R1, recurse, R2.
> ... {P} {T} {R1} {R2} -> ?
> ### This is implemented by counting the "downs" then calling an
> ### appropriate number of "ups" i.e. it's not /really/ recursive at
> ### all. There are two possible deductions from this: (1) this is
> ### not a correct implementation of linrec, or (2) the absence of
> ### lambda allows greater flexibility of recursion mechanisms.
> >>
> linrec ==
> {{
> [ 1 ] cons cons cons cons
> { << body: >>
> dup
> { rest rest first i } dip
> }
> { << test: >>
> dup first swap
> { i } dip swap
> unit programise
> { dup { rest first i } dip false }
> { uncons uncons uncons uncons first 1 + unit cons cons cons cons
> true }
> ifte
> }
> pcon
> rest rest rest
> unswons swap first
> repeat
> }}
>
> On Sat, 2004-11-20 at 04:46, Chris Double wrote:
> > Using Factor I thought I'd work through some of the Joy papers and I
> > came across the 'linrec' combinator which Factor doesn't have. A while
> > back Slava sent me an implementation of linrec but I've misplaced it so
> > I thought I'd have a go at implementing it in Factor.
>
> --
> Martin Young, at home.
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
Chris Double wrote:
> Using Factor I thought I'd work through some of the Joy papers and IHere is the original version that used to be part of the library:
> came across the 'linrec' combinator which Factor doesn't have. A while
> back Slava sent me an implementation of linrec but I've misplaced it so
> I thought I'd have a go at implementing it in Factor.
: linrec ( [ P ] [ T ] [ R1 ] [ R2 ] -- )
#! Evaluate P, if it pushes t, evaluate T. Otherwise,
#! evaluate R1, recurse, and evaluate R2. This combinator is
#! similar to the linrec combinator in Joy, except in Joy, P
#! does not affect the stack.
>r >r >r dup >r call [r> drop r> call
r> drop r> drop
] [
r> r> r> dup >r swap >r swap >r call
r> r> r> r> dup >r linrec
r> call
] ifte ;
As you can see, its quite a mess. This is why I prefer coding explicit
recursion rather than using such combinators. I don't find
: fac [ dup 1 = ] [ ] [ dup pred ] [ * ] linrec ;
Any easier to read than:
: fac dup 1 = [ dup pred fac * ] unless ;
> To keep the four quotations (if, then, rec1, rec2) readily accessible IAlong with some parsing words, this technique could be used as a basis
> store them in a vector:
for a low-overhead local variables implementation.
Slava
From: "Slava Pestov" <slava@...>
[:]
>neither do i, mainly because reading a line containing a
> As you can see, its quite a mess. This is why I prefer coding explicit
> recursion rather than using such combinators. I don't find
>
> : fac [ dup 1 = ] [ ] [ dup pred ] [ * ] linrec ;
>
> Any easier to read than:
>
> : fac dup 1 = [ dup pred fac * ] unless ;
>
recursive combinator requires remembering how many
quotations the combinator expects, as well as the logic
which dictates how they are evaluated.
i've always thought that the recursive combinators are
interesting, not because they simplify programming, but
because they aim to provide a kind of reductive analysis
of recursion. for example, it would be interesting to
know if there are recursions which can't be reduced to
some pattern of the recursive combinators in joy.
i still think that manfred's reduction of the ackermann
function to condnestrec is a tour de force.
On Sat, 20 Nov 2004, Martin Young wrote:
> For comparison rather than any suggestion of virture, here's the[..]
> implementation of linrec from the Monkey library. I'm afraid I don't
> have the detailed derivation, but as per the comment in the code, it's
> not actually recursive.
My apologies, Martin, I did not include you specifically in the
invitation to contribute to the joint paper on concatenative
languages. It had been a long time since I heard about your
Monkey language, and I clean forgot. Please do consider writing
a section like the others - which I still have not collated yet
since things are still in flux.
- Manfred