What would Squeak be like without non-local returns

Rob, ask this to a Compiler, an interpreter, but not to a Smalltalk
programmer please!


Rob Withers a écrit :

On 07/11/2007, Rob Withers <[hidden email]> wrote:
>
>
> I'll just throw this out and see what turns up.   As you have probably
> heard, I am toying with adding eventual refs to Squeak.  Unfortunately, they
> don't play well with non-local returns.  Igor and I had been discussing what
> could be done with methods having non-local returns adn it is looking nasty.
>   So I thought to look at another piece of the puzzle and question its
> existence.
>

I don't think that their existence are questionable.
Their have own purpose and in example you shown it proves that using
non-local returns is much more convenient and easier for developer.
If there are problems between exceptions/non-local returns and
eventual refs, then they must be solved in one way or another but
without sacrificing other language features.
When i started my comments about need of special care with any stack
unwinding operations i just wanted to point that you must take special
care. It not that easy as removing non-local returns, but its
solvable. So, i think, a better direction is to find a solution rather
than looking how to put new feature by removing old one.


--
Best regards,
Igor Stasenko AKA sig.

eventual refs?

        Mth



On Nov 7, 2007, at 12:48 AM, Rob Withers wrote:

>  As you have probably heard, I am toying with adding eventual refs  
> to Squeak.

----- Original Message -----
From: "Mathieu Suen" <[hidden email]>
To: "The general-purpose Squeak developers list"
<[hidden email]>
Sent: Tuesday, November 06, 2007 5:10 PM
Subject: Re: What would Squeak be like without non-local returns


> eventual refs?

This is what I am hoping to build: http://wiki.squeak.org/squeak/6011
This also describes some of what I was trying to do:
http://wiki.squeak.org/squeak/2410

The canonical source for this is here: http://www.erights.org.  I am reading
Mark Miller's thesis, which is excellent.

Rob

Are you saying you couldn't do without this feature?  I have to agree, but
still the question is worth asking.

----- Original Message -----
From: "nicolas cellier" <[hidden email]>
To: <[hidden email]>
Sent: Tuesday, November 06, 2007 4:03 PM
Subject: Re: What would Squeak be like without non-local returns

----- Original Message -----
From: "Igor Stasenko" <[hidden email]>
To: "The general-purpose Squeak developers list"
<[hidden email]>
Sent: Tuesday, November 06, 2007 4:19 PM
Subject: Re: What would Squeak be like without non-local returns


Yeah, I agree.  My brain is wired to think that way, cause if it is time to
exit the method, then go ahead.

> If there are problems between exceptions/non-local returns and
> eventual refs, then they must be solved in one way or another but
> without sacrificing other language features.

E states that non-local returns are bad and we are seeing th implications of
that statement.  Our candidate solution of mixing non-local returns and
eventual refs is not pretty.

> When i started my comments about need of special care with any stack
> unwinding operations i just wanted to point that you must take special
> care. It not that easy as removing non-local returns, but its
> solvable. So, i think, a better direction is to find a solution rather
> than looking how to put new feature by removing old one.

I wanted to consider the possibility.  We shouldn't leave rocks unturned.

Knowing we have blocks in play within the execution of a method, we say we
want to synchronize the execution of the method and not run it eventually.
How do we do this?

Cheers,
Rob

Your example is very speaking.
Searching such workaround and artefacts is contrary to Smalltalk spirit.
The simpler, the better, since it enables focusing more on contents than
on form.

Cheers

Rob Withers a écrit :

On 07/11/2007, Rob Withers <[hidden email]> wrote:
Yeah, but we talking about Smalltalk, not E. Maybe they are bad for E,
but why they should be bad for smalltalk? :)


Ok, lets look again on the problem.
Consider a code:
--
f := object future doSomeThing: someBlock.
a := a + 1.
f doSomeThingElse.
--

Semantically, if block (someBlock) does non-local return, that means
that next statements should not be evaluated at all means, because
this could lead to unpredictable behavior.

But there is no ways how to prevent that:
- any piece of code in #doSomeThing: can send a message to object(s)
which lead to execution of non-local returns or throwing an exception
causing stack unwinding.

This means that if you using futures/promises in your code, you can't
make this code to be semantically equivalent as with not using them.
In that way, i think, its better to think of how to prevent obvious
pitfalls and give developer a clear ways how to use eventual refs
safely or teach them (in some manner), that writing a code with
futures is something different than writing same code in imperative
fashion.

--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote:
> On 07/11/2007, Rob Withers <[hidden email]> wrote:
>> E states that non-local returns are bad and we are seeing th implications of
>> that statement.  Our candidate solution of mixing non-local returns and
>> eventual refs is not pretty.
>
> Yeah, but we talking about Smalltalk, not E. Maybe they are bad for E,
> but why they should be bad for smalltalk? :)

