Re: [stack] Generators revisited

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

> On 11/13/07, Don Groves <[email protected]> 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