Why isn't it possible to convert Polynomial Integer to Polynomial Fraction Integer

[Neven Sajko]

The title basically says it all. I am referring to the lack of
appropriate coerce or convert operations that make it impossible to
convert the simpler type to the more complex type with only :: in Spad
code.

On the other hand, if I do this in the interpreter:
0::Polynomial(Integer)::Polynomial(Fraction(Integer))
I get the result as expected.

Also, the situation is the same with, e.g., UnivariatePolynomial (as
with Polynomial).

I guess that it's possible to convert between polynomials with such
differing coefficient types by disassembling into coefficients,
converting coefficients, and then reassembling into a polynomial. But
why isn't this built into the library as a coerce or convert
operation?

Also, how come that the interpreter has this functionality
automatically? How is it achieved in the interpreter?

Lastly, what is the recommended way to achieve a conversion like this
in Spad code?


Thanks,
Neven

[Ralf Hemmecke]

On 07.08.21 18:41, Neven Sajko wrote:
> The title basically says it all. I am referring to the lack of
> appropriate coerce or convert operations that make it impossible to
> convert the simpler type to the more complex type with only :: in Spad
> code.

The interpreter guesses what you want, when you type
::Polynomial(FRAC(INT)). The compiler isn't allowed to do that. So *you*
must call the right function yourself.

http://fricas.github.io/api/PolynomialFunctions2.html?highlight=polynomialfunctions

(10) -> p := x+2*y*x+3*x*y*z

(10) 3 x y z + 2 x y + x
Type: Polynomial(Integer)
(11) -> map(c+->c::FRAC(INT),p)$PolynomialFunctions2(INT, FRAC INT)

(11) 3 x y z + 2 x y + x
Type: Polynomial(Fraction(Integer))

> Also, the situation is the same with, e.g., UnivariatePolynomial (as
> with Polynomial).

For that I only know this package.

http://fricas.github.io/api/PolynomialCategoryLifting.html?highlight=polynomialcategorylifting

That's pretty generic and thus a bit difficult to apply.

> I guess that it's possible to convert between polynomials with such
> differing coefficient types by disassembling into coefficients,
> converting coefficients, and then reassembling into a polynomial. But
> why isn't this built into the library as a coerce or convert
> operation?

Simple answer. It is implemented as you see from the links above, but it
is by nature of FriCAS not as simple as you would like it.

Think about it. Suppose you want to write a function

coerce: Polynomial R -> Polynomial S

In order for this coerce to work nicely, it should either live in
Polynomial(R) or Polynomial(S). OK, that means it should live in the
code of the Polynomial constructor. But wait, the definition goes

Polynomial(R: Ring): with ... == add ...

Ooops. How would you specify the second type? You could do it this way:

Polynomial(R: Ring): with
...
coerce: (S: Ring) -> % -> Polynomial S
...
== add
...
coerce(S: Ring): % -> Polynomial S == (x: %): Polynomial S +->
-- here you program the conversion into Polynomial S

But look closer at that definition. You are about to define the domain
"Polynomial". Inside of it you use the constructor "Polynomial(S)".
That's a recursive definition. And the above coerce has a dependent
type, i.e., its result type depends on the input. Pretty involve, hey?

So the original AXIOM developers chose to put that function into a
package, with the consequence that it is quite a bit harder to call.

> Also, how come that the interpreter has this functionality
> automatically? How is it achieved in the interpreter?

The interpreter is a magician. In order to understand how FriCAS works,
do little steps with the compiler and learn explicitly what functions
you have to call. When I started with AXIOM, I got quite frustrated when
I translated my .input files into .spad files. You seem to be exactly at
that stage. Yes, that's pretty frustrating, but you have been warned
that the interpreter does some magic which you cannot rely on when you
write .spad files.

Hope that helps
Ralf

[Neven Sajko]

