This is one of a set of pages about the Axiom CAS and its forks, particularly FriCAS, these pages start here. This particular page discusses the language used by FriCAS which is called SPAD. This page is a general overview of SPAD but, for an attempt at a more rigorous definition, see the syntax page.

Spad is a language for the Axiom/FriCAS symbolic computing mathematics program. The language can be used interactively as an interpreter, here we discuss its use to define new packages and domains by compiling from an '.spad' file. So just to be clear this page concerns the Spad compiler and not the Spad interpreter (these sometimes produce different results).

There are some specific requirements for a language to support a CAS. If we were to start to write some code to support some given algebra (say - vectors) then we soon find we need to use dependant types (or at least some weaker form of dependant types), we then need to make some tradeoffs between this requirement and type safety and things get messy. As far as I know, no mainstream, statically typed languages support dependant types, perhaps some variants of ML?

Therefore we need to investigate CAS programs that are designed specifically to support user defined algebras.

On this page the Spad language is compared with the Object Oriented (OO) and Functional Programming methodologies. If you are new to programming it is better to stick to the proper documentation:

 Axiom http://www.axiom-developer.org/axiom-website/documentation.html Fricas http://fricas.sourceforge.net/doc/index.html

Computer Algebra using OO and Functional Methodologies

So what are the special requirements of a maths program? How does it affect the best computer language and methodology to use? Lets take an example of representing a simple equation such as:

force = mass * acceleration

We could represent this using OO methodology, for example the variables force and acceleration could be instances of a vector class, mass could be an instance of a real class and '=','*' can then represent functions on these objects. However this does not work very well in practice because:

• The operations like '*' cut across different objects. (We could get round this by putting scalar*vector in class vector and scalar*scalar in class real but this gets more complicated when we add more classes and functions).
• If we already know that mass is of type real and acceleration is of type vector then we can infer the type of force, or we may want to infer the type of mass or acceleration. But we cant use objects until we know what type they are, we need a more dynamic matching approach.
• We need a way to support 2D or 3D vectors and so on, also vectors over reals or vectors over integers and so on.

So, unless we are only using built-in ('static') types like Integer, DoubleReal, List and String then there are two levels of instantiation, first we instantiate the type(s), then we instantiate the representation:

 ```(1) -> force := vector([0\$DoubleFloat,1])*9.81 (1) [0.0,9.809999999999999] Type: Vector(DoubleFloat) ```

So a type Vector is created by: vector([0\$DoubleFloat,1]) but I don't really understand what is going here? If a 2 dimensional vector over DoubleFloat is created several times:

 ```(2) -> cosAngle := dot(vector([0\$DoubleFloat,1]),_ vector([0\$DoubleFloat,2]))/2 (2) 1.0 Type: DoubleFloat ```

Is there a separate type for each of these?

 ```The following quote is taken from the FriCAS forum here > I think part of my problem is that I am not clear about domains like > Float and OutputForm that are not explicitly created by the user, are > instances created when needed by the system, or does the same one > remain active through the session? When you write '1::OutputForm', you in particular request sytem to create (possibly new) instance of OutputForm. Basically any code that uses some domain is in some sense requesting creating this domain. However, actual creation is done in lazy way (and split into several steps), and AFAIK typicall domains are actually in a strange "almost done" state. Domain creation is rather expensive, so once FriCAS stared creating a domain (that is created a stub ready to fill details in lazy way) it will normally reuse the already created part. Some domains are marked as "mutable", FriCAS will not re-use such domains but create new instance. Above I wrote "normally" because cache (such caches are per constructor) holding already created domains may overflow and then FriCAS will remove the oldest position for the cache. And user may explicitly clear caches using ')clear completely'. Also Spad complation clears caches. Because OutputForm has no parameters, it needs cache with single slot and this cache will never overflow, so normally you will re-use old version. But if caches are cleared, new instance is created. BTW: Normally persistent state is stored in Lisp variables, you can access them from Spad (but they must be created from Boot or Lisp). Float is not really good example, basically I think it is better to avoid variables in domains (but Float has specific needs so it is not clear if we can do better). -- Waldek Hebisch```

Functions

