environment/shared pool search order?

STSymbolTable uses an IdentitySet to store pool dictionaries and
environments.  This is fine ordinarily, but loses the search order
imposed by find_class_variable in sym.c.  Perhaps what is needed is the
semantics of an "ordered identity set"?

--
;;; Stephen Compall ** http://scompall.nocandysw.com/blog **
Failure to imagine vast possibilities usually stems from a lack of
imagination, not a lack of possibility.


_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk

Stephen Compall wrote:
> STSymbolTable uses an IdentitySet to store pool dictionaries and
> environments.  This is fine ordinarily, but loses the search order
> imposed by find_class_variable in sym.c.  Perhaps what is needed is the
> semantics of an "ordered identity set"?

That's right.  The simplest way to implement such a thing is
to subclass IdentitySet, adding something like

initialize: size
     super initialize: size.
     orderedCollection := OrderedCollection new: size.

remove: anObject ifAbsent: aBlock
     self shouldNotImplement

primAt: anIndex put: anObject
     orderedCollection addLast: anObject

do: aBlock
     orderedCollection do: aBlock


The best way to do so would be the other way round:
subclass OrderedCollection, wrapping all the "add" methods
with a test for inclusion (using the hashed collection),
and redefining #includes: so that it uses the hashed
collection.  This would have the advantage that you
could use the same class for both OrderedSet and
OrderedIdentitySet.

Either choice is fine with me.

Paolo


_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk

On Tue, 2007-04-10 at 08:06 +0200, Paolo Bonzini wrote:
> The best way to do so would be the other way round:
> subclass OrderedCollection, wrapping all the "add" methods
> with a test for inclusion (using the hashed collection),
> and redefining #includes: so that it uses the hashed
> collection.  This would have the advantage that you
> could use the same class for both OrderedSet and
> OrderedIdentitySet.

Since I wrote OrderedSet for the core as a subclass of
OrderedCollection, I thought I might ask what specifically would be more
useful:

1. An OrderedCollection that does not allow two "equal" elements
(at:put: fails if element is already present and not at that position,
add: ignores argument if already present).

2. A <Set> that remembers the order in which elements were added (the
OrderedCollection protocols missing from Set are self
shouldNotImplement)

The difference is that the attached follows 1 and supports all of
OrderedCollection's operations (forgive the usingSet: nonsense that is
just there until I come up with something better).  After writing them,
I thought that maybe they should not be supported at all (except for the
index = collection size case).

--
;;; Stephen Compall ** http://scompall.nocandysw.com/blog **
Failure to imagine vast possibilities usually stems from a lack of
imagination, not a lack of possibility.

_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk

> The difference is that the attached follows 1 and supports all of
> OrderedCollection's operations (forgive the usingSet: nonsense that is
> just there until I come up with something better).  After writing them,
> I thought that maybe they should not be supported at all (except for the
> index = collection size case).

No, I think that's correct if you want to subclass OrderedCollection.
My simpler approach would have led to a subclass of Set without the
special operations -- but your patch is the best thing to do.

I'm using your class with this tiny patch to remove the "usingSet:
nonsense" (actually replacing with a "on: nonsense").

The end of this message also includes the tiny patch to use the
OrderedSet.  For now I'm including OrderedSet.st only in the Parser
package, not in the core.

--- compiler/OrderedSet.sc.st    2007-04-16 17:49:11.000000000 +0200
+++ compiler/OrderedSet.st       2007-04-16 17:52:33.000000000 +0200
@@ -59,31 +59,23 @@


  !OrderedSet class methodsFor: 'instance creation'!

+identityNew: anInteger
+    "Answer an OrderedSet of size anInteger which uses #== to compare its
+     elements."
+    ^self on: (IdentitySet new: anInteger)!
+
  new: anInteger
      "Answer an OrderedSet of size anInteger."
-    ^(super new: anInteger)
-       unorderedSet: (self setFactory new: anInteger);
-       yourself
-!
-
-new: anInteger usingSet: anEmptySet
-    "Answer an OrderedSet of size anInteger, that uses anEmptySet as
-     an unordered set to maintain my set-property."
-    ^(super new: anInteger)
-       unorderedSet: anEmptySet;
-       yourself
-!
+    ^self on: (Set new: anInteger)!

-usingSet: anEmptySet
+on: anEmptySet
      "Answer an OrderedSet that uses anEmptySet as an unordered set to
       maintain my set-property."
-    ^self new unorderedSet: anEmptySet; yourself
-!
-
-setFactory
-    "Answer a class (<Set factory>) that can create a default
-     unordered Set for new instances."
-    ^Set
+    anEmptySet isEmpty
+       ifFalse: [ self error: 'expected empty collection' ].
+    ^(super new: anEmptySet basicSize)
+       unorderedSet: anEmptySet;
+       yourself
  ! !


  !OrderedSet methodsFor: 'accessing'!
@@ -114,9 +106,7 @@

  copyEmpty: newSize
      "Answer an empty copy of the receiver."
-    ^(self species basicNew: newSize)
-       unorderedSet: (unorderedSet copyEmpty: newSize);
-       yourself
+    ^self species on: (unorderedSet copyEmpty: newSize)
  ! !


  !OrderedSet methodsFor: 'searching for elements'!
--- compiler/STSymTable.sc.st
+++ compiler/STSymTable.st
@@ -364,7 +364,7 @@ init
      instVars := Dictionary new: 7.
      scopeVariables := OrderedCollection new: 5.
      scopes := OrderedCollection new: 5.
-    pools := IdentitySet new: 7.
+    pools := OrderedSet identityNew: 7.
      tempCount := 0.
  !


_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk