Spad for OO Programmers

[Martin Baker]

I am still trying to properly understand the Spad language properly,
what I would like is a introduction for people who have object
oriented experience. In other words to point out the differences that
may confuse and also a crib sheet for the syntax.

I have not yet found such a document (by the way, the link to st-
andrews website on Axiom documentation page is broken).

Since I have not found this I have been making some notes for my own
benefit:
http://www.euclideanspace.com/maths/standards/program/spad/
Any corrections welcome.

Martin Baker

[Ralf Hemmecke]

> I am still trying to properly understand the Spad language properly,
> what I would like is a introduction for people who have object
> oriented experience. In other words to point out the differences that
> may confuse and also a crib sheet for the syntax.

Let me confuse you. ;-)

SPAD *is* an object oriented language. But it is *not* the way one
should see it. And you probably confuse people if you tell them that
SPAD is object oriented.

A: with
foo: Integer -> Integer
== add
foo(x: Integer): Integer == 2*x

is nothing else than a class in oo terms.

if you just take

with
foo: Integer -> Integer

you have a (here unnamed) Category. Categories (SPAD) are comparable to
interfaces in Java (only that SPAD is more powerful).

You should rather take the few that with categories (SPAD) you try to
model what is known in mathematics as (multi-sorted) algebras. Domains
are then concrete instances of such algebras. The most important thing
is that SPAD is much closer to mathematics as any other known (to me) OO
programming language.

> Since I have not found this I have been making some notes for my own
> benefit:
> http://www.euclideanspace.com/maths/standards/program/spad/
> Any corrections welcome.

You should really distinguish between interactive use and library
programming. If you teach the language, concentrate on library
programming. That is cleaner. In interactive use, the interpreter often
guesses things. That should help the user, but is not part of SPAD. I.e.
use *.spad files if you want to learn the language.

Replace "Is strongly typed." by "Is statically typed, i.e. types of
elements are known at compile time."

"everything is a function"???
Where did you find that? I wouldn't say that this is true.

v: Record(a: Integer, b: String) := [3, "abc"]

The variable v is certainly not a function.

Your website looks not very convincing to me. There are just too many flaws.

Perhaps you should first study the Axiom Book (check vol 0 from
http://axiom-developer.org/axiom-website/documentation.html) and for
language specific things consult
http://www.aldor.org/docs/HTML/index.html or from
http://www.aldor.org/wiki/index.php/User_Guides_for_Compiler_and_Libraries
choose http://aldor.org/docs/aldorug.pdf . Aldor is close enough to SPAD
(I was actually supposed to be the successor of SPAD.) so that you will
get a more thorough introduction to the language.

Hope that helps
Ralf

[Martin Baker]

Ralf,

I didn't say that Spad was, or was not, object oriented. In fact,
that is the point! What I keep finding is that I need a document that
is intended for people, like me, who come from a background in object
oriented languages .

Although the documents you list are very good I find it very difficult
to pick out these subtle differences. I keep thinking, yes I know this
topic, so I read a bit faster and then I miss these issues.

I certainly would not claim my web page would be useful to other
people, it just my attempt to note these issues to help me understand
a bit better. I'm even more certainly not trying to compete with the
proper documentation (although I think it would be good if someone,
not me, were to write some notes and crib sheets for people who war
trying to translate their knowledge from other fields), I think
perhaps you mistook my intention?

> "everything is a function"???
> Where did you find that? I wouldn't say that this is true.
>
> v: Record(a: Integer, b: String) := [3, "abc"]
>
> The variable v is certainly not a function.

OK I take you point, it just looked to me that things like domain and
package definitions look like function definitions? So somehow the
function seems to have a higher status, I'm just not sure how to put
it? Would you say Spad is a functional language? Also the way that the
compiler seems to compile each function one at a time makes me think
that there is something different going on here?

Anyway, thanks for the points you make, it all helps me understand
better.

Martin

[Martin Rubey]

Martin Baker <gg8...@martinb.com> writes:

>> Where did you find that? I wouldn't say that this is true.
>>
>> v: Record(a: Integer, b: String) := [3, "abc"]
>>
>> The variable v is certainly not a function.
>
> OK I take you point, it just looked to me that things like domain and
> package definitions look like function definitions?

That's right. You want to say:

Functions may return types, as well as functions or values.

> So somehow the function seems to have a higher status, I'm just not
> sure how to put it?

It's not special treatment of functions (oh well, yes, there are even
languages where you cannot return a function :-), it's rather that
spad/aldor is quite flexible with types.