Most of the 'processing' done by an SPAD program is done by functions, for example here we define a function called 'force' and then use it to calculate the force required to accelerate a mass of 2 units by an acceleration of 3 units.

 ```(1) -> DF ==> DoubleFloat Type: Void (2) -> force(m:DF,a:DF):DF == m*a Function declaration force : (DoubleFloat,DoubleFloat) -> DoubleFloat has been added to workspace. Type: Void (3) -> force(2,3) Compiling function force with type (DoubleFloat,DoubleFloat) -> DoubleFloat (3) 6.0 Type: DoubleFloat```

When defining a function in the compiler then we may specify the function in two stages:

• function declaration - force: (DF,DF) -> DF this defines the 'signature' of the function this allows the program
• function definition - force(m,a) == m*a

So if a function like force(2,3) is called the program will recognize this as a function call and search the functions that have been stored in the program for a match. Both the function name and the number and type of input and output parameters must match, this comes from the signature from the declaration. When

Functions can have multiple input parameters but only one output (i.e. return) parameter

SPAD does not make a distinction between 'pure' functions and functions with 'side-effects' such as outputting or inputting, or writing to a global variable, or modifying an input parameter. However there are some conventions such as adding a ! to the name of a function which modifies its input parameters.

Each parameter has a type, types may be:

• Built in types.
• User defined types, such as a user defined domain as described later.
• Functions (the type of a function is its signature like: (DF,DF) -> DF).

Packages

Function declarations and definitions may be grouped together into a package. Often this is just a convenient way to keep related function declarations/definitions together but it can provide additional control over which function gets called in cases where several signatures would match.

This is done by specifying the package using the '\$' symbol.

myFunction(2,3)\$myPackage

So a package is starting to look a bit like an 'object' but only in that it is grouping functions together its not doing things like data abstraction, encapsulation, polymorphism and so on.

Domains

A domain is like a package but with an additional capability, it allows us to create a variable called Rep which allows us to create runtime instances.

Object Oriented - Similarities and Differences

In object oriented (OO) programs the data and the functions on that data are linked by putting them in a class definition. This provides data abstraction and encapsulation, because classes can hide the details of their implementation from their clients.

So for an object oriented program:

class definition:
 variables, every time this class is instantiated, by 'new' keyword, storage for these variables is allocated and they are set to their initial values with some internal link back to these function definitions. functions which can be applied to the particular instance of the object.

Spad can operate in this way, for instance mult could be defined as unary function which could be called like:

a.mult(b) mult(b)\$a

to mean a*b. There is a problem with this, if we did this we would have to create a different type for a and b. Although we can do this with Spad packages, domains give a better solution by using 'representations':

In Spad Domains we can create one instance of a type, for instance CliffordAlgebra, then multiplication is a binary function which takes two arrays representing the multivector and returning the result as a similar array. Note that these arrays are not held in the domain but their type is held in the Rep variable.

This is much more of a mathematical approach because:

• Multiplication is a binary function (%, %) -> % where % is a placeholder for the underlying set.
• '*' is defined for different types and we want to choose the type to operate on by matching (rather than specifying the type with \$a).
• This approach is closer to the functional programming approach (see below) which has the potential for additional benefits.

So how does spad match an instance of a domain to the function definition? It associates the function with the 'class' (domain) by pattern matching.

However, the program still needs to know how to associate these arrays to their function definitions, I assume that when an instance is created using the 'new' statement adds a link back to the function definition. When the CliffordAlgebra multiplication function returns a new array representing the result it creates it like this:

```Impl ==> add
dim     :=  2^n
Rep     := PrimitiveArray K
New     ==> new(dim, 0\$K)\$Rep```

In most OO languages there is a 'this' keyword, so that the code in functions can refer to the object that contains it, I get the impression that in Spad this is divided into two parts.

 % this type (domain) typically used for matching a function such as: (%, %) -> % Rep this representation

I would like to understand this better, for instance,

• Can I use any structure for the representation, such as List [], Tuple () or String "" ?
• What is PrimitiveArray? I can't find this in the documentation.
• How does the domain use the Rep parameter? Rep does not even hold the size of the PrimitiveArray.
• How should an instance of potentially sparse instance be created?

Definition and Implementation

In some OO languages such as as C++ a function can be separately declared (in .h file) and defined (in .cpp file). In other languages such as java there is no separate declaration.

