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