Full closure workaround question

Blair,

I had an interesting bug crop up a couple of days ago - well, meltdown might
be a better word for it  =:0   I tracked it down to one of two things: (1) a
thread synchronization problem; (2) something that requires full block
closures.  Thinking it might be the latter, I did some searching in the
archives, and became even more suspicious that it was a closure issue.

One caveat is that the block that seems to be causing the problem receives a
fairly complicated version of #ensure:  - something that evaluates the
block, and then some.  That whole block/evaluation-message jumble is inside
a loop, and ended up being evaluated with the last loop argument.  At first,
I added a method that answered the block but left the evaluation in place,
with no help.  A second attempt moving the block and evaluation message into
a separate method seems to correct the problem.

Are you buying it? :)

Have a good one,

Bill

--
Wilhelm K. Schwab, Ph.D.
[hidden email]

"Bill Schwab" <[hidden email]> wrote in message
news:b07r58$m1i67$[hidden email]...

> I had an interesting bug crop up a couple of days ago - well, meltdown
might
> be a better word for it  =:0   I tracked it down to one of two things: (1)
a
> thread synchronization problem; (2) something that requires full block
> closures.  Thinking it might be the latter, I did some searching in the
> archives, and became even more suspicious that it was a closure issue.
>
> One caveat is that the block that seems to be causing the problem receives
a
> fairly complicated version of #ensure:  - something that evaluates the
> block, and then some.  That whole block/evaluation-message jumble is
inside
> a loop, and ended up being evaluated with the last loop argument.  At
first,
> I added a method that answered the block but left the evaluation in place,
> with no help.  A second attempt moving the block and evaluation message
into
> a separate method seems to correct the problem.

Are you creating a block inside another block and evaluating the inside
block after the outside block terminates? For example, the following
evaluates to 100 in D5, but it should evaluate to 55:
    ((1 to: 10) collect: [:i | [i]]) inject: 0 into: [:sum :each | sum +
each value]
If it used real closures, then it would evaluate to 55 (both VW & VA do). If
you extract "[i]" into another method, then when you call the method, it
creates a context for that method and the block is evaluated in that
context, so it would evaluate correctly.

Even with full closures, you can have problems with some compiler
optimizations. For example, if we modify the code above to use a #to:do:
loop, we'll get 110 in D5 and 100 in VA:
    | blocks |
    blocks := OrderedCollection new.
    1 to: 10 do: [:i | blocks add: [i]].
    blocks inject: 0 into: [:sum :each | sum + each value]
VA uses real closures, but they also optimize the #to:do:. In the #to:do:
optimization they use the same "i" for each iteration of the block so when
the blocks are evaluated they refer to the same value: 10. VW gives the
correct answer for this one. Whenever they create the [i] block, they create
a copying block which copies the current value of "i" into the new block
closure object.


John Brant

> ((1 to: 10) collect: [:i | [i]]) inject: 0 into: [:sum :each | sum + each
value]

> | blocks |
>   blocks := OrderedCollection new.
>   1 to: 10 do: [:i | blocks add: [i]].
>   blocks inject: 0 into: [:sum :each | sum + each value]

BTW: Squeak 3.2 has the same behaviour as Dolphin in both examples.

Ciao

...Jochen

"Bill Schwab" <[hidden email]> wrote in message
news:b07r58$m1i67$[hidden email]...
> Blair,
>
> I had an interesting bug crop up a couple of days ago - well, meltdown
might
> be a better word for it  =:0   I tracked it down to one of two things: (1)
a
> thread synchronization problem; (2) something that requires full block
> closures.  Thinking it might be the latter, I did some searching in the
> archives, and became even more suspicious that it was a closure issue.
>
> One caveat is that the block that seems to be causing the problem receives
a
> fairly complicated version of #ensure:  - something that evaluates the
> block, and then some.  That whole block/evaluation-message jumble is
inside
> a loop, and ended up being evaluated with the last loop argument.  At
first,
> I added a method that answered the block but left the evaluation in place,
> with no help.  A second attempt moving the block and evaluation message
into
> a separate method seems to correct the problem.
>
> Are you buying it? :)

Most issues with Smalltalk-80 style blocks not being proper closures can
indeed be solved by extracting the code into a method.

Whether this is applicable in this case I don't know, but the sort of things
to look out for are places that capture blocks and then share them, loops
that collect blocks, recursive blocks. All the problems arise because the
blocks store their temps (including arguments) in a shared location (the
MethodContext) associated with the activation of the home method. This
sometimes means that temporary variable slots will be shared when they
shouldn't be.