In Spad if a function is required outside the domain (it is exported) then it requires both a definition and an implementation. If it is local then only an implementation is required but it will only be seen after the implementation, that is, we only use a local function below the place in the file where it is defined.

 *: (%, %) -> % in the category part (which is the "interface", i.e. the names of exported functions) and    (a: %) * (b: %): % == ... in the implementations part (the stuff that comes after the "add" keyword).

Inheritance and Composition

In OO languages we can inherit from a superclass, in a hierarchy, and our object will behave as if it were an object of the superclass. Our class can provide additional functions and can also 'overload' a function, that is use the same signature as a function in the superclass, thereby customising the functionality.

Spad supports (multiple) inheritance, Polymorphism only works when we inherit from categories (see polymorphism example below). Categories (not to be confused with category theory?) are a bit like java interfaces but they allow implementations as well as definitions of functions.

Multiple inheritance from categories can be done like this:

T ==> Join(Ring, Algebra(K)) with

and categories can inherit from other categories in a hierarchical structure.

How are conflicts handled in multiple inheritance?

How do we design the category hierarchy? I have thought about some of the issues for the case of Clifford algebra on this page.

Polymorphism

Many classes can implement the same interface, this allows us to access different types of data as if it were the same (through the same interface).

In java the inheritance and polymorphism concepts are separated In C++ polymorphism can be done by multiple inheritance and vitalization, in java there is an interface which is separate from inheritance.

The following quote is taken from the FriCAS forum here (see references at the end of this page)

> Concerning OO, Spad gives you some OO capabilities, but they are
> different than in other languages.  You may use Spad categories
> like Java interfaces and domains like classes, but while
> inheritance for categories works like in Java, inheritance for
> domains is different (in C++ speak all methods defined in a
> domain are static).