Martin

[Martin Rubey]

Dear Martin,

* everything is a function
* discourages 'side effects' of functions
* encourages immutable objects, although lists are mutable.

these three are all incorrect.


| domain definition:
| data set when domain created and apply to type such as 'dimension'
| (not specific to instance) Similar to static variables?
| functions on their own parameters, returns new instance

I don't understand this...

| So values are defined in terms of functions, functions of functions
| and so on back to fundamental values such as 0 and 1.

Oh, now I understand what you wanted to say with: "everything is a
function". 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.

But: To get a rational number, you apply /$Fraction(Integer) to two
Integer arguments.

| In many cases the brackets () around a function call are also
| optional.

precisely, when the function takes only one argument.

Martin

[Waldek Hebisch]

"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".

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).

Spad distinctive feature is its type system. Spad is "statically
typed" meaning that compiler knows how to compute "static" type
for each quantity. I put "static" in quotes because in Spad
types are actually computed at runtime (in some cases Spad
compiler can determine type already during compilation, but
frequently it can not). Spad is different from dynamically
typed languanges which bundle type information with actual
data -- in Spad type information is separate. This means that
Spad compiler has a lot of opportunities to omit computations
on types. Spad approach is also different than typical OO
approcach: in Java interfce is statically known but at
runtime you may have any object which satisfies given interface.
So in practice Jave also have to bundle object type (class) with
data. In Spad OO type inheritance is is available ony for
categories (types of types), but not for normal data. So for
normal data type computed by the compiler exactly agrees with
actual type of data.

I should mention here that many of Spad types are parametrised,
for each tuple of parameteres you get distinct type. Spad
types may be passed as arguments to functions and returned
as values -- this in principle gives quite a lot of possibilites
to do computations on types. Let me add that types computed
at runtime pose a significant challenge for the compiler,
especially that Spad has type-based overloading --
there is a risk that compiler will be forced the generate
very inefficient code. Spad solves most of this problem
putting some extra restricions: you are not allowed to do
general runtime computation on categories, all categories
(except for exact values of parameters) must be known to the
compiler at compile time. Moreover, for resolving overloading
Spad does not use actual type (which is known only at runtime),
but only category of the type. This means that in most cases
compiler is able to resolve overloading at compile time
(if it can not resolve some case the compiler simply uses
first match, or signals error if it has insufficient information
to find any mutch).

You ask "So how does spad match an instance of a domain to the function
definition?". This is not well-posed question. You probably
want to know how Spad decides which function to call. This is
two stage process. The first stage is overload resolution at
compile time. In given call place there may be several (or none)
visible definitions for given function. Each definition comes
from some domain or package. Recall that domains and package
are computed at runtine: the Spad compiler knows how to compute
apropriate domains and for each of them knows associated category.
Note that category is known at compile time and gives list of
functions available in the domain (the domain may export more
functions, but the compiler only uses compile-time information
about available functions). Given list of available functions
Spad compile tries each in turn to see if types of arguments
agree with function declaration and if the result type is acceptable.
Note that Spad allows you to have multiple functions with the
same argument types, which differ only in the result type, so
the expected result type affects choice and complicates the
resolution process. Let me say that it may be hard for
programmer to predict which function will be used by the
compiler, if that is a problem the programmer may explitely
specify types, like:

