Re: [stack] Generators revisited

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