Oh, that is true and will probably bite you some day. If you have a domain (modify Integer)

 and you say a: A := 7 b: B := 7 g(a)\$A g(b)\$B They will give the same result, since functions are not "virtual" in SPAD. B inherits the full implementation of g from A. So when you call g(b)\$B you actually call g(b)\$A. Since that does not type check (the argument of g\$A must be of type A but b is of type B, it rather calls    g(b pretend A)\$A Anyway, the implementation of f\$B does not matter for the evaluation of g(b). To see a full work through of this example see 'virtual function example' on this page.

Functional Programming - Similarities and Differences

The ideas of functional languages go back to lambda calculus (Is there a domain for lambda calculus?)

Functional programs tend to have the following properties:

• functions are first class objects, they can be passed to and returned from other functions, they can be stored in variables and so on.
• discourages 'side effects' of functions such as modifying variables that can be seen outside the function. That is functions tend to purely map inputs to outputs like mathematical functions.
• Functional style:
• The constructs in the language tend to be functions.
• encourages immutable objects (although lists are mutable)
• encourages recursion over iteration.
• If we took this to extremes values might be defined in terms of functions, functions of functions and so on back to fundamental values such as 0 and 1.

In Spad functions may return types, as well as functions or values.

 The following quote is taken from the FriCAS forum here (see references at the end of this page) No, values are not "defined in terms of functions". Rather: the only way to get a value is by applying a function of the appropriate domain. There is an exception (in spad, not aldor): for "literals", i.e., Integers, DoubleFloats, Strings there are no functions. "everything is a function" -- this is confused.  Spad has functional interfaces, meaning that you can not directly get domain data (in Java speak all member variables are private and you can get them only if there is appropriate accessor function).  Spad uses functional notation of other operations: a(b) may be: function a applied to b element number b of array a element number b on list a field b of record a something different if appropriate 'apply' operation is defined but application is not always defined, for example '1(2)' does not "work".

Program Structure Elements

Blocks are indicated by indentation (either spaces or tabs - any preferred recommendation? two spaces per indent?) not by curly bases.

Statements can be separated by ';' but this only tends to be used when statements are on the same line or to avoid ambiguous statements.

Types are also only needed to avoid ambiguity, for instance,

a : Integer := 2

or

a := 2\$Integer

The brackets () around a function call are optional when the function takes only one argument. This makes a function equivalent to an infix operator.

symbol
(keyword)
description example
f : (arguments) -> returnType function declaration t : (Float -> Float, Float) -> Float
==

rule, delayed assignment

function definition

fact(0) == 1
fact(n) == n*fact(n-1)

t(fun, x) == fun(x)**2 + sin(x)**2

var +-> function

+-> is an infix operator meaning 'maps-to'
It can be used to create anonymous functions, so instead of:
myFunct(x:Type):Type == if x >0 then x else -x
we can have:
x +-> if x >0 then x else -x

x +-> if x >0 then x else -x
name macro == body macro is a general textual substitution

==>

macro name == body
macro name(arg1,...) == body

macro definition

provides general textual substitution

NNI==> NonNegativeInteger

T ==> Join(Ring, Algebra(K), VectorSpace(K)) with

g(arg1: INT, arg2: FLOAT, arg3: INT): STRING == ... function combined declaration and definition
:=

immediate assignment

multiple immediate assignment

variable := expression

( var1, var2, ...,
varN ) := ( expr1, expr2,
..., exprN )

:*
= equation
PackageForm : Exports == Implementation simplified package definition
PackageForm : Exports == Implementation where
optional type declarations
Exports == with
list of exported operations
list of function definitions for exported operations
package definition
DomainForm : Exports == Implementation simplified domain definition
DomainForm : Exports == Implementation where
optional type declarations
Exports == [ Category Assertions] with
list of exported operations
[Rep := Representation]
list of function definitions for exported operations
domain definition
CategoryForm : Category == Extensions [ with Exports ] category
inport RepeatedSquaring(\$)
statement ; mark end of statement, not usually required unless we put more than one statement on a line. a:=1;b:=2
: Type indicates type a : Integer := 2
:: Type convert to type
pretend Type treat one type as another, only works if they have the same internal structure (how do I know what the internal structure is?) (2/3) pretend Complex Integer

\$

function() \$Type

variable \$ Type

specify domain

call function for a given type

force variable to a given type

new(dim, 0\$K)\$Rep

sin(4.3) \$Float

4.3\$Float

calculation @ Type tell Axiom the desired type of a result of a calculation
```(1) -> (1 + 2)@Float
(1)  3.0
Type: Float```
free variable allows us to declare a variable that is global free counter
local variable allows us to declare a variable that is not global local counter
( )

tuple (array of different types)

parameters for a function are a tuple, so prefix operator on a tuple is equivalent to a function.

```(1) -> (1,2,3)
(1)  [1,2,3]
Type: Tuple(PositiveInteger)
```
[ ]

list literal (mutable array of items with the same type)
many functions availible see List below

Also used for Records and Unions (like lists but elements may be of different types and elements have selector)

```(1) -> [1,1,2]
(1)  [1,1,2]
Type: List(PositiveInteger)```

[2^i for i in l]

{ }

In FriCAS now block delimiter
Was Set ( like list but order unimportant )

```(1) -> set [1,1,2,3,3]
(1)  {1,2,3}
Type: Set(PositiveInteger)
```
" " string literal (array of char)

if boolean then
if equation then
if ... not ... and ...or ... then
if ... then ... else ...

if ... then [else ...] always returns a value so we can use this on the right hand side of an assignment

since there is an explicit 'then' keyword there is no need to put the condition in brackets

a:= if x >0 then x else -x

if R has Field then ...
if myUnion case mtType then ... Select from Union values if not (n.parameters case boundbox) then
BoolExpr=>Expr if BoolExpr is true then return from block with value Expr ~prime?(i) => iterate
~= returns true if both sides not equal

_ escape character and continue on next line if at the end of a line _" to put " into a string
-- comment for rest of line
++ comment for following variable, function, etc.
% this domain
while BoolExpr repeat loopBody
do

while ...repeat ... iterate ...

skips over the remainder of a loop if odd? then () iterate
break leave current loop
return leave current function

for i in n..m repeat ... is 1
for i in n..m by s repeat ...
for i in list repeat ...
for j in n..m repeat loopBody
for j in n..m | odd? j repeat

for i in n..m repeat ... is 1
for i in list repeat ...
for j in 200..300 repeat loopBody
for j in 200..300 repeat loopBody
for j in 200..300 by s repeat...
default
define
export
extend
fluid fluid variables are bound to a function and can be used by functions it calls.
from
generate
goto fortran code
inline
never
of
to
yield
.
,
'

Common Types

Definable Operators

 by case mod quo rem # + - +- ~ ^ * ** .. = ~= ^= / \ /\ \/ < > <= >= << >> <- ->

I have listed some of the built-in types and the functions defined on them here:

Boolean Z
Integer

PI
PositiveInteger

Equation Symbolic
+     ?+?
-
*     ?*?
/     recip
power     ?^?
and ?/\?
?and?

or ?\/?
?or?

~ not
nand nand(%,%)
nor nor(%,%)
xor xor(%,%)
= ?=?   ?=?
~= ?~=?   ?~=?
> ?>?   ?>?
< ?<?   ?<?
smaller?(%,%)

>= ?>=?   ?>=?
<= ?<=?   ?<=?
max max(%,%)   max : (%,%)
min min(%,%)   min : (%,%)
not not?
random
gcd     gcd(%,%)

constants false
true
1
test     one? : %
odd?
bit?

to see exports for a given type:

)show Boolean

