Bill Page wrote:
>
> Equality in Computer Algebra and Beyond
> James H. Davenport, JSC Volume 34 Issue 4, October 2002
>
> On 24 March 2015 at 09:35, Waldek Hebisch <[email protected]> wrote:
> >
> > There is a serious problem with this patch. Namely, your
> > 'hashUpdate!' only depends on representation. This means if
> > we have two expressions 'e1' and 'e2' such that 'e1 = e2'
> > (according to equality in Expression), but 'rep(e1) ~= rep(e2)'
> > then it may happen that 'hash(e1) ~= hash(e2)'.
>
> Yes, certainly I (mostly) agree with you, although my definition of
> 'hashUpdate!' does not depend on the representation as such since it
> uses only exported operations. The representation could change
> without changing this definition.
>
> That is why I wrote:
>
> >> Also
> >> included is a patch to XHashTable to optionally pass a user specified
> >> function representing equality in the key domain. This is important
> >> for the use of XHashTable in domains like Expression where equality
> >> is not canonical."
> >> ...
>
> > However, correct
> > implementation of 'hash' must satisfy 'hash(e1) = hash(e2)' if
> > 'e1 = e2'. Due to this requirement finding correct hash function
> > for domains with noncanonical representation is quite tricky.
> > Expression adds additional difficulties due to dynamic nature.
> >
>
> Sure, but Davenport 2002 advises that I should ask: "equal as what?"
> To satisfy this that we need to be able to pass an additional
> parameter to XHashTable.
Well, Axiom philosophy (which probably is quite close to Davenport
philosophy) is to say "equal in given domain". That is, if you
want different equality you are supposed to create a different
domain.
Generaly, hash function and equalty should be compatible.
If you want non-default equality then IMO the only reasonable
way it to pass _both_ equality and hash function as parameter
to XHashTable. In such case it is user responsibility to
ensure that they are compatible. But default equality
and hash function if present should be compatible.
> I think a better way to solve this is to realize that the
> "unsoundness" is in the specification not the implementation. It seems
> to me that 'hash' and 'hashUpdate!' should be exported by the category
> 'Comparable' without presuming any relationship with the
> "mathematical" equality = that should actually be exported by
> SetCategory rather than BasicType. Then we only need that
>
> 'hash(e1) = hash(e2)' if 'not (smaller?(e1,e2) or smaller?(e2,e1)'
I do not understand why do you want to add Comparable to the mix?
If correctly implemented your test with 'smaller?' should give
the same result as '='. In the paper you mentioned Davenport
writes about system beeing congruential (or not). Clearly
congruential systems are nicer. So equality in a domain may
be a bit strange but still should obey usual axioms. And
my main objection is that your patch would make Expression
with operations restricted to '=' and 'hash' non-congruential.
In case of Expression AFAICS we always have
not(smaller?(x, y) or smaller?(y, x)) implies x = y
so any lack of equality means that Expression with '=' and 'smaller?'
is not congruential. As I wrote I think that this can happen but
consider such thing as a bug. ATM I do not have a testcase,
if I had I would consider this as high-priority bug.
Extra remark: my inpression after reading Davenport paper it
that he did not want to praise Axiom too much, but he thinks
that system should be organized into domains and _operation
from the domain should be compatible (congruential)_. Real
word can force us to use inferior equality (like MoteCarlo
tests), but we should introduce no gratitious incompatibilities.
> > We could easily add 'hashUpdate!' to canonical domains, like Polynomial
> > or SAE. Also we could add 'hashUpdate!' to Set (but implementation
> > is tricky). But Expression and Float pose serious difficulties.
>
> The fact that there are "serious difficulties" should be an indication
> that the specification is wrong. In fact as you know according to
> Richardson's theorem it is impossible even in princple in Expression
> since we have rational functions plus 'abs', and 'sin'. But the
> concept of hashing is so important that we should not make it to
> extraordinary things in order to use it in domains like Expression.
You are mixing two things: Richardson's theorem says that equality
of functions represented by expressions is not computable.
Practically this means that equality in Expression should be
conservative approximation to equality of functions. This
says nothing about possibility of building hash function
compatible with equality in Expression. Serious difficulty
is because we expect hash functions to be efficient.
Slow hash function can be implemented using association
list of arguments and values. We compute hash function
first searching association list via linear search. If
argument is there we return associated values. If not
we generate new values and append new pair to the
association list. Now, main use of hash functions is
to avoid linear search. Of course the method above
is useless for such purpose because we use linear
search to comput hash.
You write about changing specification. However, hash function
which do not agree with equality is useless for speading up
existing searches. So you need to change specification
of searches and the question is if you gain anything using
such modified searches. Even if there is gain required
changes are likely to be nontrivial and using changes search
without other changes is likely to lead to bugs. In
other words we have problem that types system is suppesed
to solve: current set of operations should go together and
your redefined operations should go togeter and do not
mix with original ones (except when data is explicitely
converted). I hope that you see now why using current
signatures has problems. Now domain or new name for operation
would resolve this. Of course, there is still question
if there are interesting use cases for redefined operations...
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
