# Generators revisited

## Don Groves — 2007-11-14 00:01:46

    In rethinking the design of generators, it occurred to me that a

    generator is in fact a closure. I'm not familiar enough with the

    literature yet to know if closures already have an accepted

    methodology in this group, so please enlighten me if this is so.

    A generator might look like [[f] a b ..] where f is the generation

    function and a, b, etc, are its static data.  A new combinator,

    generate (as suggested by Billy), would be needed which would

    disassemble the generator; apply f to the the list [a b ..];

    reassemble the generator; and push the new value on the stack.

    Further discussion on this topic will be greatly appreciated,

    --

    Don Groves

## William Tanksley, Jr — 2007-11-14 00:20:19

    Don Groves <dgroves@...> wrote:

     > In rethinking the design of generators, it occurred to me that a

    > generator is in fact a closure. I'm not familiar enough with the

    > literature yet to know if closures already have an accepted

    > methodology in this group, so please enlighten me if this is so.

     Sure is! Actually, I kinda assumed that was going to be how you'd

    implement them :-).

     > A generator might look like [[f] a b ..] where f is the generation

    > function and a, b, etc, are its static data.  A new combinator,

    > generate (as suggested by Billy), would be needed which would

    > disassemble the generator; apply f to the the list [a b ..];

    > reassemble the generator; and push the new value on the stack.

     Yup. It's a simple enough function to define.

    The hard part is building all of the 'f's you might need. It's

    impossible to build them all; in general you have to let programmers

    build 'em for you. Icon takes one route (by making expressions be

    capable of repeating themselves); anyone know any others?

     > Don Groves

     -Billy

## Don Groves — 2007-11-14 00:42:43

    On Nov 13, 2007, at 19:20 , William Tanksley, Jr wrote:

     > Don Groves <dgroves@...> wrote:

    >> In rethinking the design of generators, it occurred to me that a

    >> generator is in fact a closure. I'm not familiar enough with the

    >> literature yet to know if closures already have an accepted

    >> methodology in this group, so please enlighten me if this is so.

    >

    > Sure is! Actually, I kinda assumed that was going to be how you'd

    > implement them :-).

     I may be slow at times but I eventually catch up ;-)

     >> A generator might look like [[f] a b ..] where f is the generation

    >> function and a, b, etc, are its static data.  A new combinator,

    >> generate (as suggested by Billy), would be needed which would

    >> disassemble the generator; apply f to the the list [a b ..];

    >> reassemble the generator; and push the new value on the stack.

    >

    > Yup. It's a simple enough function to define.

    >

    > The hard part is building all of the 'f's you might need. It's

    > impossible to build them all; in general you have to let programmers

    > build 'em for you. Icon takes one route (by making expressions be

    > capable of repeating themselves); anyone know any others?

     Sure, a few simple ones could be built in (Z for example) but others

    would be up to users to define as needed. I'm implementing a

    Fibonacci generator in ACL at the moment to serve as an example.

    --

    Don

     >> Don Groves

    >

    > -Billy

## Daniel Ehrenberg — 2007-11-14 03:28:55

    On 11/13/07, Don Groves <dgroves@...> wrote:

     > In rethinking the design of generators, it occurred to me that a

    >  generator is in fact a closure. I'm not familiar enough with the

    >  literature yet to know if closures already have an accepted

    >  methodology in this group, so please enlighten me if this is so.

    >

    >  A generator might look like [[f] a b ..] where f is the generation

    >  function and a, b, etc, are its static data. A new combinator,

    >  generate (as suggested by Billy), would be needed which would

    >  disassemble the generator; apply f to the the list [a b ..];

    >  reassemble the generator; and push the new value on the stack.

    >

    >  Further discussion on this topic will be greatly appreciated,

    >  --

    >  Don Groves

     That's a really interesting idea. One thing you could do, though, is

    implement a word ... such that when you call this quotation, the

    generator's value is returned along with a new generator quotation.

    Sketch implementation in Factor:

    : ... ( data quot -- data quot )

        dup slip over >r [ ... ] 2curry r> ;

    For those who don't know Factor, here's a rough translation to a more

    Joy-like language:

    ... == dup dip over [ [ ... ] cons cons ] dip;

    With this, you can make a trivial generator like [ 1 [ 1+ ] ... ]. If

    you call that, you get 2, with the quotation [ 2 [ 1+ ] ... ]. If you

    call that quotation, you get the quotation [ 3 [ 1+] ...] and 3, and

    so on. You could have internal hidden data by adding "first" (aka

    head) to the end of the definition, so for fibonacci, you might use [

    { 0 1 } [ first2 tuck + 2array ] ... ] (though that's not extremely

    elegant-looking.)

    Anyway, there's no reason why you'd need self-generating code, I just

    think it's interesting. It doesn't compile in the current

    implementation of Factor, but it should be possible to mechanically

    type and compile with lambda lifting given a sufficiently smart

    compiler.

    Daniel Ehrenberg

