Transcript presentation source

Abstract Classes –
pure computer science meets
pure mathematics.
The Beauty of Implementing
Abstract Structures as Abstract
Structures.
Marc Conrad, University of Luton.
05.03.2003
Marc Conrad, University of Luton
1
An Overview – the context.
"pure" mathematics
Mathematics before
the 20th century
computer
algebra etc.
computer science
05.03.2003
Marc Conrad, University of Luton
2
Some motivating remarks




Students in Computer Science learn object oriented
techniques as a method for designing software systems.
Without explicitly knowing it they learn fundamental
principles of abstract mathematics.
Java as an object oriented language is widely used and
accepted for many areas as Graphical User Interfaces or
Networking. We will see that the underlying principles
are also very well suited for implementing
"mathematics".
More possibilities to deal with abstract mathematical
entities in software.
L'art pour l'art
05.03.2003
Marc Conrad, University of Luton
3
Object Oriented Concepts

History:




Since 1962 with SIMULA 1.
Inheritance used since 1967 in SIMULA 67.
Today: Java, C++.
Concepts:



Objects send messages to other objects.
Classes are blueprints for objects. A class defines
the behaviour of an object using methods.
Classes are linked via associations & inheritance.
05.03.2003
Marc Conrad, University of Luton
4
Classes and Objects:
A class has data and methods.


Textbook Example:

A car class may have
the following methods:




startEngine()
move()
speed, numberOfDoors,
numberOfSeats, ...
05.03.2003
A finite field class may have as
methods:

And as data:

Math Example

add(), multiply(), subtract(),
divide(), exponentiate(),
computeFrobenius()
And as data:

characteristic, generating
polynomial, generator of
multiplicative group, ...
Rings, spaces, categories, etc.
can easily identified as classes
Conrad, University of Luton
orMarcobjects.
5
Inheritance: Give one class (the child class) all
the methods and data of another class (the
parent class): An "is a" relationship.

Vehicle
Car
Textbook:

The class car gets all
methods of the vehicle +
additional own methods.
Math Example
Quadratic Extension
F(d)
Complex Field
C
Specifying a special case from
a general concept.
05.03.2003
C = R(-1) "is a"
quadratic extension
of R
Marc Conrad, University of Luton
6
Inheritance hierarchies usually have a tree or
directed graph structure
Ring R
Vehicle
R/fR
Car
R[x]
R
Bicycle
F(d) = F/ (x2 – d)F
Estate
Hatchback
C = R(-1)
05.03.2003
Marc Conrad, University of Luton
7
Overriding methods: Reimplement a method of
the parent class in the child class.

Textbook:

Math Example

Vehicle:

F(d):


Car (inherits Vehicle):


Implement a method move().
Also implements a method
move().
 Car objects execute the
move() method defined in
the Car class.
05.03.2003


Implement multiplication
C (inherits F(d) ):

Re-implement
multiplication, e.g. using
polar coordinates in
some cases.
Reinterpreting behavior
in the specialisation
Marc Conrad, University of Luton
8
An advantage of Overriding methods:
Generic algorithms



Textbook:

A class Driver can be
associated with the Vehicle
class.
The Driver can move the
Vehicle moving in fact a
car or a bicycle.

Math Example
Define a polynomial ring
over an arbitrary ring of
coefficients and obtain
polynomials over C, Q,
F(d) etc.
Define new structures on an abstract level.
05.03.2003
Marc Conrad, University of Luton
9
Abstract methods – abstract classes.


That is, the driver moves only Cars, Bicycles, but not
a "Vehicle". In fact the Vehicle class does not need to
define the move() method.
Similarly a Ring class does not need to define
addition and multiplication. (But it is obvious, that a
Ring has addition, multiplication, etc.)
The object oriented paradigm allows to declare
a method in a class without implementing it.
This is the concept of abstract classes.
05.03.2003
Marc Conrad, University of Luton
10
Abstract methods: Declare a method in the
parent class – implement in the child class.

Textbook:

Math Example

Vehicle:

A Ring R:


Car (inherits Vehicle):


Declare a method move().
Also implements a method
move().
 Car objects execute
the move() method
defined in the Car class.
05.03.2003


Declare multiplication.
C (inherits R):

Implement multiplication.
Reinterpreting behavior
in the specialisation
Marc Conrad, University of Luton
11
Example: A ring.

We cannot implement:







addition
negation
multiplication
inversion
"zero"
"one"
check if zero

We can implement:

a-b = a + (-b)

exponentiation:
n
an = a  ...  a.




05.03.2003
subtraction:
embedding of Z, Q.
check for equality
polynomials over this
ring
etc.
Marc Conrad, University of Luton
12
An Experiment. Implementing abstract
mathematics in Java from scratch.





Implement a class Ring. Methods which cannot be
implemented are declared abstract.
Implement a polynomial ring using an abstract Ring as
coefficient ring.
The polynomial ring is a child of the ring class.
Implement Z as a child of the Ring class.
  This generates a simple arithmetic for
multivariate polynomials with integral coefficients.
See http://ring.perisic.com for a Java implementation.
05.03.2003
Marc Conrad, University of Luton
13
Some results


It is astonishing simple to implement complex
mathematical structures in an object oriented
environment from scratch.
Drawbacks:
 Performance.
 Decisions on how to organise classes (e.g. is field a
property of a ring or is it a child class of a ring).
 Special algorithms as primality testing or factoring do
not fit into an object oriented environment.
05.03.2003
Marc Conrad, University of Luton
14
More abstract structures




It is possible to work with abstract structures!
 Modular Ring R/p(x), where R is abstract.
 Quotient Field Quot(R), where R is abstract.
 Same amount of work as implementing Z/mZ or Q.
 Infinite algebraic extensions.
Multivariate polynomials can be used although only
univariate polynomials have been implemented
Advanced structures can be derived as child classes:
 Complex numbers, rational function fields, cyclotomic
fields ...
Concepts for automatic mapping from one ring to another.
05.03.2003
Marc Conrad, University of Luton
15
Conclusions




The experiments with Java show that object oriented
programming deserves a closer look in the context of
mathematics.
Knowledge of the mechanism of overriding and dynamic
binding allows a straightforward implementation of
abstract mathematical structures.
Object oriented programming should be a main feature in
CAS (as user defined functions a couple of years ago).
Mathematical software should use object oriented
terminology instead of "reinventing the wheel".
05.03.2003
Marc Conrad, University of Luton
16
Maple/Mathematica and
Object Oriented Programming

Maple


Not designed to be object oriented. Maple 8.0
allows to link Maple with Java using MathML as
interface language The aim however is not to do
“object oriented” mathematics but to allow the
design of Java applets (MapleNet, Maplets).
Mathematica

05.03.2003
Not designed as an object oriented system. The
J/Link technology enables calling of Java classes
from Mathematica and vice versa.
Marc Conrad, University of Luton
17
Other Systems and Object Oriented
Programming

Axiom.


Although not explicitly designed as an Object
Oriented System it has many aspects of this. E.g.
a type hierarchy, generic functions, generic types.
Since September 2002 Axiom is open source.
MuPAD

05.03.2003
Has clearly object oriented aspects. Allows
Domains which are organised similar to a class
hierarchy. The user can add own domains. Not
related to Java or C++. Limited capabilities
compared to Maple/Mathematica.
Marc Conrad, University of Luton
18