This notebook is licenced under CC BY-SA 4.0.

FriCAS Tutorial (Types)

Ralf Hemmecke <ralf@hemmecke.org>

Sources at Github.

In [1]:
)set message type off
)set output algebra off
setFormat!(FormatMathJax)$JFriCASSupport
)set message type on
In [2]:
)version

Value = "FriCAS a9422d32eb6f6b03d98ac6adfc9bf05ec0f5e8bd compiled at Sa 03 Apr 2021 00:29:13 CEST"

Type conversion

Having types available also means to be able to convert elements from one type to another explicitly or specify functions that come from a particular domain.

We have already seen that with identifier: SomeType one can declare an identifier to be of a particular type without actually assigning a value to this identifier.

Suppose we have a value which is of type SomeType. The notation value :: OtherType is used to convert a value of SomeType to OtherType. Of course this operation does not always succeed. In fact, it only succeeds if FriCAS is able to find in its library an appropriate function (usually called coerce, convert, or retract) of type $\text{SomeType} \to \text{OtherType}$ which does the job.

The FriCAS interpreter applies coercion function automatically. For example, when FriCAS sees x+5 on the command line, it figures out that x is an identifier that has no value, so it converts this to a variable.

In [2]:
x
Out[2]:
\[ x \]

The number 5 is of type PositiveInteger.

FriCAS knows that + is in infix operator, so it looks for in its library for a function +: (Variable(x), PositiveInteger) -> ??. The result type is not yet clear. Such a function does not exist.

Before FriCAS says that the expression does not make sense, it tries harder. There is a coercion from Variable(x) to Polynomial(??) where the coefficient ring would still be unknown. The obvious idea would be to take PositiveInteger as the coefficient domain. But wait, polynomials are defined over a ring and the positive integers do not form a ring. Next try is a superdomain of PositiveInteger that is a ring. Integer is a good candidate. So we arrive at Polynomial(Integer).

In Polynomial(Integer) there is a function +: (%, %) -> % defined, because FriCAS knows that integer polynomials form a ring. Note that % is FriCAS' abbreviation for "this type".

It remains to embed 5 into this polynomial ring. This is done via the coercions coerce: PositiveInteger -> Integer and coerce: Integer -> Polynomial(Integer).

Taking everything into account, we see that the resulting type is Polynomial(Integer).

In [3]:
e1 := x+5
Out[3]:
\[ x+5 \]

You should not be surprised that subtracting x from the above expresssion is still a polynomial.

In [4]:
e2 := e1-x
Out[4]:
\[ 5 \]

Of course, this result can be retracted to a more specific domain. However, in general this is impossible and costs time, since the representations of 5 as an element of Polynomial(Integer) and 5 as an element of Integer are different.

In [5]:
e2 :: Integer
Out[5]:
\[ 5 \]

Typeless computer algebra systems internally store a*b as an expression tree. Usually then it is concluded that this is the same as b*a. In FriCAS the meaning of the multiplication operator depends on the context it is used in. Non-commuting structures are easily representable in FriCAS.

In [8]:
p: Quaternion(Integer) := quatern(1,2,0,0)
q: Quaternion(Integer) := quatern(1,0,3,0)
p*q - q*p
Out[8]:
\[ 1+2\, i \]
Out[8]:
\[ 1+3\, j \]
Out[8]:
\[ 12\, k \]

FriCAS has a simple way to ask for properties of domains.

In [9]:
Integer has Ring
Out[9]:
\[ \texttt{true} \]
In [10]:
Integer has Field
Out[10]:
\[ \texttt{false} \]
In [11]:
Fraction Integer has Field
Out[11]:
\[ \texttt{true} \]
In [12]:
Polynomial Fraction Integer has Field
Out[12]:
\[ \texttt{false} \]

FriCAS allows to assign types to variables.

In [14]:
Q := Fraction Integer
PQ := SparseUnivariatePolynomial Q
Out[14]:
Out[14]:

The name of the variable plays no role. FriCAS shows it by default with a question mark.