This sort of thing will not be a problem in D6, which supports full
closures.

Regards

Blair

"Jochen Riekhof" <[hidden email]> wrote in message
news:[hidden email]...
> > ((1 to: 10) collect: [:i | [i]]) inject: 0 into: [:sum :each | sum +
each
> value]
>
> > | blocks |
> >   blocks := OrderedCollection new.
> >   1 to: 10 do: [:i | blocks add: [i]].
> >   blocks inject: 0 into: [:sum :each | sum + each value]
>
> BTW: Squeak 3.2 has the same behaviour as Dolphin in both examples.


And Dolphin 6 gives the correct (55) result in both cases.

It is possible to construct some examples where the inlined code created by
the Dolphin 6 compiler doesn't give the correct result because the inlined
code stores its temps in the context of the method where true blocks would
not. Here's a case in point:

| i factorial |
factorial := i := 1.
[i <= 10] whileTrue: [| j | j isNil ifTrue: [j := i].
    factorial := factorial * j. j := i. i := i + 1].
self assert: factorial = 10 factorial

This test fails in D6, although one can at least make it work this way:

...
block := [| j | j isNil ifTrue: [j := i]. factorial := factorial * j. j :=
i. i := i + 1].
[i <= 10] whileTrue: block.
...

or by "perform"ing the #whileTrue:, since either way the compiler inlining
of the #whileTrue: argumjent block will be supressed. On D5 it will be fail
either way.

One could detect cases like this and insert an instruction to nil the temp
at the start of each loop evaluation (and I believe VW does do this), but we
didn't consider it worthwhile.

Regards

Blair

Blair and others,

> Most issues with Smalltalk-80 style blocks not being proper closures can
> indeed be solved by extracting the code into a method.
>
> Whether this is applicable in this case I don't know, but the sort of
things
> to look out for are places that capture blocks and then share them, loops
> that collect blocks, recursive blocks. All the problems arise because the
> blocks store their temps (including arguments) in a shared location (the
> MethodContext) associated with the activation of the home method. This
> sometimes means that temporary variable slots will be shared when they
> shouldn't be.

Thanks for the summary!


> This sort of thing will not be a problem in D6, which supports full
> closures.

That will be most welcome, but my main concern now is to not falsely blame
it on lack of full closures.  Combining the various replies, I get the sense
that it is in fact plausible that a little too much shared state is the
cause.

There is one more problem I need to find, but it looks like a classic "why
won't this object go away?" kind of bug.  So far it's being stubborn.  The
ReferenceFinder seems to be pointing only at the event mechanism, which
shouldn't be able to hold the objects by itself.  The objects in question
are derived from ProtoObject, but I am using (I think<g>) the relevant fixes
from the beta patch.  As promised, I will soon install the whole thing to
see if that makes a difference.

Have a good one,

Bill

--
Wilhelm K. Schwab, Ph.D.
[hidden email]

"Blair McGlashan" <[hidden email]> wrote in message
news:b0eins$okd57$[hidden email]...

> It is possible to construct some examples where the inlined code created
by fail
> either way.
>
> One could detect cases like this and insert an instruction to nil the temp
> at the start of each loop evaluation (and I believe VW does do this), but
we
> didn't consider it worthwhile.

You can use the RBReadBeforeWrittenTester class to find which variables need
to be assigned to nil. It uses a conservative analysis so it may return some
variables that are actually written before read. VW's read before written
analysis isn't conservative and sometimes produces incorrect results. For
example, by changing your code somewhat, we can make VW produce the same
result as Dolphin:
    | i factorial |
    factorial := i := 1.
    [i <= 10] whileTrue:
        [| j |
        2 = 3 ifTrue: [j := 1].
        j isNil ifTrue: [j := i].
        factorial := factorial * j.
        j := i.
        i := i + 1].
    factorial = 10 factorial
The "2=3" line makes VW believe that j is assigned. Of course, that only
happens if I redefine SmallInteger>>=. :-)


John Brant

John,

> You can use the RBReadBeforeWrittenTester class to find which variables
need
> to be assigned to nil. It uses a conservative analysis so it may return
some
> variables that are actually written before read. VW's read before written
> analysis isn't conservative and sometimes produces incorrect results. For
> example, by changing your code somewhat, we can make VW produce the same
> result as Dolphin:

Are you even suggesting<g> that it could sniff out a block temporary that,
if not set to nil, could be causing my recent non-gc snag?  How much code
would it need to see?  Just the offending method (contaning "the" block), or
the whole system?

Have a good one,

Bill

