SPAD and Polymorphism
Martin Baker
the best way to model an algebraic structure (is it more suited to
modeling a co-algebra?) however in the wider Axiom/FriCAS environment,
especially in things like geometry/graphics there seem to be occasions
where it would be handy to be able to do things like polymorphism.
I have a specific example in mind, I would like to implement a
scenegraph as discussed on this page.
http://www.euclideanspace.com/maths/standards/program/mycode/graph/
The same principles would also apply to reading and writing other tree
structures like XML. The reasons I think the OO approach would be
appropriate are:
This could be a very big structure, it could potentially hold hundreds
of nodes, each of which could hold thousands of points. We would want
to be able to modify this structure, apply transforms and so on, in an
efficient way. So the model needs to be 'mutable' that is we need to
be able to change things without creating a duplicate of the
structure. In this case I think the advantages of a mutable structure
outweigh the disadvantages. Of course this is no problem to implement
in SPAD (use a list) but it does line up with OO approach.
The main reason that I would like to use some form of polymorphism is
that it provides a very nice way to break down the functionality into
manageable pieces.
To illustrate this here I need to greatly simplify (probably would not
use these nodes in the real scene graph but they illustrate the
point).
First a Rectangle node which can render itself:
Rectangle(): T==C where
T== ShapeCategory with
render:(n:%,t:Transform) -> Void
C== add
Rep := Record(width: NNI,height: NNI)
render(t:Transform):Void ==
-- code to apply cumulative transform goes here
sayTeX$Lisp
concat["rectangle(",string(width),",",string(height),")"]
Then a Circle node which can also render itself:
Circle(): T==C where
T== ShapeCategory with
render:(n:%,t:Transform) -> Void
C== add
Rep := Record(radius: NNI)
render(t:Transform):Void ==
-- code to apply cumulative transform goes here
sayTeX$Lisp concat["circle(",string(radius),")"]
Then I would like a group node which can contain any combination of
nodes:
Group(): T==C where
T== ShapeCategory with
render:(n:%,t:Transform) -> Void
C== add
Rep := List ShapeCategory
render(t:Transform):Void ==
-- code to apply cumulative transform goes here
for node in % repeat
render(node,t)
I know this won't work because:
* List of a category does not seem to work.
* These domains could be extended from a domain but polymorphism
does not work,as illustrated on this page,
http://www.euclideanspace.com/maths/standards/program/spad/example/
So I know that this does not work but I like this way of doing things
because it seems a nice clean way to divide the code into manageable
bits and we could easily add another node (say Triangle) without
affecting the existing nodes.
So, is there a way to get these benefits in an SPAD style?
By the way, there is sourcecode distributed with FriCAS, that does
implement a scenegraph like this in:
* invnode.as.pamphlet
* invrender.as.pamphlet
* invtypes.as.pamphlet
* invutils.as.pamphlet
However, these are Aldor so they probably would not work in SPAD and
even then, they seem to need a much more convoluted code pattern than
above, this seems to involve 'inner node' (in invtypes) domains to
implement the tree structure and another set of nodes (in invnode)
with indexed links to the other nodes.
I really don't want to implement such a complex system so I was
wondering if anyone knows an alternative?
Martin Baker
Waldek Hebisch
>
> Group(): T==C where
> T== ShapeCategory with
> render:(n:%,t:Transform) -> Void
> C== add
> Rep := List ShapeCategory
> render(t:Transform):Void ==
> -- code to apply cumulative transform goes here
> for node in % repeat
> render(node,t)
>
The Spad way should be:
Rep := List Record(item: type, type : ShapeCategory)
but ATM it does not work (this is one of things that people
who write about "dependent types" want).
Note that List ShapeCategory means list of _types_.
> So, is there a way to get these benefits in an SPAD style?
IIUC you want to apply functions from ShapeCategory on items
in the list without any extra work -- I believe this is
impossible in Spad. The best thing in Spad spirit would
be to have Rep as I wrote, use 'item' field and have
type inference to figure out right the call (but ATM
this does not work). I think that the following will
work:
Rep := List Record(item: None, type : ShapeCategory)
but at each use you need:
t := x.type
it := (x.item) pretend t
Alternatively, you may define polymorphic version of shape:
PolymorphicShape: ShapeCategory ==
add
Rep := Record(val : None, type : ShapeCategory)
f1(x) ==
t := x.type
nx := (x.val) pretend t
f1(nx)
f2(x) ==
....
That is for each operation in ShapeCategory you need a dispatcher
function.
Note that both variants are much less efficient than typical
Spad code.
>
> By the way, there is sourcecode distributed with FriCAS, that does
> implement a scenegraph like this in:
>
> * invnode.as.pamphlet
> * invrender.as.pamphlet
> * invtypes.as.pamphlet
> * invutils.as.pamphlet
>
> However, these are Aldor so they probably would not work in SPAD and
> even then, they seem to need a much more convoluted code pattern than
> above, this seems to involve 'inner node' (in invtypes) domains to
> implement the tree structure and another set of nodes (in invnode)
> with indexed links to the other nodes.
>
> I really don't want to implement such a complex system so I was
> wondering if anyone knows an alternative?
>
In Spad normal way to build complex data structures is via
Union constructor. Union requires that you explicitely
test for branches, so is more "heavy" than what you want.
OTOH frequently tests for branches are required anyway
by the computation logic.
Sometimes functional style works better: instead of putting
functions in domains make generic function which works
on any type from given category.
One extra comment: polymorphic containers are problematic
in most typed languages. Spad containers are parametized
by type, but any instance contains only elements of single
type. This solves some problems (it is easy to visit
all nodes in type safe way), but causes extra problems
if you want to use OO style subtyping (inheritance).
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Ralf Hemmecke
not a OO language. Or actually, it is, but you shouldn't program in it
in a OO style. SPAD puts emphasis on functions rather than objects.
> First a Rectangle node which can render itself:
>
> Rectangle(): T==C where
> T== ShapeCategory with
> render:(n:%,t:Transform) -> Void
> C== add
> Rep := Record(width: NNI,height: NNI)
> render(t:Transform):Void ==
> -- code to apply cumulative transform goes here
> sayTeX$Lisp
> concat["rectangle(",string(width),",",string(height),")"]
I must admit that I'd like a proper output type rather than Void. Your
function returns something, right? Let's call this RETTYPE.
OK. Then let's transform your render to
render: % -> Transform -> RETTYPE
Your definition above is wrong anyway, since you forgot the % parameter
in the "add" part.
render(n: %)(t: Transform): RETTYPE ==
-- implementation goes here
> Then a Circle node which can also render itself:
Similar for Circle.
> Then I would like a group node which can contain any combination of
> nodes:
> Group(): T==C where
> T== ShapeCategory with
> render:(n:%,t:Transform) -> Void
> C== add
> Rep := List ShapeCategory
> render(t:Transform):Void ==
> -- code to apply cumulative transform goes here
> for node in % repeat
> render(node,t)
Why not like this...
Group(): T == C where
T == with
construct: List(Transfrom -> RETTYPE) -> %
render: % -> Transform -> RETTYPE
C == add
Rep := List (Transform -> RETTYPE)
construct(l: List(Transform -> RETTYPE)): % == l
render(x: %)(t: Transform): RETTYPE ==
lr: List RETTYPE := [f t for f in x]
-- now transform that List(RETTYPE) into RETTYPE
Then, of course, you would say
g: Group := construct(render(somerect)$Rectangle,
render(somecirc)$Circle,
render(otherrect)$Rectangle)
And finally
render(g)(sometransform)
gives something of RETTYPE.
Think SPAD not OO.
Ralf
PS: I haven't actually tested the code, but I hope the idea is clear.
Martin Baker
valuable time with these questions but I was stuck and it seems the
only way to get this information. Both the general programming style
and the specific information about what works and what causes problems
are very helpful.
So now you have given me some ideas to continue experimenting.
Just one last folowup question for this thread: what decides whether
an entry in the Rep variable is a reference (pointer to another
structure) or a value (memory allocated to hold actual value)?
I am guessing that this is determined by what it is:
Rep % -- reference?
Rep category -- reference?
Rep domain -- value?
Rep None -- empty until set?
Rep Union(s1: domain,s2 domain) - which domain(s) are created at
instantiation?
Rep List --
Rep Type --
Rep Any --
The reason I ask is if Rep contained say: a list of child nodes, and/
or a parent node, these would have to be links to other structures
rather than values.
Thanks,
Martin Baker
Ralf Hemmecke
> an entry in the Rep variable is a reference (pointer to another
> structure) or a value (memory allocated to hold actual value)?
I don't quite understand your concern. Please look in the AUG in the
section about Rep. In fact, in Aldor one could completely programm
without ever using Rep. But I don't want to confuse you too much.
> The reason I ask is if Rep contained say: a list of child nodes, and/
> or a parent node, these would have to be links to other structures
> rather than values.
Rep actually is not used as a container. In that sense it contains
nothing. Rep is just there to have a particular name for the type of the
representation domain.
Rep is always a type or (more precisely) a domain.
The best way to think about Rep is in terms of the underlying set of a
universal algebra. Consider for example a semigroup. S. S consists of an
underlying set R and an operation *, i.e. S = (R, *).
In terms of SPAD you write
S: with
_*: (%, %) -> %
== add
Rep := SomeDomainYouLike
((a: %) * (b: %)): % == ...
Then our underlying set R is Rep.
I hope that makes it clear.
Of course, S is not the same as Rep, since if you choose, for example,
SomeDomainYouLike to be Integer, then S exports just one operation,
namely *, whereas Integer exports also +, 1, 0, etc.
Ralf