(foo(x1@Type1, x2@Type2)$Type3)@Type4

which means that the compiler will check that x1 is of type Type1,
x2 is of type Type2 and then search domain (or package) Type4 for
function foo which takes arguments of types Type1 and Type2 and
returns value of type Type3. Let me add that code for resolving
overloading in the compiler is not very large, but in a sense it
is most complicated part of Spad compiler. Actually, the problem
with overloading is that it is impossible to do "right thing"
with reasonable efficiency, so the compiler takes shortcuts
which make hard to describe what the compiler is actually doing.

Now, you may think that overload resolution chooses concrete
function to call, but in fact there is more to this. First,
list of available fuctions is known at compile-time, but the
domain may be only known at runctime -- this is quite similar
to Java where interface in statically known, but actually
object class in known only at runtime. Second, the function
in not necessarily implemented in given domain -- it may be
inherited. This requires runtime search. While inheritance
have similarity to typical OO languages, there are significant
differences.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[Ralf Hemmecke]

> I didn't say that Spad was, or was not, object oriented. In fact,
> that is the point! What I keep finding is that I need a document that
> is intended for people, like me, who come from a background in object
> oriented languages .

I understood that. And what I wanted to say, is: Forget about OO and
just learn a new language. You will more easily find the true style of
SPAD programming.

Just think in terms of mathematics, not objects.

For example look at mult. In an oo language mult is actually a unary
function. You call it like

a.mult(b)

to mean a*b. In mathematics * is a function (%, %) -> % where % is a
placeholder for the underlying set (or THISDOMAIN, if you like). So in
SPAD you define

*: (%, %) -> %

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).

Although, domains are like classes, in normal SPAD-programming, you
never think that way. You don't send messages to objects, you call
functions. It's a nicer view for mathematicians. ;-)

> Although the documents you list are very good I find it very difficult
> to pick out these subtle differences. I keep thinking, yes I know this
> topic, so I read a bit faster and then I miss these issues.

Learn a new language and ask the list whether you've understood it
correctly. We are here to help.

> OK I take you point, it just looked to me that things like domain and
> package definitions look like function definitions? So somehow the
> function seems to have a higher status, I'm just not sure how to put
> it? Would you say Spad is a functional language? Also the way that the
> compiler seems to compile each function one at a time makes me think
> that there is something different going on here?

It seems that you have missed an important point from my last message.
If you want to learn the language, you should rather avoid the
interpreter (i.e. the FriCAS command line) for programming.
Write .spad files with an ordinary editor and then use

)compile myfile.spad

to compile your code and *use* it on the command line.

Ralf

[Ralf Hemmecke]

> but application is not always defined, for example '1(2)' does
> not "work".

Yep, because, in vanilla FriCAS, it is not defined. But compile the file

---rhxBEGIN inte.spad
)abbrev domain INTE Inte
Inte: Join(IntegerNumberSystem, ConvertibleTo String, OpenMath,_
Canonical, canonicalsClosed) with
elt: (%, Integer) -> %
== Integer add
elt(a: %, b: Integer): % == a + ((b*b) pretend %)
---rhxEND inte.spad

i.e. store this in some directory then say

fricas
)compile inte.spad
1(2)

and the result should be 5.

(1) -> 1(2)

(1) 5
Type: Inte

Note that the type is "Inte" and not "Integer".

> 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 Inte above)

A: with
...
f: % -> %
g: % -> %
== Integer add
f(x: %): % == 2*x
g(x: %): % == f(x) + 10

and a domain B like this...

B: with
...
f: % -> %
g: % -> %
== B add
f(x: %): % == 3*x

and you say

a: A := 7
b: B := 7

g(a)$A
g(b)$B

They will give the saym 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).

> Spad distinctive feature is its type system. Spad is "statically
> typed" meaning that compiler knows how to compute "static" type
> for each quantity. I put "static" in quotes because in Spad
> types are actually computed at runtime (in some cases Spad
> compiler can determine type already during compilation, but
> frequently it can not).

