Understanding GNU Smalltalk Closure

The following piece of code is giving the error error: did not understand '#generality'

pqueue := SortedCollection new.
freqtable keysAndValuesDo: [:key :value |
   (value notNil and: [value > 0]) ifTrue: [
      |newvalue|
       newvalue := Leaf new: key count: value.
       pqueue add: newvalue.
   ]
].

    [pqueue size > 1] whileTrue:[
      |first second new_internal  newcount|
      first := pqueue removeFirst.
      second := pqueue removeFirst.
      first_count := first count.
      second_count := second count.
      newcount := first_count + second_count.
      new_internal := Tree new: nl count: newcount left: first right: second.
      pqueue add: new_internal.
    ].

The inconsistency is in the line pqueue add: new_internal. When I remove this line, the program compiles. I think the problem is related to the iteration block [pqueue size > 1] whileTrue: and pqueue add: new_internal.

Note: This is the algorithm to build the decoding tree based on huffman code.

error-message expanded

Object: $<10> error: did not understand #generality
MessageNotUnderstood(Exception)>>signal (ExcHandling.st:254)
Character(Object)>>doesNotUnderstand: #generality (SysExcept.st:1448)
SmallInteger(Number)>>retryDifferenceCoercing: (Number.st:357)
SmallInteger(Number)>>retryRelationalOp:coercing: (Number.st:295)
SmallInteger>><= (SmallInt.st:215)
Leaf>><= (hzip.st:30)
optimized [] in SortedCollection class>>defaultSortBlock (SortCollect.st:7)
SortedCollection>>insertionIndexFor:upTo: (SortCollect.st:702)
[] in SortedCollection>>merge (SortCollect.st:531)
SortedCollection(SequenceableCollection)>>reverseDo: (SeqCollect.st:958)
SortedCollection>>merge (SortCollect.st:528)
SortedCollection>>beConsistent (SortCollect.st:204)
SortedCollection(OrderedCollection)>>removeFirst (OrderColl.st:295)
optimized [] in UndefinedObject>>executeStatements (hzip.st:156)
BlockClosure>>whileTrue: (BlkClosure.st:328)
UndefinedObject>>executeStatements (hzip.st:154)
Object: $<10> error: did not understand #generality
MessageNotUnderstood(Exception)>>signal (ExcHandling.st:254)
Character(Object)>>doesNotUnderstand: #generality (SysExcept.st:1448)
SmallInteger(Number)>>retryDifferenceCoercing: (Number.st:357)
SmallInteger(Number)>>retryRelationalOp:coercing: (Number.st:295)
SmallInteger>><= (SmallInt.st:215)
Leaf>><= (hzip.st:30)
optimized [] in SortedCollection class>>defaultSortBlock (SortCollect.st:7)
SortedCollection>>insertionIndexFor:upTo: (SortCollect.st:702)
[] in SortedCollection>>merge (SortCollect.st:531)
SortedCollection(SequenceableCollection)>>reverseDo: (SeqCollect.st:958)
SortedCollection>>merge (SortCollect.st:528)
SortedCollection>>beConsistent (SortCollect.st:204)
SortedCollection(OrderedCollection)>>do: (OrderColl.st:64)
UndefinedObject>>executeStatements (hzip.st:164)

Solution

One learning we can take from this question is to acquire the habit of reading the stack trace trying to make sense of it. Let's focus in the last few messages:

1. Object: $<10> error: did not understand #generality
2. MessageNotUnderstood(Exception)>>signal (ExcHandling.st:254)
3. Character(Object)>>doesNotUnderstand: #generality (SysExcept.st:1448)
4. SmallInteger(Number)>>retryDifferenceCoercing: (Number.st:357)
5. SmallInteger(Number)>>retryRelationalOp:coercing: (Number.st:295)
6. SmallInteger>><= (SmallInt.st:215)
7. Leaf>><= (hzip.st:30)
8. optimized [] in SortedCollection class>>defaultSortBlock (SortCollect.st:7)

Each of these lines represents the activation of a method. Every line represents a message and the sequence of messages goes upwards (as it happens in any Stack.) The full detail of every activation can be seen in the debugger. Here, however, we only are presented with the class >> #selector pair. There are several interesting facts we can identify from this summarized information:

In line 1 we get the actual error. In this case we got a MessageNotUnderstood exception. The receiver of the message was the Character $<10>, i.e., the linefeed character.
Lines 2 and 3 confirm that the not understood message was #generality.
Lines 4, 5 and 6 show the progression of messages that ended up sending #generality to the wrong object (linefeed). While 4 and 5 might look obscure for the non-experienced Smalltalker, line 6 has the key information: some SmallInteger received the <= message. This message would fail because the argument wasn't the appropriate one. From the information we already got we know that the argument was the linefeed character.
Line 7 shows that SmallInteger >> #<= came from the way the same selector #<= is implemented in Leaf. It tells us that a Leaf delegates #<= to some Integer known to it.
Line 8 says why we are dealing with the comparison selector #<=. The reason is that we are sorting some collection.

So, we are trying to sort a collection of Leaf objects which rely on some integers for their comparison and somehow one of those "integers" wasn't a Number but the Character linefeed.

If we take a look at the Smalltalk code with this information in mind we see:

The SortedCollection is pqueue and the Leaf objects are the items being added to it.
The invariant property of a SortedCollection is that it always has its elements ordered by a given criterion. Consequently, every time we add: an element to it, the element will be inserted in the correct position. Hence the comparison message #<=.
Now let's look for #add: in the code. Besides of the one above, there is another below:
```
  new_internal := Tree new: nl count: newcount left: first right: second.
  pqueue add: new_internal.
```
This one is interesting because is where the error happens. Note however that we are not adding a Leaf here but a Tree. But wait, it might be that a Tree and a Leaf belong to the same hierarchy. In fact, both Tree and Leaf represent nodes in an acyclic graph. Moreover, the code confirms this idea when it reads:
```
  Leaf new: key count: value.
  ...
  Tree new: nl count: newcount left: first right: second.
```

See? Both Leaf and Tree have some key (the argument of new:) and some count. In addition, Trees have left and right branches, which Leafs not (of course!)

So, in principle, it would be ok to add instances of Tree to our pqueue collection. This cannot be what causes the error.

Now, if we look closer to the way the Tree is created we can see a suspicious argument nl. This is interesting because of two reasons: (i) the variable nl is not defined in the part of the code we were given and (ii) the variable nl is the key that will be used by the Tree to respond to the #<= message. Therefore, nl must be the linefeed character $<10>. Which makes a lot of sense because nl is an abbreviation of newline and in the Linux world newlines are linefeeds.

Conclusion: The problem seems to be caused by the wrong argument nl used for the Tree's key.