In [15]:
q1: PQ := 2*x+8
Out[15]:
\[ 2\, \texttt{?}+8 \]

The output routine decides how the variable is actually printed.

In [16]:
[outputForm(q1,x), outputForm(q1,z)]
Out[16]:
\[ \left[2\, x+8, 2\, z+8\right] \]
In [17]:
q2: PQ := x^2-16
Out[17]:
\[ {\texttt{?}}^{2}-16 \]
In [18]:
gcd(q1,q2)
Out[18]:
\[ \texttt{?}+4 \]
In [19]:
extendedEuclidean(q1,q2+1, 1)
Out[19]:
\[ \left[coef1=-\frac{1}{2}\, \texttt{?}+2, coef2=1\right] \]
In [20]:
PZ := SparseUnivariatePolynomial Integer
Out[20]:
In [21]:
p1: PZ := 2*x+8
Out[21]:
\[ 2\, \texttt{?}+8 \]
In [22]:
p2:PZ := x^2-16
Out[22]:
\[ {\texttt{?}}^{2}-16 \]
In [23]:
gcd(p1, p2)
Out[23]:
\[ \texttt{?}+4 \]

Since polynomials with integers as coefficients do not form a euclidean domain, there is no euclidean algorithm available.

In [22]:
extendedEuclidean(p1,p2+1, 1)

There are 1 exposed and 0 unexposed library operations named 
extendedEuclidean having 3 argument(s) but none was determined to be 
applicable. Use HyperDoc Browse, or issue
                        )display op extendedEuclidean
to learn more about the available operations. Perhaps package-calling the 
operation or using coercions on the arguments will allow you to apply the 
operation.
Cannot find a definition or applicable library operation named 
extendedEuclidean with argument type(s) 
                     SparseUnivariatePolynomial(Integer)
                     SparseUnivariatePolynomial(Integer)
                               PositiveInteger
 
Perhaps you should use "@" to indicate the required return type, or "$" to 
specify which version of the function you need.

Domains and Categories

In FriCAS everything has a type. Elements like numbers, polynomials, array, have domains as their types. For example, the type of -5 is Integer. The type of a domain is called a category. The type of Integer is IntegerNumberSystem. The type of a category is the distinguished name Category.

In [24]:
-5
Out[24]:
\[ -5 \]

FriCAS does not normally show the names of the categories a domain belongs to. In fact, Integer does not only belong to IntegerNumberSystem, but also to ConvertibleTo(String), LeftOreRing, Canonical, and canonicalsClosed.

In [25]:
Integer
Out[25]:
In [26]:
Integer has IntegerNumberSystem
Out[26]:
\[ \texttt{true} \]
In [27]:
Integer has LeftOreRing
Out[27]:
\[ \texttt{true} \]

A category only describes the sigatures of functions that domains that belong to this category must provide.

Categories are organised in hierarchies. A category can inherit from several other categories. Multiple inheritance is not a problem since categories only describe the interface of domains but do not implement any function themselves.

A domain must provide all function signatures of the category it belongs to. Domains can only inherit code from one single other domain.

Neither domains nor categories are built into the SPAD language. They are all implemented in a library that comes with FriCAS as source code.

A user can easily write new domains and categories and compile them. There is no difference between user defined types and library defined types.

Like the domains Polynomial(Integer) and Complex(Integer) or the categories Module(Integer) and VectorSpace(PrimeField(5)), domains and categories can be constructed as the result of a function, a domain or category constructor. This is the basis for parametrized polymorphism.

Which functions a category exports may depend on a parameter, for example, SparseUnivariatePolynomial(R) is of type EuclideanDomain only if the domain R that is given as a parameter is of type Field.

In [28]:
SparseUnivariatePolynomial Fraction Integer has EuclideanDomain
Out[28]:
\[ \texttt{true} \]
In [29]:
SparseUnivariatePolynomial Integer has EuclideanDomain
Out[29]:
\[ \texttt{false} \]