--
Wilhelm K. Schwab, Ph.D.
[hidden email]

"Bill Schwab" <[hidden email]> wrote in message
news:b0hhdi$83$[hidden email]...

> > You can use the RBReadBeforeWrittenTester class to find which variables
> need
> > to be assigned to nil. It uses a conservative analysis so it may return
> some
> > variables that are actually written before read. VW's read before
written
> > analysis isn't conservative and sometimes produces incorrect results.
For
> > example, by changing your code somewhat, we can make VW produce the same
> > result as Dolphin:
>
> Are you even suggesting<g> that it could sniff out a block temporary that,
> if not set to nil, could be causing my recent non-gc snag?  How much code
> would it need to see?  Just the offending method (contaning "the" block),
or
> the whole system?

No, it was more of a suggestion to Blair. However, if you want to see
methods that have variables possibly read before written, then you can run
the "Temporaries read before written" lint rule. Without the Smalllint
interface, you can use something like:
    | methods |
    methods := OrderedCollection new.
    (SmalllintChecker runRule: BlockLintRule tempsReadBeforeWritten
        onEnvironment: (BrowserEnvironment new forPackages: (Array
                    with: (SmalltalkSystem current packageManager
packageNamed: 'RBRefactorings'))))
            result
            classesAndSelectorsDo: [:class :selector | methods add: (class
compiledMethodAt: selector)].
    SmalltalkSystem current browseMethods: methods
This will open a method browser on the methods in RBRefactorings that have
temporaries that are possibly read before written.


John Brant

Blair McGlashan wrote:

> ... Most issues with Smalltalk-80 style blocks not being proper
> closures can indeed be solved by extracting the code into a method.

My main concern is a method like:

  myMethod
  |temp |
   temp := 0 .
  ^[ temp := temp + 1.  temp ]

Do these work in Dolphin, and in which version?
Thanks

-Panu Viljamaa

panu wrote:
This should work in all Smalltalks.  It doesn't depend on having full
closures.  It depends on a block closing over temp, which it does.

The lack of full closures in the Blue Book (Dolphin) scheme has two
effects.  

1.  The arguments of a block aren't local to that block; they're
actually temporaries of the enclosing method.  e.g. with blue book
blocks in

        | fact |
        fact := [:n| n = 0 ifTrue: [n] isFalse: [(fact value: n - 1) * n]

n is actually a temporary at the same level as fact.  Were we to use
full closures to get the same effect it would be rewritten as

        | fact n |
        fact := [:nx| n := nx. n = 0 ifTrue: [n] isFalse: [(fact value: n - 1)
* n]

which shows the problem; n is overwritten each time fact is evaluated so
fact evaluates to 0 for all positive integral arguments, but the
following works since n is referenced before it is overwritten:

        | fact n |
        fact := [:nx| n := nx. n = 0 ifTrue: [n] isFalse: [n * (fact value: n -
1)]

2. blue book blocks are represented as partially initialized instances
of BlockContext, i.e. by an activation of the block.  Any attempt to
recurse causes the single activation's sender and pc to be overwritten,
breaking recursion.  There is a simple work-around which is to make the
value primitives create a copy of the BlockContext as was done in the
Tektronix Smalltalk-80 implementation and might well be done in DOlphin,
Blair?

So the only issue that bites is 1. and it is due to the blue book
bytecode set not providing bytecodes to address local temporaries or
temps at particular nesting levels.  But this doesn't affect a block's
ability to function as a closure as long as the block is not activated
concurrently more than once (e.g. used recursively or shared between
processes).

And of course one needs to say that this problem only affects blue book
implementations, namely Squeak, Dolphin and ObjectStudio.  VisualWorks,
VisualAge, GemStone, Agents, S# et al are all full closure
implementations.

> Thanks
>
> -Panu Viljamaa

--
_______________,,,^..^,,,____________________________
Eliot Miranda              Smalltalk - Scene not herd

"Eliot Miranda" <[hidden email]> wrote in message
news:[hidden email]...
> ...snip...
> 2. blue book blocks are represented as partially initialized instances
> of BlockContext, i.e. by an activation of the block.  Any attempt to
> recurse causes the single activation's sender and pc to be overwritten,
> breaking recursion.  There is a simple work-around which is to make the
> value primitives create a copy of the BlockContext as was done in the
> Tektronix Smalltalk-80 implementation and might well be done in DOlphin,
> Blair?

Dolphin has always represented the activation separately from the block
itself (it uses an explicit stack to represent activations), so (2) is not
an issue.

As will be (is) Dolphin 6.

Regards

Blair