Indeed. And as a matter of fact I can't recall that particular
statement. Who said it and in what context? The main rule that matters
to E (for many reasons) is about globally mutable state which is a
complete no-no. But non-local returns? The only issue I can imagine with
this is that code could conceivably "escape" from an evaluation which
may make it harder for auditing but that's about all I can see.

Cheers,
   - Andreas

----- Original Message -----
From: "Andreas Raab" <[hidden email]>
To: "The general-purpose Squeak developers list"
<[hidden email]>
Sent: Tuesday, November 06, 2007 5:55 PM
Subject: Re: What would Squeak be like without non-local returns


Well, now I can't find that statement, but I was sure I had read it on
erights or Mark's thesis.  I searched and found nothing.  It may have been a
statement regarding eventual-sending specifically with non-local return.  It
IS strange thinking about the correct behavior of an expression:

object eventual ifTrue: [^3].
^4

What should be the result?

What I did find was discussion about escape from a block with an ejector,
which I had always wondered about.  It is non-local return from a
synchronous send.  Click on ii.3 Escape:
http://www.erights.org/elib/concurrency/msg-passing.html and also
http://www.erights.org/elang/kernel/EscapeExpr.html

Cheers,
Rob

----- Original Message -----
From: "Igor Stasenko" <[hidden email]>

Does it mean this?  Because this violates the rule that there should be no
blocking.   Msgs should just be sent.  Maybe the rule in play is that
someBlock does a non-local return that is no longer valid, because it was
scheduled eventually outside the scope of the method it could return from,
so it should cause an Error and the return value of doSomeThing: is a broken
ref.    A way out of this pickle?


> But there is no ways how to prevent that:
> - any piece of code in #doSomeThing: can send a message to object(s)
> which lead to execution of non-local returns or throwing an exception
> causing stack unwinding.

Ok, but if what I just said holds, then the unwinding terminates where the
msg was eventually sent and never gets to interact with the sending context.


> This means that if you using futures/promises in your code, you can't
> make this code to be semantically equivalent as with not using them.

I think that's true.

> In that way, i think, its better to think of how to prevent obvious
> pitfalls and give developer a clear ways how to use eventual refs
> safely or teach them (in some manner), that writing a code with
> futures is something different than writing same code in imperative
> fashion.

Yes, it is not transparent.   On the other hand, any ref could be eventual.
So the rules for how they behave in various imperative situations are
important.  As to how to write our example clearly, in the eventual style:

f := object future doSomeThing: someBlock.
f whenResolved: [:fVow |
    a := a + 1.
    fVow doSomeThingElse].

Rob

It seems like everything after has to become eventual.
But worse, some inst var could contain blocks with local return (see
ifFail: [^nil] pre-exception-handling kind in Compiler).

object eventual ifTrue: [failBlock value].
^4

Nothing obvious at compile time...

As already stated by Igor, you also have modern exception handling that
could play tricks...

Nicolas

Rob Withers a écrit :

On 07/11/2007, nicolas cellier <[hidden email]> wrote:
> It seems like everything after has to become eventual.
> But worse, some inst var could contain blocks with local return (see
> ifFail: [^nil] pre-exception-handling kind in Compiler).
>
> object eventual ifTrue: [failBlock value].
> ^4
>
> Nothing obvious at compile time...

Hmm, this creates a non-deterministic behavoir each time we using
non-local returns in futures.
suppose we having execution flow:
 A
/  \
B C
\  /
 D
 |
 E

Where A is our initial state where we divide our execution in two
parallel threads B and C (one of them considered as future).
Then, at some point we have both of them resolved and merged to single
thread again (D).
But in case of non-local return we actually should skip D, and jump
directly to state E.
The question is, if both B and C using non-local return, then which of
them should be granted as a result of computation? One, which emerged
from B, or from C?
If we use 'first who is done - is winner' rule, then it makes our
system very unpredictable, because due to scheduling there can be
situations where either B or C can return first even given same input
in algorithm.
Ok, then we come to point, that if one of them are exited non-locally,
we must wait for completion of another one, and only then decide which
result to use..
But question is stays: which return result to use?

--
Best regards,
Igor Stasenko AKA sig.

Rob Withers wrote:
Without any question, 4. Since ifTrue:[] is sent eventual it will return
immediately (answering a promise), and the method will continue and
return 4. There is absolutely no question about it.

When the eventual ifTrue: is executed it will barf because it will try
to return from a method with no home but that's the way out-of-scope
blocks go. It's just as well-defined as a non-local return from an
out-of-scope block today, e.g.,

Foo>>createBlock
   ^[^self]

Foo>>callBlock
   self createBlock value.

This will simply signal BlockCannotReturn and the eventual ifTrue:[]
will - and should - do the same.

Cheers,
   - Andreas

On 07/11/2007, Andreas Raab <[hidden email]> wrote:
Let suppose that Mr.Satan will rewrite an example above as following:

object eventual ifTrue: [100 atRandom seconds asDelay wait.  ^3].
100 atRandom seconds asDelay wait.
^4