## Don Groves — 2007-11-14 04:05:41

    On Nov 13, 2007, at 19:28 , Daniel Ehrenberg wrote:

     > On 11/13/07, Don Groves <dgroves@...> wrote:

    >> In rethinking the design of generators, it occurred to me that a

    >>  generator is in fact a closure. I'm not familiar enough with the

    >>  literature yet to know if closures already have an accepted

    >>  methodology in this group, so please enlighten me if this is so.

    >>

    >>  A generator might look like [[f] a b ..] where f is the generation

    >>  function and a, b, etc, are its static data. A new combinator,

    >>  generate (as suggested by Billy), would be needed which would

    >>  disassemble the generator; apply f to the the list [a b ..];

    >>  reassemble the generator; and push the new value on the stack.

    >>

    >>  Further discussion on this topic will be greatly appreciated,

    >>  --

    >>  Don Groves

    >

    > That's a really interesting idea. One thing you could do, though, is

    > implement a word ... such that when you call this quotation, the

    > generator's value is returned along with a new generator quotation.

     Hi Daniel,

    Yes, that's the idea exactly. In ACL (which I will post soon now)

    it looks like:

    [uncons mapf cons swap] defun generate (where mapf is the

    same as map but it pushes the function before exiting).

    [uncons swap uncons dup swapYZ cons

      rotup dup rotup + swapYZ append] defun fibgen

    [[fibgen] 0 1] defcon fib

    The usage is:

    Invoking fib pushes the initial generator, [[fibgen] 0 1]

    Subsequent activations by generate achieve the desired result:

    [[fibgen] a b] generate --> [[fibgen] a a+b] b

    --

    Don

     > Sketch implementation in Factor:

    >

    > : ... ( data quot -- data quot )

    >     dup slip over >r [ ... ] 2curry r> ;

    >

    > For those who don't know Factor, here's a rough translation to a more

    > Joy-like language:

    >

    > ... == dup dip over [ [ ... ] cons cons ] dip;

    >

    > With this, you can make a trivial generator like [ 1 [ 1+ ] ... ]. If

    > you call that, you get 2, with the quotation [ 2 [ 1+ ] ... ]. If you

    > call that quotation, you get the quotation [ 3 [ 1+] ...] and 3, and

    > so on. You could have internal hidden data by adding "first" (aka

    > head) to the end of the definition, so for fibonacci, you might use [

    > { 0 1 } [ first2 tuck + 2array ] ... ] (though that's not extremely

    > elegant-looking.)

    >

    > Anyway, there's no reason why you'd need self-generating code, I just

    > think it's interesting. It doesn't compile in the current

    > implementation of Factor, but it should be possible to mechanically

    > type and compile with lambda lifting given a sufficiently smart

    > compiler.

    >

    > Daniel Ehrenberg