Common Functions

I have listed some of the functions that are common to a lot of domains here:

Function Use
reduce

the reduce operation is used to extend binary operations to more than two arguments

reduce(binary function,List of operands, initial value)

reduce(max,[2,3,7,3,-4])

(((A,B) -> B),List A,B) -> B

successively uses the binary function (A,B) -> B on the elements of the list and the results of previous applications

Lisp Functions

Lisp is the underlying runtime environment and SPAD relies on direct calls to Lisp to provide basic functionality. The names of these function calls end with \$Lisp.

I have started making a list of these function calls on the page here.

Input / Output

SPAD domains can define how a given algebra will be displayed on the output device. How that works is explained on the page here.

Lists

I get the impression that

 elt(list,index) list . index extract the first element at index .. segment 1..10 for var in seg repeat loopBody loop through segment m := matrix [ [4*i + j for j in 1..4] for i in 0..3] for var in list repeat loopBody loop through list for var in seg | BoolExpr repeat loopBody such that (must be boolean) # size of

Statically Typed

Is statically typed, i.e. types of elements are known at compile time.

Package

Package is similar to a class definition in OO and it is also a function which returns an implementation. However it is not really like a OO class because, although the following package constructor looks like an OO constructor the parameters UP and Par are part of the package type (like generics) they are not intended as parameters set differently each time an individual instance is created and they can't be modified by functions.

 ComplexRootPackage(UP,Par) : T == C where UP : UnivariatePolynomialCategory Complex Integer Par : Join(Field, OrderedRing) T == with

So a package is really intended as a collection of function calls which are self contained but perhaps share generic types. In other words a package does not have a set of changeable parameters that could be set and read by functions. The general form is:

PackageForm : Exports == Implementation

Since, in practice we need declarations and implementations, it is usually used in an extended form:

 PackageForm : Exports == Implementation where optional type declarations Exports == with list of exported operations Implementation == add list of function definitions for exported operations

There are two parts to this:

• The first part contains the function declarations (named Exports here but could be called anything), this declares the 'signature' of the function which is exported (made available to the rest of the code and to the interpreter). This is a bit like an interface definition to the rest of the system.
• The second part contains the function definitions (named Implementation here but could be called anything), this defines the body of the functions, is defines what the function actually does.

All operations have types expressed as mappings with the syntax:

source -> target

Domain

This is similar to package with the addition of a representation, it is also a function which returns an implementation:

DomainForm : Exports == Implementation

Again this is usually extended to:

 DomainForm : Exports == Implementation where optional type declarations Exports == [ Category Assertions] with list of exported operations Implementation == [ Add Domain] add [Rep := Representation] list of function definitions for exported operations

Representation Example:

Rep := SquareMatrix(n,K) --representation

One of the differences from package is the special variable Rep to identify the lower level data type used to represent the objects representation of the domain.

representation

The Rep for quadratic forms is SquareMatrix(n, K).
This means that all objects of the domain are required to be n by n matrices with elements from K.

Category

CategoryForm : Category == Extensions [ with Exports ]

Each exported operation has a name and a type expressed by a
declaration of the form
``name: type''.

