kredel@unipas.fmi.uni-passau.de (Heinz Kredel) (05/09/91)
Archive-name: math/symbolic/mas/1991-05-02
Archive-directory: alice.fmi.uni-passau.de:/mas6/ [132.231.10.1]
Original-posting-by: kredel@unipas.fmi.uni-passau.de (Heinz Kredel)
Original-subject: MAS (Modula-2 Algebra System) Version 0.6
Reposted-by: emv@msen.com (Edward Vielmetti, MSEN)
MAS Modula-2 Algebra System
Computer Algebra Group
University of Passau, Germany
Version 0.60
Abstract
--------
MAS is an experimental computer algebra system combining imperative
programming facilities with algebraic specification capabilities for
design and study of algebraic algorithms. MAS views mathematics in the
sense of universal algebra and model theory and is in some parts
influenced by category theory. We give an overview of system design,
the current state of the MAS project and the actual distribution.
Major changes between release 0.30 and 0.60 are:
-------------
1. added language extensions for specification capabilities,
2. added a parser for the ALDES language and
possibility for interpretation of ALDES programs,
3. added a linear algebra package,
4. added an interface between the MAS language
and the distributive polynomial system,
5. improved symbol handling by hash tables
combined with balanced trees,
6. EMS support for IBM PC implementations.
The minor changes between release 0.30 and 0.60 are:
1. PRAGMA construct for the state definition of
the MAS executable program.
2. Overloading of MAS arithmetical operators
by generic function names.
3. Typed string constants in MAS expressions.
4. VAR parameters in MAS procedure declarations in
ALDES style.
5. Static scope analysis by the parser.
6. Explicit stack overflow check since not all compilers
handled stack overflow correctly.
Introduction
------------
Starting point for the development of MAS was the requirement for a
computer algebra system with an up to date language and design which
makes the existing ALDES / SAC-2 algorithm libraries available. At this
time there have been about 650 algorithms in ALDES / SAC-2 and in
addition I had 450 algorithms developed on top of ALDES / SAC-2. The
tension of reusing existing software in an interactive environment with
specification capabilities contributes most to the evolution of MAS.
The resulting view of the software has many similarities with the model
theoretic view of algebra. The abstract specification capabilities are
realized in a way that an interpretation in an example structure (a
model) can be denoted. This means that is is not only possible to
compute in term models modulo some congruence relation, but it is
moreover possible to exploit an fast interpretation in some optimized
(or just existing) piece of software.
Overview
--------
MAS is an experimental computer algebra system combining imperative
programming facilities with algebraic specification capabilities for
design and study of algebraic algorithms. The goal of the MAS system is
to provide:
* an interactive computer algebra system
* comprehensive algorithm libraries, including
the ALDES/SAC-2 system [Collins 82],
* a familiar program development system
with an efficient compiler,
* an algebraic specification component for
data structure and algorithm design
* algorithm documentation open to the users.
Key attributes of the MAS system are:
* portability (it is portable to a
computer during a student exercise `Praktikum'),
machine dependencies isolated in a small kernel,
* extendability (it is possible to add
and interface to external algorithm libraries),
open system architecture,
* transparent low level facilities:
storage management (garbage collection
is provided without user cooperation),
stable error handling (no system break down on
misspelled expressions and runtime exceptions),
input / output with streams (no changes are
required to existing libraries to redirect I/O).
* effectivity (critical parts can be compiled and
still be accessed interactively)
* expressiveness (possiblitity to specify
abstract algebraic concepts like rings or fields)
The goals and attributes have been achieved by the following main design
concepts:
MAS replaces the ALDES language [Loos 76] and the FORTRAN implementation
system of SAC-2 by the Modula-2 language [Wirth 85]. Modula-2 is well
suited for the development of large program libraries; the language is
powerful enough to implement all parts of a computer algebra system and
the Modula-2 compilers have easy to use program development
environments.
To provide an interactive calculation system a LISP interpreter is
implemented in Modula-2 with full access to the library modules. For
better usability a Modula-2 like imperative (interaction) language was
defined, including a type system and function overloading capabilities.
To increase expressiveness high-level specification language constructs
have been included together with conditional term rewriting
capabilities. They resemble facitilies known from algebraic
specification languages like ASL [Wirsing 86].
Further design issues are:
MAS views mathematics in the sense of universal algebra and model theory
and is in some parts influenced by category theory. In contrast to
other computer algebra systems (like Scratchpad II [Jenks 85]), the MAS
concept provides a clean seperation of computer science and mathematical
concepts. The MAS language and its interpreter has no knowledge of
mathematics and mathematical objects; however it is capable to describe
(specify) and implement mathematical objects and to use libraries of
implemented mathematical methods. Further the imperative programming,
the conditional rewriting and function overloading concepts are
seperated in a clean way.
MAS includes the capability to join specifications and to rename sorts
and operations during import of specifications. This allows both the
specification of abstract objects (rings, fields), concrete objects
(integers, rational numbers) and concrete objects in terms of abstract
objects (integers as a model of rings). Specifications can be
parameterized in the sense of lambda-abstraction.
The semantics of a specification can be described either by
implementations, axioms or models. The implementation part describes
(imperative) procedures and data representations.
The axioms part describes conditional rewrite rules which define a
reduction relation on the term algebra generated by the sorts and
operations of the specification. The semantics is therefor the class of
models of the term algebra modulo the (congruence) relation. Currently
there are no facilities to solve conditional equations.
The model part describes the association between abstract specifications
(like rings) and concrete specifications (like integers). The semantics
is the interpretation of the (abstract) function in the model.
Operations in models can be compiled functions, user defined imperative
functions or term rewrite rules. The function overloading capabilities
are realized by this concept. Dynamic abstract objects like finite
fields can be handled by a descriptor concept.
Evaluation of functional terms is as follows: If there is a model in
which the function has an interpretation and a condition on the
parameters is fulfilled, then the interpretation of the function in this
model is applied to the interpretation (values) of the arguments. If
there is an imperative procedure, then the procedure body is evaluated
in the procedure context. If the unification with the left hand side of
a rewrite rule is possible and the associated condition evaluates to
true, then the right hand side of the rewrite rule is evaluated.
Otherwise the functional term is left unchanged.
In contrast to functional programming languages (like SML [Appel 88])
which implement typed lambda calculus the types of operations are not
deduced from the program text but must be explicitly defined in the
specification of an operation, in a variable declaration or in a typed
string expression.
A weak point in the current MAS design is that the language is only
interpreted. This is actualy not a handicap in execution speed since
compiled libraries can be used, but in a too weak semantic analysis of
the specifications. This means that certain errors in the
specifications are only detected during actual evaluation of an
expression.
Achievements and Current State
------------------------------
The steps towards the MAS system have been:
* definition of a syntax transformation scheme between
ALDES and Modula-2;
development of a translator and translation of most of
the ALDES / SAC-2 libraries to Modula-2;
* development of a storage management system in Modula-2 with
automatic garbage collection in an uncooperative environment;
implementation of a input / output system in Modula-2
with streams;
* implementation of a LISP interpreter in Modula-2 with
access to the compiled procedures (using Modula-2 procedure
types and variables);
* definition of an imperative Modula-2 like interaction language;
* implementation of a parser for the interaction language and
corresponding modifications to the LISP interpreter;
* design of high-level language constructs for algebraic
specification and a type system with function overloading
capabilities;
modification of the language parser and the interpreter;
* design of specifications for relevant algebraic structures.
Steps 1 and 2 were subject to the restriction that the interface had to
be compatible with the existing ALDES / SAC-2 libraries. Steps 1 and 2
have been reported in [Kredel 88]. Reports on steps 3, 4, 5 and
progress reports on step 6 have been given in [Kredel 90]. A reasonable
state of step 6 has been reached during end of 1990. Step 7 is
currently under work.
Versions of the MAS system are running on Atari ST (TDI and SPC Modula-2
compilers), IBM PC/AT (M2SDS and Topspeed Modula-2 compilers) and
Commodore Amiga (M2AMIGA compiler).
The ALDES/SAC-2 libraries have been implemented including the Polynomial
Factorization System and the Real Root Isolation System. From the DIP
system the Buchberger Algorithm System and the Ideal Decomposition and
Ideal Real Root System have been implemented. Groebner Bases are also
available for non-commutative polynomial rings of solvable type. The
combination of the MAS programs with numerical Modula-2 libraries has
been tested. The mathematical libraries have been enlarged by a package
for linear algebra.
Some logic programming facilities have been incorporated by means of the
conditional rewriting capabilities of the algebraic specification
component. Further there is a parser for the ALDES language and the MAS
interpreter is now able to evaluate ALDES statements (although with low
performance). In the symbol table system the unbalanced symbol tree has
been repaced by a hash table with balanced symbol tree entries.
The current development concentrates on filling some gaps in the ALDES /
SAC-2 and DIP libraries, the design of suitable specifications for
relevant algebraic structures and completing the system documentation.
Availability
------------
MAS (0.3x and 06.x) is available on electronic networks (internet)
via anonymous ftp from:
alice.fmi.uni-passau.de = 123.231.10.1
or from the author.
Disk Contents / Distribution
----------------------------
MAS.EXE, MAS.PRG - execuable MAS program
MAS.INI - start up data set for MAS
\HELP - Modula-2 definition modules
\SPEC - Specifications
ED.EXE - mini editor
EDITOR.PRG - microEMACS
*.IN - input data sets for MAS
*.OUT - output data sets for MAS
MASTUT.ARC - MAS tutorial in LaTeX
MASDEF.ARC - MAS indexes in LaTeX
READ.ME - how to use and start MAS
RELNOTES.TXT - notes on the actual release of MAS
Installation: no special installation procedures are required,
just copy all MAS files into some directory and start it.
Start - Stop
------------
- start 'MAS.EXE' or 'MAS.PRG'
- banner 'MAS Version r.xx'
- system prompt 'MAS: '
- system answer 'ANS: '
- leave with 'EXIT.'
Acknowledgements
----------------
Due to limited space I apologize for only global thanks to all who made
contributions and influenced the project.
Copyrights: MAS: (c) 1989, 1990, 1991, by H. Kredel.
ALDES/SAC-2: (c) 1982, by G.E.Collins, R.Loos.
All Rights Reserved.
Permission is granted for unrestricted use and redistribution if and
only if the copyright notice is retained when a copy is made. There are
no known bugs, however I disclaim any usefulness and make no warranty on
the correctness of the Modula-2 Algebra System.
Passau, 4. April 1991, H. Kredel.
Bibliography
------------
[Appel 88] A. W. Appel, R. Milner, R. W. Harper, D. B. MacQueen,
"Standard ML Reference Manual (preliminary draft)",
University of Edinburgh, LFCS Report, 1988.
[Collins 82] G.E. Collins, R. Loos,
"ALDES/SAC-2 now available",
SIGSAM Bulletin 1982, and several reports distributed
with the ALDES/SAC-2 system.
[Jenks 85] R. D. Jenks et al.,
"Scratchpad II Programming Language Manual",
Computer Algebra Group, IBM, Yorktown Heights, NY, 1985.
[Kredel 88] H. Kredel,
"From SAC-2 to Modula-2",
Proc. ISSAC'88 Rome, LNCS 358, pp 447-455, Springer, 1989.
[Kredel 90] H. Kredel,
"MAS Modula-2 Algebra System",
Proc. DISCO 90 Capri, LNCS 429, pp 270-271, Springer, 1990.
[Loos 76] R. G. K. Loos.
"The Algorithm Description Language ALDES (Report)",
SIGSAM Bulletin 14/1, pp 15-39, 1976.
[Wirsing 86] M. Wirsing,
"Structured Algebraic Specifications:
A Kernel Language",
Theoretical Computer Science 42, pp 123-249,
Elsevier Science Publishers B.V. (North-Holland) (1986).
[Wirth 85] N. Wirth,
"Programming in Modula-2",
Springer, Berlin, Heidelberg, New York, 1985.
-- comp.archives file verification
alice.fmi.uni-passau.de
total 536
dr-xr-xr-x 2 ftp 22 512 Mai 06 22:17 srcst
-r--r--r-- 1 ftp 22 14282 Apr 08 11:04 masanno.txt
-r--r--r-- 1 ftp 22 652 Apr 04 11:37 READ_ME
dr-xr-xr-x 2 ftp 22 512 Mr 26 10:28 atari
dr-xr-xr-x 2 ftp 22 512 Mr 26 10:28 ibmpc
-r--r--r-- 1 ftp 22 152177 Mr 26 10:12 masdef.arc
-r--r--r-- 1 ftp 22 8598 Mr 26 10:07 masspec.arc
-r--r--r-- 1 ftp 22 152469 Mr 26 10:07 mashelp.arc
-r--r--r-- 1 ftp 22 189952 Mr 25 22:00 mastut.arc
found mas ok
alice.fmi.uni-passau.de:/mas6/