Waldek, what does that mean? Can you give an example? Would you agree
that this is a weakness of the compiler?

> In given call place there may be several (or none)
> visible definitions for given function. Each definition comes
> from some domain or package.

Ehm, Waldek, would you say that SPAD does not allow top-level functions
that do not live in domains? For sure the interpreter allows that. I
haven't tested putting a function in a .spad file, though.

> Let me say that it may be hard for
> programmer to predict which function will be used by the
> compiler,

I'd say that it must be predictable. Easily predictable. The compiler
should NEVER guess and choose one function where it has serveral options
to choose from. In such cases the compiler MUST throw an error. If it
doesn't, I consider that a compiler bug.

Ralf

[Arthur Ralfs]

Ralf Hemmecke wrote:
>>
>
> Perhaps you should first study the Axiom Book (check vol 0 from
> http://axiom-developer.org/axiom-website/documentation.html)

Martin,

If, like me, you don't like long pdf's you might be interested in
my translation of the axiom book to xhtml+mathml format.

Arthur

[Arthur Ralfs]

and here's the link

http://mathbrane.ca/axiom/

[Martin Baker]

Arthur,

Yes, I do prefer html documentation and upto now I have been using the
documentation here:

http://axiom-wiki.newsynthesis.org/uploads/contents.xhtml

Thanks for the link, I will try your documentation.

With all these versions of documentation it is certainly a problem
knowing which is more upto date and complete, especially all the
versions from the Axiom/FriCAS/Aldor forks, I guess I'll just have to
try them and see what works best.

However my main problem how to take Ralf s advise: "Forget about OO

and just learn a new language. You will more easily find the true

style of SPAD programming" also "Just think in terms of mathematics,
not objects.". Good advise I'm sure, but very difficult for me to do.

Martin

[Martin Rubey]

Martin Baker <gg8...@martinb.com> writes:

> Arthur,
>
> Yes, I do prefer html documentation and upto now I have been using the
> documentation here:
>
> http://axiom-wiki.newsynthesis.org/uploads/contents.xhtml
>
> Thanks for the link, I will try your documentation.
>
> With all these versions of documentation it is certainly a problem
> knowing which is more upto date and complete, especially all the
> versions from the Axiom/FriCAS/Aldor forks, I guess I'll just have to
> try them and see what works best.

For the documentation of the language itself, I still recommend the
Aldor (!) User Guide. Aldor was the successor of Spad, but never became
free. I think I'm doing (i.e., programming) well by pretending that
Spad is a crippled Aldor.

Martin

[Waldek Hebisch]

> > Spad distinctive feature is its type system. Spad is "statically
> > typed" meaning that compiler knows how to compute "static" type
> > for each quantity. I put "static" in quotes because in Spad
> > types are actually computed at runtime (in some cases Spad
> > compiler can determine type already during compilation, but
> > frequently it can not).
>
> Waldek, what does that mean? Can you give an example? Would you agree
> that this is a weakness of the compiler?
>

It not compiler weakness but the core of Spad design. You get
example by taking any parametrized domain or package, like:

PolynomialToUnivariatePolynomial(x:Symbol, R:Ring): with
univariate: (Polynomial R, Variable x) ->
UnivariatePolynomial(x, Polynomial R)
== add
univariate(p, y) ==
q:SparseUnivariatePolynomial(Polynomial R) := univariate(p, x)
map(x1+->x1, q)$UnivariatePolynomialCategoryFunctions2(Polynomial R,
SparseUnivariatePolynomial Polynomial R, Polynomial R,
UnivariatePolynomial(x, Polynomial R))

since R is know only at runtime only at runtime it is known
what Polynomial R is. Note: since Polynomial is a literal
constructor Spad at compile time creates apropriate category
("category of Polynomial(R) with R being an arbitrary ring")
and this categorty is used to determine available signatures.
Also given:

p1 : Polynomial R
p2 : Polynomial R

Spad compiler knows that p1 and p2 are of the same type. But
only at runtime it will compute the actual domain.

BTW: In simple natural examples it is possible to completely
eliminate runtime types -- while compiler does not know types
the code will run exactly the same for all values of paramaters.
But for example conditionals based on types are computed at
runtime and require actual types. To know types in places
where they are really needed we need to compute types at
runtime in many places where at first glance everything could
happen at compile time.

Let me add that in cases where types are known at compile
time (when you use constructors without parameters, like
Boolean or Integer), the compiler uses types for optimization,
but nevertheless the types are again computed at runtime (this
may be considered compiler weakness, but actually there are
good reasons to do this).

> > In given call place there may be several (or none)
> > visible definitions for given function. Each definition comes
> > from some domain or package.
>
> Ehm, Waldek, would you say that SPAD does not allow top-level functions
> that do not live in domains? For sure the interpreter allows that. I
> haven't tested putting a function in a .spad file, though.
>

ATM Spad compiler assumes that top level functions are constructors.
But the simplest method to add top-level functions to language
description is to add special "top-level domain". So assuming
that each function live in a domain simplifies description whithout
restricting possible usage.

> > Let me say that it may be hard for
> > programmer to predict which function will be used by the
> > compiler,
>
> I'd say that it must be predictable. Easily predictable. The compiler
> should NEVER guess and choose one function where it has serveral options
> to choose from. In such cases the compiler MUST throw an error. If it
> doesn't, I consider that a compiler bug.
>

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).

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.

