argument domain
Serge D. Mechveliani
I have the two questions.
1. Extracting agrument domain from under a constructor
------------------------------------------------------
Is it possible in Spad to extract an argument domain (type) from a
constructed domain?
For example,
F : Field := ...
And it is known that F = Fraction D for some D : IntegralDomain,
so that F pretend Field and F pretend QuotientField
are correct.
But D is not given in the scope.
Can D be extracted from F by some operations,
so that, for example, the operations `1 :: D', `(f^2) $UP(x, D)'
become possible?
I think of
F := ... pretend QuotientField
unD := denom (1 :: F) -- unity of the searched D
sD : SExpression := dom unD
D := pretend IntegralDomain
I do not know whether this will works, I shall see.
On the other hand, as F is constructed as Fraction D, may be, D
can be directly extracted from F ?
2. Canonic fraction
-------------------
For a mutually prime n, d : (D : IntegralDomain),
how to set fraction of n/d in Spad with avoiding gcd and also
obtaining a correct fraction?
Recall that (2, -3) are mutually prime in Integer, as well as (-2, 3), or
(-2,-3).
There is desirable a function which can be applied like this:
fraction(NoGCD, n, d).
In the DoCon library a polymorphic function
canFr :: GCDRing a => String -> a -> a -> Fraction a
canFr mode n d = ...
canonizes a fraction n:/d to n':/d' over a GCDRing a.
mode = "g" means to cancel the pair by gcd.
"i" to cancel by canonical invertible,
"gi" to cancel by both.
If the client knows that n:/d is canonical, he can write n:/d,
and this costs 1 (the constructor `:/' applied -- 1 step).
If he knows that n and d are mutually prime, and he does not know the
value of (canInv d) == 1, he can write canFr "i" n d.
For example,
canFr "i" 2 (-3 :: Integer) --> (-2):/3
(canInv (-3) = -1).
Otherwise, he writes canFr "gi" n d.
This is arranged so because gcd may cost much, for example, for
Integer[x,y,z,u].
May be, in some cases, canInv may cost much.
But currently I care only of the gcd cost.
When DoCon puts a string to Axiom, fractions are in their canonical form
by "gi". And it is desirable to avoid gcd when parsing (by dParse)
of such a fraction to Axiom.
After parsing n, d : D, dParse applies
CONS(n, d)$Lisp pretend Fraction D.
But there arises the question of the cancellation by canInv.
Because if Axioms has a different idea of canInv, this parsing may occur
incorrect.
I tried:
(CONS(-2, 3)$Lisp pretend Fraction INT) = ((-2)/3 :: Fraction INT)
-->
true
So, for Integer, Axiom has the same notion of the canonical invertible.
For R[x1..xn], GCDRing R, DoCon defines canInv via canInv for
the leading coefficient, in a natural way.
Can you please, comment the subject?
Thanks,
------
Sergei
mec...@botik.ru
Ralf Hemmecke
> ------------------------------------------------------
> Is it possible in Spad to extract an argument domain (type) from a
> constructed domain?
In general: No.
> For example,
> F : Field := ...
If you know that the type of F is Field, you don't know that it was
constructed by Fraction.
> And it is known that F = Fraction D for some D : IntegralDomain,
How do you happen to know this information in a program? I would bet, if
you know that it's a fraction, you also know D.
Your use case is not quite clear. I guess it has something to do with
parsing and coercing strings to FriCAS expressions, but please be more
precise.
> But D is not given in the scope.
Why do you need D at all?
> Can D be extracted from F by some operations,
> so that, for example, the operations `1 :: D', `(f^2) $UP(x, D)'
> become possible?
Extracting D would be possible by something like this:
Foo(D: IntegralDomain): with
...
argDomain: () -> IntegralDomain
== add
...
argDomain(): IntegralDomain == D
BUT, now comes the problem. If you have
D ==> Integer
F ==> Foo(D)
E ==> argDomain(F)
how can the compiler check that for
d: D := 1
e: E := 1
it can add d and e? The compiler would have to verify that there is a
function +: (D, E) -> ??? or check that D is the same as E. But checking
that would involve evaluating the *function* argDomain at compile time.
The compiler doesn't do this.
Of course, since you know, you can simply pretend, but that is
inherently type unsafe.
Generally, I don't find the extraction of argument domains very
attractive. IMHO, it would be wiser to remember the construction of the
domain in question and also remember its arguments so that they can be
used in other places.
Ralf
Ralf Hemmecke
> -------------------
> For a mutually prime n, d : (D : IntegralDomain),
> how to set fraction of n/d in Spad with avoiding gcd and also
> obtaining a correct fraction?
Simplest answer is: use pretend.
Better answer is: without knowing the representation of Fraction(D) it's
impossible. And nobody, except the programmer of Fraction should know
the representation.
> Recall that (2, -3) are mutually prime in Integer, as well as (-2, 3), or
> (-2,-3).
Internally, Fraction uses a record, but it tries to keep the
representation normalized. So (2,-3) would be different from (-2,3).
> There is desirable a function which can be applied like this:
> fraction(NoGCD, n, d).
However, there is more. If you look into Fraction
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/fraction.spad.pamphlet#L314
you see that the argument type is only required to be IntegralDomain. So
one could form Fraction(X) for X being of type IntegralDomain, but not
of type GcdDomain. If X has not gcd function, it will of course not be
applied if you construct an element via n/d.
Anyway, you probably need it for X=Integer.
So the only way you can do what you want is "pretend" or provide a patch
that adds a function constructFractionWithoutCancelling:(S,S)->%.
But I will probably argue a lot that this function is basically like
pretend and should better be avoided.
[snip]
> When DoCon puts a string to Axiom, fractions are in their canonical form
> by "gi". And it is desirable to avoid gcd when parsing (by dParse)
> of such a fraction to Axiom.
OK, this is a situation where your parsing framework should know about
the internal structure of FriCAS domains and Fraction in particular,
i.e. "pretend" should be the way to go.
You should, however, mark such "pretend" places in big bold red letters
so that maintenance does not become a nightmare. Whenever a FriCAS
domain changes its representation, your framework must be changed as
well. So keep producing lots of test cases so that such situations are
caught before a new release.
Ralf
Serge D. Mechveliani
>> 2. Canonic fraction
>> -------------------
>
>> For a mutually prime n, d : (D : IntegralDomain),
>> how to set fraction of n/d in Spad with avoiding gcd and also
>> obtaining a correct fraction?
>
> Simplest answer is: use pretend.
>
?
For example, CONS(-2, 3 ::INT)$Lisp pretend Fraction INT (I)
avoids gcd. (-2)/3 over INT is defined as canonical in DoCon.
But it may occure not canonical in Axiom.
Suppose that in the next version of FriCAS its canonical form becomes
CONS(2, -3)$Lisp (II)
-- FriCAS is free to choose a different canonical form method, a matter
of internal representation etc.
In this case, it will occur (I) ~= (II), and this `pretend' usage will
occur incorrect. Right?
Moreover, this CONS-pretend is not safe because Axiom's idea of
canonizing a fraction may differ from DoCon's one.
Currently, DoCon can form Fraction D only for a GCDRing D.
But even in this restricted case Axiom's method may differ from DoCon's
for some instances of such D.
This is why I suggest for an Axiom (FriCAS) library to provide
package ... (D : IntegralDomain)
...
fraction(m : FooMode, num : D, den : D) : Fraction D == ...
in which m may be MtPrime or Generic
(may be, to provide the second format for `fraction', with skipped `m').
MtPrime means that num and den are mutually prime,
that is Ideal(num) + Ideal(den) = (1).
Example:
D = POLY([x,y,z], INT), and gcd(f:D, g) = 1
is found in previous computation (done for a need other than Fraction).
This is a good point to write
(1) fr : Fraction D := fraction(MtPrime, f, g)
instead of (2) fr := (f/g) :: Fraction D
and instead of (3) fr := CONS(f, g)$Lisp pretend Fraction D.
Because (2) is often more expensive than (1), and (3) is not safe.
Generally, this `fraction MtPrime'
a) gives a hope for optimized computation,
b) guarantees correctness, because it is a part of the standard library,
it is implemented by the Axiom developers,
the user does not need to look into the Fraction representation.
It is a matter of the Axiom implementation of how to use the knowledge
given by m = MtPrime.
This `fraction' may also become an operation from the
QuotientFieldCategory.
Am I missig something?
In the first letter I wrote `m = NoGCD'.
But now I improve it to MtPrime, because it has more sense, because
probably, Axiom canonizes fraction not only for a GcdRing (and MtPrime
talks generally, of the sum of ideals).
> So the only way you can do what you want is "pretend" or provide a patch
> that adds a function constructFractionWithoutCancelling:(S,S)->%.
>
> But I will probably argue a lot that this function is basically like
> pretend and should better be avoided.
No. constructFractionWithoutCancelling and `pretend' (for canonic)
is the same. And they both are incorrect, depend on a particular
representation.
I suggest fraction(m, num, den),
a) where m may be MtPrime or Generic,
b) this operation to be implemented by the Axiom library, not by the user,
c) in simple cases (D = INT, POLY(vars, INT), POLY(vars, Rational), and
such) it will hopefully lead to optimization,
d) which usage is totally safe.
>> When DoCon puts a string to Axiom, fractions are in their canonical form
>> by "gi". And it is desirable to avoid gcd when parsing (by dParse)
>> of such a fraction to Axiom.
>
> OK, this is a situation where your parsing framework should know about
> the internal structure of FriCAS domains and Fraction in particular,
> i.e. "pretend" should be the way to go.
>
> You should, however, mark such "pretend" places in big bold red letters
> [..]
In this case I will need to change dParse each time when FriCAS changes
treating of Fraction.
Also I would need to study just now all the details of treating Fraction
in Axiom -- for the case of D : GcdRing.
This way does not look safe nor nice.
So, if Axiom(FriCAS) rejects my above suggestion of joining
fraction(m : Mode, num : D, den : D) : Fraction D,
then I would be forced to apply (num/den) :: Fraction D,
and this will lead to an unneeded gcd computation during the interface.
Regards,
------
Sergei
mec...@botik.ru
Ralf Hemmecke
> For example, CONS(-2, 3 ::INT)$Lisp pretend Fraction INT (I)
No!!! If ever possible avoid Lisp in your program. That's in my eyes
even worse than using pretend. As for Fraction(...) you track the
representation down along the "add" inheritance. Since SPAD doesn't
allow multiple inheritance in the "add" line, that should be easy.
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/fraction.spad.pamphlet#L314
There you have
Fraction(S: IntegralDomain): QuotientFieldCategory S with
if S has IntegerNumberSystem and S has OpenMath then OpenMath
if S has Canonical and S has GcdDomain and S has canonicalUnitNormal
then Canonical
++ \spad{Canonical} means that equal elements are in fact
identical.
== LocalAlgebra(S, S) add
Rep:= Record(num:S, den:S)
...
Actually, already the definition of Rep as Record is bad, since it makes
the assumption that LocalAlgebra(S, S) has this Record representation.
Better would have been
Rep := LocalAlgebra(S, S)
But OK, that's legacy software.
Anyway, if ever you use "pretend" for your purpose in Fraction(Integer),
you should do something like
([n,d]$Record(num:Integer,den:Integer)) pretend Fraction(Integer)
That is expressing everything in terms of the SPAD language without ever
saying that the underlying assembly language is LISP.
It's important for the future. Maybe some day, we change from LISP to
Forth or to C or LLVM or whatever.
> -- FriCAS is free to choose a different canonical form method, a matter
> of internal representation etc.
> In this case, it will occur (I) ~= (II), and this `pretend' usage will
> occur incorrect. Right?
Exactly.
I think, you can decipher what these lines mean
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/fraction.spad.pamphlet#L316
if S has Canonical and S has GcdDomain and S has canonicalUnitNormal
then Canonical
> Moreover, this CONS-pretend is not safe because Axiom's idea of
> canonizing a fraction may differ from DoCon's one.
Also right.
> Currently, DoCon can form Fraction D only for a GCDRing D.
> But even in this restricted case Axiom's method may differ from DoCon's
> for some instances of such D.
I guess, currently, it doesn't. At least not for Fraction(Integer). But
Fraction as a generic domain constructor is quite general. It's not so
totally obvious how one would for example make the representation of
Fraction(SUP(INT)) canonical.
> This is why I suggest for an Axiom (FriCAS) library to provide
>
> package ... (D : IntegralDomain)
> ...
> fraction(m : FooMode, num : D, den : D) : Fraction D == ...
>
> in which m may be MtPrime or Generic
> (may be, to provide the second format for `fraction', with skipped `m').
But the maintenance effort is the same if it lives in your package or in
a separate package in the Algebra library. This "fraction" function has
to know the internal representation of Fraction. And the only place
where the representation should be known is Fraction itself. So one
would have to introduce this function into the Fraction code and *trust*
the programmer that the input is as required. But since that cannot (and
by design should not) be checked, the only place for a good
specification of that function would be the documentation.
The documentation/specification of that function would have to be
changed if the representation changes. But of course, any external code
does not care about the documentation, only a programmer can realize
that there was a change. So programs will after some iterations assume
things that are no longer true.
I wouldn't want to hunt for bugs in such situations. It's already
complicated enough to implement the right mathematics correctly.
> MtPrime means that num and den are mutually prime,
> that is Ideal(num) + Ideal(den) = (1).
> Example:
> D = POLY([x,y,z], INT), and gcd(f:D, g) = 1
> is found in previous computation (done for a need other than Fraction).
> This is a good point to write
> (1) fr : Fraction D := fraction(MtPrime, f, g)
>
> instead of (2) fr := (f/g) :: Fraction D
> and instead of (3) fr := CONS(f, g)$Lisp pretend Fraction D.
I clearly understand your point. So maybe the idea is to create a domain
Coprime(G: GcdDomain): with
construct: (G, G) -> %
== add
Rep == Product(G, G)
construct(x: G, y: G): % == ...
and in Fraction(D) have a function
fraction: Coprime(D) -> %
such a function "fraction" would trust that elements in Coprime(D) are
supposed to be coprime.
Well, now the problem is, how to construct elements of Coprime(D) in a
typesafe and fast fashion?
Maybe you have a function
gcd: (D, D) -> Union(D, Coprime(D))
where the result is the gcd if the elements are not coprime and the
Coprime(D) element (i.e. a pair), if the input is coprime.
> I suggest fraction(m, num, den),
> a) where m may be MtPrime or Generic,
> b) this operation to be implemented by the Axiom library, not by the user,
Sorry, but we are not in a situation like in Maple or Mathematica. User
code is indistinguishable and treated in exactly the same way as the
library that comes with FriCAS. In Maple or Mathematica, they have a
kernel and then there are (interpreted) user functions. That's not the
case for SPAD files. Domains/Categories/Packages in user defined .spad
files are compile in the same way as library functions just like in any
other ordinary programming language.
> c) in simple cases (D = INT, POLY(vars, INT), POLY(vars, Rational), and
> such) it will hopefully lead to optimization,
> d) which usage is totally safe.
>>> When DoCon puts a string to Axiom, fractions are in their canonical form
>>> by "gi". And it is desirable to avoid gcd when parsing (by dParse)
>>> of such a fraction to Axiom.
>>
>> OK, this is a situation where your parsing framework should know about
>> the internal structure of FriCAS domains and Fraction in particular,
>> i.e. "pretend" should be the way to go.
>>
>> You should, however, mark such "pretend" places in big bold red letters
>> [..]
>
> In this case I will need to change dParse each time when FriCAS changes
> treating of Fraction.
Yes, that's called maintenance nightmare. ;-)
> Also I would need to study just now all the details of treating Fraction
> in Axiom -- for the case of D : GcdRing.
> This way does not look safe nor nice.
But there are not too many people who would do the job for you. It's
open source and unfortunately, FriCAS is not that wide-spread yet.
> So, if Axiom(FriCAS) rejects my above suggestion of joining
>
> fraction(m : Mode, num : D, den : D) : Fraction D,
>
> then I would be forced to apply (num/den) :: Fraction D,
> and this will lead to an unneeded gcd computation during the interface.
Well yes that should be the first way to go. I think you should first
program in a typesafe way and only then look for bottlenecks that slow
down your code.
Ralf
Serge D. Mechveliani
> On Mon, Feb 27, 2012 at 12:15:08PM +0100, Ralf Hemmecke wrote:
> >> 2. Canonic fraction
> >> -------------------
> >
> >> For a mutually prime n, d : (D : IntegralDomain),
> >> how to set fraction of n/d in Spad with avoiding gcd and also
> >> obtaining a correct fraction?
> [..]
> This is why I suggest for an Axiom (FriCAS) library to provide
> package ... (D : IntegralDomain)
> ...
> fraction(m : FooMode, num : D, den : D) : Fraction D == ...
>
> in which m may be MtPrime or Generic
> (may be, to provide the second format for `fraction', with skipped `m').
>
> MtPrime means that num and den are mutually prime,
> that is Ideal(num) + Ideal(den) = (1).
Error!!
I am sorry, x and y have not any non-trivial common divisor in Z[x,y]
but Ideal(x) + Ideal(y) /= (1).
I think now that MtPrime must mean:
D : UniqueFactorizationRing and
num : D, den : D have not any non-trivial common divisor.
With all the rest, my sugestion remains ... I think
(remove the words about "sum of ideals" in another place).
Another note:
once a fraction over a GcdRing is input, in most cases it is subjected
to many further arithmetics, most of which will still require finding
gcd. This considerably reduces the need of my suggestion for
`fraction-with-mode'.
Anyway, here is the example:
in my DParse.zip on the Web, using `pretend' for Fraction Int
saves 1/15 of the time for parsing of f :: UP(x, Fraction INT)
(test2Fr)
(this is curious, because 0 < num, den < 9 in the coefficients).
Note aside:
also I worked trustfully with replacing recursive calls with loops --
and this has slowed the example back on 1/15 !
Regards,
------
Sergei
mec...@botik.ru
Waldek Hebisch
>
> People,
> I have the two questions.
>
> 1. Extracting agrument domain from under a constructor
> ------------------------------------------------------
> Is it possible in Spad to extract an argument domain (type) from a
> constructed domain?
There is no general Spad level way to do it.
>
> Can D be extracted from F by some operations,
> so that, for example, the operations `1 :: D', `(f^2) $UP(x, D)'
> become possible?
One can extract arguments of domain in low-level way. I was
thinking about adding such operation as standard feature.
However, ATM I am not sure about details. One possibility,
general but less efficient, is to just expose existing
low level routines. However, this would give you arguments
just as a Type and you would have to use 'pretend' to get
correct category. Another possiblilty is to add operation
called 'baseDomain' to Fraction and some other domains.
That would allow to get correct category, but would mean
more work adding such functions to the library.
You can implement variation of second way yourself:
)abbrev domain MYFRAC MyFraction
MyFraction(S : IntegralDomain): QuotientFieldCategory S with
getBaseDomain : () -> IntegralDomain
if S has IntegerNumberSystem and S has OpenMath then OpenMath
if S has Canonical and S has GcdDomain and S has canonicalUnitNormal
then Canonical
== Fraction(S) add
getBaseDomain() == S
You should be able to use MyFraction is most places where Fraction
is usable and use getBaseDomain to have acces to S.
BTW: In most cases where I would like to know S I need some way
to decide that the domain is Fraction, so you probably need more
than 'getBaseDomain'.
BTW2: In few places in the library there is code which tries to
determine if domain is of specific form and handle it is special
way. Unfortunatly, this is exactly code which works with fraction,
but may fail when given MyFraction.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Waldek Hebisch
>
> Anyway, here is the example:
> in my DParse.zip on the Web, using `pretend' for Fraction Int
> saves 1/15 of the time for parsing of f :: UP(x, Fraction INT)
> (test2Fr)
> (this is curious, because 0 < num, den < 9 in the coefficients).
Not so curious: you save a call to '/' in Fraction.
Calling functions from domain which are computed at runtime inside
a function is much more expensive than normal call using domains
which are computed "at constuctor toplevel": the second case
is cached, the first pays cost seach for correct function per
each call.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Serge D. Mechveliani
>>> Simplest answer is: use pretend.
>
>> For example, CONS(-2, 3 ::INT)$Lisp pretend Fraction INT (I)
>
> No!!! If ever possible avoid Lisp in your program. That's in my eyes
> even worse than using pretend. As for Fraction(...) you track the
> representation down along the "add" inheritance. Since SPAD doesn't
> allow multiple inheritance in the "add" line, that should be easy.
>
> Anyway, if ever you use "pretend" for your purpose in Fraction(Integer),
> you should do something like
>
> ([n,d]$Record(num:Integer,den:Integer)) pretend Fraction(Integer)
>
> That is expressing everything in terms of the SPAD language without ever
> saying that the underlying assembly language is LISP.
>
> It's important for the future. Maybe some day, we change from LISP to
> Forth or to C or LLVM or whatever.
I see. Thank you.
> if S has Canonical and S has GcdDomain and S has canonicalUnitNormal
> then Canonical
Sounds like GCDRing sS in DoCon.
>
>> Currently, DoCon can form Fraction D only for a GCDRing D.
>> But even in this restricted case Axiom's method may differ from DoCon's
>> for some instances of such D.
>
> I guess, currently, it doesn't. At least not for Fraction(Integer). But
> Fraction as a generic domain constructor is quite general. It's not so
> totally obvious how one would for example make the representation of
> Fraction(SUP(INT)) canonical.
I thought, there is a natural way. For example, canInv (x:INT)
(the canonical invertible factor) is defined as signum x (for x /= 0).
canInv(f : SUP INT) == canInv(lc(f)) :: SUP INT;
and cancelling the fraction of num and den in Fraction(SUP(INT)) is
by
c := canInv den; (num/c, den/c).
I am sorry if I have forgotten something.
Does this look natural?
>> This is why I suggest for an Axiom (FriCAS) library to provide
>>
>> package ... (D : IntegralDomain)
>> ...
>> fraction(m : FooMode, num : D, den : D) : Fraction D == ...
>>
>> in which m may be MtPrime or Generic
>> (may be, to provide the second format for `fraction', with skipped `m').
>
> But the maintenance effort is the same if it lives in your package or in
> a separate package in the Algebra library. This "fraction" function has
> to know the internal representation of Fraction. And the only place
> where the representation should be known is Fraction itself. So one
> would have to introduce this function into the Fraction code and *trust*
> the programmer that the input is as required. But since that cannot (and
> by design should not) be checked, the only place for a good
> specification of that function would be the documentation.
>
>> MtPrime means that num and den are mutually prime,
>> that is Ideal(num) + Ideal(den) = (1).
Please, see the improvement in another my letter!
>> I suggest fraction(m, num, den),
>> a) where m may be MtPrime or Generic,
>> b) this operation to be implemented by the Axiom library, not by the user,
>
> Sorry, but we are not in a situation like in Maple or Mathematica. User
> code is indistinguishable and treated in exactly the same way as the
> library that comes with FriCAS. In Maple or Mathematica, they have a
> kernel and then there are (interpreted) user functions. That's not the
> case for SPAD files. Domains/Categories/Packages in user defined .spad
> files are compile in the same way as library functions just like in any
> other ordinary programming language.
>
I do not understand why does this matter.
For example, the Glasgow Haskell (GHC) library has the module Data.Map
for operations with finite maps. They are programmed in Haskell and
are compiled similarly as user programs.
I can write my own code for Data.Map, and overload it.
Another way is to rely on GHC.
Because the GHC team announces that it is going to support Data.Map, as
other GHC library. Each new version is going to support union of maps,
etc. If I find a bug there I report them.
This software is free, and they are not oblidged.
But this team somehow announces:
we are going to support at least this set of
functions and operations and language extesion features.
And this has a name: "ghc-ext (language) + GHC library"
(in addition to the standard Haskell-2010 and its library).
Each impementation announces whether it supports the standard of
Haskell-2010. This is very important for users.
If GHC stops supporting some needed thing in ghc-ext, then I'll
either remain with an old GHC version or re-implement the thing in
Haskell.
The most dangerous thing there is Overlapping Instances in the Language.
If they stop their support, I'll need to remain with old version.
What is the notion of standard in Axiom and FriCAS community?
The difference between the FriCAS developers and user is greater than
the difference between GHC team and GHC users.
Because in GHC more part is programmed in Haskell than the part of
Axiom programmed in Spad. Haskell anf GHC have a library, but most of
this libarary is _not built-in_, it is just a prelude witten in Haskell,
and even can be overloaded by the user.
>> Also I would need to study just now all the details of treating Fraction
>> in Axiom -- for the case of D : GcdRing.
>> This way does not look safe nor nice.
>
> But there are not too many people who would do the job for you. It's
> open source and unfortunately, FriCAS is not that wide-spread yet.
>
>> So, if Axiom(FriCAS) rejects my above suggestion of joining
>>
>> fraction(m : Mode, num : D, den : D) : Fraction D,
>>
>> then I would be forced to apply (num/den) :: Fraction D,
>> and this will lead to an unneeded gcd computation during the interface.
>
> Well yes that should be the first way to go. I think you should first
> program in a typesafe way and only then look for bottlenecks that slow
> down your code.
I fear, my noise was greater than the real need (see another my letter).
> and only then look for bottlenecks that slow down your code.
Currently it is so slow that without a real speed up the interface
project hardly ever has sense. That is the matter.
For INT, Fraction INT, UP(x, Fraction INT):
a) parse*interptet of FriCAS is 10 times slower than my special dParse
written in Spad,
b) dParse is 90 times slower than addition (+) of the these data to
itself in a Spad program.
And before using SBCL, this all was slower even 3 times more.
I do not understand, so far, what is the cost of this domain evaluation
in dParse.
May be, I need profiling.
I have FriCAS-1.1.6 built from source under SBCL-1.0.55, and may be,
could set profiling in this Lisp.
For example, what time takes lexLots (initial breaking to lexemes),
and so on.
Regards,
------
Sergei
mec...@botik.ru
Ralf Hemmecke
>> totally obvious how one would for example make the representation of
>> Fraction(SUP(INT)) canonical.
>
> I thought, there is a natural way. For example, canInv (x:INT)
> (the canonical invertible factor) is defined as signum x (for x /= 0).
> canInv(f : SUP INT) == canInv(lc(f)) :: SUP INT;
> and cancelling the fraction of num and den in Fraction(SUP(INT)) is
> by
> c := canInv den; (num/c, den/c).
>
> I am sorry if I have forgotten something.
> Does this look natural?
Well, yes. That would probably every mathematicians way. I admit that
FRAC(SUP(INT)) was not the best example, but I guess you understood what
I meant, namely that there may be several good choices for a canonical
form and without proper documentation, you cannot rely that the
programmer of the Algebra library has chosen the same as you in DoCon.
>>> I suggest fraction(m, num, den),
>>> a) where m may be MtPrime or Generic,
>>> b) this operation to be implemented by the Axiom library, not by the user,
>>
>> Sorry, but we are not in a situation like in Maple or Mathematica. User
>> code is indistinguishable and treated in exactly the same way as the
>> library that comes with FriCAS. In Maple or Mathematica, they have a
>> kernel and then there are (interpreted) user functions. That's not the
>> case for SPAD files. Domains/Categories/Packages in user defined .spad
>> files are compile in the same way as library functions just like in any
>> other ordinary programming language.
> I do not understand why does this matter.
You seemed to make a distiction (in (b)) between the Axiom library code
and the user code. If *you* write code and it enters the "official"
repository. Will you count that as user code, because you are just a
user or as library code? If your code enters FriCAS, you will probably
be asked to help maintaining it. Otherwise it faces the chance of
becoming dead.
And as Waldek said, you can write MyFraction, which behaves exactly as
Fraction except for a few functions that you override.
In Aldor one would even have the "extend" keyword and so could add new
properties/functions to already existing domains.
> But this team somehow announces:
> we are going to support at least this set of
> functions and operations and language extesion features.
> And this has a name: "ghc-ext (language) + GHC library"
> (in addition to the standard Haskell-2010 and its library).
Yes, yes. I understand this. But you know how many FriCAS developers
there are. Most of the burden is on Waldek's shoulders. So making a
support promise is not so simple.
> Each impementation announces whether it supports the standard of
> Haskell-2010. This is very important for users.
Clear. I would be happy if there were a defined standard for SPAD. All
there is is a vague document (the Axiom book) and the source code.
> What is the notion of standard in Axiom and FriCAS community?
I would say it's the Axiom book. But this is a vague document in terms
of specification of the SPAD language and the specification of the library.
> The difference between the FriCAS developers and user is greater than
> the difference between GHC team and GHC users.
Unfortunately true. I would like more users to speak up on the mailing
list and slowly become involved in FriCAS development. Dream, dream.
Ralf
Serge D. Mechveliani
>>> It's not so
>>> totally obvious how one would for example make the representation of
>>> Fraction(SUP(INT)) canonical.
>>
>> I thought, there is a natural way. For example, canInv (x:INT)
>> (the canonical invertible factor) is defined as signum x (for x /= 0).
>> canInv(f : SUP INT) == canInv(lc(f)) :: SUP INT;
>> and cancelling the fraction of num and den in Fraction(SUP(INT)) is
>> by
>> c := canInv den; (num/c, den/c).
>
> Well, yes. That would probably every mathematicians way. I admit that
> FRAC(SUP(INT)) was not the best example, but I guess you understood what
> I meant, namely that there may be several good choices for a canonical
> form and without proper documentation, you cannot rely that the
> programmer of the Algebra library has chosen the same as you in DoCon.
Yes, probably, there exist difficult examples for defining any correct
canInv method. Anyway, it is desirable for documentation to explain what
is canInv as notion, and what method is chosen -- at least for easy cases.
>>>> I suggest fraction(m, num, den),
>>>> a) where m may be MtPrime or Generic,
>>>> b) this operation to be implemented by the Axiom library, not by the user,
>>>
>>> Sorry, but we are not in a situation like in Maple or Mathematica. User
>>> code is indistinguishable and treated in exactly the same way as the
>>> library that comes with FriCAS. In Maple or Mathematica, they have a
>>> kernel and then there are (interpreted) user functions. That's not the
>>> case for SPAD files. Domains/Categories/Packages in user defined .spad
>>> files are compile in the same way as library functions just like in any
>>> other ordinary programming language.
>
>> I do not understand why does this matter.
>
> You seemed to make a distiction (in (b)) between the Axiom library code
> and the user code. If *you* write code and it enters the "official"
> repository. Will you count that as user code, because you are just a
> user or as library code? If your code enters FriCAS, you will probably
> be asked to help maintaining it. Otherwise it faces the chance of
> becoming dead.
(b) is due to that this requires to deal with the internal representation,
this cannot be written correctly in Spad, and, I think, this is for the
official developers
(but I wrote later that the practical need of fraction-MtPrime is small).
> In Aldor one would even have the "extend" keyword and so could add new
> properties/functions to already existing domains.
>
This is the most suspicious thing which I observe in Axiom.
So far, I hope that I have missed some point. But you are the second
why mention the feature.
It is difficult to imagine how can an user behave without adding his
category instances to the standard library domains.
For example, in DoCon, I introduce a category (class), say (contrived)
class Sized a where size :: a -> Integer
And usually the first instances for such a category are like this:
instance Sized Integer where size = abs
instance Sized a => Sized [a] where size = sum . map size
instance (Sized a, Sized b) => Sized (a, b)
where
where size (x, y)= (size x) + (size y)
Here Integer, [] := List, and (,) := Pair
are type constructors from the standard library. And this helps a lot
the furher usage of Sized.
For example, when an user defines a category Foo, very often, Integer
must be a member of this category, that is mathematics itself strongly
requires this. This way things are explained in textbooks.
Hence an instance of Foo must be defined for Integer.
If Spad does not allow this, then this is extremely strange.
Because the very claim of the Axiom/Spad project was just following
mathematics in defining algorthms in a generic way.
Now, if one needs to use this Sized for Integer in Spad, one has to
define a copy domain Integer2 and add an implemantation of Sized to
Integer2 ??
And to write almost everywhere in the program Integer2 instead of
Integer ??
And if the program uses 50 library domains in a simialr way, one needs
to create 50 more domains or constructors and use 50 different names for
them ??
MyList, MyProduct, MyInteger, MyFraction, MyUP, MyPOLY, MyMatrix ... ?
Am I missing something?
>> The difference between the FriCAS developers and user is greater than
>> the difference between GHC team and GHC users.
>
> Unfortunately true. I would like more users to speak up on the mailing
> list and slowly become involved in FriCAS development. Dream, dream.
I meant a different thing. I meant that the FriCAS developers deal more
often with a language other than Spad, with internals
(which is almost impossible for users, and not needed for users),
the compiler messages look lispy, and so on,
while the Haskell team writes just in Haskell (except certain very
particular libraries).
This is only my impression, may be wrong.
Regards,
------
Sergei
mec...@botik.ru
Bill Page
> ...
> On Mon, Feb 27, 2012 at 10:38:05PM +0100, Ralf Hemmecke wrote:
>> In Aldor one would even have the "extend" keyword and so could add new
>> properties/functions to already existing domains.
>>
Although "extend" is part of Aldor, my point of view is that this is
rarely needed and maybe only rarely a good idea in Axiom.
>
> This is the most suspicious thing which I observe in Axiom.
> So far, I hope that I have missed some point. But you are the
> second why mention the feature.
> It is difficult to imagine how can an user behave without adding
> his category instances to the standard library domains.
> For example, in DoCon, I introduce a category (class), say (contrived)
>
> class Sized a where size :: a -> Integer
>
> And usually the first instances for such a category are like this:
>
> instance Sized Integer where size = abs
> instance Sized a => Sized [a] where size = sum . map size
>
> instance (Sized a, Sized b) => Sized (a, b)
> where
> where size (x, y)= (size x) + (size y)
>
> Here Integer, [] := List, and (,) := Pair
> are type constructors from the standard library. And this helps a lot
> the further usage of Sized.
In Axiom categories are not classes. An Axiom category is a kind of
predicate. It must be explicitly asserted by the programmer that a
domain satisfies some category expression (formed from Join and with
clauses). Domains satisfy only the named categories. In addition this
category assertion requires that the domain implement a specific set
of exported operations for which it is the programmers responsibility
to ensure that the operations exported by the domain respect the
axioms that are implicit in the category names which occur in the
category expression. So categories are a kind of "interface contract".
Axiom categories form a lattice of sub-categories based on domain
satisfaction, i.e. Any domain which satisfies category C==Join(A,B)
also satisfies both A and B.
> For example, when an user defines a category Foo, very often,
> Integer must be a member of this category, that is mathematics
> itself strongly requires this. This way things are explained in
> textbooks. Hence an instance of Foo must be defined for Integer.
What you want is that the category assertion of the domain Integer be
extended by the category Foo. In Axiom terms this is tantamount to
asking to change the definition of Integer so that it becomes some new
domain somehow different than the old one, having additional
properties and operations.
> If Spad does not allow this, then this is extremely strange.
> Because the very claim of the Axiom/Spad project was just
> following mathematics in defining algorithms in a generic way.
>
I don't think that it is strange to require that the definition of
domains such as Integer (normally) remain nearly static.
> Now, if one needs to use this Sized for Integer in Spad, one has
> to define a copy domain Integer2 and add an implemantation of
> Sized to Integer2 ?
This is facilitated by the use of
== Integer add ...
in your definition of Integer2.
> And to write almost everywhere in the program Integer2 instead of
> Integer ??
> And if the program uses 50 library domains in a simialr way, one needs
> to create 50 more domains or constructors and use 50 different names
> for them ??
> MyList, MyProduct, MyInteger, MyFraction, MyUP, MyPOLY, MyMatrix ... ?
>
No, this is normally not necessary.
> Am I missing something?
>
Yes, I think so.
In Axiom there is a way to introduce new operations related to Integer
without redefining what you mean by Integer. This is done by defining
a package. It is common to see in the Axiom library for example
something like:
)abbrev package INTHEORY IntegerNumberTheoryFunctions
IntegerNumberTheoryFunctions(): with
divisors : Integer -> List(Integer)
...
In your example this would become something like this:
)abbrev package SIZED Sized
Sized(A:OrderedRing): with
size: A -> Integer
size: List A -> Integer
size: DirectProduct(2,A) -> Integer
== add
size(a:A):Integer == abs(a)
size(a:List A):Integer == reduce(+,map(size$SizedInt(A),a))
size(a:DirectProduct(2,A)):Integer == size(first a)$SizedInt(A) +
size(second a)$SizedInt(A)
Note: This code is just of illustration. I haven't actually tried to compile it.
Regards,
Bill Page
Serge D. Mechveliani
The syntax is different, but I do not see any difference in the meaning.
For example, in Haskell there is not a standard Set, nor AdditiveMonoid,
the user must define them, if needs.
Imagine now that Spad is similar in this.
The user defines in Haskell
class Set a => AdditiveMonoid a where (+) :: a -> a -> a
0 :: a
-- Documentation: + must be associative, commutative,
-- it must hold forall x (x+0 == x).
And in Spad ( sorry, the syntax needs correction! ):
Category AdditiveMonoid(...) ... with Join(Set) ... ==
add
+ : (%, %) -> %
0 : %
+++ Documentation: + must be associative, commutative,
+++ it must hold forall x (x+0 = x).
In both cases the meaning _for the compiler_ is
the Universal Algebra defined by the signature
{(+) :: % -> % -> %, 0 :: %}.
intersected with the Universal Algebra of Set.
-- it does not include any additional laws.
In Haskell, `Set a' is placed before `=>',
and in Spad it is placed under Join(...).
And the meaning for the compiler in both cases is just the
_class of domains_
which signature include this signature and the signature of Set.
And in both cases the _intended meaning for a CA developer_
is denoted in the _commentary_
(and Haskell does not presume any CA developer, Haskell is for CA as well
as, for example, for designing a parser, or a compiler for Prolog).
Further, Spad says:
a domain belongs to a category only by explicit assertion placed in
the domain definition.
Haskell is similar: such an assertion is an instance declaration:
instance AdditiveMonoid Integer where (+) = +_Integer
0 = zero_Integer
instance (AdditiveMonoid a, AdditiveMonoid b) =>
AdditiveMonoid (a, b)
where
(x,y) + (x', y') = (x+x', y+y')
(the second declares the instance for the domain constructor of Pair
-- what is Product in Spad).
If the user defines for Integer x+y = x+1 instead of +_Integer,
the compiler will still consider Integer as a member of AdditiveMonoid.
But this (+) instance is not associative.
Hence the AdditiveMonoid class does not coincide _for the compiler_
with the _class of additive monoids_ known in algebra.
Similar is with Spad.
In this part, I do not see any difference between Haskell and Spad --
except that the standard library domains can be extended in Haskell
(like in the above example).
This feature follows the line of mathematical _textbooks_.
A mathematician writes in a textbook
"Consider Z := Integer as an Euclidean ring, and also as an instance
of the Sized category, where size(n) = ...
",
and furher one writes Z and uses size(n), one does not write "Z2".
But I think, if your below suggestion with a `package' works, then,
probably, this feature is not so a great disadvantage in Spad.
Return to the concept difference.
The first real point I see is that in Spad, a domain constructor is a
Spad function whose return value belongs to Type.
The compiler understands this.
And I even use this in Spad when programing a certain generic parser.
In Haskell a function cannot neither return a type (domain) nor take it:
types (domains) are totally static.
> In Axiom there is a way to introduce new operations related to Integer
> without redefining what you mean by Integer. This is done by defining
> a package. It is common to see in the Axiom library for example
> something like:
>
> )abbrev package INTHEORY IntegerNumberTheoryFunctions
> IntegerNumberTheoryFunctions(): with
> divisors : Integer -> List(Integer)
> ...
>
> In your example this would become something like this:
>
> )abbrev package SIZED Sized
> Sized(A:OrderedRing): with
> size: A -> Integer
> size: List A -> Integer
> size: DirectProduct(2,A) -> Integer
> == add
> size(a:A):Integer == abs(a)
> size(a:List A):Integer == reduce(+,map(size$SizedInt(A),a))
> size(a:DirectProduct(2,A)):Integer == size(first a)$SizedInt(A) +
> size(second a)$SizedInt(A)
>
> Note: This code is just of illustration. I haven't actually tried to
> compile it.
Thank you. I shall think of this.
Regards,
------
Sergei
mec...@botik.ru
Ralf Hemmecke
> Although "extend" is part of Aldor, my point of view is that this is
> rarely needed and maybe only rarely a good idea in Axiom.
Since "ëxtend" does not yet exist in FriCAS SPAD, we are talking about
the empty set, but anyway, I firmly believe that "extend" would be a
good idea. Even if it is only used to straighten up the current
bootstrap process.
In FriCAS we have all the sources, so in theory, one could simply modify
the original sources and recompile. The problem is that such a
modification might have effects on distant other domains. In some sense,
I think, "extend" makes the code safer, by not allowing to break
existing code.
Just my 2 cents.
Ralf
Waldek Hebisch
>
> On 03/01/2012 12:03 AM, Bill Page wrote:
> > Although "extend" is part of Aldor, my point of view is that this is
> > rarely needed and maybe only rarely a good idea in Axiom.
>
> the empty set, but anyway, I firmly believe that "extend" would be a
> good idea. Even if it is only used to straighten up the current
> bootstrap process.
>
> In FriCAS we have all the sources, so in theory, one could simply modify
> the original sources and recompile. The problem is that such a
> modification might have effects on distant other domains. In some sense,
> I think, "extend" makes the code safer, by not allowing to break
> existing code.
>
I do not think this is true -- the only difference between 'extend'
and extending by modifying code is that in case of 'extend'
compiler have no information about extensions while in the
second case compiler knows more. If in the second case
you get error at compile time, it means that extension was
wrong and would probably give troubles at runtime. If
modified code compiles, you have essentially the same
possibility for breakage as in case of 'extend'.
Of course, by modifying code you can do much more than via
'extend' -- above I only consider changes that could be
done via 'extend'. In other words, if you get any extra
safety, it is not due to 'extend' itself, but rather
because 'extend' limits you to subset of possible
changes (basically adding new signatures to domains and
joining domains to categories). If it is all want you
need than there is no safety gain. If you need more
then since you can not use 'extend' there is no
comparison.
--
Waldek Hebisch
heb...@math.uni.wroc.pl