On Sat, 7 Aug 2021 at 17:06, Ralf Hemmecke <ra...@hemmecke.org> wrote:
> Think about it. Suppose you want to write a function
>
> coerce: Polynomial R -> Polynomial S
>
> In order for this coerce to work nicely, it should either live in
> Polynomial(R) or Polynomial(S). OK, that means it should live in the
> code of the Polynomial constructor. But wait, the definition goes
>
> Polynomial(R: Ring): with ... == add ...
>
> Ooops. How would you specify the second type? You could do it this way:
>
> Polynomial(R: Ring): with
> ...
> coerce: (S: Ring) -> % -> Polynomial S
> ...
> == add
> ...
> coerce(S: Ring): % -> Polynomial S == (x: %): Polynomial S +->
> -- here you program the conversion into Polynomial S
>
> But look closer at that definition. You are about to define the domain
> "Polynomial". Inside of it you use the constructor "Polynomial(S)".
> That's a recursive definition. And the above coerce has a dependent
> type, i.e., its result type depends on the input. Pretty involve, hey?

Hmmm, this is all very interesting. A couple of questions:

1. On what level are recursive definitions a problem? I know, for
example, that in the C programming language it is possible to define a
struct with fields that contain pointers to the struct type itself.
Most other programming languages likewise support features like this.
Fricas itself has a linked list type: List. I should really look at
how List is implemented in the library when I get the chance.

2. This seems to tie in with my previous recent question about the
possibility of polymorphic functions. How hard would it be to
implement those? Superficially it seems like they could be implemented
as simple syntax sugar over parametric packages (each function
parameterized over type T gets its own (anonymous?) package with T as
constructor parameter).

3. I noticed that there's a category called CoercibleFrom (and one
called CoercibleTo, too). Could one of those categories be used to
solve this issue, maybe?
So it would go something like this (I don't know the appropriate
syntax, I'm just asking if this could be possible):
For any types A and B that Polynomial can be parameterized with, if
type A is in CoercibleFrom(B), define a function like so:

coerce: Polynomial(B) -> Polynomial(A)

coerce(b: Polynomial(B)): Polynomial(A) ==
map(c +-> coerce(c)@A, b)$PolynomialFunctions2(B, A)


Thanks,
Neven

[Ralf Hemmecke]

> 1. On what level are recursive definitions a problem?

I don't think they are a problem for the spad compiler. Also the
dependent type stuff should work fine. (Something that doesn't work in
most languages.) But in some sense it looks ugly
from the design point of view. This kind of mapping from Polynomial(Z)
to Polynomial(Q) is a function that is neither attached to the first nor
to the second domain, so it rather should live on its own in a new
package and have Z and Q as parameters of the package. It is exactly as
the original developers have designed it.

> 2. This seems to tie in with my previous recent question about the
> possibility of polymorphic functions. How hard would it be to
> implement those? Superficially it seems like they could be
> implemented as simple syntax sugar over parametric packages (each
> function parameterized over type T gets its own (anonymous?) package
> with T as constructor parameter).

Usually, with a bit of thinking one can do with a design that does not
need polymorphic functions. Usually, you put the function in a package
that is parametrized by a type and implement the function for this
parameter type. At the time of usage you call the function from the
package giving the right parameter type that you want.

> 3. I noticed that there's a category called CoercibleFrom (and one
> called CoercibleTo, too). Could one of those categories be used to
> solve this issue, maybe?

No. These categories are not implementations of any function. They
basically only provide the signatures

coerce: X -> %

or

coerce: % -> X

for some domain X, but no implementation of such a function.

> So it would go something like this (I don't
> know the appropriate syntax, I'm just asking if this could be
> possible): For any types A and B that Polynomial can be
> parameterized with, if type A is in CoercibleFrom(B), define a
> function like so:

> coerce: Polynomial(B) -> Polynomial(A)
>
> coerce(b: Polynomial(B)): Polynomial(A) == map(c +-> coerce(c)@A,
> b)$PolynomialFunctions2(B, A)