<rant>
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.
</rant>

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[Ralf Hemmecke]

> For the documentation of the language itself, I still recommend the
> Aldor (!) User Guide.

True. In terms of understanding the language (SPAD), that is probably
the best reference. There are a few things that probably won't work in
SPAD, but that should not bother you much. Use the list if you get
stuck. In fact, you can compile Aldor programs for use in FriCAS.

The biggest problem with Aldor is that the compiler is not free and
currently unmaintained, i.e. dead. :-(

Ralf

[Martin Rubey]

Martin,

Ralf Hemmecke <ra...@hemmecke.de> writes:

> The biggest problem with Aldor is that the compiler is not free and
> currently unmaintained, i.e. dead. :-(

Yes, Aldor is dead. But I didn't recommend the Aldor User Guide as a
book for learning Aldor, but rather for learning Spad :-)

Martin

[Waldek Hebisch]

Martin Baker wrote:
>
> With all these versions of documentation it is certainly a problem
> knowing which is more upto date and complete, especially all the
> versions from the Axiom/FriCAS/Aldor forks, I guess I'll just have to
> try them and see what works best.
>

For FriCAS the official documentation is the one shown by Hypertex
browser -- it should be reasonably up to date.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[Ralf Hemmecke]

On 11/25/2009 08:27 PM, Waldek Hebisch wrote:
>>> Spad distinctive feature is its type system. Spad is "statically
>>> typed" meaning that compiler knows how to compute "static" type
>>> for each quantity. I put "static" in quotes because in Spad
>>> types are actually computed at runtime (in some cases Spad
>>> compiler can determine type already during compilation, but
>>> frequently it can not).
>> Waldek, what does that mean? Can you give an example? Would you agree
>> that this is a weakness of the compiler?

> It not compiler weakness but the core of Spad design. You get
> example by taking any parametrized domain or package, like:

[snip]

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.
>
> <rant>
> 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.
> </rant>

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?

Ralf

[Martin Baker]

Thank you very much for all the helpful replies to this thread.

I hope you don't mind? but I have included your replies on the web
page:
http://www.euclideanspace.com/maths/standards/program/spad/

Its just that I find the information so useful that, in addition to
the proper documentation, I like to keep all my other working
knowledge in one place so that I can update it as I go and I don't
have to remember where to find it.

If you object I can easily remove anything.

Thanks,

Martin Baker