Bill Page wrote:
>
> The following patches provide hashUpdate! and as a result hash
> functions to the Expression, Kernel, Float and Complex domains. 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.
>
> Please review and let me know if I can commit.
>
> wspage@opensuse:~/fricas-ker> svn diff > ../exprhash.patch
> wspage@opensuse:~/fricas-ker> cat ../exprhash.patch
> Index: src/algebra/expr.spad
> ===================================================================
> --- src/algebra/expr.spad (revision 1893)
> +++ src/algebra/expr.spad (working copy)
> @@ -147,7 +147,10 @@
> x : % = y : % == (x - y) =$Rep 0$Rep
> numer x == numer(x)$Rep
> denom x == denom(x)$Rep
> -
> + hashUpdate!(s : HashState, x : %) : HashState ==
> + s := hashUpdate!(s, numer x)
> + s := hashUpdate!(s, denom x)
> +
> EREP := Record(num : MP, den : MP)
>
> coerce(p : MP) : % == [p, 1]$EREP pretend %
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)'. 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.
I admit that current situation where at category level we claim
there here is hash function, but a lot of domains lack implementaion
is unsatisfactry. But it is not clear what to do. We could
introduce new category, say 'Hashable' and make sure that
domains which export 'Hashable' also implement 'hash'. Or we
could weaken requirement on 'hash' and say that equality
of representations is enough to have equality of hashes.
However, weaker requirement on 'hash' would seriously limit
its usefulness, basicaly to cases when one works with
representaion. Since we want to hide representation, this
is serious limitation.
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.
Similarely, power series and streams are problematic (they are
supposed to be lazy but hash function has to access elements).
Extra comment: current handling of kernels is unsound so why
I oppose adding code which is "no worse" than existing one?
The point is that I would like to eventiually remove
unsoundness. If we allow new unsoundness to get in then
there is almost no chance of removing unsoundness: new
one is likely to get in faster than old is removed.
So I keep old unsoundness for pragmatic reasons: replacing
it by sound code is a lot of work and takes time and
without unsound parts we would loose important functionality.
--
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.
