Generators

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Generators

Bert Freudenberg
Hi all,

there was an interesting question about Generators on StackOverflow:


It's about a pseudo-Prolog implementation using Generators and yield.

Our Generator *almost* works for this, except there is a little problem with the timing of side-effects:

| x gen |
x := 0.

gen := Generator on: [:g |
x := 1.
g yield: nil.

x := 2.
g yield: nil.

x := 3.
g yield: nil].

gen do: [:i | Transcript cr; show: x].

This *should* print '1 2 3' but actually prints '2 3 3'. This is because our Generator is written to support a streaming interface (using atEnd and peek) so it always computes one yield ahead.

In other languages (e.g. JavaScript, Python, C#) this is different, the execution is paused at the current yield statement, not 'before' the next one. In general, a generator cannot know if there will be more "yields" without executing more code. In Javascript, 'next' returns both a value and a 'done' flag, and if the flag is true, the returned value must not be used.

IMHO we should fix this - see attached changeset Marcel and I came up with. We did not fix the tests yet, but the behavior seems right.

Even though generators are in the image for a long time they are not used widely yet (AFAIK) so maybe we can still change the behavior? What do people think?

- Bert & Marcel -




generator-fix.1.cs (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generators

Frank Shearar-3
FWIW I think this is a good change to make.

frank

On Apr 12, 2017 06:43, "Bert Freudenberg" <[hidden email]> wrote:
Hi all,

there was an interesting question about Generators on StackOverflow:


It's about a pseudo-Prolog implementation using Generators and yield.

Our Generator *almost* works for this, except there is a little problem with the timing of side-effects:

| x gen |
x := 0.

gen := Generator on: [:g |
x := 1.
g yield: nil.

x := 2.
g yield: nil.

x := 3.
g yield: nil].

gen do: [:i | Transcript cr; show: x].

This *should* print '1 2 3' but actually prints '2 3 3'. This is because our Generator is written to support a streaming interface (using atEnd and peek) so it always computes one yield ahead.

In other languages (e.g. JavaScript, Python, C#) this is different, the execution is paused at the current yield statement, not 'before' the next one. In general, a generator cannot know if there will be more "yields" without executing more code. In Javascript, 'next' returns both a value and a 'done' flag, and if the flag is true, the returned value must not be used.

IMHO we should fix this - see attached changeset Marcel and I came up with. We did not fix the tests yet, but the behavior seems right.

Even though generators are in the image for a long time they are not used widely yet (AFAIK) so maybe we can still change the behavior? What do people think?

- Bert & Marcel -






Reply | Threaded
Open this post in threaded view
|

Re: Generators

Levente Uzonyi
In reply to this post by Bert Freudenberg
Wouldn't it be better to make Generator >> #do: not use #atEnd?
With the new implementation the following happens:

| generator |
generator := Generator on: [ :g | ].
generator atEnd
"==> false"

| generator |
generator := Generator on: [ :g | ].
generator next; atEnd
"==> true"

Also, this change set will break existing Generator instances if you load
them into your image and it happens to have some.

Levente

On Wed, 12 Apr 2017, Bert Freudenberg wrote:

> Hi all,
> there was an interesting question about Generators on StackOverflow:
>
> http://stackoverflow.com/questions/43340007/yield-prolog-adaptation-for-smalltalk
>
> It's about a pseudo-Prolog implementation using Generators and yield.
>
> Our Generator *almost* works for this, except there is a little problem with the timing of side-effects:
>
> | x gen |
> x := 0.
>
> gen := Generator on: [:g |
> x := 1.
> g yield: nil.
>
> x := 2.
> g yield: nil.
>
> x := 3.
> g yield: nil].
>
> gen do: [:i | Transcript cr; show: x].
>
> This *should* print '1 2 3' but actually prints '2 3 3'. This is because our Generator is written to support a streaming interface (using atEnd
> and peek) so it always computes one yield ahead.
>
> In other languages (e.g. JavaScript, Python, C#) this is different, the execution is paused at the current yield statement, not 'before' the next
> one. In general, a generator cannot know if there will be more "yields" without executing more code. In Javascript, 'next' returns both a value
> and a 'done' flag, and if the flag is true, the returned value must not be used.
>
> IMHO we should fix this - see attached changeset Marcel and I came up with. We did not fix the tests yet, but the behavior seems right.
>
> Even though generators are in the image for a long time they are not used widely yet (AFAIK) so maybe we can still change the behavior? What do
> people think?
>
> - Bert & Marcel -
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Generators

Kjell Godo

is there documentation on these Generators?

i only know the Timothy Budd variety 
     from LittleSmalltalk
     i guess his variety of Generator
          was used extensively in LittleSmalltalk




On Wed, Apr 12, 2017 at 09:52 Levente Uzonyi <[hidden email]> wrote:
Wouldn't it be better to make Generator >> #do: not use #atEnd?
With the new implementation the following happens:

| generator |
generator := Generator on: [ :g | ].
generator atEnd
"==> false"

| generator |
generator := Generator on: [ :g | ].
generator next; atEnd
"==> true"

Also, this change set will break existing Generator instances if you load
them into your image and it happens to have some.

Levente

On Wed, 12 Apr 2017, Bert Freudenberg wrote:

> Hi all,
> there was an interesting question about Generators on StackOverflow:
>
> http://stackoverflow.com/questions/43340007/yield-prolog-adaptation-for-smalltalk
>
> It's about a pseudo-Prolog implementation using Generators and yield.
>
> Our Generator *almost* works for this, except there is a little problem with the timing of side-effects:
>
> | x gen |
> x := 0.
>
> gen := Generator on: [:g |
> x := 1.
> g yield: nil.
>
> x := 2.
> g yield: nil.
>
> x := 3.
> g yield: nil].
>
> gen do: [:i | Transcript cr; show: x].
>
> This *should* print '1 2 3' but actually prints '2 3 3'. This is because our Generator is written to support a streaming interface (using atEnd
> and peek) so it always computes one yield ahead.
>
> In other languages (e.g. JavaScript, Python, C#) this is different, the execution is paused at the current yield statement, not 'before' the next
> one. In general, a generator cannot know if there will be more "yields" without executing more code. In Javascript, 'next' returns both a value
> and a 'done' flag, and if the flag is true, the returned value must not be used.
>
> IMHO we should fix this - see attached changeset Marcel and I came up with. We did not fix the tests yet, but the behavior seems right.
>
> Even though generators are in the image for a long time they are not used widely yet (AFAIK) so maybe we can still change the behavior? What do
> people think?
>
> - Bert & Marcel -
>
>
>



Reply | Threaded
Open this post in threaded view
|

Re: Generators

Bert Freudenberg
In reply to this post by Levente Uzonyi
On Wed, Apr 12, 2017 at 6:51 PM, Levente Uzonyi <[hidden email]> wrote:
Wouldn't it be better to make Generator >> #do: not use #atEnd?
With the new implementation the following happens:

| generator |
generator := Generator on: [ :g | ].
generator atEnd
"==> false"

The generator has not run, it can not know if it's at the end yet.
 
| generator |
generator := Generator on: [ :g | ].
generator next; atEnd
"==> true"

Now the generator has run, so it knows it ended. Unless we solve the Halting Problem we cannot know if the Generator will do another yield or not.

Basically, we need need to call next, and then use atEnd to see if we can use that result or need to ignore it. This is similar to other languages. Here's an example from JavaScript:

function* foo() {
  var index = 0;
  while (index <= 2)
    yield index++;
}
var iterator = foo();
console.log(iterator.next()); // { value: 0, done: false }
console.log(iterator.next()); // { value: 1, done: false }
console.log(iterator.next()); // { value: 2, done: false }
console.log(iterator.next()); // { value: undefined, done: true }

Also, this change set will break existing Generator instances if you load them into your image and it happens to have some.

Okay, this is a problem. Maybe a new class?

Or maybe try to accommodate both - *if* peek or atEnd are called, then compute ahead, otherwise don't... but that might be tricky and confusing.

- Bert -

 

Bert Freudenberg wrote:

Hi all,
there was an interesting question about Generators on StackOverflow:

http://stackoverflow.com/questions/43340007/yield-prolog-adaptation-for-smalltalk

It's about a pseudo-Prolog implementation using Generators and yield.

Our Generator *almost* works for this, except there is a little problem with the timing of side-effects:

| x gen |
x := 0.

gen := Generator on: [:g |
x := 1.
g yield: nil.

x := 2.
g yield: nil.

x := 3.
g yield: nil].

gen do: [:i | Transcript cr; show: x].

This *should* print '1 2 3' but actually prints '2 3 3'. This is because our Generator is written to support a streaming interface (using atEnd
and peek) so it always computes one yield ahead.

In other languages (e.g. JavaScript, Python, C#) this is different, the execution is paused at the current yield statement, not 'before' the next
one. In general, a generator cannot know if there will be more "yields" without executing more code. In Javascript, 'next' returns both a value
and a 'done' flag, and if the flag is true, the returned value must not be used.

IMHO we should fix this - see attached changeset Marcel and I came up with. We did not fix the tests yet, but the behavior seems right.

Even though generators are in the image for a long time they are not used widely yet (AFAIK) so maybe we can still change the behavior? What do
people think?

- Bert & Marcel -






Reply | Threaded
Open this post in threaded view
|

Re: Generators

Levente Uzonyi
On Thu, 13 Apr 2017, Bert Freudenberg wrote:

> On Wed, Apr 12, 2017 at 6:51 PM, Levente Uzonyi <[hidden email]> wrote:
>       Wouldn't it be better to make Generator >> #do: not use #atEnd?
>       With the new implementation the following happens:
>
>       | generator |
>       generator := Generator on: [ :g | ].
>       generator atEnd
>       "==> false"
>
>
> The generator has not run, it can not know if it's at the end yet.
>  
>       | generator |
>       generator := Generator on: [ :g | ].
>       generator next; atEnd
>       "==> true"
>
>
> Now the generator has run, so it knows it ended. Unless we solve the Halting Problem we cannot know if the Generator will do another yield or not.
It has nothing to do with the halting problem, because #atEnd don't have
to tell if your generator will ever stop yielding or not. It should just
tell if the upcoming #next send will return something meaningful or not.
The current implementation does exactly that.

Here's another example:

| generator |
generator := Generator on: [ :g | g yield: 1 ].
generator next; atEnd
"==> false"

My point is that the stream-like API forces you to read one object ahead.
Which is why I suggested rewriting #do: to not use it.

Levente

>
> Basically, we need need to call next, and then use atEnd to see if we can use that result or need to ignore it. This is similar to other languages. Here's an example from JavaScript:
>
> function* foo() {
>   var index = 0;
>   while (index <= 2)
>     yield index++;
> }
>
> var iterator = foo();
> console.log(iterator.next()); // { value: 0, done: false }
> console.log(iterator.next()); // { value: 1, done: false }
> console.log(iterator.next()); // { value: 2, done: false }
> console.log(iterator.next()); // { value: undefined, done: true }
>
>       Also, this change set will break existing Generator instances if you load them into your image and it happens to have some.
>
>
> Okay, this is a problem. Maybe a new class?
>
> Or maybe try to accommodate both - *if* peek or atEnd are called, then compute ahead, otherwise don't... but that might be tricky and confusing.
>
> - Bert -
>
>  
>
>       Bert Freudenberg wrote:
>
>             Hi all,
>             there was an interesting question about Generators on StackOverflow:
>
>             http://stackoverflow.com/questions/43340007/yield-prolog-adaptation-for-smalltalk
>
>             It's about a pseudo-Prolog implementation using Generators and yield.
>
>             Our Generator *almost* works for this, except there is a little problem with the timing of side-effects:
>
>             | x gen |
>             x := 0.
>
>             gen := Generator on: [:g |
>             x := 1.
>             g yield: nil.
>
>             x := 2.
>             g yield: nil.
>
>             x := 3.
>             g yield: nil].
>
>             gen do: [:i | Transcript cr; show: x].
>
>             This *should* print '1 2 3' but actually prints '2 3 3'. This is because our Generator is written to support a streaming interface (using atEnd
>             and peek) so it always computes one yield ahead.
>
>             In other languages (e.g. JavaScript, Python, C#) this is different, the execution is paused at the current yield statement, not 'before' the next
>             one. In general, a generator cannot know if there will be more "yields" without executing more code. In Javascript, 'next' returns both a value
>             and a 'done' flag, and if the flag is true, the returned value must not be used.
>
>             IMHO we should fix this - see attached changeset Marcel and I came up with. We did not fix the tests yet, but the behavior seems right.
>
>             Even though generators are in the image for a long time they are not used widely yet (AFAIK) so maybe we can still change the behavior? What do
>             people think?
>
>             - Bert & Marcel -
>
>
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Generators

Bert Freudenberg
On Thu, Apr 13, 2017 at 10:42 AM, Levente Uzonyi <[hidden email]> wrote:
It has nothing to do with the halting problem, because #atEnd don't have to tell if your generator will ever stop yielding or not. It should just tell if the upcoming #next send will return something meaningful or not.
The current implementation does exactly that.

Yes, but at the price of executing up to the next yield in advance. That's the only way it can know if the "upcoming #next send will return something meaningful or not".

Here's another example:

| generator |
generator := Generator on: [ :g | g yield: 1 ].
generator next; atEnd
"==> false"

In the current implementation it returns true.
 
In the new one, it returns false, you will have to send #next another time and check atEnd to see if the value returned from #next is an actual value, or not. This is the reason why I posted the JavaScript example - it returns the value plus the flag if the value is valid.

My point is that the stream-like API forces you to read one object ahead.
Which is why I suggested rewriting #do: to not use it.

We did rewrite #do: so it does the right thing. Are you suggesting we could rewrite #do: in the old implementation to do the right thing? That would be pretty awesome. 

In the end, what I want is this:

    | gen out x |
    
x := 0.
    
gen := Generator on: [ :g |
        
x := 1.
        
g yield: 'A'.
        
        
x := 2.
        
g yield: 'B'.
        
        
x := 3.
        
g yield: 'C'].
    
    
out := ''.
    
gen do: [ :s | out := out, x, s].
    
    
out = '1A2B3C'. 
    
"==> true"

If we can make that happen by slightly modifying the current implementation, great. I just don't know how to do it (other than the changeset we posted).

- Bert -