Smalltalk › Squeak › Squeak - Dev

Really strange problem

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

7 messages Options

CdAB63

Really strange problem

Hello,

I'm writing an example (a message for calculating combinations out of a collection and I found an amazing error. When line combOfRest := workList combinations: (n - 1) is called VM tries to evaluate things in the self context (as if workList was self) and then x is nil and that causes an error. Is this behavior expected?

I was expecting that workList combinations: x would be executed in a new context (since it's an instance of IntegerArray)

By the way, when I inspect I discover that there are 3 instances of x (one with right value, and two nil).

CdAB

IntegerArray>>combinations: n
    "This message returns all possible combinations of n elements from self"

    | theCombinations workList |

    "First let's check conditions"
    n class ~= SmallInteger ifTrue: [ self error: 'argument should be SmallInteger but is: ',n class asString ].
    (n < 1 or: [ n > self size ]) ifTrue: [ self error: 'argument out of range: ',n asString ].

    theCombinations := OrderedCollection new.

    "Basic case #1: size equals to data size"
    n = self size ifTrue: [
        | x |
        x := OrderedCollection newFrom: self.
        theCombinations add: x.
        ^theCombinations ].

    "Basic case #2: size equals to 1"
    n = 1 ifTrue: [
        1 to: self size do: [ :i |
            | x |
            x := OrderedCollection with: (self at: i).
            theCombinations add: x ].
        ^theCombinations ].

    workList := self class newFrom: self.

    "Generic case"
    1 to: self size - n + 1 do: [ :i |
        | x combOfRest |

        x := workList at: 1.

        workList := workList allButFirst.

        combOfRest := workList combinations: (n - 1).

        1 to: combOfRest size do: [ :j |
            (combOfRest at: j) add: x before: 1 ].

        theCombinations add: combOfRest ].

    ^theCombinations

Levente Uzonyi-2

Re: Really strange problem

On Tue, 18 Jan 2011, Casimiro de Almeida Barreto wrote:

> Hello,
>
> I'm writing an example (a message for calculating combinations out of a
> collection and I found an amazing error. When line combOfRest :=
> workList combinations: (n - 1) is called VM tries to evaluate things in
> the self context (as if workList was self) and then x is nil and that
> causes an error. Is this behavior expected?

Which VM and image do you use? (I couldn't reproduce this problem.)

But I found a bug in your code. This line:
(combOfRest at: j) add: x before: 1 ].
should probably be:
(combOfRest at: j) addFirst: x ].

And there's another bug(?) which causes your method to sometimes return a
hierarchical structure instead of simply a collection of collections. But
you shouldn't bother with it, because this method can be implemented much
easier:

SequenceableCollection >> combinations: n

^Array streamContents: [ :stream |
self combinations: n atATimeDo: [ :each |
stream nextPut: each copy ] ]

Levente