Categories can export symbols, as well as
0 and 1 which denote
domain constants.The
numbers 0 and 1 are operation names in Axiom.
In the current implementation, all other exports are operations with
types expressed as mappings with the syntax

source -> target

Performance Issues

When writing a program it is useful to have some sore of model in ones head of how to write efficient code. Otherwise there is no way to guess which is best without actually timing the output.

• What are performance issues of recursion verses iteration? Is tail recursion better and so on?
• Does Spad use garbage collection?

To help with these

 > It not compiler weakness but the core of Spad design.  You get > example by taking any parametrized domain or package, like: Ah... you meant parametrization of domains. That's indeed tricky. Even in Foo(R: Ring): Category == with    foo: % -> % Foo actually is a (parametrized) type (category). Now, Bar(R: Ring): Foo(R) == add ... defines another type (a domain) Bar that depends on a Ring R. I still would have called that static. But, in fact, the actual concrete category like Foo(Integer) only exists at runtime. Still, the compiler can derive a lot from the parametrized formulation of the category. Actually, Foo is not a category, but rather a function that (given a concrete domain for its parameter R) returns a category. And Bar is not a domain, but rather a function that (given a concrete domain for its parameter R) returns a domain. Interestingly, here is that Bar is a function whose return type, i.e. Foo(R) (not only the value, i.e. Bar(R)) depends on the input parameter. That is know under the name "dependent types" and is not often found in any programming language. Also note that in the definitions of Bar and Foo, the parameter must be of type Ring, so it will already be detected at *compile-time* that Foo(String) is not a valid type since String does not satisfy the Ring properties. > Concerning guessing: I general I agree.  But there are cases where > choice does not matter and then making arbitrary choice is not > bad (I do not know if such cases apply to overloading). Only, if the resulting function is exactly the same, I would agree, since then guessing does not matter. (It's actually not guessing anymore.) But if there are cases when there are two functions that do the same thing, the compiler should complain that it doesn't know what to choose. Why I want that behaviour is that the functionality of the cases might be the same, but they may differ in complexity. I don't think it is a good idea to give up control over complexity of algorithms. But maybe you meant something else. Do you have a concrete case? > Concerning ability to easily predict: this is programmer responsiblity. > IIUC one can encode any NP problem (like breaking AES) into > overload resolution problem for current compiler.  Making compiler > closer to right theoretical model involves solving harder problems. > While the method currently used is too stupid to handle "intersting" > problems, it still should easily beat humans. > > > Fact that compiler can do things which are hard > for humans is not a reason to cirpple the compiler.  For example > I agreed that compiler signals error for anonymous functions > without type declaration in cases which require search.  This > forces programmes to add declarations in tricky cases.  But > it also forces declarations in many cases which are obvious > to humans.  More general, trying to force clear progams by > language restrictions may easily backfire. > Oh, I don't want to add restrictions to the language, I just want deterministic programs, i.e. programs whose result does not depend on the compiler implementation. Why I am so much for explicit type declarations, is that it makes programs more easily understandable by humans. One doesn't have to grep through all the inheritance chains to find the corresponding export. Maybe all would be easier with a good IDE that pops up a window with the corresponding type of the object under the mouse pointer. ;-) Who is going to write that?

Comments preceded by ++ have the following structure:

In function definition:

```myFunction:(param1:aType1,param2:aType2) -> aType
++ myFunction(param1,param2) gives such-and-such a result
++ param1 is such-and-such
++ param2 is such-and-such
++ and other free format comments
-- any comments that we don't want to go into user ducumentation such as todo list.```

In category definition:

```<<category MYSHORTNAME MyLongName>>=
)abbrev category MYSHORTNAME MyLongName
++ Author: MyName
++ Date Created: month year
++ Date Last Updated: month year
++ Basic Operations:
++ Related Constructors:
++ Keywords: whatever
++ Description:
++  Category of whatever, allows us to model whatever
++
++ References:
++ http://www...```

I have put some information about my attempts to debug Spad programs here.

References

The quotes on this page are from a discussion on the FriCAS forum here the following people gave very helpful and informative answers to my questions on this topic:

• Waldek Hebisch
• Ralf Hemmecke
• Martin Rubey
• Arthur Ralfs

Obiously I claim no rights to their work, I just quote them here to make sure that the information is not lost or hard to find.