# linrec in Factor

## Chris Double — 2004-11-20 04:46:09

    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@...

## Martin Young — 2004-11-20 11:57:52

    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.

## stevan apter — 2004-11-20 15:17:05

    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

    >

    >

    >

    >

    >

    >

    >

## Slava Pestov — 2004-11-20 18:06:59

    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.

     Here is the original version that used to be part of the library:

    : 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 I

    > store them in a vector:

     Along with some parsing words, this technique could be used as a basis

    for a low-overhead local variables implementation.

    Slava

## stevan apter — 2004-11-20 18:53:58

    From: "Slava Pestov" <slava@...>

    [:]

     >

    > 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 ;

    >

     neither do i, mainly because reading a line containing a

    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.

## phimvt@lurac.latrobe.edu.au — 2004-12-17 04:44:35

    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