instance overlaps
Serge D. Mechveliani
> Example: for determinant of a SquareMatrix over rR, DoCon has
>
> (1) det for CommutativeRing rR => SquareMatrix rR,
>
> (2) det_euc for Euclidean rR => SquareMatrix rR,
>
> (3) det_upol_finField ::
> Field k => [ResidueE (UPol k)] -> [[UPol k]] -> UPol k
> -- ext mM
> -- A degree cost method to compute det M over k[x] for a finite
> -- field k.
>
> On average, (2) is faster than (1), (3) is faster than (2).
> DoCon provides three different functions, for some reasons.
> If it introduced class WithDet, may be, it could have a unique
> operation `det', whose instances are efficienly resolved for these
> three functions (I am not sure, needs recollection, trying).
I need to correct this. With DoCon and Haskell, this all is not so nice.
Suppose one defines
class CommutativeRing rR => WithDet rR -- I
where
det :: SquareMatrix rR -> rR
-- default implementation
det mt = if rR has EuclideanRing then
gaussEliminationForEuclidean mt
else genericMethod mt
class CommutativeRing rR => WithDet rR -- II
where
det :: SquareMatrix rR -> rR
det = genericAlgorithm -- this is the default implementation
-- for any commutative ring
instance EuclideanRing rR => WithDet rR -- II-1
where
det mt = gaussEliminationForEuclidean mt
instance FiniteField k => WithDet (UPol k) -- II-2
where
det mt = mostSpecialMethod mt
Currently
(I) is not possible in Haskell +glasgow-ext,
II-2 must work,
II-1 is not possible in Haskell +glasgow-ext.
This is why DoCon introduces more than one function for Det.
But this is done for temporary and technical (in my mind) reasons.
Putting more effort in Haskell+ext implementation will fix this,
(though, developing such things in practice needs years and years).
As the Spad language is more expressive, it is likely to have an
easier resolution.
Thus, can Spad handle (I) ? Something like this:
Category(R : CommutativeRing) : WithDet ==
...
with
det : SquareMatrix R -> R
Default Implementation ==
det mt = if rR has EuclideanRing then
gaussEliminationForEuclidean mt
else genericMethod mt -- expand by row
-- correct the syntax if needed.
Regards,
------
Sergei
mec...@botik.ru
Ralf Hemmecke
> Thus, can Spad handle (I) ? Something like this:
>
> Category(R : CommutativeRing) : WithDet ==
> ...
> with
> det : SquareMatrix R -> R
>
> Default Implementation ==
>
> det mt = if rR has EuclideanRing then
> gaussEliminationForEuclidean mt
> else genericMethod mt -- expand by row
>
> -- correct the syntax if needed.
---rhxBEGIN foo.spad
)abbrev domain FOO Foo
Foo(R: Ring): with
coerce: % -> OutputForm
foo: R -> %
== add
Rep == R
coerce(x: %): OutputForm ==
"FoO"::OutputForm + (x pretend R)::OutputForm
if R has Field then
foo(r: R): % == (1/r) pretend %
else
foo(r: R): % == r pretend %
---rhxEND foo.spad
Use it like this...
(3) -> foo(3)$Foo(Integer)
(3) FoO + 3
Type: Foo(Integer)
(5) -> foo(3)$Foo(Fraction Integer)
1
(5) FoO + -
3
Type: Foo(Fraction(Integer))
The interesting part here is that there is no overhead in finding the
right foo. This is done at instantiation time of the domains
Foo(Integer) and Foo(Fraction Integer). ((Well, perhaps, that is not
quite true, since AFAIK the resolution of which function is called is
postponed until the *first use* of foo in the respective domain. I.e. if
after the above use, I call
foo(7)$Foo(Integer)
there will be no runtime test to check whether Integer has Field.
(Waldek, please correct me if I am wrong.)
Ralf
Serge D. Mechveliani
Thank you.
You changed from defining a Category to defining a Domain ...
All right, can `factor' be the dispatched by Axiom in this manner?
So that the user would not search which package among 20 fits the best
for `factor'.
------------------------------
)abbrev domain INT Integer
Integer(): with ...
Join(EuclideanDomain, UniqueFactorizationDomain ...)
== add
Rep == ?
factor n == factorInteger
)abbrev domain SUP SparseUnivariatePolynomial
SparseUnivariatePolynomial(R : CommutativeRing):
with ...
Join(CommutativeRing,
R has IntegerLike or R has FiniteField or
R has SuchAndSuchCategory => UniqueFactorizationDomain
)
== add
Rep == ?
factor(f : UP R) : Factored (UP R) ==
R has IntegerLike => factorUPOverInteger f
R has FiniteField => factorUPByExtendedBerlekemp(R, f)
R has SuchAndSuchCategory => factorUPByGeneric(R, f)
------------------------------
Usage: factor(6) $INT,
(f := (x^2 - 1) :: SUP INT; factor(f) $SUP INT)
(F := ResidueRing(INT, 7); f := (x^7 +2) :: F; factor(f)$F)
So Axiom will dispatch itself to the `factor' version which is the most
efficient for this particular domain.
Can this be done?
I am trying to find out whether the language allows, in principle, a clear
and efficient dispatching for such operations which have a complex set of
implementation cases overlapping non-trivially and having different
generality levels.
Regards,
------
Sergei
mec...@botik.ru
Ralf Hemmecke
> SparseUnivariatePolynomial(R : CommutativeRing):
> with ...
> Join(CommutativeRing,
> R has IntegerLike or R has FiniteField or
> R has SuchAndSuchCategory => UniqueFactorizationDomain
> )
> == add
> Rep == ?
> factor(f : UP R) : Factored (UP R) ==
> R has IntegerLike => factorUPOverInteger f
> R has FiniteField => factorUPByExtendedBerlekemp(R, f)
> R has SuchAndSuchCategory => factorUPByGeneric(R, f)
Of course that can be done. But I have the impression you haven't that
you haven't got the point in me writing
if R has Field then
foo(r: R): % == (1/r) pretend %
else
foo(r: R): % == r pretend %
instead of
foo(r: R): % == if R has Field then
(1/r) pretend %
else
r pretend %
In the second case (as in your case above), calling factor will *always*
perform the test "R has Field". In my version that test is only at
instantiation time of the domain.
> I am trying to find out whether the language allows, in principle, a clear
> and efficient dispatching for such operations which have a complex set of
> implementation cases overlapping non-trivially and having different
> generality levels.
I think my previous mail should have shown you how dispatching can be
done on a domain level. The exports would simply list the function
unconditionally.
Ralf
Serge D. Mechveliani
factorUPOverInteger f is an expensive loop, and the relative cost of
preliminary (R has IntegerLike) is usually small.
Still your solution looks indeed considerably better.
>> I am trying to find out whether the language allows, in principle, a clear
>> and efficient dispatching for such operations which have a complex set of
>> implementation cases overlapping non-trivially and having different
>> generality levels.
>
> I think my previous mail should have shown you how dispatching can be
> done on a domain level. The exports would simply list the function
> unconditionally.
Then, the next question is
why the `factor' instances are not so nicely
dispatched in the current FriCAS, Axiom ?
For I am a bit confused.
1. Waldek wrote about the category of Explicit...,
and of some performance problems related to dispatching `factor'.
2. I write in my testParse.spad :
factor(f) $UnivariateFactorize(UP(x,INT))
-- and this is by the advice read from e-mail.
Could I happen to call `factor' in this case from other place, where
its impementation is less efficient?
3. Waldek wrote, that it is not nicely dispatched -- if I understand
correct.
Is this by occasion or there are some fundamental reasons for this?
Regards,
------
Sergei
mec...@botik.ru
Waldek Hebisch
I would say that general dispatching features of Spad are adequate.
There are limitations, for example conditions in export lists have
restricted form (basically you can form boolean formula where
atomic tests are 'A is B' and 'A has C').
However, in case of factor:
- there are several places when dispatching would be needed
(minimally in SparseUnivariatePolynomial and
SparseMultivariatePolynomial, but there are other polynomial
domains).
- information needed for dispatching is not available in places
where we would like to dispatch.
- we also need appropriate conditions in export lists.
- besides dispatching we need actual code, at least code
which converts from one represetation to another
Original Axiom developers invented a clever scheme, where
only two conditions are used for dispatching, namely
PolynomialFactorisationExplicit and characteristic, the
rest is done by "generic" code. This scheme
involves more than 'factor', namely also gcd and
square-free factorisation. And it adds operations
to several domains: baseline cases to Integer and
finite fields, and recursive reductions to Fraction,
algebraic exensions and polynomial domains.
As I wrote problem with PolynomialFactorisationExplicit
is that supporting _implementation_ is too slow (slower
than current factoring and gcd routines). Of course
one could try to mix the two implementations. This
is doable, but not very attractive:
- there would be are several dispatching places and
messy conditions, so one would end up with maze of
conditionals
- besides adding conditionals one would have to propagate
information needed for dispatching
- the end result would be code which is is much slower
than what is possible -- simply because better algorithms
were invented after our current factoring routines and
PolynomialFactorisationExplicit were written.
In other words, after adding dispatching code we would
later have to throw it out because we want better
implementation (which needs _different_ conditions).
So I decided to work on new implementation. In other
words, if I thought that we really need dispatching
between implementations I would do it. But IMHO it
is too much work (and too little effect) to do it
knowing that it will be removed later.
--
Waldek Hebisch
heb...@math.uni.wroc.pl