When, in real case, a random delay could be replaced by any code which
needs a time to evaluate.
What is the answer then? :)

> Cheers,
>    - Andreas
>
>


--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote:
> Let suppose that Mr.Satan will rewrite an example above as following:
>
> object eventual ifTrue: [100 atRandom seconds asDelay wait.  ^3].
> 100 atRandom seconds asDelay wait.
> ^4
>
> When, in real case, a random delay could be replaced by any code which
> needs a time to evaluate.
> What is the answer then? :)

Same answer (though strictly speaking you may get an error that you
can't *wait* in an eventual system). The reason being that <object> will
only get an eventual ref to the block so it will only be able to send
other eventual messages to it. Put differently, ifTrue: would need to be
implemented as:

True>>ifTrue: aBlock
   "I am true, so evaluate aBlock"
   aBlock isBlock "if it's an immediate block..."
     ifTrue:[aBlock value] "... evaluate it directly ..."
     ifFalse:[aBlock eventual value] "... otherwise eventual"

(I'm ignoring the issues of meta-circularity for ifTrue: here; the above
is purely conceptual) The main point is that because the evaluation of
the block would be eventual it would *necessarily* evaluate after the
immediate delay and the entire message has completed *regardless* of how
long or how short that delay is. If that were different it would violate
one of the fundamental axioms of event-loop concurrency (the fact that
only one message is ever executed at the time) and wouldn't count as
message passing concurrency anymore.

Cheers,
   - Andreas

On 07/11/2007, Andreas Raab <[hidden email]> wrote: This doesn't change anything, you may put:
(1 to: 1000000 atRandom) do: [1+1]
instead of delay.

Hmm. An example above was to show that when running in parallel there
is equal chance to get to ^3 or ^4 first.
And in previous message you described behavior, when running code gets
to ^4 first. But what if it gets to ^3 first?
And if there no code running in parallel, then there's nothing to argue about.

> Cheers,
>    - Andreas
>
>


--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote:
> On 07/11/2007, Andreas Raab <[hidden email]> wrote:
>> Same answer (though strictly speaking you may get an error that you
>> can't *wait* in an eventual system).
> This doesn't change anything, you may put:
> (1 to: 1000000 atRandom) do: [1+1]
> instead of delay.

Sure. But it makes no difference. I was only pointing this out for
completeness.

> Hmm. An example above was to show that when running in parallel there
> is equal chance to get to ^3 or ^4 first.

No, there isn't. It's simply not how it works. This code cannot run in
parallel because it's on the same island (necessarily so for non-shared
state concurrency since blocks have access to receiver variables) and
can therefore *not* be executed in parallel. The order is completely
deterministic - scheduling the message in the future *guarantees* that
it will be executed only after the ^4 has completed. It can't be any
other way for it to work; if you'd want to run it in parallel you'd need
to copy it to a different island first in which case the return value
from the method would *still* be 4! It's completely deterministic, the
result is 4.

> And in previous message you described behavior, when running code gets
> to ^4 first. But what if it gets to ^3 first?

It cannot. It simply cannot. If you don't understand why, then you don't
fully understand how E and Croquet works. The block is created in the
same island as the receiver. When it is passed to another island (as
argument to the future ifTrue: message) it will be converted into a
remote reference. This reference only understands future messages (all
the immediate messages relate entirely to its role as a reference not
the underlying object) which is the reason why I distinguished these
cases in the True>>ifTrue: code (simply because #value on a remote
reference has no bearing on executing the block that this reference
points to but scheduling a future value message does).

This in turn means that the second island (the one containing the
boolean) *must schedule* the future #value with the first island which
means that the first island will only execute it after the ^4 has been
executed. It is the *only* way in which this can work in an event-loop
environment.

What happens is something like here:

Island A:                                     Island B:
->message starts running
   -> aBool future ifTrue:[] ..... -> .....  <schedules True>>ifTrue:>
   -> Delay wait

                        ... time passes ...
            <at this point Island A is running the message>
            <and Island B has the #ifTrue: message scheduled>

                                                -> executes True>>ifTrue:
    <schedules aBlock value>   ..... <- .....   <- aBlock future value
                                                -> True>>ifTrue: finishes

                      .... time passes ....
             <Island A is still not finished with the delay>
             <Island B has posted the eventual #value to Island A>

   -> Delay wait ends.
   -> message returns 4
-> message completes

        <Now, and *only* now the pending #value call will be executed>

-> aBlock value starts
    -> Attempts to [^3]
    -> Raises BlockCannotReturn


The result is 4. Each and every time.

Cheers,
   - Andreas

Consider the code

object eventual: [...  ^3]
...
^4

Depending on the missing code, it could return either 3 or 4.  If not,
something is very strange, and the language is no longer Smalltalk.

If you get rid of non-local returns, the language is no longer
Smalltalk.  it might be a good language, but it is not Smalltalk.

-Ralph