## Don Groves — 2007-11-14 04:32:00

    On Nov 13, 2007, at 19:05 , Don Groves wrote:

     > On Nov 13, 2007, at 19:28 , Daniel Ehrenberg wrote:

    >

    >> On 11/13/07, Don Groves <dgroves@...> wrote:

    >>> In rethinking the design of generators, it occurred to me that a

    >>>  generator is in fact a closure. I'm not familiar enough with the

    >>>  literature yet to know if closures already have an accepted

    >>>  methodology in this group, so please enlighten me if this is so.

    >>>

    >>>  A generator might look like [[f] a b ..] where f is the generation

    >>>  function and a, b, etc, are its static data. A new combinator,

    >>>  generate (as suggested by Billy), would be needed which would

    >>>  disassemble the generator; apply f to the the list [a b ..];

    >>>  reassemble the generator; and push the new value on the stack.

    >>>

    >>>  Further discussion on this topic will be greatly appreciated,

    >>>  --

    >>>  Don Groves

    >>

    >> That's a really interesting idea. One thing you could do, though, is

    >> implement a word ... such that when you call this quotation, the

    >> generator's value is returned along with a new generator quotation.

    >

    > Hi Daniel,

    >

    > Yes, that's the idea exactly. In ACL (which I will post soon now)

    > it looks like:

    >

    > [uncons mapf cons swap] defun generate (where mapf is the

    > same as map but it pushes the function before exiting).

    >

    > [uncons swap uncons dup swapYZ cons

    >   rotup dup rotup + swapYZ append] defun fibgen

    >

    > [[fibgen] 0 1] defcon fib

    >

    > The usage is:

    >

    > Invoking fib pushes the initial generator, [[fibgen] 0 1]

    >

    > Subsequent activations by generate achieve the desired result:

    >

    > [[fibgen] a b] generate --> [[fibgen] a a+b] b

     Sorry, that should be --> [[fibgen] b a+b] b

    --

    Don

     > --

    > Don

    >

    >

    >> Sketch implementation in Factor:

    >>

    >> : ... ( data quot -- data quot )

    >>     dup slip over >r [ ... ] 2curry r> ;

    >>

    >> For those who don't know Factor, here's a rough translation to a more

    >> Joy-like language:

    >>

    >> ... == dup dip over [ [ ... ] cons cons ] dip;

    >>

    >> With this, you can make a trivial generator like [ 1 [ 1+ ] ... ]. If

    >> you call that, you get 2, with the quotation [ 2 [ 1+ ] ... ]. If you

    >> call that quotation, you get the quotation [ 3 [ 1+] ...] and 3, and

    >> so on. You could have internal hidden data by adding "first" (aka

    >> head) to the end of the definition, so for fibonacci, you might use [

    >> { 0 1 } [ first2 tuck + 2array ] ... ] (though that's not extremely

    >> elegant-looking.)

    >>

    >> Anyway, there's no reason why you'd need self-generating code, I just

    >> think it's interesting. It doesn't compile in the current

    >> implementation of Factor, but it should be possible to mechanically

    >> type and compile with lambda lifting given a sufficiently smart

    >> compiler.

    >>

    >> Daniel Ehrenberg

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Don Groves — 2007-11-14 07:13:37

    Okay, I finally got this right and it works beautifully in ACL.

    The generate combinator is:

    [uncons I* cons swap] defun generate

    (I had my head in dark place when I wrote mapf last time.

    It's not map I want, it's the identify combinator modified to

    push the quoted function back on the stack after executing it.

    I* is that combinator)

    The Fibonacci generator works like this:

    [a b] fibgen -- b [b a+b]

    The overall result of applying generate is:

    [[fibgen a b] generate -- [[fibgen] b a+b] b

    Any function which leaves its new result beneath its updated

    argument list on the stack will work as a generator. I hope others

    will find this construct useful.

    --

    Don

     On Nov 13, 2007, at 19:32 , Don Groves wrote:

    > On Nov 13, 2007, at 19:05 , Don Groves wrote:

    >

    >> On Nov 13, 2007, at 19:28 , Daniel Ehrenberg wrote:

    >>

    >>> On 11/13/07, Don Groves <dgroves@...> wrote:

    >>>> In rethinking the design of generators, it occurred to me that a

    >>>>  generator is in fact a closure. I'm not familiar enough with the

    >>>>  literature yet to know if closures already have an accepted

    >>>>  methodology in this group, so please enlighten me if this is so.

    >>>>

    >>>>  A generator might look like [[f] a b ..] where f is the generation

    >>>>  function and a, b, etc, are its static data. A new combinator,

    >>>>  generate (as suggested by Billy), would be needed which would

    >>>>  disassemble the generator; apply f to the the list [a b ..];

    >>>>  reassemble the generator; and push the new value on the stack.

    >>>>

    >>>>  Further discussion on this topic will be greatly appreciated,

    >>>>  --

    >>>>  Don Groves

    >>>

    >>> That's a really interesting idea. One thing you could do, though, is

    >>> implement a word ... such that when you call this quotation, the

    >>> generator's value is returned along with a new generator quotation.

    >>

    >> Hi Daniel,

    >>

    >> Yes, that's the idea exactly. In ACL (which I will post soon now)

    >> it looks like:

    >>

    >> [uncons mapf cons swap] defun generate (where mapf is the

    >> same as map but it pushes the function before exiting).

    >>

    >> [uncons swap uncons dup swapYZ cons

    >>   rotup dup rotup + swapYZ append] defun fibgen

    >>

    >> [[fibgen] 0 1] defcon fib

    >>

    >> The usage is:

    >>

    >> Invoking fib pushes the initial generator, [[fibgen] 0 1]

    >>

    >> Subsequent activations by generate achieve the desired result:

    >>

    >> [[fibgen] a b] generate --> [[fibgen] a a+b] b

    >

    > Sorry, that should be --> [[fibgen] b a+b] b

    > --

    > Don

    >

    >

    >

    >> --

    >> Don

    >>

    >>

    >>> Sketch implementation in Factor:

    >>>

    >>> : ... ( data quot -- data quot )

    >>>     dup slip over >r [ ... ] 2curry r> ;

    >>>

    >>> For those who don't know Factor, here's a rough translation to a

    >>> more

    >>> Joy-like language:

    >>>

    >>> ... == dup dip over [ [ ... ] cons cons ] dip;

    >>>

    >>> With this, you can make a trivial generator like [ 1 [ 1

    >>> + ] ... ]. If

    >>> you call that, you get 2, with the quotation [ 2 [ 1+ ] ... ]. If

    >>> you

    >>> call that quotation, you get the quotation [ 3 [ 1+] ...] and 3, and

    >>> so on. You could have internal hidden data by adding "first" (aka

    >>> head) to the end of the definition, so for fibonacci, you might

    >>> use [

    >>> { 0 1 } [ first2 tuck + 2array ] ... ] (though that's not extremely

    >>> elegant-looking.)

    >>>

    >>> Anyway, there's no reason why you'd need self-generating code, I

    >>> just

    >>> think it's interesting. It doesn't compile in the current

    >>> implementation of Factor, but it should be possible to mechanically

    >>> type and compile with lambda lifting given a sufficiently smart

    >>> compiler.

    >>>

    >>> Daniel Ehrenberg

    >>

    >>

    >>

    >>

    >> Yahoo! Groups Links

    >>

    >>

    >>

    >>

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >