[Axiom-developer] Set Any and SXHASH

[Bill Page]

In http://wiki.axiom-developer.org/347BugInMapSet

'oklhazi' reported that "map confuses sets" and gives
the example

  A:=set [-2,-1,0]
  B:=set [0,1,4]
  C:=map(x +-> x^2,A)
  test(C=B)

where the map operation produces a "Set" C with the same
elements as B but which is not equal to B, thus violating
a major axiom of set theory.

The documentation for Set

http://wiki.axiom-developer.org/axiom--test--1/src/algebra/SetsSpad

says, (in part):

++ In our implementation, \Language{} maintains the entries
++ in sorted order.  Specifically, the parts function returns
++ the entries as a list in ascending order and the extract
++ operation returns the maximum entry.

but the example shows that this is not true even if the Set
is composed of elements from a domain which has OrderedSet.
In the #347 I proposed a simple patch to correct this
behaviour but it is easy to show that it still fails if the
element domain is not an OrderedSet.

At the following page:

http://wiki.axiom-developer.org/SandBoxSetAny

I have proposed an more ambitious fix that provides a constant
but otherwise arbitrary ordering for all SETs based on comparing
the Lisp SXHASH of the elements:

order(x:S,y:S):Boolean == integer(SXHASH(x)$Lisp)$Sexpression
                          < integer(SXHASH(y)$Lisp)$Sexpression

This provides an easy to compute order but since this is a
hash the ordering is in general only a partial order, so perhaps
this is not such a good idea?

The reference:

http://www.lisp.org/HyperSpec/Body/fun_sxhash.html#sxhash

says:

"3. The hash-code for an object is always the same within a
single session provided that the object is not visibly modified
with regard to the equivalence test equal.

"4. The hash-code is intended for hashing. This places no
verifiable constraint on a conforming implementation, but the
intent is that an implementation should make a good-faith effort
to produce hash-codes that are well distributed within the
range of non-negative fixnums.

---------

So my question for Axiom Developers and Lisp aficionados is
what is your opinion of the use of SXHASH? How well does SXHASH
behave in GCL? What might be a reasonable alternative for
defining a total ordering on the elements of a Set given the
possibility of the type 'Set Any'?

Also on page SandBoxSetAny I proposed a patch to the code for
the domain Any that makes use of the Lisp EQUAL comparison
instead of EQ. I think that in general EQ is too restrictive.
Do you think this change is reasonable and correct?

Regards,
Bill Page.