Closure Compiler in 3.9 ?

>> The queastion remains: why does the mere existence of such recursive
>> structures throw Squeak into a tizzy?
>> No one answered this.  What does the doIt mechanism do before it  
>> executes my
>> code?
>
> This is because the compiler internally stores the bindings of the
> Workspace in a dictionary with the binding-association as a key.
> Unfortunately the association are calculating the #hash using the key
> and the value, what causes an infinite recursion on your dictionary
> before you code is even compiled.

> There is a reason why this is not done in Smalltalk. Have a look at
> the examples below:
>
> aClass>>add: a with: b
>     b = 0 ifTrue: [ SomeGlobal := thisContext ].
>     ^ self add: a with: b+1
>
> aClass>>add: a with: b
>     self become: #zork.
>     ^ self add: a with: b+1
>
> aClass>>add: a with: b
>     self class removeSelector: #add:with:.
>     ^ self add: a with: b+1
>
> There is an infinite number of other examples.

>> Cue another long discussion about hashing.
>>
>> Just what do you believe the hash value should be based on?
>
> What about the key only?
>
> I quickly had a look at some other Smalltalk implementations (VW,
> Dolphin, Ambrai) they all use the key for hashing only.
>
> Lukas
>
> --  
> Lukas Renggli
> http://www.lukas-renggli.ch
>

>> Cue another long discussion about hashing.
>>
>> Just what do you believe the hash value should be based on?
>
> What about the key only?
>
> I quickly had a look at some other Smalltalk implementations (VW,
> Dolphin, Ambrai) they all use the key for hashing only.
>
> Lukas
>

>From: "Lukas Renggli" <[hidden email]>
>Reply-To: The general-purpose Squeak developers
>list<[hidden email]>
>To: "The general-purpose Squeak developers
>list"<[hidden email]>
>Subject: Re: Equality of Recursive Structures [Was: Closure Compiler in
>3.9?]
>Date: Fri, 11 May 2007 21:10:46 +0200
>
>>Cue another long discussion about hashing.
>>
>>Just what do you believe the hash value should be based on?
>
>What about the key only?
>
>I quickly had a look at some other Smalltalk implementations (VW,
>Dolphin, Ambrai) they all use the key for hashing only.
>
>Lukas
>
>--
>Lukas Renggli
>http://www.lukas-renggli.ch
>

> Lukas Renggli a écrit :
> >> Cue another long discussion about hashing.
> >>
> >> Just what do you believe the hash value should be based on?
> >
> > What about the key only?
> >
> > I quickly had a look at some other Smalltalk implementations (VW,
> > Dolphin, Ambrai) they all use the key for hashing only.
> >
> > Lukas
> >
>
> As a LookupKey, Association should behave like Lukas said.
> Also, look at this funny bug introduced by Association>>#= :
>
> | a1 a2 |
> a1 := #a -> 1.
> a2 := #a -> 2.
> {a1 >= a2. a2 >= a1. a1 = a2}
>         "true, true, false"
>
> I do not know how mathematicians do qualify this kind of relation...
>
>
> But among more than 30 references to Association, and 100 sendes of #->
> how to tell whether Association>>#= ever need to test the value ?
> (this is of course why Associations>>#hash is defined )
>
> Quiet sure there are some uses that do not consider Association like a
> LookupKey but just as a C++ std::pair.
>
> Nicolas
>

>
> >From: "Lukas Renggli" <[hidden email]>
> >Reply-To: The general-purpose Squeak developers
> >list<[hidden email]>
> >To: "The general-purpose Squeak developers
> >list"<[hidden email]>
> >Subject: Re: Equality of Recursive Structures [Was: Closure Compiler in
> >3.9?]
> >Date: Fri, 11 May 2007 21:10:46 +0200
> >
> >>Cue another long discussion about hashing.
> >>
> >>Just what do you believe the hash value should be based on?
> >
> >What about the key only?
> >
> >I quickly had a look at some other Smalltalk implementations (VW,
> >Dolphin, Ambrai) they all use the key for hashing only.
> >
> >Lukas
> >
> >--
> >Lukas Renggli
> >http://www.lukas-renggli.ch
> >
>
> _________________________________________________________________
> Catch suspicious messages before you open them—with Windows Live Hotmail.
> http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migration_HM_mini_protection_0507
>
>
>

> thanks for the email. It was cool.
> I learned something today.
>
> Stef
>
> On 10 mai 07, at 08:46, Andrew P. Black wrote:
>
>> This started as a story about what I realized in the shower this  
>> morning, and ended up as a story about what I don't know about  
>> Squeak (again :-( )
>>
>> On 8 May 2007, at 17:12, Andreas Raab wrote:
>>
>>> A while ago Association>>= was changed to compare the values in  
>>> addition to its keys which has bitten me many, many times since  
>>> it was introduced. Most likely it is the culprit here, too.
>>
>> No, Andreas, this was a different problem but an interesting one.  
>> This is the third time in my life that i has bitten me.  It's  
>> worth writing a pattern about: comparing recursive structures.
>>
>> Suppose that you have two potentially recursive data structures,  
>> and you need to compare them — perhaps for equality, or perhaps  
>> for dominance of one over the other.  (I met this problem first  
>> when figuring out the type conformance algorithm for Emerald in  
>> about 1984.)
>>
>> To be concrete, suppose that the structures are dictionaries,  
>> which contain simple data as keys (like symbols), and more complex  
>> data as values — including, perhaps, other dictionaries.  The  
>> obvious thing is to walk both structures in parallel, checking  
>> that they have the same keys, and that the values for each  
>> occurrence of a key are also the same.   It's possible that those  
>> values are also dictionaries, in which case you execute the same =  
>> code that you were in the middle of running ...
>>
>> This is not a problem, unless: the dictionary stored in the  
>> dictionary is the very same dictionary that you started with.  In  
>> which case, the naive recursive search will go on for ever.
>>
>> I first met this in Squeak when I executed Smalltalk = Smalltalk.  
>> Of course, Smalltalk, as the dictionary of all globals, includes  
>> Smalltalk as a value, and the equality computation never  
>> terminated.  I filed a bug fix for that one, and it's in the image  
>> now.  My fix was to simply compare the two objects for identity  
>> first, and only then do the recursive equality check.  This, or  
>> course, answers true ot Smalltalk = Smalltalk quite quickly.
>>
>> The situation is the same with my recursive block example.
>>
>> b := [(i:= i-1) > 0 ifTrue: [j := j+1 . b value.] ifFalse:[j]] .
>>
>> It's compiled as a method, which has (presumably, I haven't  
>> looked) a literal that points to itself ... and the equality  
>> comparision goes on forever.  Why Squeak was doing an equality  
>> comparision when all I asked for was to "DoIt" is another question.
>>
>> I'm deducing all this from Mathieu's fix.   The identity test  
>> isn't a complete fix, however.  If you have two isomorphic  
>> recursive structures that don't share any elements, the test will  
>> still go on for ever.
>>
>> Here is a small example: two isomorphic one-element dictionaries.  
>> Type this in a workspace (BUT DON"T TRY THIS IN AN IMAGE THAT YOU  
>> WANT TO KEEP USING!)
>>
>> a := Dictionary new.
>> a at: #foo put: a.
>> b := Dictionary new.
>> b at: #foo put: b.
>>
>> I expected that if I then did a printIt on a==b, I would get an  
>> immediate "false", but if I did a printit on a=b, the system would  
>> go off into never-land.
>>
>> But actually, it's more interesting than that.  The system goes  
>> off into never-land almost regardless of what you do!  Debug it a  
>> == b will do it.  So will a simple printIt of b or inspectIt of  
>> b.  A doIt of "self halt. a == b" goes into a loop /before/  
>> executing the self halt.  If you interrupt the computation, you  
>> can look at b in the debugger, and even launch an inspector from  
>> there: printStringLimtedTo: does its job, as it's supposed to.  
>> The system is trying to evaluate hash on the cyclic dictionary;  
>> hash is also broken for the same reason.  Asking for a fullStack  
>> in the debugger to see _why_ it's trying to compute hash puts the  
>> system into another recursive loop!
>>
>> This explains why I saw the same behavior with my recursive block,  
>> but not the root cause.  Anyone have an explanation?
>>
>> By the way, the real solution to the recursive equality comparison  
>> is to maintain a cache.
>> A pair of elements goes into the cache when you start to comapre  
>> them for equality.  If, in the process of doing the comparision,  
>> you find that you are asking the same equaility question again,  
>> then the second time around, you can assume that the answer is  
>> true.  This is OK, evne though you haven't finished doing the  
>> comparison yet.  If it turns out that there is indeed a  
>> difference, the "outer" equality will eventually find it, and will  
>> answer false.   The same trick can be employed for computing the  
>> hash.  Assume that the hash of the structure that you are  
>> computing the has over is some constant, say 0.  Start computing  
>> its hash, but if you find in the process that you need to compute  
>> the has of the same structure again, then just assume that it is  
>> 0.  The "real" hash might be thought of as the fixed-point of this  
>> process, but since hashes are just approximations anyway, once  
>> around the loop is enough.
>>
>> The queation remains: why does the mere existence of such  
>> recursive structures throw Squeak into a tizzy?
>>
>> Andrew
>>
>>
>>
>>
>
>
>

> Tony Garnock-Jones wrote:
>> sig wrote:
>>> But then, what to deal with such cases:
>>>
>>> aClass>>add: a with: b
>>> ^ self add: a with: b+1
>> This is a call in tail position, and it's a crying shame that the Squeak
>> VM doesn't presently allow the associated degenerate stack frames to be
>> elided.
>
> Lukas Renggli gave a series of examples where replacing the "tail send"
> with a "goto" would give use the wrong semantics. That, however, is a
> separate issue from avoiding the creation of stack frames.
>
> Dan Ingalls said that VM implementors can cheat as long as they don't
> get caught and if you ever get into the debugger you will certainly
> notice the lack of some stack frames and will curse whoever had the
> brilhant idea of eliminating them to get some extra speed. The Self guys
> were very fanatical about not getting caught this way no matter what the
> costs in terms of performance.
>
> For tinySelf 1, however, the cost in performance would have been
> extremely high since having tail send optimization made programs far
> more parallel than they would be otherwise. Unfortunately this single
> feature was responsible for practically all the hard to find bugs in the
> implementation and so when I had to move on to another project they
> became the reason why tinySelf 1 remained unfinished. Given this
> experience I think it would have been better for me to first have made
> the system fully functional without this optimization and then add it in
> a second version. But I would have added it.
>
> - -Jecel
>
>

> > aClass>>add: a with: b
> >    self become: #zork.
> >    ^ self add: a with: b+1
> >
> > aClass>>add: a with: b
> >    self class removeSelector: #add:with:.
> >    ^ self add: a with: b+1
>
> Neither of these are affected at all by removing the no-op frames,
> unless I'm missing something.

>> One more example, that is even more striking and that doesn't use
>> nasty reflection tricks. Imagine that #add:with: was called from a
>> subclass implementation using super. Recycling the stack would  
>> clearly
>> change the behavior of the code:
>
> How? The stack frame, at the point the super send has just been made,
> has exactly one role remaining: to return to its caller. Nothing can
> happen between the stack frame becoming active again and its immediate
> return to its calling frame.