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