>
> I was expecting that workList combinations: x would be executed in a new
> context (since it's an instance of IntegerArray)
>
> By the way, when I inspect I discover that there are 3 instances of x
> (one with right value, and two nil).
>
> CdAB
>
> IntegerArray>>combinations: n
> "This message returns all possible combinations of n elements
> from self"
>
> | theCombinations workList |
>
> "First let's check conditions"
> n class ~= SmallInteger ifTrue: [ self error: 'argument should
> be SmallInteger but is: ',n class asString ].
> (n < 1 or: [ n > self size ]) ifTrue: [ self error: 'argument
> out of range: ',n asString ].
>
> theCombinations := OrderedCollection new.
>
> "Basic case #1: size equals to data size"
> n = self size ifTrue: [
> | x |
> x := OrderedCollection newFrom: self.
> theCombinations add: x.
> ^theCombinations ].
>
> "Basic case #2: size equals to 1"
> n = 1 ifTrue: [
> 1 to: self size do: [ :i |
> | x |
> x := OrderedCollection with: (self at: i).
> theCombinations add: x ].
> ^theCombinations ].
>
> workList := self class newFrom: self.
>
> "Generic case"
> 1 to: self size - n + 1 do: [ :i |
> | x combOfRest |
>
> x := workList at: 1.
>
> workList := workList allButFirst.
>
> *combOfRest := workList combinations: (n - 1)*.
>
> 1 to: combOfRest size do: [ :j |
> (combOfRest at: j) add: x before: 1 ].
>
> theCombinations add: combOfRest ].
>
> ^theCombinations
>
>
>
>
>
>
>

CdAB63

Re: Really strange problem

Em 18-01-2011 11:21, Levente Uzonyi escreveu:
> (...)
> Which VM and image do you use? (I couldn't reproduce this problem.)
Happens both VMs ("traditional" and cog)
>
> But I found a bug in your code. This line:
> (combOfRest at: j) add: x before: 1 ].
> should probably be:
> (combOfRest at: j) addFirst: x ].
Yes, but add: x before: 1 works...
>
> And there's another bug(?) which causes your method to sometimes
> return a hierarchical structure instead of simply a collection of
> collections. But you shouldn't bother with it, because this method can
> be implemented much easier:
Never even enters in this error case.

I'm concerned with the fact that

SomeClass>>method: x
| y |
...
y := self class new.
...
k := y method: z.

may fail because things are interpreted flatly (in the same context as
calling object)
>
> SequenceableCollection >> combinations: n
>
> ^Array streamContents: [ :stream |
> self combinations: n atATimeDo: [ :each |
> stream nextPut: each copy ] ]
>
Yeah, that works. Shorter & more elegant. Thnx.
>
> Levente

Levente Uzonyi-2

Re: Really strange problem

On Tue, 18 Jan 2011, Casimiro de Almeida Barreto wrote:

> Em 18-01-2011 11:21, Levente Uzonyi escreveu:
>> (...)
>> Which VM and image do you use? (I couldn't reproduce this problem.)
> Happens both VMs ("traditional" and cog)

Doesn't happen for me with Cog version 2349. What's your test case?

>>
>> But I found a bug in your code. This line:
>> (combOfRest at: j) add: x before: 1 ].
>> should probably be:
>> (combOfRest at: j) addFirst: x ].
> Yes, but add: x before: 1 works...

It means that you want to add x before the element 1 in the collection. If
1 is not in the collection (which is the case most of the time), then it
doesn't work.

Levente

>>
>> And there's another bug(?) which causes your method to sometimes
>> return a hierarchical structure instead of simply a collection of
>> collections. But you shouldn't bother with it, because this method can
>> be implemented much easier:
> Never even enters in this error case.
>
> I'm concerned with the fact that
>
> SomeClass>>method: x
> | y |
> ...
> y := self class new.
> ...
> k := y method: z.
>
> may fail because things are interpreted flatly (in the same context as
> calling object)
>>
>> SequenceableCollection >> combinations: n
>>
>> ^Array streamContents: [ :stream |
>> self combinations: n atATimeDo: [ :each |
>> stream nextPut: each copy ] ]
>>
> Yeah, that works. Shorter & more elegant. Thnx.
>>
>> Levente
>
>
>

CdAB63

Re: Really strange problem

Em 18-01-2011 12:03, Levente Uzonyi escreveu:
> On Tue, 18 Jan 2011, Casimiro de Almeida Barreto wrote:
>
>> Em 18-01-2011 11:21, Levente Uzonyi escreveu:
>>> (...)
>>> Which VM and image do you use? (I couldn't reproduce this problem.)
>> Happens both VMs ("traditional" and cog)
>
> Doesn't happen for me with Cog version 2349. What's your test case?
[casimiro@localhost 3.9-7]$ ./squeak -version
3.9-7 #1 Ter Jan 4 16:12:30 BRST 2011 gcc 4.5.1
Croquet Closure Cog VM [CoInterpreter VMMaker-oscog.43]
Linux localhost.localdomain 2.6.35.10-74.fc14.i686.PAE #1 SMP Thu Dec 23
16:10:47 UTC 2010 i686 i686 i386 GNU/Linux
plugin path: /opt/cog/lib/squeak/3.9-7/ [default:
/opt/cog/lib/squeak/3.9-7/]

Downloaded in 2011/01/04 16:01 using: svn co
http://www.squeakvm.org/svn/squeak/branches/Cog/

Same error as standard VM.

>
>>>
>>> But I found a bug in your code. This line:
>>> (combOfRest at: j) add: x before: 1 ].
>>> should probably be:
>>> (combOfRest at: j) addFirst: x ].
>> Yes, but add: x before: 1 works...
>
> It means that you want to add x before the element 1 in the
> collection. If 1 is not in the collection (which is the case most of
> the time), then it doesn't work.
>
>
> Levente

Levente Uzonyi-2

Re: Really strange problem

On Tue, 18 Jan 2011, Casimiro de Almeida Barreto wrote:

> Em 18-01-2011 12:03, Levente Uzonyi escreveu:
>> On Tue, 18 Jan 2011, Casimiro de Almeida Barreto wrote:
>>
>>> Em 18-01-2011 11:21, Levente Uzonyi escreveu:
>>>> (...)
>>>> Which VM and image do you use? (I couldn't reproduce this problem.)
>>> Happens both VMs ("traditional" and cog)
>>
>> Doesn't happen for me with Cog version 2349. What's your test case?
> [casimiro@localhost 3.9-7]$ ./squeak -version
> 3.9-7 #1 Ter Jan 4 16:12:30 BRST 2011 gcc 4.5.1
> Croquet Closure Cog VM [CoInterpreter VMMaker-oscog.43]

AFAIK this version of Cog had some bugs that could cause such issues. Also
using gcc 4.5 may introduce problems. I'll try it with SqueakVM soon, but
if you compiled yours with gcc 4.5, then it *may* also be the cause of the
problems.

Levente

> Linux localhost.localdomain 2.6.35.10-74.fc14.i686.PAE #1 SMP Thu Dec 23
> 16:10:47 UTC 2010 i686 i686 i386 GNU/Linux
> plugin path: /opt/cog/lib/squeak/3.9-7/ [default:
> /opt/cog/lib/squeak/3.9-7/]
>
> Downloaded in 2011/01/04 16:01 using: svn co
> http://www.squeakvm.org/svn/squeak/branches/Cog/
>
> Same error as standard VM.
>>
>>>>
>>>> But I found a bug in your code. This line:
>>>> (combOfRest at: j) add: x before: 1 ].
>>>> should probably be:
>>>> (combOfRest at: j) addFirst: x ].
>>> Yes, but add: x before: 1 works...
>>
>> It means that you want to add x before the element 1 in the
>> collection. If 1 is not in the collection (which is the case most of
>> the time), then it doesn't work.
>>
>>
>> Levente
>
>
>

CdAB63

Re: Really strange problem

In reply to this post by Levente Uzonyi-2

Ok: I found the problem. There was a border condition I imposed on
lengths and values and then workList went nil if size < a certain
established size.

Nothing related to VM...

BTW thanks Levente for your help !!!

CdAB

signature.asc (269 bytes) Download Attachment