# Generators in Factor

## Chris Double — 2004-06-07 07:50:41

    Here's some code to create a tree generator and generic code to iterate

    over generators:

    ! Given a tree and an escaping continuation, call that continuation with

    ! a generator. The generator can be called with 'call-generator' and

    ! it will return successive items from the tree in-order from left to

    right.

    : make-tree-generator ( tree escape -- cont )

    	swap [

    		rot

    		call

    	] callcc1

    	[ nip ] dip

    	swap

     	[

    		[

    		   cons

                       swap call

                    ] callcc1

    		[ 2drop ] dip

    	] tree-each

            f swap call ;

    ! Given a tree, return a generator for that tree. The generator can be

    ! called with 'call-generator' and will return successive items from

    ! the tree in-order from left to right on each call.

    : tree>generator ( tree -- generator ) [ make-tree-generator ] callcc1

    nip ;

    ! Call a generator. It will return the next item

    ! in the tree at the top of the stack followed by the generator to call

    to get the

    ! next value in the tree. If there are no values left in the three a

    single f

    ! value is returned.

    : call-generator ( generator --  generator v )

    	[ swap call ] callcc1 nip dup [ uncons swap ] [ ] ifte ;

    ! Given a generator call the given code on each generated item

    : generator-each ( generator code -- )

    	swap

    	[

    		call-generator dup

    	] [

    		swap

                    [ over [ swap call ] dip ] dip

    	] while

    	2drop ;

    [ 1 2 [ 3 4 ] 5 ] tree>generator

    call-generator .

    => 1

    call-generator .

    => 2

    call-generator .

    => 3

    call-generator .

    => 4

    call-generator .

    => 5

    call-generator .

    => f

    [ 1 2 [ 3 4 ] 5 ] tree->generator [ . ] generator-each

    => 1

       2

       3

       4

       5

    Note that generator-each will work on any 'generator' where the generator

    is a function that has the signature ( escape-continuation -- [ v

    generator ] or f ).

    Chris.

    --

      Chris Double

      chris.double@...

## Chris Double — 2004-06-07 08:41:39

    The tree iteration example can be generalized further using the

    equivalent of Pythons yield:

    [ [ 1 2 [ 3 4 ] 5 ] [ yield ] tree-each ] make-generator

    call-generator

     => 1

    call-generator

     => 2

    [ . ] generator-each

     => 3

        4

        5

    Here's the implementation:

    ! Python's yield statement. From inside a block passed to make-generator,

    ! calling yield will return the value on the top of the stack to the

    ! caller (access to the caller provided by the escape continuation). When

    ! the generator is called again, execution is returned from the point

    ! after the yield call will the new escape continuation on the stack.

    : yield ( escape value -- escape ) [ cons swap call ] callcc1 ;

    ! Given a code block create and return a generator that when called will

    ! pass the escape continuation to the code block. This block can then

    ! 'yield' using that continuation to return a value back to the caller

    and

    ! suspend the generator.

    : make-generator ( code -- generator )

    	[

    		[

    			swap

    			call

    		] callcc1

    		nip

    		swap call

    		nip

    		f swap

    		call

    	] callcc1

    	nip ;

    ! Simple yield example

    [ 5 yield 10 yield 30 yield ] make-generator [ . ] generator-each

     => 5

        10

        30

    [ 5 yield 10 yield 30 yield ] make-generator [ dup ] generator-each

     => 5

        5

        10

        10

        30

        30

    ! The previously given tree example can be done with these generic tools

    [ [ 1 2 [ 3 4 ] 5 ] [ yield ] tree-each ] make-generator

    call-generator

     => 1

    call-generator

     => 2

    [ . ] generator-each

     => 3

        4

        5

    --

      Chris Double

      chris.double@...

## stevan apter — 2004-06-07 21:22:16

    this is interesting, but hard to follow.  it would be great

    if one of you could write up a tutorial on continuations and

    generators in factor (for dummies).  i.e. assume no knowledge

    of factor beyond the simple stack processing model.  explain

    each word as you introduce it.  &c.

    again, i recommend close study of manfred's exemplary papers.

    note that each one starts pretty much from the same place,

    namely, ignorance of joy, and then introduces just those

    words/concepts which are required by the topic.

     ----- Original Message -----

    From: "Chris Double" <chris.double@...>

    To: "concatenative mailing list" <concatenative@yahoogroups.com>

    Sent: Monday, June 07, 2004 4:41 AM

    Subject: Re: [stack] Generators in Factor

    > The tree iteration example can be generalized further using the

    > equivalent of Pythons yield:

    >

    > [ [ 1 2 [ 3 4 ] 5 ] [ yield ] tree-each ] make-generator

    > call-generator

    >  => 1

    > call-generator

    >  => 2

    > [ . ] generator-each

    >  => 3

    >     4

    >     5

    >

    > Here's the implementation:

    >

    > ! Python's yield statement. From inside a block passed to make-generator,

    > ! calling yield will return the value on the top of the stack to the

    > ! caller (access to the caller provided by the escape continuation). When

    > ! the generator is called again, execution is returned from the point

    > ! after the yield call will the new escape continuation on the stack.

    > : yield ( escape value -- escape ) [ cons swap call ] callcc1 ;

    >

    > ! Given a code block create and return a generator that when called will

    > ! pass the escape continuation to the code block. This block can then

    > ! 'yield' using that continuation to return a value back to the caller

    > and

    > ! suspend the generator.

    > : make-generator ( code -- generator )

    > [

    > [

    > swap

    > call

    > ] callcc1

    > nip

    > swap call

    > nip

    > f swap

    > call

    > ] callcc1

    > nip ;

    >

    > ! Simple yield example

    > [ 5 yield 10 yield 30 yield ] make-generator [ . ] generator-each

    >  => 5

    >     10

    >     30

    >

    > [ 5 yield 10 yield 30 yield ] make-generator [ dup ] generator-each

    >  => 5

    >     5

    >     10

    >     10

    >     30

    >     30

    >

    > ! The previously given tree example can be done with these generic tools

    > [ [ 1 2 [ 3 4 ] 5 ] [ yield ] tree-each ] make-generator

    > call-generator

    >  => 1

    > call-generator

    >  => 2

    > [ . ] generator-each

    >  => 3

    >     4

    >     5

    > --

    >   Chris Double

    >   chris.double@...

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## Chris Double — 2004-06-07 23:34:25

    On Mon, 7 Jun 2004 17:22:16 -0400, "stevan apter" <sa@...> said:

     > this is interesting, but hard to follow.  it would be great

    > if one of you could write up a tutorial on continuations and

    > generators in factor (for dummies).

     Sure, I'll see what I can do. I'm completely new to Factor myself so

    don't know what makes good coding style or idiomatic usage though. Much

    of what can be done with generators is done in languages like Joy by just

    passing a code block to a combinator. The only thing the generator gets

    you is the ability to 'early escape' (ie. it's effectively a lazy list).

    The difficulty with the implementation I did was having to pass the

    escape continuation around which I'm not sure is the best approach.

     > again, i recommend close study of manfred's exemplary papers.

     Yes, I agree they are great and very approachable.

    Chris.

    --

      Chris Double

      chris.double@...