Actually, I think, one can do this starting a package like this

PolyMap(A, B): Exports == Implementation where
A: Ring
B: Join(Ring, CoercibleFrom A)
Exports ==> with
coerce: Polynomial A -> Polynomial B
Implementation ==> add
coerce(x: Polynomial A): Polynomial B ==
map(c +-> coerce(c)@A, x)$PolynomialFunctions2(A,B)

(WARNING: I haven't checked whether the above code actually works.)

But what would that help you? Suppose in your program you construct a
polynomial p of type Polynomial(INT). Just typing

p :: Polynomial(FRAC(INT))

will not work. Why? Simple, you would ask the compiler to search for a
function coerce with type Polynomial(INT) -> Polynomial(FRAC INT).
You might say that, well, there is PolyMap with exactly that function in
the library. But how does the compiler know that there is PolyMap?
Having all packages visible all the time is not a good idea.
Furthermore, what should the compiler do if someone programs another
package later, say, PolyMapHemmecke(A, B) that also provides a function
coerce: Polynomial A -> Polynomial B? Should the compiler choose the
implementation from PolyMap or from PolyMapHemmecke. You see, **you**
have to give the exact function name and the exact package from where
this function comes. This is how programming works in FriCAS.

Ralf

[Waldek Hebisch]

Ralf already mentioned PolynomialFunctions2. Interpreter has
several buitin rules for coercion, one of them is: "if there
is map between T(C) and T(D) and coerce from C to D, then
map(c -> coerce(c)@D, t) gives coercion". Currently, in Spad
one has to provide explicit code for such coercions.

What could be done: easy thing would be to add 'coerce' to
PolynomialFunctions2. In fact, there are several xxFunctions2
packages, so probably several coercions to add. OTOH,
actual code to implement coercion is smaller than package
specification, so there would be little gain from such 'coerce'.

More general problem is that currently Spad compiler sees
what is explicitly or implicitly imported, but ignores
everthing else. In particular, Spad compiler will not
"invent" a package name containing some needed function,
when needed package must be explicitely imported. Spad
compiler will not "invent" a parameter, even if for
human specific parameter looks like obvious choice.

As an example, if you need list of integers and list of
symbols you need import both List(Integer) and List(Symbol).
In principle, there shuld be possible to write something like

import List(?)

to import all possible lists and let compiler choose appropriate
parameter. However, currently this is not implemented, and
if implemented it is not clear how well it would work. There
is question of syntax, '?' could mean uspecified parameter, but
what to do when there are two parameters, or one parameter that
appears in two places? And which rules should govern choice
of parameter values. Currently interpreter uses bunch of ad-hoc
rules for parameters, and sometimes it gives rather surprising
results, in other cases interpreter is unable to find parameters
that are "obvious" to people. In interpreter normally there
is user who knows what is intended and can react to wrong
choices. In compiler we want robust rules, code that compiles
and works today, should compile and work in future, even if
compiler is enhanced and there are new domains.

--
Waldek Hebisch

[Grégory Vanuxem]

Hi,

I would preferably use /1

Something like *1/1 ord use 2/1 for example. Awful but usable.

Greg

> --
> 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 fricas-devel...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/20210807200244.GB12798%40math.uni.wroc.pl.

[Waldek Hebisch]

On Fri, Aug 13, 2021 at 06:09:20PM +0000, Gr??gory Vanuxem wrote:
> Hi,
>
> I would preferably use /1
>
> Something like *1/1 ord use 2/1 for example. Awful but usable.

I am not sure what you mean here. "convertion" by divison
works in interpreter, but Neven wrote about Spad.

--
Waldek Hebisch

[Grégory Vanuxem]

Yes, I saw that too late and not tested it in Spad. It was a good question in fact.

Regards

--
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 fricas-devel...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/20210814232537.GB1171%40math.uni.wroc.pl.