MAS

Modula–2 Algebra System Interactive Usage

Computer Algebra Group University of Passau

MAS Version 0.6^{1}

1Document revision January 25, 1992

Abstract

MAS is an experimental computer algebra system combining imperative programming facilities with algebraic specification capabilities for design and study of algebraic algorithms. This document describes the interactive usage of MAS, the MAS language, the specification component, basic arithmetic and polynomial system libraries.

Copyrights

The MAS system was developed using several public domain programs. So permission is granted for unrestricted use of MAS as long as the copyrights are preserved. The copyrights are:

MAS: \begin{matrix}c \\ ◯ \end{matrix}1989, 1990, 1991, by H. Kredel, University Passau.
ALDES / SAC–2: \begin{matrix}c \\ ◯ \end{matrix}1982, by G.E.Collins and R.Loos.

Remember: We make no warranty and disclaim any usefulness. Use this program at your own risk.

Preface

MAS (Modula–2 Algebra System) 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. MAS combines Modula–2 program development, a LISP interpreter with a Modula–2 like language and an algebraic specification component. MAS can be used interactively, but includes access to to the comprehensive ALDES/SAC–2 and DIP algebraic algorithm libraries. MAS can also be used as ordinary Modula–2 program library. Despite of its design it can directly access numerical Modula–2 libraries. The current implementations run on an Atari 1040ST / GEM–TOS and IBM–PC / MS–DOS (or compatible), further implementations are planned on Commodore Amiga / Amiga–DOS, IBM–370 / VM–CMS, Sun / Unix, and VAX / VMS. It is completely written in the programming language Modula–2 [Wirth 85a]. Major changes of the current version 0.6 of MAS are:

• added language extensions for specification capabilities,

• added a parser for the ALDES language and possibility for interpretation of ALDES programs,

• added a linear algebra package,

• added an interface between the MAS language and the distributive polynomial system,

• improved symbol handling by hash tables combined with balanced trees,

• EMS support for IBM PC implementations.

Organization

This document is a description of the front–end part of the system: the interpreter. It is intended as a manual for the MAS interactive part. The syntax of the MAS language together with informal semantics and examples is discussed. Further basic arithmetic and polynomial system data structures and libraries are discussed. A document for implementors is already available under the title ‘MAS Library description’. The definition modules and indexes are contained in a seperate document ‘MAS Specifications, Definition Modules, Indexes’. Some discussions are currently rather short but will be improved in later revisions of the document. The first two chapters are already self contained and can serve as a tutorial introduction into MAS. The later chapters are complete, but very condensed so you may need some knowledge of LISP, the ALDES / SAC–2 computer algebra system and Modula–2 in the more advanced chapters. The plan of this document is as follows: Chapter 1 gives a short introduction of MAS and shows how to use MAS for the first time. Chapter 2 gives an tutorial overview of MAS, and discusses several important aspects of MAS, such as arithmetic, help facilities, specifications and function overloading, talking LISP and handling errors. Chapter 3 describes the MAS language and chapter 4 describes the MAS specification component. Chapter 5 gives an introduction into list processing and algorithm complexity. In chapter 6 the basic arithmetic algorithms and in chapter 7 the polynomial systems are described. In Chapter 8 the parser for the ALDES language and the syntax of the ALDES language are presented. Chapter 9 summarizes system commands: display commands, pragmas and command line parameters. Chapter 10 provides some background information on the underlying LISP. Chapter 11 gives some information on the system components, on the internal structure, on implementation issues and on the configuration of MAS. The appendices contain notes on the distribution and the current release of MAS and an index of this document.

Acknowledgements

Many thanks to all who made contributions or influenced this project: R. Loos, G. E. Collins and co–workers for the ALDES / SAC–2 system; I. Giese, W. Kynast and H. Czytrek for discussions in the early stages of the MAS project; M. Pesch, B. Haible, V. Weispfenning and T. Becker for feedback during the later stages of the development of MAS. In the current version also contributions from students are incorporated:

• port to IBM PC, M2SDS by B. Deyle,

• port to IBM PC, Topspeed Modula–2 by H. Friebel,

• port to Atari ST, SPC by E. Reisinger,

• port to Amiga, M2Amiga by M. Rothmeier, • an ALDES parser by K. Rieger,

• a hash table symbol handling by T. Wollersberger,

• a linear algebra library by J. Müller.

The MAS system was first developed using the following hard– and software: Computer: Atari 1040 ST, (1 MB) 1986. Compiler: TDI: Modula–2/ST, Clifton, Bristol, UK, 1986. Editor: micro EMACS, by Daniel Lawrence, 1988. Shell: Guläm by Prabhaker Mateti at Case, 1988. If you find a bug in MAS, please let me know. Also any suggestions will be welcome. Most of the MAS system is available via anonymous ftp from internet address 132.231.10.1

= alice.fmi.uni-passau.de.

Passau, January 25, 1992. H. Kredel^{1}

1University of Passau, Innstraße 33, D-8390 Passau, FRG, Tel: (49,0) 851/ 509-315, E-mail: kredel @ unipas.fmi.uni-passau.de

Contents

1 Introduction 12 1.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Elementary Concepts 15 2.1 Edit–run–debug Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Elementary Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Specification Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Getting Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.1 HELP Command . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 System Browser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.3 Signatures, Generic Functions and Sorts . . . . . . . . . . . . . . . 23

2.5 Handling Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.6 Talking LISP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 The MAS Language 28

3.1 Lexical Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.1 Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.2 Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.3 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.4 Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.1.5 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.6 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.7 Blanks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Syntax Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.2 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.3 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.1 Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.2 Procedure Call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.3 Statement Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.4 BEGIN–END Statement . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.5 IF Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3.6 WHILE Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3.7 REPEAT Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.4 Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4.1 VAR Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4.2 PROCEDURE Declaration . . . . . . . . . . . . . . . . . . . . . . . 44

3.5 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.5.1 Stream Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.5.2 Operating System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4 Specification Component 51 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.2.1 Syntax Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3 Unit Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4 Specifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4.1 SORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4.2 IMPORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.4.3 SIGNATURE Declaration . . . . . . . . . . . . . . . . . . . . . . . 55 4.4.4 Example Specification . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.5 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.5.1 SORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.5.2 IMPORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.5.3 VAR Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.5.4 PROCEDURE Declaration . . . . . . . . . . . . . . . . . . . . . . . 58 4.5.5 Example Implementation . . . . . . . . . . . . . . . . . . . . . . . . 58

4.6 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.6.1 SORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6.2 IMPORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6.3 MAP Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6.4 Example Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.7 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.7.1 SORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.7.2 IMPORT Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.7.3 RULE Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.7.4 Example Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.8 EXPOSE Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.9 Operator Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.10 Expression Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5 List Processing 66 5.1 List Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2 List Destruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3 List Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.5 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.7 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.8 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6 Basic Arithmetic 76

6.1 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.2 Rational Number Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.3 Floating Point Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.3.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.3.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7 Polynomial Systems 101 7.1 Coefficient Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.2 Recursive Polynomial System . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.2.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.3 Dense Polynomial System . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.4 Distributive Polynomial System . . . . . . . . . . . . . . . . . . . . . . . . 110

7.4.1 Term Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.4.2 Description of Term Orders by Linear Forms . . . . . . . . . . . . . 114 7.4.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7.5 Interface to the MAS Language . . . . . . . . . . . . . . . . . . . . . . . . 124

7.6 Appendix: Optimization of the Term Order . . . . . . . . . . . . . . . . . 127

8 The ALDES Language 130

8.1 Lexical Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.1.1 Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.1.2 Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.1.3 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.1.4 Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.1.5 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.1.6 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.1.7 Blanks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

8.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

8.2.1 Syntax Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

9 System Commands 137 9.1 Information Display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9.2 Pragmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.3 Operating System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 9.4 Input / Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.5 Command Line Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 140

10 The LISP Interpreter 142

10.1 Functions and Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

10.1.1 What is Not Contained . . . . . . . . . . . . . . . . . . . . . . . . . 143 10.2 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

11 Internal Structure of MAS 145 11.1 System Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.2 Module Layout of MAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 11.3 Program Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 11.4 LISP to Modula–2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 148 11.5 Configuration Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 11.6 Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

A Distribution 152 A.1 Anonymous FTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 A.2 Distribution Disk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.3 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 CONTENTS 9

A.4 Release Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Bibliography 155 Index 159

List of Tables

3.1 Constants and Ranges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Transliteration Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 MAS Syntax Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Syntax Error Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Syntax Warning Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.1 Specification Syntax Diagram . . . . . . . . . . . . . . . . . . . . . . . . . 53

7.1 Computing Times for Different Term Orders . . . . . . . . . . . . . . . . . 129

8.1 ALDES Syntax Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 8.2 ALDES Syntax Error Messages . . . . . . . . . . . . . . . . . . . . . . . . 134 8.3 ALDES Syntax Warning Messages . . . . . . . . . . . . . . . . . . . . . . . 134

List of Figures

9.1 Generic Operators and Functions . . . . . . . . . . . . . . . . . . . . . . . 139 11.1 System Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.2 Module Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

Chapter 1

Introduction

MAS is a computer algebra system in contrast to symbol manipulation systems. The MAS data objects are not considered as symbolic expressions, but they are considered to be elements of algebraic structures. So working with MAS usually requires that you have to decide in which algebraic structure you want to compute. Data objects can then be converted from their external representation (character sequences) to their internal representation (lists over numbers). These internal objects can then be used as inputs to programs which are implementations of algebraic functions. In contrast, other symbol manipulation programs such as Derive [Rich et. al. 88], Reduce [Hearn 87], Maple [Char et. al. 86], Mathematica [Wolfram 88], or Macsyma [Pavelle et. al. 85] view their input as untyped expressions built from numbers, symbols, operators and functions. The user has then a wide variety of tools to manipulate expressions (like expanding expressions, collecting or extracting subexpressions or applying substitutions or rewrite rules to the expressions). The interpreter of the Scratchpad II [Jenks et. al. 84, Jenks et. al. 85] computer algebra system is further equipped with an algebraic ‘knowledge’ and tries to determine the algebraic domain to which the input expression belong. On the other hand in MAS an expression is evaluated and is normally not manipulated. Algebraic objects are constants for the interpreter and can only be modified using appropriate methods from the respective algebraic structures. The mathematical knowledge of MAS is only contained in the algorithm libraries (either Modula–2 programs or specification definitions).

1.1 Getting Started

In this section we give a first look on the usage of the MAS system. To start the program, select the directory containing the MAS program and data files.

       start:           MAS.PRG or MAS.TTP or MAS.EXE
       banner:          MAS Version r.xu
       system prompt:   MAS:
       system answer:   ANS:

       leave with:      EXIT.

When MAS is started, it first initializes all available storage for list processing. Then it reads the data set ‘mas.ini’ from the current directory. It next issues the following prompt:

       MAS:

Now MAS is waiting for a program to be typed in. The program has to be in a Modula–2 like syntax (see below). The parser reads the parts of the program: declarations and statements. A simple assignment like a:=1. suffices as program. From this program the parser generates a LISP S–expression which is then fed into the evaluator. The result is displayed after

       ANS:

Then the read-eval-print loop is repeated. Example 1:

       MAS: a:=2*3.   (* this is a one statement program *)
       ANS: 6.

By this one statement program 2*3 is evalauted and the result 6 is bound to the symbol (or variable) ‘a’. Comments are enclosed in (* and *). The next example shows the usage of the WHILE statement. Example 2:

       MAS: d:=0. i:=0.    (* two one statement programs *)
       ANS: 0
       ANS: 0
       MAS: WHILE i < 17 DO
                  i:=i+1; d:=d+i*i
                  END.
       ANS: 1785

First the symbol ‘d’ is bound to 0 and also the symbol ‘i’ is bound to 0. Then commes a WHILE–loop in Modula–2 style. In its body the squares of ‘i’are computed and summed to ‘d’. Observe that statements have values as in LISP. However constructions like d:=IF cond THEN ... END are syntactically invalid in the MAS language. It is possible to access compiled functions and procedures. However you must use the corresponding write procedures to display the object not as list. Example 3:

       MAS: p:=APPI().
       ANS: (2 (221327762 71487876 210828714))
       MAS: APWRIT(p).
       0.314159265358979323846E1
       ANS: ()

In this example APPI denotes a function from the arbitrary precision floating point library which returns the value of π in the actual precision (initially 20 decimal digits). The computed value in in internal lisp representation and to display the value in readable form the procedure APWRIT must be called. To find out which compiled procedures are accessible there is a ‘HELP’ command. With ‘HELP.’ you get a list of all available functions together with their signature. During the display screen scrolling can be stopped by pressing any key (in particular <CNTRL>-S will work), output can be resumed by again pressing any key (e.g. <CNTRL>-Q). If the specification support is loaded it is possible to declare variables and to use generic assignments. If further generic parse is enabled (with PRAGMA(GENPARSE)) then also generic expressions are possible. Example 4:

       MAS: VAR f: FLOAT.        (* declare FLOAT variable *)
       ANS: FLOAT.
       MAS: f:="1.0E99".
       ANS: "0.100000000000000000000E100"
       MAS: f:= "2.0": FLOAT * f - f.
       ANS: "0.100000000000000000000E100"

In this example MAS uses the type information of the variable ‘f’ to determine the correct conversion function from the string ”1.0E99” to the internal representation of floating point numbers. During the evaluation the data object is tagged, so that the output routine can call the correct printing function. If PRAGMA(GENPARSE) was executed, then the arithmetical operators (like * and - in line 5) are associated with generic functions (in this case with PROD and DIF). The constant 2.0 form the FLOAT structure can be entered in the form "2.0": FLOAT. The generic operations can also be used within algorithms. In this section we have seen that control statements can be entered directly from the keyboard, that compiled functions can be accessed and that variable declarations and generic expressions are available in MAS.

Elementary Concepts

In this section we will discuss some of the key features and concepts of MAS. 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. The main design concepts are: MAS replaces the ALDES language [Loos 76] and the FORTRAN implementation system of SAC–2 by the Modula–2 language [Wirth 85a]. 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. LISP was chosen because it seemed to be most flexible and well understood to provide a basis for an interactive system and experimenting with generic functions. Using Modula–2 procedure types, the compiled procedures are made accessible from the LISP interpreter. To add a new compiled procedure one has to compile an interface module coded in Modula–2 with the appropriate import lists and declaration procedures and then one re–links the MAS main program. This guarantees maximum efficiency of the developed algorithms. As mentioned above, the mathematical knowledge of MAS is only contained in the Modula–2 algorithm libraries. Thus the Modula–2 compiler with its linker serves as a knowledge acquisition system without requiring any further effort to setup knowledge– based computer algebra systems as suggested by [Calmet et. al. 87]. For better usability a Modula–2 like imperative (interaction) language was defined, including a type system and function overloading capabilities. The MAS parser generates LISP S–expressions, which are then evaluated by the LISP interpreter. 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]. 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. The type declaration concept equips the interpreter with the knowledge that some variables and objects have types. Applying generic functions to these typed variables or objects causes the interpreter to look for an executable function, which can work with the specific object types. The system design also assures high portability of the software. All storage and input/output management is handled by only two library modules MASSTOR and MAS-BIOS. They have been first implemented for an Atari 1040 computer running TOS and GEM and are also running on other computers. In the following sections we explain how to make efficient use of MAS: editing files, reading files, browsing definition modules. Further some basic arithmetic functions are explained and the error handling of MAS is discussed.

2.1 Edit–run–debug Cycle

In general you will not type every statement directly to the MAS terminal. It is much more convenient to use your favourable editor to prepare a sequence of statements for MAS. Then you can feed this data set into MAS, save some output and determine your next action. Although editors are computer and operating system dependent, any implementation of MAS should provide some similar statements as discussed now for the Atari implementation. On the Atari there are two ways to call an editor: EDIT("data-set-name") or via the operating system DOS("editor-name data-set-name"). After return from the editor the data set can be read in with IN("data-set-name"). Output can be saved in a file with

OUT("data-set-name") and then the file can be closed using SHUT("data-set-name").

To speedup this cycle and minimize typing you can use the following two procedures

       VAR what: STRING.
       PROCEDURE doit;
       BEGIN what:="data set name";
             EDIT(what) END doit.

       PROCEDURE run;
       IN(what) run.

So typing doit. will call the editor and after return typing run. will execute the file. You can also place several procedures like ‘doit’ in the startup file ‘MAS.INI’, so that they are ready to be used. run will then always execute the last edited file. The editor can also be used to browse the appropriate definition modules during editing. If the editor is programmable (like microEMACS) further improvements of this procedure are possible and are described in the section on ‘getting help’.

2.2 Elementary Arithmetic

As mentioned above, the interpreter only knows about atoms and lists, that means the arithmetic operators ‘+, −, ∗, /’ and relations ‘<, =, <=, >, >=’ are only valid with atoms as arguments. But this is not checked, and may lead to unpredictable results, so you are self responsible to supply the correct arguments to the compiled subroutines. In the next example we will discuss the computation of n factorial for different values of n. If you know that you need factorial(n) only for small values of n, such that factorial(n) < beta = 2^{29}, that is for n <= 12 you may write:

       MAS: PROCEDURE fac(n);
            VAR   d, i: ANY;
            BEGIN d:=1; i:=n;
                  WHILE i > 1 DO
                        d:=d*i; i:=i-1
                        END;
                  RETURN(d)
                  END fac;
            fac(6).
       ANS: 720

For bigger values of n you must use arbitrary precision integers as provided with the ALDES/SAC-2 subroutine libraries. Here we use IPROD for multiplication (∗) and IWRITE to display the result, otherwise the internal SAC-2 list representation of arbitrary precision integers is displayed.

       MAS: PROCEDURE fac(n);
            VAR   d, i: ANY;
            BEGIN d:=1; i:=n;
                  WHILE i > 1 DO
                        d:=IPROD(d,i); i:=i-1
                        END;
                  RETURN(d)

                  END fac;
            j:=fac(50).
       ANS: (0 373030912 375187572 439570590 300896040
               154982421 452089979 2365)
       MAS: IWRITE(j).
            30414093201713378043612608166064768844377641
            568960512000000000000

Note that since i contains only small integers, the built-in operations can be used. The computing time for ‘fac(50)’ is 4 seconds on an Atari 1040 ST and 2 seconds are needed to print the result. Question: how are the arbitrary precision integers internally represented if you know that 2^{29} is represented by the list (0, 1) and −2^{29} by (0, −1). It is also possible to use recursion as with LISP or Modula–2:

       PROCEDURE fac(n);
       IF n <= 1 THEN RETURN(1)
                 ELSE RETURN(IPROD(n,fac(n-1))) END fac.

Now let’s try a more difficult example: compute 50 digits of e using arbitrary precision rational numbers. The function ‘Exp’ takes x and the desired precision eps as input parameter. It computes the taylor series of the exponential function: ∑_{i=1,...} \frac{x^{i}}{fac(i)}. The summation runs until

\frac{x^{i}}{fac(i)} < \frac{eps}{2}, that is the rest is smaller than the desired precision. Integers are converted to rational numbers by the function ‘RNINT’ or ‘RNRED’. ‘RNPROD’, ‘RNSUM’, ‘RNABS’ and ‘RNCOMP’ denote the product, sum, absolute value and comparison of rational numbers.

       dig:=50.
       Eps:=RNRED(1,IEXP(10,dig)).
       PROCEDURE Exp(x,eps);
       (*Exponential function. eps is the
       desired precision. *)
       VAR   s, xp, i, y, p: ANY;
       BEGIN
       (*1*) y:=RNINT(1); s:=RNINT(1); i:=0;
             p:=RNPROD(eps,RNRED(1,2));
       (*2*) REPEAT i:=i+1; xp:=RNRED(1,i);
                    y:=RNPROD(y,x); y:=RNPROD(y,xp);
                    s:=RNSUM(s,y)
                    UNTIL RNCOMP(RNABS(y),p) <= 0;
             RETURN(s)
       (*9*) END Exp.

The results of the computation can be displayed by the functions ‘RNDWR’ and ‘RN-WRIT’. RNWRIT writes out a rational number as ‘nominator/denominator’ and RNDWR writes a rational number as decimal number with specified number of digits after the decimal point.

       one:=RNINT(1).
       e:=Exp(one,Eps).
       BEGIN CLOUT("AbsErr = "); RNDWR(Eps,dig); BLINES(0) END.
       BEGIN CLOUT("Result = "); RNDWR(e,dig); BLINES(0) END.
       BEGIN CLOUT("Result = "); RNWRIT(e); BLINES(0) END.

The following output is produced:

       {0 sec} ANS: (1 1)
       {20 sec} ANS: ((119769761 450433631 444044040 360650700
                      406458113 17125896) (0338539520 159342123
                      356614372 176392732 6300265))
       AbsErr = 0.000000000000000000000000000000000
                  00000000000000001
       Result = 2.718281828459045235360287471352662
                  49775724709369996-
       Result = 76384051975228859737656454938414688
                9815927382313633/281001223550575979
                708628521248902313987276800000000

The computing time for ‘Exp(1)’ is 20 seconds on an Atari 1040 ST and 4 seconds are needed to print the result with ‘RNDWR’.

2.3 Specification Component

As already mentioned 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 et. al. 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 λ abstraction. The specification language constructs are discussed in detail in chapter 4. In this overview we will just describe the advantages in the interactive usage which are gained when using the specification component. In this section we will only discuss some features of the interactive use of the specification component by means of the following example:

        VAR r, s: RAT.             ANS: RAT().
        r:="2222222222.777777777777777".
        ANS: "2222222222777777777777777/1000000000000000".
        s:=r/r.                    ANS: "1".
        s:=r^0 + s - "1": RAT.     ANS: "1".

The first line declares the variables r and s to be of type RAT, that is to be rational numbers. The second line is a so called generic assignment. Depending on the type of r the character string on the right hand side is read (or converted to internal form). Internally an object with type, value and descriptor information is created. This information is then used by the generic write function WRITE(RAT) for displaying the result in the next line. The fourth line shows the computation of r/r. According to the type information of r the corresponding generic function is determined. Then the interpretation of the generic function in the rational numbers is determined and executed. Finally the information on the output parameters is used to create a new typed object. This object is then bound to the variable s and finally it is displayed. The last line shows the computation of a more complex expression r^0 + s - "1": RAT. The term "1": RAT denotes a constant from the rational numbers, namely 1. The contents of the character string are read by the generic function READ(RAT) and a new typed object is created. The expression r^0 is computed by an abstract function (namely EXP) of the abstract RING implementation. We have seen, that the usage of the specification component is easy when the specification libraries are available. However a detailed explanation of the complete truth is somewhat complex and cannot be discussed here.

2.4 Getting Help

One problem in using MAS is that information is required on what functions are available. Further the specifications of the functions are often required. MAS provides several help facilities which are discussed in this section.

2.4.1 HELP Command

There is a HELP command showing all accessible compiled functions, all interpreter functions and all signatures, a EXTPROCS command showing accessible external compiled functions, an SIGS command showing defined signatures of functions, a VARS command which displays defined variables, a SORTS command which displays defined sorts, a GE-NERICS command listing all generic functions, a LISTENV command to display values of variables, and a system browse facility for Modula–2 definition modules. Use the HELP command to display a list of all compiled functions accessible from the interpreter. The HELP command output is like the following:

List of all functions and procedures:
SIGNATURE add(nat nat): nat
GENERIC   add
SIGNATURE and(bool bool): bool
GENERIC   and
PROCEDURE arith()
SIGNATURE Adefault(): atom
...
FUNCTION  RNABS(LIST): LIST
FUNCTION  RNCOMP(LIST,LIST): LIST
FUNCTION  RNDEN(LIST): LIST
SIGNATURE RNDIF(RAT RAT): RAT
FUNCTION  RNDIF(LIST,LIST): LIST
SIGNATURE RNDRD(RAT): RAT
FUNCTION  RNDRD(): LIST
...
SIGNATURE ZERO(INT): INT
GENERIC   ZERO
145 signatures,
75 interpreter procedures,
188 compiled functions,
42 compiled procedures
accessible.

From this list you can deduce the name of a function and its ‘arity’, that is the number of input or output parameters. For example the function named ‘RNCOMP’ has two input parameters, or ‘ZERO’ is a generic function which has an interpretation in the integers ‘INT’. For the specification of these functions you must refer to the respective ALDES / SAC–2 or MAS documentation or to the corresponding Modula–2 definition modules.

2.4.2 System Browser

For better online help it would be nice if the Modula–2 program development system has some browser facilities as in the Smalltalk–80 system with its class hierarchy browser [Goldberg 81]. We have added macros and data sets for the microEMACS editor to mimic some system browsing facilities. Therefore if you use the microEMACS editor, you can browse a system file containing a procedure to module cross reference. When pressing the function key ‘F3’, an editor window is opened with the following contents:

Procedure to module cross-reference:
saci.def 10:     AADV(L: LIST; VAR AL,LP: LIST);
sacsym.def 18:   ACOMP(A,B: LIST): LIST;
sacsym.def 23:   ACOMP1(A,B: LIST): LIST;
masstor.def 44:  ADV(L: LIST; VAR a, LP: LIST);
saclist.def 10:  ADV2(L: LIST; VAR AL,BL,LP: LIST);
saclist.def 15:  ADV3(L: LIST; VAR AL1,AL2,AL3,LP: LIST);
saclist.def 20:  ADV4(L: LIST; VAR AL1,AL2,AL3,AL4,LP: LIST);
sacanf.def 10:   AFDIF(AL,BL: LIST): LIST;
sacanf.def 15:   AFINV(M,AL: LIST): LIST;
sacanf.def 21:   AFNEG(AL: LIST): LIST;
sacanf.def 26:   AFPROD(M,AL,BL: LIST): LIST;
sacanf.def 32:   AFQ(M,AL,BL: LIST): LIST;
sacanf.def 38:   AFSIGN(M,I,AL: LIST): LIST;
sacanf.def 44:   AFSUM(AL,BL: LIST): LIST;
masapf.def 67:   APABS(A: LIST): LIST;
masapf.def 73:   APCMPR(A,B: LIST): LIST;
masapf.def 12:   APCOMP(ML,EL: LIST): LIST;
masapf.def 103:  APDIFF(A,B: LIST): LIST;
masapf.def 115:  APEXP(A,NL: LIST): LIST;
masapf.def 23:   APEXPT(A: LIST): LIST;
masapf.def 38:   APFINT(N: LIST): LIST;
masapf.def 121:  APFRN(A: LIST): LIST;
...

The three columns have the following meaning: 1) name of the definition module containing the procedure, 2) the line number of the procedure within the definition module, 3) the procedure header with formal parameter declarations.

From the variable names it is sometimes possible to remember the meaning of the variables. If this information is not sufficient the corresponding definition module can be browsed. Place the cursor in the line with the procedure you are interested in and press function key ‘F4’. Then the system browser window is replaced by a window containing the corresponding definition module. The cursor is moved to the comment of the function.

...
PROCEDURE APSPRE(N: LIST);
(*Arbitrary precision floating point set precision.
N is the desired precision of the floating point numbers. *)
PROCEDURE APFINT(N: LIST): LIST;
(*Arbitrary precision floating point from integer.
The integer N is converted to an arbitrary precision
floating point number. *)
...

So browsing the definition modules you can determine which programs you want to call. Then using the HELP function you can determine if the program is accessible from the interpreter.

2.4.3 Signatures, Generic Functions and Sorts

The signature shows more verbose and mnemonic names of the data types of the formal parameters of the procedures. Signature declarations for the most often used procedures are contained in separate files and can be loaded upon request (or automatically during startup). This information can then be displayed using the SIGS command. Generic functions are defined in an abstract structure and have an interpretation in some model. The information which interpretations are available for a generic function can be displayed using the GENERICS command. The specification declarations are discussed in more detail in chapter 4.

List of all signatures:
SIGNATURE add(nat nat): nat.
SIGNATURE and(bool bool): bool.
SIGNATURE Adefault(): atom.
SIGNATURE ADD(atom atom): atom.
SIGNATURE ADV(list object list).
SIGNATURE Aone(): atom.
SIGNATURE APDIF(FLOAT FLOAT): FLOAT.
SIGNATURE APFINT(INT): FLOAT.
...
SIGNATURE DIRPPR(dirp dirp): dirp.

SIGNATURE DIRPSM(dirp dirp): dirp.
SIGNATURE equal(nat nat): bool.
SIGNATURE equival(bool bool): bool.
SIGNATURE EQUAL(object object): atom.
...
SIGNATURE TRUE(): bool.
SIGNATURE WRITE(INT).
SIGNATURE ZERO(INT): INT.
145 signatures.

For example ‘and’ is a function (actually a rewrite rule) taking two elements of an Boolean ring (‘bool’) as input and returns a Boolean element. ‘EQUAL’, tests two objects if they are the same sequences of atoms and returns 0 or 1. The available interpretations for the ‘EXP’, ‘PROD’ and ‘equal’ functions could look as follows:

EXP:
MAP (ipol atom) -> IPEXP(DESC, VAL, VAL).
MAP (dirp dirp) -> DIRPEX(VAL, VAL).
PROCEDURE EXP(X, n);
   BEGIN
   VAR x: LIST(ring, ());
   VAR i: LIST(atom, ());
   IF (n <= 0) THEN x:=ONE(X); RETURN(x) END;
   i:=n; x:=X;
   WHILE (i > 1) DO i:=(i-1);
         x:=PROD(x, X) END;
   RETURN(x) END EXP.
...
PROD:
MAP (atom atom) -> MUL(VAL, VAL).
MAP (INT INT) -> IPROD(VAL, VAL).
MAP (nat nat) -> prod(VAL, VAL).
MAP (ipol ipol) -> IPPROD(DESC, VAL, VAL) WHEN EQ(DESC, DESC).
MAP (dirp dirp) -> DIRPPR(VAL, VAL).
MAP (RAT RAT) -> RNPROD(VAL, VAL).
MAP (MI MI) -> MIPROD(DESC, VAL, VAL) WHEN EQ(DESC, DESC).
MAP (FLOAT FLOAT) -> APPROD(VAL, VAL).
...
equal:
RULE equal(X, X) => TRUE().
RULE equal(succ(X), null()) => FALSE().
RULE equal(null(), succ(X)) => FALSE().
RULE equal(succ(null()), null()) => FALSE().

       RULE equal(succ(X), succ(Y)) => equal(X, Y).
       ...
       66 generic items.

A list of defined sorts can be obtained by the ‘SORTS’ command. The output may look as follows:

       List of all sorts:
       ag, atom, bool, dc, diip, dip, dirp, elem, field,
       fm, func, FLOAT, gbring, ipol, INT, list, melem,
       mod, MI, name, nat, nint, obj, object, pair, pol,
       rep, ring, RAT
       29 sorts.

2.5 Handling Errors

There is a wide variety of sources for errors: If the parser detects any syntax errors he tries to skip invalid program parts, at least until he finds a period ( = end of program mark ) in the input source. Then he returns a quoted expression of what he was able to generate so far. So only syntactically correct programs become evaluated. Errors during evaluation are reported, but execution can usually be continued if the errors are not too severe. Errors occurring at runtime in compiled code are also reported. This includes errors trapped by the processor (p.e. division by zero). Whether execution is continued depends on the severity of the error. Such a case may look like:

       5 Division by Zero
       ** fatal error: processor interrupt
       (a)bort, (b)reak, (c)ontinue (d)ebug or <ENTER> ? <ENTER>
       Trying to restart processor ...
       MAS:

In general you should hit <ENTER> or <RETURN> and the system will take the appropriate action:

error: continue, that means take some corrective action and try to continue

fatal error: break, that means return to the top level command loop

confusion: abort, that means execute processor HALT instruction You should not respond with a ‘softer’ reaction than the system would do unless you know what you are doing. But you can freely break to the top level command loop or abort the run completely. The error handler executes the command loop as a coroutine to the main MAS program. It further installs itself into the error handler provided by the Modula–2 runtime support. By these mechanisms the error handler can catch runtime errors and most software errors. However as with any LISP system incorrect input data may cause infinite loops, which cannot be handled. Only if MAS is still producing output you may press the ESC key, which will cause a fatal error. In other cases you must rely on the reset button (or some software monitors providing hotkeys). As you may have noticed in the above example, there is also a debug option. Typing ‘d’ will take you to the command loop of a debug processor. It is usually a restricted form of the main MAS command loop. The commands entered must be in LISP syntax to emphasize its role as emergency aid. New errors produced during debugging count higher and may very quickly lead to total program abort. Beside these considerations you can use almost all LISP functions, especially you can list variable contents or modify variables. Finally typing ‘EXIT’ takes you back to the error prompt.

2.6 Talking LISP

Not all LISP constructs have an equivalent in the MAS language, e.g. the ‘DM’ define macro is not available in the MAS language. So it can be necessary to switch to LISP by calling the PRAGMA(LISP) procedure which switches the parser to LISP syntax. To return to Modula style input you must use the (PRAGMA MODULA) procedure in LISP syntax to switch the MAS parser back on.

       MAS:  PRAGMA(LISP).         (* switch to LISP *)
       ANS:  ()
       LISP: (SETQ a 5)            (* use LISP syntax now *)
       ANS: 5
       LISP: (PRAGMA MODULA)              (* switch to MAS *)
       ANS: ()

A macro example for those who miss a FOR–statement:

      PRAGMA(LISP).
      (DM FOR (X)
          (LIST (QUOTE PROGN)
                (CAR  (CDR X))
                (LIST (QUOTE WHILE)
                      (CAR (CDR (CDR X)))
                      (LIST (QUOTE PROGN)
                           (CAR (CDR (CDR (CDR (CDR X)))))

                           (CAR (CDR (CDR (CDR X))))
                           ) ) ) )
      (PRAGMA MODULA)
      a:=0.
      FOR( SETQ(i,0), LEQ(i,10), SETQ(i,i+1), SETQ(a,a+i*i) ).
      ANS: 11

The syntax is similar to the syntax of the FOR–statement in C. Only the executed statement must be included in the parameter list of the FOR macro:

      FOR(init,cond,step,stat)  ==  (FOR init cond step stat)

The semantics of the FOR macro is defined by the following WHILE statement:

      init; WHILE cond DO stat; step END  ==
      (PROGN init (WHILE cond (PROGN stat step)))

The MAS language (like Modula–2) does not allow assignments as expressions, so all parameters of the FOR macro must be calls of the SETQ function or expressions. In C the FOR statement would be:

      FOR( i:=0, i <= 10, i:=i+1) a:=a+i*i

The evaluation can be traced using the TRACE procedure which turns the trace flag in the evaluator ON and OFF.

The MAS Language

This chapter contains the MAS language description. Besides the lexical and syntactical constructs it gives information on conventions, program interpretation and input / output facilities. The specification component is discussed seperately in chapter 4. It does not contain a description of the algebraic data structures and functions. The MAS language is only a ’cover’ for the MAS LISP. The language parser can be switched of and programs in pure LISP syntax can be entered as well. Moreover some MAS facilities are only accessible in LISP mode. Therefore also some LISP constructs are discussed in this chapter. The reader not interested in them may skip such parts during

a first reading. Such parts are indicated by small letter type style.

The initial language definition was the PL/0 language as described in N. Wirth’s book ”Compilerbau” [Wirth 85b]. This definition was extended to allow procedures with parameters and several new declarations where provided. Some polishing was done to allow the interactive use of the parser, e.g. empty programs are accepted. In the following sections we discuss first the lexical conventions and then the language syntax.

3.1 Lexical Conventions

The ’atomic’ constituents of the language are characters and tokens (character sequences with special meaning).

3.1.1 Character Set

The character set of MAS is a subset of the ASCII character set. It consists of the

 digits 0123456789
 letters aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
 others .,=+-*/$()␣!"#%&':;<>?@[\]^_`{}|~

The number of characters is denoted by χ (= 95 here).

3.1.2 Tokens

Lexical tokens of the language are:

     #  <  >  =  <=  >=  <>
     +  -  *  /  %
     (  )  ,  .  ;  :
     -> => :=
     keyword  number  identifier
     string  comment

Characters not contained in this list of tokens may only appear in strings and comments. The keywords are:

NOT, AND, OR,

IF, THEN, ELSE, END,

WHILE, DO, REPEAT, UNTIL, PROCEDURE, BEGIN, EXPOSE, SPECIFICATION, IMPLEMENTATION, MODEL, AXIOMS, SORT, VAR, IMPORT, SIGNATURE, MAP, RULE, WHEN.

The meanings of most of the tokens and keywords should be ’as expected’ and are discussed later. At this place we will only say some words on numbers, identifiers, strings and comments.

3.1.3 Numbers

Numbers may be only so called β–integers. The set of β–integers is defined as:

B = {x ∈ Z| − β < x < β},

where Z denotes the set of integral numbers.

The magnitude of β depends on the implementation of MAS on the actual computer. Precisely β is defined as a power of 2 such that:

χ < β and 4β ≤ γ,

where χ denotes the number of characters and γ is the least number such that for all, representable integral numbers y: |y| ≤ γ. On 32 bit computers γ = 2^{31} (32 minus one sign bit). Some basic constants and ranges are summarized in table 3.1.3.

Commonly β = 2^{29} = 536870912. β–integers are also called atoms. Other kinds of numbers such as floating point numbers, arbitrary precision integral numbers, rational numbers etc. are provided by library modules. These modules also supply read / parse and write / pretty print routines for the respective data types.

Name  Definition  Value
γ  integer size  2^{31} = 2147483648
β  4β ≤ γ  2^{29} = 536870912
γ–integer  {n ∈ Z | −γ < n < γ}
β–integer  {n ∈ Z | −β < n < β}
ν number of cells run time dependent
atoms  β–integers
pointers {n ∈ Z | β ≤ n ≤ β + (8ν)}
empty list  β
SIL  β
NIL  β

Table 3.1: Constants and Ranges

3.1.4 Identifiers

Identifiers are used as names of variables and names of procedures. The character sequence of an identifier must start with a letter and may be followed by digits and letters. Identifiers are case sensitive, that means upper case and lower case letters are distinct. The length of identifiers is restricted by the requirement that they must fit on one input line. Example: NIL, p123, AL9, XSH, AlongName.

Naming Conventions

Identifier names from the ALDES / SAC–2 system follow the so called ’Implementation ALDES’ naming scheme. However in comments we have already introduced upper case and lower case letters according to the ’Publication ALDES’ naming scheme. So it is useful to know the transliteration between both conventions. The transliterations are summarized in table 3.1.4. Several ornaments are transliterated in clockwise order.

Publication ALDES Implementation ALDES Meaning
a, b  AL, BL  lower case
A′, B′  AP, BP  prime
A^{∗}, B^{∗}  AS, BS  star
Ā, B̄  AB, BB  bar
Â, B̂  AH, BH  hat
A_{0}, B_{1}  A0, B1  subscript
ā′_{0}  ALBP0  clockwise

Table 3.2: Transliteration Scheme Procedure and variable names from the ALDES / SAC–2 system are at most 6 characters long and follow certain further conventions. The first letters identify the data structure and the following letters are choosen according to the meaning of the identifier. Example:

IPROD Integer Product

MPPROD Modular Polynomial Product

DIRPPR Distributive Rational Polynomial Product

3.1.5 Strings

Character sequences enclosed in double or single quotes are called strings. Within the quotes any character from the character set may appear. Quotes itself can be part of a string, if they are written twice. Example:

     "this is a string" denotes the string this is a string,

"'" denotes the string ', '"' denotes the string ", "x'7""'" denotes the string x'7"'

Strings are internally represented as lists of numbers (β–integers). So all list operations are applicable to strings, like concatenating, reversing.

3.1.6 Comments

Comments are sequences of characters enclosed in (* and *). Comments may be nested, that means the comment character sequence may contain pairs of (*, *). Comments can appear everywhere except in other tokens.

3.1.7 Blanks

Blanks can appear everywhere except in numbers, identifiers, keywords or two letter tokens. Blanks must be used in some cases to separate keywords. So ENDEND would mean the identifier ENDEND and not two END keywords. Characters in input lines which do not belong to the MAS character set are converted to blanks. ASCII characters like CR (return), LF (line–feed), EOL (end–of–line) are ignored during input form data sets.

3.2 Syntax

In this section we discuss the MAS language syntax and the meaning of the language constructs. First we give the complete syntax diagram and the list of syntax errors. Then we will concentrate the description on the procedural aspects of the MAS language. The MAS type system and generic function support will be discussed later in a separate section.

3.2.1 Syntax Diagram

The syntax definition is given in extended BNF notation. That means name denotes syntactic entities, {} denotes (possibly empty) sequences, () denotes required entities, | denotes case selection and [] denotes optional cases. Terminal symbols are enclosed in double quotes and productions are denoted by =. The syntax diagram is listed in table 3.2.1. Observe, that a program is a (possibly empty) sequence of declarations, followed by a (possibly empty) statement followed by a period. A statement can be an assignment, a procedure call or a IF–, WHILE–, REPEAT– or BEGIN–statement. Declarations are VAR and PROCEDURE. The syntax of the language constructs for specifications is discussed in chapter 4. The semantics of the statements are discussed next, but let us first mention the syntax errors and syntax warnings detected by the parser (see tables 3.2.1 and 3.5). If a syntax error is detected one of the error messages is displayed followed by the actual input line where the last character read is underscored. However this last character is one character and one lexical token to far. That means the syntax error is caused by one token behind. Error repair is limited to skipping tokens until something meaningful is found. In case syntax errors are detected, the execution of the program is totally suppressed, that means no executable code is generated. If a syntax warning is given execution proceeds.

3.2.2 Expressions

Expressions are built from numbers, strings, identifiers and function calls. Mathematical operators defined in the MAS language are only valid on numbers (β–integers), variables having a number as value or function calls with a number as return value or on generic items (defined in chapter 4. Variables are bound to values by means of the assignment statement, which is discussed later. So expressions are sums or differences of terms:

       expression = ["+"|"-"] term {("+"|"-") term}

The operators + and - correspond to the LISP functions ADD and SUB or to the generic functions SUM, NEG and DIF. Terms are themselves products, quotients or remainders of powers:

program      = block"."
block        = { "VAR" identlist  ":" ident [string] ";"
               | "PROCEDURE" ident ["( "[identlist]
                                  [";" "VAR" identlist] ")"]
                            [":" ident]";" block ident ";"
               }
               statement
statement    = [ident ":="expression |
               ident [ "(" [actualparms] ")" ] |
               "RETURN" [ "(" [ expression ] ")" ]
               "BEGIN" statementseq "END" |
               "IF" condition "THEN" statementseq
                            ["ELSE" statementseq] "END" |
               "WHILE" condition "DO" statementseq "END" |
               "REPEAT" statementseq "UNTIL" condition ]
identlist     = ident {"," ident}
actualparms  = expression {"," expression}
statementseq = statement {";" statement}
condition    = "NOT" condition |
               "(" condition ")" ("AND"|"OR") "(" condition ")"
               expression ("="|"#"|"<"|"<="|">"|">=") expression
expression   = ["+"|"-"] term {("+"|"-") term}
term         = power {("*"|"/"|"%") power}
power        = factor [ ("^"|"**") number ]
factor       = ident ["("[actualparms]")"] |
               number | string [ ":" typeexpr ] |
               "(" expression ")"
string       = ('"' {character} '"' | "'" {character} "'")
ident        = letter {letter|digit}
number       = digit {digit}

Table 3.3: MAS Syntax Diagram

1 = expected
2 type declaration expected
4 identifier expected
5 ; or , expected
6 expression expected
7 ) expected
8 factor expected
9 . expected
10 assignment expected
13 := or ( expected
14 statement expected
15 : expected
16 THEN expected
17 ; or END expected
18 DO expected
20 relation expected
21 , or ) expected
22 -> expected
23 ( or identifier expected
24 ( expected
25 condition expected
26 number expected
27 , or ) or ; expected
28 ; expected
29 END or ; expected
30 , or ] expected
31 / expected
32 == expected
33 END or ; or BEGIN expected

Table 3.4: Syntax Error Messages

1 identifier expected
2 algorithm name expected

Table 3.5: Syntax Warning Messages

       term = power {("*"|"/"|"%") power}

The operators *, / and % correspond to the LISP functions MUL, QUOT and REM or to the generic functions PROD and Q. Note: From the syntax definition follows, that ’*’, ’/’ and ’%’ have precedence over ’+’ and ’-’. Powers are factors with an optional number as exponent.

       power = factor [ ("^"|"**") number ]

The operators + and - correspond to the LISP function POW or to the generic function

EXP.

Factors are identifiers, function calls, numbers, strings or expressions enclosed in parenthesis.

       factor = ident ["("[actualparms]")"] |
                number |
                string [ ":" typeexpr ] |
                "(" expression ")"

Strings can be accompanied by type information. This is discussed in chapter 4. Function calls can be supplied by actual parameters which are sequences of expressions:

       actualparms = expression {"," expression}

Note, that function calls are distinguished from variables (identifiers) only by syntax. Function names must be specified with parenthesis, even if no arguments are supplied. Names without parenthesis are considered to be variable names. Example:

name = variable,

name() = function call without argument, name(1) = function call with argument ’1’, name1(name2) = function call with variable as argument.

S–expressions

We include some information on LISP. This may be skipped during a first reading.

The main LISP language construct is the so called S–expression or symbolic expression. S– expressions are lists of objects, where the first object evaluates to a function symbol. For example the S–expression corresponding to the MAS expression 2+3 is the list (ADD 2 3). The translation scheme between variables and functions in MAS and in LISP is the following:

       MAS expression          S-expression
       name                    name
       name()                  (name)
       name(1)                 (name 1)
       name1(name2)            (name1 name2)

3.2.3 Conditions

Two expressions combined by an relational operator are a condition. Further two conditions can be combined by AND or OR, or a condition can be negated by NOT:

 condition = "NOT" condition |
             "(" condition ")" ("AND"|"OR") "(" condition ")" |
             expression ("="|"#"|"<>"|"<"|"<="|">"|">=") expression

The hash character (#) denotes ’not equal’. The LISP functions corresponding to the relational operators (in the same sequence as above are): EQ, NE, NE, LT, LEQ, GT and GEQ. Conditions evaluate to true or false depending on the expressions and the relational operators. How are true and false defined ? The are at least two possibilities:

1. LISP like:

In LISP systems usually false is defined to be NIL, and every thing which is not NIL is considered to be true. There is additionally a variable T to denote true.

2. ALDES / SAC–2 like: false is defined to be 0 (zero) and true is defined to be 1 (one). In the implementation of ALDES it is however also assumed, that everything ≠ 0 is considered to be true.

In MAS LISP we have implemented the first variant. But the ALDES / SAC–2 boolean routines return 0 or 1, so some care is needed to obtain the right result from the evaluation of the condition. However the syntax of the MAS language does not allow a function call as condition. So one is forced to write a condition with relational operator. Then one can decide to compare the function value against 0 or NIL or what else.

3.3 Statements

Statements are assignment, procedure call, return, begin, if, while and repeat:

       statement = [ assignment | procedurecall |
                     beginend | return |
                     if | while | repeat ]

Observe that a statement can be empty.

3.3.1 Assignment

The assignment statement has the following syntax:

3.3. STATEMENTS 37

       ident ":=" expression

The expression is evaluated and the result is bound to the variable named ’ident’. It is not required to declare variables before they are used in an assignment statement. However variables with type information must be defined with a VAR statement. Example:

     x:=4*7+3-29*5. evaluates to -114.

The corresponding S–expression is:

      (ASSIGN x (SUB (ADD (MUL 4 7) 3) (MUL 29 5)))

where ASSIGN denotes the LISP assignment function. In this case ASSIGN is equivalent to the LISP SETQ function which might be more familiar.

     y:=x*x. evaluates to 12996.

The corresponding S–expression is:

      (ASSIGN y (MUL x x))

3.3.2 Procedure Call

A procedure call has the following syntax:

       ident [ "(" [actualparms] ")" ]

The actual parameters can be expressions as described in the section on MAS expressions. If no parameters are required, then the parenthesis can be omitted. Example:

ADD(1,3). evaluates to 4.

The corresponding S–expression is:

      (ADD 1 3)

Contrary to other LISP systems, but closer to Modula–2 syntax, identifiers as statements are supposed to be procedure calls and not variable names. Schematically we have:

       MAS statement           S-expression
       name.                   (name)
       name().                 (name)
       name(2).                (name 2)

By this translation scheme we obtain several equivalent formulations of MAS statements. For example the S–expression

       (ASSIGN x (ADD 1 3))

is generated from any of the following MAS statements:

       ASSIGN(x,ADD(1,3)).
       x:=ADD(1,3).
       x:=1+3.

So all 3 statements are equivalent.

Further examples:

     x:=IEXP(2,100). evaluates to (0 0 0 8192).

The function IEXP stands for integer exponentiation and delivers the internal representation of 2^{100}. Then x is bound to the list (0 0 0 8192).

IWRITE(x). evaluates to () and as a side effect produces 12...376.

This statement is a procedure call. First x is evaluated to the value to which it is bound (0 0 0 8192). This list is then supplied as input to the procedure IWRITE, which means integer write. Procedures always evaluate to NIL (= ()). IWRITE writes the external (decimal) representation 12...376 of (0 0 0 8192) to the terminal.

External and Internal Functions

We have to distinguish between internal, external and user defined functions or procedures. User defined functions are those declared with the PROCEDURE declaration in MAS. Internal functions are the functions which are builtin LISP functions, that means functions implemented in the LISP evaluator. Especially all functions which correspond to MAS operators are builtin. External functions are compiled Modula–2 procedures which are accessible from the interpreter. A list of all external functions can be displayed with the HELP procedure. The output looks like the following:

     List of all compiled functions and procedures:
     PROCEDURE ADV(LIST; LIST,LIST)
     FUNCTION  APFINT(LIST): LIST
     FUNCTION  APFRN(LIST): LIST
     ...
     PROCEDURE TIME
     PROCEDURE TRACE
     FUNCTION  TSGBASE(LIST,LIST,LIST): LIST
     65 functions and 27 procedures accessible.

The first column contains the type FUNCTION or PROCEDURE, which indicates if a value is returned or not. In the second column follows the name of the function. Finally the type of input and output parameters is shown. Currently all displayed parameters types are LIST, so this gives only a hint on the number of input and output parameters. The description of the procedures and the meaning of the parameters must be taken from the Modula–2 library definition modules. A procedure to module cross reference is contained in the data set browse.rc. The definition modules are contained in a folder named HELP. See the section on help facilities for more information on the system browser.

Bindings

The assignment statement is one way to bind a value to a variable. In MAS a variable and a procedure cannot both have the same name, that means the identifier names are unique. Caution: Other LISP systems allow variables and procedures to have the same name but to mean different objects. MAS allows procedure names to be used as variable names. So procedure names can be bound to variables and the variable can then be used as synonym for the procedure. Consider the example:

     say:=IWRITE.

Note that no parenthesis are following the IWRITE name. The variable say is now bound to the procedure IWRITE. So it is valid to use it in a procedure call:

     say(7).

which writes 7 to the terminal. But don’t bind a value to a procedure name, since this overwrites the procedure definition (unless you want to bind it to a different procedure body). Example:

     IWRITE:=foo. now

IWRITE(7). leads to a run time error:

     ** error: invalid function object in APPLY: foo.

Such a problem can be ‘resolved’ by the following assignment.

     IWRITE:=QUOTE(QUOTE(IWRITE)).

This assures that IWRITE is bound to QUOTE(IWRITE) which evaluates to IWRITE when used. One further remark on bindings is that you can produce infinite loops with them. Consider the example: x:=y. assume x and y are undefined, y:=x. y is bound to itself, a:=y. evaluates infinitely.

The actual (top level) bindings can be displayed by the DUMPV and LISTV procedures. LISTV lists the variable values in the syntax:

name:=value.

value is listed in MAS syntax as far as possible, but it is not always guaranteed that such listings can be read by the MAS parser again. The output of LISTV may look like:

exit:=EXIT.
PROCEDURE tuwas();
EDIT(was) tuwas.
PROCEDURE run();
IN(was) run.
PROCEDURE masini();
BEGIN was:="MAS.INI"; EDIT(was) END masini.
NIL:=().

DUMPV lists the variable values in the syntax:

(SETQ name value)

value is listed in LISP syntax, so it is always guaranteed, that such listings can be read in LISP mode again. The output of DUMPV may look like:

(SETQ exit EXIT)
(SETQ was (25 21 39 21 49 29 17 68 29 39))
(SETQ tuwas (LAMBDA () (EDIT was)))
(SETQ run (LAMBDA () (IN was)))
(SETQ masini (LAMBDA () (PROGN (ASSIGN was (STRING 37
            12 51 68 29 39 29)) (EDIT was))))
(SETQ NIL ())

VAR parameters

Usually function and procedure parameters are evaluated from left to right upon invocation. Exceptions to this rule are so called FEXPR functions or external Modula–2 functions with VAR parameters. VAR parameters mean that only a reference to a variable is used as parameter and not the value bound to a variable. FEXPR functions do not evaluate their arguments at all. They are described in the section on LISP and not discussed here. The ALDES / SAC–2 libraries contain many procedures with VAR parameters. The VAR and non VAR parameters are organized in the scheme: first all non VAR parameters, then all VAR parameters. This is respected by the MAS interpreter when external procedures are called. The user may therefore supply only variable names in places were VAR parameters appear. Upon exit from the procedure the variables are bound to the computed values. Example:

     PROCEDURE ADV(L: LIST; VAR a, LP: LIST);

This procedure expects one value input parameter L and two VAR parameters a and LP. ADV selects the first element of a list and the rest of a list:

     ADV(LIST(1,2,3),a,B). binds a to 1 and B to (2,3).

The integer quotient and remainder function is another example:

     IQR(44,7,a,b). binds a to 6 and b to 2.

3.3.3 Statement Sequence

In certain situations it is allowed to write sequences of statements separated by semicolons (";"). Note that since statements may be empty one can view the semicolon also as statement terminator character. The syntax of statement sequences is:

       statement { ";" statement }

3.3.4 BEGIN–END Statement

In cases where no statement sequences are allowed, but only a statement, the BEGIN– END statement can be used to enclose a statement sequence. Its syntax is:

       "BEGIN" statement-sequence "END"

Note: BEGIN–END does not create a new block with new local variables !

The LISP code generated from BEGIN–END is the PROGN S–expression. This implies that the value of a BEGIN–END statement is the value of the last executed statement.

Example:

       BEGIN a:=IEXP(2,49); IWRITE(a) END.

The corresponding LISP expression is

       (PROGN (ASSIGN a (IEXP 2 49) (IWRITE a))

On the interpreter top level the BEGIN–END statement is often useful to suppress unused output: in the above example the internal representation of 2^{49} is not written, only the external representation appears in the output stream.

3.3.5 IF Statement

The syntax of the IF statement is:

       "IF" condition "THEN" statementseq1
                     ["ELSE" statementseq2] "END"

When the evaluation of condition yields true then statementseq1 is executed, otherwise statementseq2 is executed (if present). Example:

       a:=1. b:=2.
       IF a = b THEN CLOUT("equal")
                ELSE CLOUT("not equal") END.

The LISP equivalent of the IF statement is:

       (IF (EQ a b) (CLOUT "equal")
                    (CLOUT "not equal"))

The expression produces not equal as side effect.

Note: The IF statement returns the value of the statement sequence which gets evaluated. Note: With the Modula–2 like IF statements all ambiguities of nested IF statements in Pascal are resolved.

3.3.6 WHILE Statement

The syntax of the WHILE statement is:

       "WHILE" condition "DO" statementseq "END"

The condition is evaluated. When the result is true, the statement sequence is executed, when the result is false then the evaluation of the WHILE statement is finished. After execution of the statement sequence the WHILE statement is again evaluated. Note: The WHILE statement returns the value of the last executed statement sequence or NIL if the first evaluation of condition is false. Example:

3.4. DECLARATIONS 43

       i:=0. a:=0.
       WHILE i < 17 DO i:=i+1; a:=a+i*i END.

The WHILE statement evaluates to 1785, the sum of the squares of the numbers from 0 to 17.

3.3.7 REPEAT Statement

The syntax of the REPEAT statement is:

       "REPEAT" statementseq "UNTIL" condition

First the statement sequence is executed, then the condition is evaluated. When the result is true, the execution of the REPEAT statement is finished. When the result is false, the REPEAT statement is again executed. Note: The REPEAT statement returns the value of the last executed statement sequence. Example:

       i:=0. a:=1.
       REPEAT i:=i+1; a:=a*2 UNTIL i > 5.

The REPEAT statement evaluates to 64, the 6–th power of 2.

3.4 Declarations

Elementary declarations can be

       { variabledecl | proceduredecl }

In this place we will only discuss elementary declarations, the specification declarations will be described in a later section.

3.4.1 VAR Declaration

The syntax of the VAR declaration is:

       "VAR" identifierlist ":" identifier [ string ]

The VAR declaration is used to define global or local variables. In general it is not required to declare variables in MAS. But certain usages (support type information, generic function arguments) require defined variables. The identifier in the above definition denotes an arbitrary name. The meaning of string is explained in chapter 4. The identifierlist has the following syntax:

       identifier { "," identifier }

This is a sequence of identifiers separated by commas.

3.4.2 PROCEDURE Declaration

The syntax of the PROCEDURE declaration is:

       "PROCEDURE" ident1
                   [ "(" [identlist] [";" "VAR" identlist] ")" ]
                   [ ":" ident2 ] ";"
                   block ident1 ";"

With this declaration it is possible to define a new procedure, which can be used afterwards in the same way as the builtin procedures. ident1 denotes the name of the procedure, it must be repeated at the end of the procedure declaration.

[ "(" [identlist] [";" "VAR" identlist] ")" ] denotes the so called formal pa-

rameter list. The formal parameter list is a list of identifiers separated by commas, followed optionaly by a VAR parameter list. When the procedure is called (used, invoked) the so called actual parameters are evaluated and bound to the formal parameters and are then accessible within the procedure body. The numbers of actual and formal parameters must be equal at runtime, otherwise an error occurs. The formal parameters should be pair wise disjoint, otherwise only the last (that is the right most) actual parameter is bound to the formal parameter. The VAR parameters are not evaluated and must be identifiers. Uppon return from a procedure with VAR parameters, the local values of these parameters are bound to the actual parameter symbols. The [ ":" ident2 ] construct specifies the type of the return value. However this information is not used further by the interpreter. block denotes a sequence of declarations followed by a statement. Results computed within the body of a procedure can be returned to the caller by function values. The return values can be specified explicitly be the RETURN statement or implicitly as value of the last evaluated statement. Several return values can only be returned as a single list. The syntax of the RETURN statement is:

       "RETURN" [ "(" [ expression ] ")" ]

The expression is evaluated and the result is returned to the caller. The execution of statement sequences or iteration statements is suspended after evaluation of a RETURN statement.

The generated code for the procedure declaration is

       (DE ident1 (identifierlist) block)

DE stands for ‘Define–Expr–function’, and means that the actual parameters are evaluated before they are bound to the formal parameters. ‘fexpr’ functions, which do not evaluate their arguments, and ‘macros’ are discussed in the section on LISP. They cannot be defined in the MAS language, but only in LISP.

The following examples define a function, that squares its argument, in several ways:

       PROCEDURE sqr(a);
       RETURN(a*a) sqr.

The square of ’a’ is explicit returned with a RETURN statement.

       PROCEDURE sqr(a);
       VAR b: ANY;
       b:=a*a sqr.

A local variable ’b’ is declared to be of ANY type. The square of ’a’ is bound to ’b’. Since the assignment statement returns a value, this value is then returned by the function.

       PROCEDURE sqr(a);
       VAR b: ANY;
       BEGIN b:=a*a END sqr.

The assignment statement can also be enclosed in a BEGIN–END statement.

       PROCEDURE sqr(a): LIST;
       BEGIN RETURN(a*a) END sqr.

This is almost in Modula–2 syntax except the missing type specification of the formal parameter ’a’.

Scoping Rules

The scope of a variable is the ’area’ within the variable is ’visible’. The visibility is can be determined statically from the program text, or dynamically during execution of the program. The MAS parser uses statical scoping and the MAS interpreter uses dynamical scoping. Variables which are defined on the top level interpreter are global variables. Local variables are those which are only visible in a procedure body. But there is a case, when a variable is defined within a procedure, but used within a further procedure called from the first procedure. These variables are called fluid variables. The values of fluid variables depend on the actual (run–time) environment of the procedure. For MAS the following scoping rules apply:

1. Variables which are defined in the procedure header, (formal parameters) are local variables.

2. Variables defined with the VAR declaration after the procedure header are local variables.

3. For undeclared variables the following cases apply:

(a) If there does not exist a global variable or a local variable in a calling procedure in the textual scope with the same name, then the variable is declared as local. In this case a VAR declaration is generated by the parser and a warning message is issued.

(b) If there exists a global variable or a local variable in a calling procedure in the textual scope with the same name, then the variable is fluid. Care has to be taken in the case when a procedure containing fluid variables is transfered (assigned to a global variable or returned as value) outside of its lexical block. In this case the dynamical scoping of the interpreter is used.

Note: Declare variables to ensure the correct usage of them. Note: Mutual recursive procedures will need a dummy forward reference to be in the textual scope when they are used.

Procedure Variables

In a procedure declaration the name of the procedure becomes a variable, which is bound to the S–expression corresponding to the procedure body. In other words

       (DE name (formals) body)

is equivalent to

       (ASSIGN name (LAMBDA (formals) body))

where LAMBDA is a tag to denote procedure bodies.

By this definition it is possible to use procedures as input to other procedures or to assign procedures to variables. Compiled procedures are not defined in this way and have no associated LAMBDA expressions. However the evaluation mechanism takes care that also compiled procedures can be used as parameters. Example: Definition of a function apply, which applies its first argument to its second argument.

       PROCEDURE apply(f,x); RETURN(f(x)) apply.
       apply(INEG,4).         --> -4
       x:=INEG. apply(x,4).   --> -4

A definition of a function mapcar, which applies its first argument to each list element of its second argument is discussed in the section on list processing. This completes the discussion of the basic MAS language. In the next section we discuss input and output. Although it is not defined in the language it is included here since is understanding is required to write MAS programs.

3.5 Input and Output

The facilities for reading and writing data are described in this section. The concept for input and output in MAS is based on streams. Streams are continuous sequences of characters. A stream is called open, when it is connected to a physical device. MAS allows maximal 25 streams to be open at a time. From these streams at any time two are the current streams. That means all read operations go to the current (or actual) input stream and all write operations go to the current output stream. It is possible to switch between open streams and a switch to a non open stream implies a open operation for that stream. From the beginning of the execution the current input stream is connected to the terminal (the keyboard) and the current output stream is also connected to the terminal (the screen). These two streams are always open. Further the terminal never becomes full during a write operation and never becomes empty during a read operation. One exception to the concept of current streams is the error stream. It is always connected to the terminal and can not be switched. So all error messages appear on the terminal and response to them is expected from the terminal. The streams are moreover managed like a stack. If an open input stream becomes empty, then the next open input stream becomes automatically the current input stream. If an open output stream becomes full, then the next open output stream is used. ’Last stream’ means the stream which was current before the last stream switch operation. The stream switching functions are:

IN(”stream”) the current input stream is switched to the stream ‘stream’,

OUT(”stream”) the current output stream is switched to the stream ‘stream’,

SHUT(”stream”) the specified stream is closed.

The ‘stream’ name may be prefixed by a ’device name’ to specify non–disk data sets:

CON: is the terminal

WIN: is a window (not yet implemented)

RAM: is an internal memory stream, ‘RAM–disk’

GRA: is a graphic window (not yet implemented)

NUL: is a dummy stream to suppress output, always empty on input, never full on output,

Other ’device names’ are passed to the operating system and are usually interpreted as disk data sets. Notes on the usage of the IN function. Consider the following two MAS inputs:

      a)  IN("x.y"). statement.

and

      b)  BEGIN IN("x.y"); statement END.

In a) the IN function switches the actual stream to ‘x.y’. The contents of this stream are evaluated, then the statement is executed. In b) the BEGIN–END statement is parsed and evaluated. The IN function switches the actual stream to ‘x.y’. But now the statement is executed and afterwards the contents of the stream ‘x.y’ are executed. In other words the IN function does only a switch to the next stream. If MAS is already executing some statements it finishes first and afterwards takes the next input from the new stream. The following two functions are for output:

BLINES(i) writes i blank lines to the output stream

CLOUT(”string”) writes this string to the output stream

Example: We will write a function, which puts a character string to the input stream.

  PROCEDURE cltis(S);
  (*Character list to input stream. S is a character list.
  S is transferred to the input stream. *)
  BEGIN
  (*1*) SHUT("RAM:help"); OUT("RAM:help");
        CLOUT(S);
        SHUT("RAM:help"); IN("RAM:help");
  (*9*) END cltis.

An utility stream ‘RAM:help’ is opened for output. Then the string is written to this stream and finally the current input stream is switched to ‘RAM:help’. As an application we discuss a function to convert a string to an integer. (A detailed description of integers will be given later.)

  PROCEDURE s2i(S);
  (*Character list to integer. S is a character list. S is
  converted to an integer and the result is returned.*)
  BEGIN
  (*1*) cltis(CCONC(S," "));
        RETURN(IREAD());
  (*9*) END s2i.

The string ‘S’ is put to the input stream, then ‘IREAD’ reads an integer from the current input stream. Note that a blank must be appended with the CCONC function to the string to stop ‘IREAD’ from requesting more digits from the terminal, or whatever stream is open. With this function it is now more convenient to write

       a:=s2i("12345678901234567890").

instead of

       a:=IREAD().  12345678901234567890

3.5.1 Stream Summary

A list of all streams can be obtained by the BIOS function. Its output look like the following:

 Summary of stream IO
 Name     temp.out,
 Output,  Byte-IO 11, Line-IO 14, Lmarg 0, Rmarg 79, Size 79.
 Name     MAS.INI,
 Closed,  Byte-IO 11, Line-IO 14, Lmarg 0, Rmarg 79, Size 79.
 Name     CON:,
 Output,  Byte-IO 25, Line-IO 13, Lmarg 0, Rmarg 79, Size 79.
 Name     CON:,
 Input,   Byte-IO 3, Line-IO 0, Lmarg 0, Rmarg 79, Size 79.
 4 Files used.

The first line contains the name of the stream. The second line contains information on the status of the stream Closed etc. Next the number of bytes and lines transferred to or received from the respective stream are displayed. Finally the left margin Lmarg, the right margin Rmarg and line length Size are shown.

3.5.2 Operating System

On some computers the MAS system provides access to the operating system. Most important is the possibility to call an editor from within MAS. The two functions DOS and EDIT are summarized as follows:

DOS(”prog parms”) Calls the program ’prog’ with the parameters ’parms’. The meaning of the string depends on the operating system.

EDIT(”data set name”) Edits the specified data set.

The editor is expected to be ’EDITOR.PRG’ on the current directory. The editor on disk is ’microEMACS 3.9’. The data set name string is prefixed by the string ” @MAS.RC ” which specifies the startup file for EMACS to be ’MAS.RC’.

50 CHAPTER 3. THE MAS LANGUAGE Examples: List the directory on an IBM PC:

       PROCEDURE dir;
       DOS("c:\command.com /c dir/p") dir.

Call the PC command interpreter:

       PROCEDURE command;
       DOS("c:\command.com") command.

Specification Component

In this chapter we discuss the specification capabilities of MAS. In the first section we give an overview over the design considerations. Then we define the syntax of the respective language constructs and then we discuss the semantics of the constructs.

4.1 Overview

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 et. al. 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. The denotational semantics of the MAS language is discussed in [Kredel 91]. 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 λ 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 et. al. 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.

4.2 Syntax

To precisely define the syntax we first specify the syntactic domains and then give the EBNF definition of the language. Note that we use the terms ‘function’ and ‘procedure’ interchangeably throughout the rest of the text.

4.2.1 Syntax Diagram

The syntax definition is given in extended BNF notation. That means name denotes non– termial symbols, {} denotes (possibly empty) sequences, () denotes required entities, | denotes case selection and [] denotes optional cases. Terminal symbols are enclosed in double quotes and productions are denoted by =. The syntax diagramms are listed in table 4.1. Observe that a program is a (possibly empty) sequence of declarations, followed by a (possibly empty) statement followed by a period. A statement can be an assignment, a procedure call or a IF–, WHILE–, REPEAT–, BEGIN–statement or EXPOSE–statement. Declarations are VAR and PROCEDURE; Unit specifications are SPECIFICATION, IMPLEMENTATION, MODEL, AXIOMS, IMPORT, SORT, SIGNATURE, MAP and RULE. The syntax of statements and expressions has already been discussed in chapter 3. Context conditions have also been discussed there.

4.2. SYNTAX 53

program      = topblock "."
topblock     = { ( unitspec | var | proc | expose ) ";" }
               statement
block        = { ( var | proc ) ";" } statement
unitspec     = { spec | implement | model | axioms }
spec         = "SPECIFICATION" header ";"
                { ( sort | import | sig ) ";" } "END" ident
implement    = "IMPLEMENTATION" header ";"
                { ( sort | import | var | proc ) ";" }
                statement "END" ident
model        = "MODEL" header ";"
                { ( sort | import | map ) ";" } "END" ident
axioms       = "AXIOMS" header ";"
                { ( sort | import | rule ) ";" }  "END" ident
sort         = "SORT" identlist
import       = "IMPORT" header [ renamings ]
sig          = "SIGNATURE" ident [ "(" [identlist] ")" ]
                                 [ ":" "(" [identlist]")" ]
var          = "VAR" identlist  ":" typeexpr
proc         = "PROCEDURE" ident ["("[identlist ]")"]
                           [":" ident]";" block ident
map          = "MAP" header "->" header [ "WHEN" header ]
rule         = "RULE" expression "=>" expression
                      [ "WHEN" condition ]
typeexpr     = header [ string ]
header       = ident [ "(" [identlist] ")" ]
renamings    = "[" { ident "/" ident ";" } "]"
expose       = "EXPOSE" ident [ "(" [actualparms] ")" ]

Table 4.1: Specification Syntax Diagram

4.3 Unit Declarations

A collection of denotations which belong to the same algebraic structure is called a unit. A unit consists of at most one SPECIFICATION construct which defines the (algebraic) language of the structure. Optionally several constructs may accompany a specification which define the semantics of the algebraic object: IMPLEMENTATION, MODEL and AXIOMS. The pair SPECIFICATION, IMPLEMENTATION is similar to the pair DEFINITION MODULE, IMPLEMENTATION MODULE in Modula–2. The semantics for functions is fixpoint semantics of λ–terms which are given by (imperative) procedures contained in the IMPLEMENTATION construct. The pair SPECIFICATION, AXIOMS is similar to constructs from algebraic specification languages. The semantics of functions is given by a term model modulo a congruence relation defined by the rewrite rules defined in the AXIOMS construct. The pair SPECIFICATION, MODEL is as far as I know unique to MAS. The semantics of functions is given by mappings which associate an interpretation function according to certain types of arguments. When all constituents of an unit have been defined, the unit must be exposed (with the EXPOSE construct) to make the functions available for use in expressions. We turn now to a more detailed discussion of these constructs.

4.4 Specifications

The specification part defines the (algebraic) language of an algebraic structure. The syntax of the SPECIFICATION declaration is:

     spec = "SPECIFICATION" header ";"
            { ( sort | import | sig ) ";" } "END" ident1
   header = ident1 [ "(" [identlist] ")" ]

The identifier ident1 defines the name of the specification and of the unit. The specifications can be parametrized with formal parameters given by identlist. The semantics is λ–abstraction of a specification.

4.4.1 SORT Declaration

The syntax of the SORT declaration is:

      sort = "SORT" identlist

The SORT declaration reserves the names in identlist for use as sorts.

4.4.2 IMPORT Declaration

The syntax of the IMPORT declaration is:

      import = "IMPORT" header [ renamings ]
   renamings = "[" { ident "/" ident ";" } "]"

The IMPORT declaration includes an already defined specification, named by the identifier in the header, into the actual specification. Since several specifications can be imported it is possible to join specifications. The actual specification is therefore extended by the (old) specification. During import it is possible to rename functions and sorts in the imported specification. The ident after the ‘/’ must be defined in the imported specification and is given the new name before the ‘/’.

4.4.3 SIGNATURE Declaration

The syntax of the SIGNATURE declaration is:

      sig = "SIGNATURE" ident [ "(" [identlist] ")" ]
                             [ ":" "(" [identlist]")" ]

The SIGNATURE declaration defines new function names (ident). Together with the input and output parameter sorts named by the identifieres in identlist.

4.4.4 Example Specification

These constructs allow 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). The specification of a concrete item like the rational numbers could be as follows:

        SPECIFICATION RATIONAL;
        (*Rational numbers specification. *)
        (*1*) SORT RAT, INT, atom;
        (*2*) SIGNATURE RNWRITE (RAT)     ;
              SIGNATURE RNDRD   (RAT)     : RAT;
        (*3*) SIGNATURE RNone   ()        : RAT;
              SIGNATURE RNzero  ()        : RAT;
        (*4*) SIGNATURE RNPROD  (RAT,RAT) : RAT;
              SIGNATURE RNSUM   (RAT,RAT) : RAT;
              SIGNATURE RNDIF   (RAT,RAT) : RAT;
              SIGNATURE RNNEG   (RAT)     : RAT;
              SIGNATURE RNINV   (RAT)     : RAT;
              SIGNATURE RNQ     (RAT,RAT) : RAT;

(*5*) SIGNATURE RNINT   (INT)     : RAT;
      SIGNATURE RNprec  (atom)    ;
(*9*) END RATIONAL.

In this specification the sorts RAT, INT and atom are defined. Then the input and output parameter sorts of various functions are defined. The most general unit is an object which specifies the communication (input / output) operations of objects.

SPECIFICATION OBJECT;
(*Object specification. *)
(*1*) SORT obj;
(*2*) SIGNATURE READ     (obj) : obj;
      SIGNATURE WRITE    (obj) ;
(*3*) SIGNATURE DECREAD  (obj) : obj;
      SIGNATURE DECWRITE (obj) ;
(*4*) SIGNATURE DEFAULT  (obj) : obj;
      SIGNATURE COERCE   (obj) : obj;
(*9*) END OBJECT.

Abstract specifications can be build from smaller pieces. For example (commutative) fields can be defined in terms of two abelian groups, which are themselves build from abelian monoids (which extend objects).

SPECIFICATION AMONO;
(*Abelian monoid specification. *)
(*1*) IMPORT OBJECT[ amono/obj ];
(*2*) SIGNATURE ZERO (amono)       : amono;
(*3*) SIGNATURE SUM  (amono,amono) : amono;
(*9*) END AMONO.
SPECIFICATION AGROUP;
(*Abelian group specification. *)
(*1*) IMPORT AMONO[ ag/amono ];
(*2*) SIGNATURE DIF  (ag,ag) : ag;
      SIGNATURE NEG  (ag)    : ag;
(*9*) END AGROUP.
SPECIFICATION FIELD;
(*Field specification joining two abelian groups. *)
(*1*) IMPORT AGROUP[ field/ag ];
      IMPORT AGROUP[ field/ag, ONE/ZERO, PROD/SUM,
                     REZIP/NEG, Q/DIF ];
(*9*) END FIELD.

The renamings are used to write one abelian group ‘multiplicatively’, like PROD for SUM.

Using the field specification one could derive an alternative definition of the rational number specification.

        SPECIFICATION RATIONAL;
        (*Rational numbers specification using the abstract
        field specification. *)
        (*1*) SORT INT, atom;
        (*2*) IMPORT FIELD[ RAT/field,
                           RNDRD/READ, RNWRITE/WRITE,
                           RNone/ONE, RNzero/ZERO,
                           RNSUM/SUM, RNNEG/NEG, RNDIF/DIF,
                           RNPROD/PROD, RNQ/RECIP, RNQ/Q ];
        (*3*) SIGNATURE RNINT  (INT): RAT;
              SIGNATURE RNprec (atom);
        (*9*) END RATIONAL.

Note that some unique functions for rational numbers must be specified seperately.

4.5 Implementations

The implementation part describes (imperative) procedures and data representations. The syntax of the IMPLEMENTATION declaration is:

    implement = "IMPLEMENTATION" header ";"
                 { ( sort | import | var | proc ) ";" }
                 statement "END" ident1
   header = ident1 [ "(" [identlist] ")" ]

The identifier ident1 defines the name of the specification and of the unit. The specifications can be parametrized with formal parameters given by identlist. A statement can be a BEGIN–statement and is executed during the exposition of the unit. The Modula–2 library functions exist a priori and can be accessed without further implementation definitions. An implementation defines a closed environment for the contained variable and procedure declarations (so called closures).

4.5.1 SORT Declaration

The syntax of the SORT declaration is:

      sort = "SORT" identlist

The SORT declaration reserves the names in identlist for use as sorts.

4.5.2 IMPORT Declaration

The syntax of the IMPORT declaration is:

      import = "IMPORT" header [ renamings ]
   renamings = "[" { ident "/" ident ";" } "]"

The IMPORT declaration makes the sorts and operations of a specification locally available. Its semantics correspond to the EXPOSE statement.

4.5.3 VAR Declaration

The syntax of the VAR declaration is the same as already discussed in chapter 3:

      var          = "VAR" identlist  ":" typeexpr
      typeexpr     = header [ string ]

The VAR declaration reserves names for local variables and associates type information with them.

4.5.4 PROCEDURE Declaration

The syntax of the PROCEDURE declaration is the same as already discussed in chapter 3:

      proc         = "PROCEDURE" ident ["("[identlist ]")"]
                                [":" ident]";" block ident
      block        = { ( var | proc ) ";" } statement

The PROCEDURE declaration defines the imperative (or functional) implementation of a procedure. A block can contain further declarations and a statement.

4.5.5 Example Implementation

The implementations can be used to define concrete procedures, abstract procedures or as extension to some existing library functions. The imperative language constructs (like assignments and loops) are fairly standard and are not discussed here. In case of the rational number unit just some gaps left by the library functions need to be filled.

        IMPLEMENTATION RATIONAL;
              VAR s: atom;
        (*1*) PROCEDURE RNone();
              BEGIN RETURN(RNINT(1)) END RNone;
        (*2*) PROCEDURE RNzero();

              BEGIN RETURN(RNINT(0)) END RNzero;
        (*3*) PROCEDURE RNWRITE(a);
              BEGIN IF s < 0 THEN RNWRIT(a) ELSE RNDWR(a,s) END;
                    END RNWRITE;
        (*4*) PROCEDURE RNprec(a);
              BEGIN s:=a END RNprec;
        (*8*) BEGIN
                    s:=-1;
        (*9*) END RATIONAL.

Here RNWRITE is defined for convenience and internally switches between the two rational number write functions RNWRIT and RNDWR according to the local precision variable s. Abstract functions are those which use function names of abstract specifications to implement something. For example in an ring one could have an abstract exponentiation function EXP.

        IMPLEMENTATION RING;
        (*1*) PROCEDURE EXP(X,n);
              VAR   x: ring; VAR   i: atom;
              BEGIN
              (*1*) IF n <= 0 THEN x:=ONE(X); RETURN(x) END;
              (*3*) i:=n; x:=X;
                    WHILE i > 1 DO i:=i-1;
                         x:=PROD(x,X) END;
                    RETURN(x)
              (*9*) END EXP;
        (*9*) END RING.

Here ONE and PROD denote (abstract) functions from the ring. The operators <=, > and - are used on atoms (integers k in the range −2^{29} = β < k < β = 2^{29}).

4.6 Models

The model part describes the association between abstract specifications (like rings) and concrete specifications (like integers). The syntax of the IMPLEMENTATION declaration is:

    model = "MODEL" header ";"
             { ( sort | import | map ) ";" } "END" ident1
   header = ident1 [ "(" [identlist] ")" ]

The identifier ident1 defines the name of the specification and of the unit. The specifications can be parametrized with formal parameters given by identlist. Operations / functions in models can be compiled functions, user defined imperative functions or term rewrite rules. Dynamic abstract objects like finite fields can be handled by a descriptor concept. The descriptor can then specify the characteristic of the field.

4.6.1 SORT Declaration

The syntax of the SORT declaration is:

      sort = "SORT" identlist

The SORT declaration reserves the names in identlist for use as sorts.

4.6.2 IMPORT Declaration

The syntax of the IMPORT declaration is:

      import = "IMPORT" header [ renamings ]
   renamings = "[" { ident "/" ident ";" } "]"

The IMPORT declaration makes the sorts and operations of a specification locally available. Its semantics correspond to the EXPOSE statement.

4.6.3 MAP Declaration

The syntax of the MAP declaration is:

     map = "MAP" header1 "->" header2 [ "WHEN" header3 ]

The MAP declaration defines the interpretation of an abstract operation (named by the identifier in header1) In the parameter list of an abstract function the sort names of a model are specified. In the parameter list of a concrete function (named by the identifier in header2) the two selectors VAL and DESC can appear. The i–th VAL selects the value of the i–th abstract function parameter. The i–th DESC selects the descriptor of the i–th abstract function parameter. Descriptors are only sketched in the sequel. Conditional interpretation can be expressed by a WHEN clause following the real function. header3 defines the name and parameters of a LISP condition. In the condition the VAL and DESC selectors can be used. Observe that the model interpretation can be viewed as function overloading. The abstract functions are sometimes also called generic functions.

4.6.4 Example Model

On the left hand side in a MAP clause appears the abstract function name with sort names as parameters. On the right hand side after the ‘->’ stands the concrete function name with VAL and DESC selector parameters.

        MODEL FIELD;
        (*Rational numbers are a model for fields. *)
        (*1*) IMPORT RATIONAL;
        (*2*) MAP READ(RAT)      -> RNDRD();
              MAP WRITE(RAT)     -> RNWRITE(VAL);
        (*3*) MAP ONE(RAT)       -> RNone();
              MAP ZERO(RAT)      -> RNzero();
        (*4*) MAP PROD(RAT,RAT)  -> RNPROD(VAL,VAL);
              MAP SUM(RAT,RAT)   -> RNSUM(VAL,VAL);
              MAP DIF(RAT,RAT)   -> RNDIF(VAL,VAL);
              MAP NEG(RAT)       -> RNNEG(VAL);
              MAP Q(RAT,RAT)     -> RNQ(VAL,VAL);
              MAP REZIP(RAT)     -> RNINV(VAL);
        (*9*) END FIELD.

This reads as follows: the product function PROD is interpreted in the model of rational numbers (two rational numbers as parameters RAT) as the concrete function RNPROD (from the abstract parameters the values are to be taken according to the VAL selectors). An example using descriptors and conditional interpretation is as follows.

      MODEL FIELD;
      (*Modular integers are a model for fields. *)
            ...
      (*4*) MAP PROD(MI,MI)   -> MIPROD(DESC,VAL,VAL)
                           WHEN EQ(DESC,DESC);
            ...
      (*9*) END FIELD.

MI denotes the modular integer Z/_{(p)} sort. MIPROD denotes the modular integer product where the first parameter is the modulus p selected by DESC. The WHEN clause specifies that only numbers from the same finite field are to be multiplied (that is their descriptors must be equal (EQ)). Descriptors can be specified in VAR declarations provided the specifications have defined them.

4.7 Axioms

The axioms part describes conditional rewrite rules. The syntax of the AXIOM declaration is:

   axioms = "AXIOMS" header ";"
            { ( sort | import | rule ) ";" }  "END" ident1
   header = ident1 [ "(" [identlist] ")" ]

The identifier ident1 defines the name of the specification and of the unit. The specifications can be parametrized with formal parameters given by identlist.

4.7.1 SORT Declaration

The syntax of the SORT declaration is:

      sort = "SORT" identlist

The SORT declaration reserves the names in identlist for use as sorts.

4.7.2 IMPORT Declaration

The syntax of the IMPORT declaration is:

      import = "IMPORT" header [ renamings ]
   renamings = "[" { ident "/" ident ";" } "]"

The IMPORT declaration makes the sorts and operations of a specification locally available. Its semantics correspond to the EXPOSE statement.

4.7.3 RULE Declaration

The syntax of the MAP declaration is:

      rule = "RULE" expression1 "=>" expression2
              [ "WHEN" condition ]

The RULE declaration defines a rewrite rule. The meaning is as follows: if the left hand side of a rule (expression1 above) can be unified with the expression under consideration, then the variables in the right hand side (expression2 above) are substituted according to the unification. Then the right hand side replaces the actual expression. The rules define a reduction relation on the term algebra generated by the sorts and operations of the specification. Variables need not be declared and are assumed to be universally quantified and unbound. Conditional rewriting can be expressed by a WHEN clause following the right hand side of the rewrite rule (condition above). The condition is evaluated with the variables substituted according to the actual unification of the left hand side. Currently there are no facilities to solve conditional equations since there is no back tracking of unsuccessful rewritings. There are also no provisions to check if the rewrite system is confluent or Noetherian.

4.7.4 Example Axioms

The Peano structure can be specified as follows:

SPECIFICATION PEANO;
(*Peano structure specification. *)
(*1*) SORT nat, bool;
(*2*) SIGNATURE null  ()        : nat;
      SIGNATURE one   ()        : nat;
   (* SIGNATURE succ  (nat)     : nat; *)
      SIGNATURE add   (nat,nat) : nat;
      SIGNATURE prod  (nat,nat) : nat;
(*3*) SIGNATURE equal (nat,nat) : bool;
(*9*) END PEANO.

Observe that the succ (successor) constructor need not be defined in the specification, since no rule has succ on the first functional term in the right hand side expression. The Peano axioms can then be coded as rewrite rules as follows:

AXIOMS PEANO;
(*Axioms for Peano system. *)
      IMPORT PROPLOG;
      RULE one()                  => succ(null());
(*1*) RULE equal(X,X)             => TRUE();
      RULE equal(succ(X),null())  => FALSE();
      RULE equal(null(),succ(X))  => FALSE();
(*2*) RULE equal(succ(X),succ(Y)) => equal(X,Y);
(*3*) RULE add(X,null())          => X;
      RULE add(null(),X)          => X;
(*4*) RULE add(X,succ(Y))         => succ(add(X,Y));
(*5*) RULE prod(X,null())         => null();
      RULE prod(null(),X)         => null();
(*6*) RULE prod(X,succ(Y))        => add(prod(X,Y),X);
(*9*) END PEANO.

PROPLOG denotes a propositional logic specification not listed here. There the constant functions TRUE() and FALSE() are defined. During unification the variables X and Y are bound in the left hand side and then substituted in the right hand side.

4.8 EXPOSE Statement

Once this specification aparatus has been setup one wants to see how it works and what benefits are obtained. The language constructs discussed so far modify only the decalaration data base. To access the defined functions they must first be exposed, that means they must be made visible. The syntax of the EXPOSE statement is:

expose = "EXPOSE" ident [ "(" [actualparms] ")" ]

The identifier ident defines the name of the unit. The actual parameters are given by actualparms and can be any MAS expression which evaluate to an item meaningful in the unit. During the exposition of an implementation part the actual environment is used to define the procedure closures. This implies that the order of the exposition is important. So only models which have already been exposed are visible in an abstract implementation. For example the earlier defined units can be exposed as follows:

        EXPOSE RATIONAL.
        EXPOSE PEANO.
        EXPOSE FIELD.

From then on the functions like PROD can be used in expressions or top level statements and procedures.

4.9 Operator Overloading

For convenience of the users the MAS parser can be instructed to generate generic function names for the arithmetic operators. However some care is needed since then also a specification of the atoms structure is required to access the built–in primitive arithmetic.

This feature of the parser is set by the pragma switch GENPARSE. It activates / inactivates the generic code generation of the parser. The operators correspond to the following functions: + to SUM, - to DIF or NEG, * to PROD, / to Q and ^to EXP. See also the section on PRAGMAS 9.2.

4.10 Expression Evaluation

We turn now to the evaluation of arbitrary expressions. Expressions are transformed to functional terms by the parser. The evaluation of functional terms is defined as follows:

1. If there is a model in which the function has an interpretation and the WHEN– condition on the parameters is fulfilled, then the interpretation of the function in this model is applied to the interpretation (values) of the arguments.

2. If there is an imperative procedure, then the procedure body is evaluated in the procedure context.

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

4. Otherwise the functional term is left unchanged.

Let us step through the following examples:

        VAR r, s: RAT.             ANS: RAT().
        r:="2222222222.777777777777777".
        ANS: "2222222222777777777777777/1000000000000000".
        s:=r/r.                    ANS: "1".
        s:=r^0 + s - "1": RAT.     ANS: "1".

The first line declares the variables r and s to be of type RAT, that is to be rational numbers. The second line is a so called generic assignment. Depending on the type of r the character string on the right hand side is read (or converted to internal form). Recall that the interpretation of READ(RAT) was defined as RNDRD() which reads a rational number in decimal representation. Internally an object with type, value and descriptor information is created. This information is then used by the generic write function WRITE(RAT) for displaying the result in the next line. The fourth line shows the computation of r/r. According to the type information of r the corresponding generic function Q(RAT,RAT) is determined. Then RNQ(VAL,VAL) is computed where the values of the data objects are substituted. Finally the information on the output parameters of RNQ namely RAT is used to create a new typed object. This object is then bound to the variable s and finally it is displayed. The last line shows the computation of a more complex expression r^0 + s - "1": RAT. The term "1": RAT denotes a constant from the rational numbers, namely 1. The contents of the character string are read by the generic function READ(RAT) and a new typed object is created. Note further that r^0 is computed by an abstract function (namely EXP) of the abstract RING implementation. Then the computation proceeds as expected. A final example for the use of term algebras which explains itself:

        x:=one().          ANS: succ(null()).
        x:=add(x,x).       ANS: succ(succ(null())).
        x:=prod(x,x).      ANS: succ(succ(succ(succ(null())))).

This concludes the discussion of the language constructs used in the specification component.

List Processing

In this section we give an introduction to list processing. Definition: An atom is a β–integer. A list is a finite sequence of atoms and / or lists. Atoms and lists are objects. In MAS there is a second kind of lists which can also contain symbols (variables). Definition: An S–expression is a list where the first element is a symbol or the first element is an S–expression. S–expressions may contain further symbols. Empty lists are denoted by the variable NIL. Other lists are denoted by their elements separated by commas and enclosed in parenthesis. E. g. (1,a) denotes the list of the two elements 1 and a. The size of lists is only limited by the available computer memory.

5.1 List Construction

One way to construct a list is by the LIST function. LIST can be called by any number of arguments and returns a list of its evaluated arguments. Example:

      x:=LIST(1,2,3,4).         --> (1,2,3,4)
      y:=LIST(1,LIST(2,3),4).   --> (1,(2,3),4)

A second function to construct a list is the COMP function (COMPosition). Its first argument is an object and the second argument is a list. The object is added as first element to the list. Example:

      a:=COMP(0,x).             --> (0,1,2,3,4)
      b:=COMP(3,NIL).           --> (3) == LIST(3)

The length of a list can be determined by the LENGTH function.

Two lists can be combined to one list by the CONC and CCONC functions (CONCatenation, Constructive CONCatenation). CONC and CCONC take two lists as arguments and return the concatenation of the inputs. CONC modifies the first list to produce the concatenated list and CCONC produces a copy of the first input. Example:

      a:=CCONC(x,y).            --> (1,2,3,4,1,(2,3),4)
      b:=CONC(x,y).             --> (1,2,3,4,1,(2,3),4), but x=b

5.2 List Destruction

The basic parts of lists are their first element and the rest list without the first element. The functions FIRST and RED (for REDuctum = rest) access these parts. Example: (with the same lists as before)

      a:=FIRST(y).              --> 1
      b:=RED(y).                --> ((2,3),4)
      FIRST(RED(y)).            --> (2,3)

The procedure ADV combines the FIRST and RED function. ADV takes a list as first argument; it returns in the second argument the first element of the list and in the third argument the rest of the list. Example:

      ADV(y,a,b).               --> (), now a=1, b=((2,3),4)
      a:=a.                     --> 1
      b:=b.                     --> ((2,3),4)

When a new list is constructed while an old list is processed, the new list is in most cases in the wrong order. So there is a need to reverse lists. There are two functions to accomplish this: INV (INVerse) and CINV (Constructive INVerse). INV modifies the existing list where CINV constructs a new list. Example: (with the same lists as before)

      a:=CINV(y).               --> a=(4,(2,3),1) y=(1,(2,3),4)
      a:=INV(y).                --> a=(4,(2,3),1) y=(1) !!!

5.3 List Diagrams

Lists are stored in the computer in memory cells which have a first field and a reductum field. These memory cells are often represented as boxes with two fields:

FIRST RED The FIRST field contains objects. The RED field contains the address (called pointer) of the next cell of the list or NIL to denote the end of the list. Example: LIST(7). can be represented as:

                                  NIL 7

LIST(0,NIL,LIST(1)). would have the following representation:

        • ; 0  ⟶  • ; NIL  ⟶  NIL ; •

↓

                                                            NIL 1

The pointers are shown as ‘•’ and ‘⟶’. ‘•’ indicates that the field is occupied by a pointer and ‘⟶’ ‘points’ to the next cell of the list. Note that in this representation the cells used to store a list can overlap with other cells:

       a:=LIST(2).                     --> (2)
       b:=COMP(COMP(0,a),COMP(1,a)).   --> ((0,2),1,2)

The list b contains two pointers to the list a:

        • ; •  ⟶  • ; 1  ⟶  NIL 2

↓  ↑
• ; 0  ⟶  ⟶  ⟶  ·

Some care is needed when such lists are reversed. If it is done with the INV function, then a pointer circle may be constructed:

       NIL ; •  ⟵  • ; 1  ⟵  • ; 2

↓  ↑
• ; 0  ⟶  ⟶  ⟶  ·

And if this list is printed one would obtain infinite output:

      INV(b).    -->  (2,1,(0,2,1,(0,2, ... infinitely

In such situations it may be required to use the CINV function to reverse a list.

5.4 Exercises

1. Construct a list of the numbers 1,…, 100.

2. Compute the sum of all numbers in this list.

3. Construct an ‘infinite’ list.

4. Write a function which ‘maps’ a function to to the elements of a list and returns the list of function results.

Solution to exercise 1:

i:=1. w:=NIL.
WHILE i <= 100 DO w:=COMP(i,x); i:=i+1 END.
w:=w.   --> (100, 99, ..., 2, 1)

In the WHILE loop the list w is composed from the numbers. The variable i runs from 1 to 100. The list w is in the descending order. To get the list in ascending order use w:=INV(w). to reverse the list. Solution to exercise 2:

s:=0. u:=w.
WHILE u <> NIL DO ADV(u, j,u); s:=s+j END.
s:=s.   --> 5050
u:=u.   --> ()

In the WHILE loop each element of u is accessed and summed in the variable s. The sum must be below β since + is used as sum operator. Solution to exercise 3:

w:=NIL. i:=0.
WHILE i = 0 DO w:=COMP(i,w) END.
-->
** Garbage Collection ... nnn cells, 3 sec.
** ... GC completed.
...
** fatal error: Garbage Collection: too few cells reclaimed.
(a)bort, (b)reak, (c)continue, (d)ebug, <ENTER> ? break
ARG: w:=NIL.

In this example the WHILE loop will never terminate since the variable i is not incremented within the loop. When the available cell space is consumed, a garbage collection takes place. This means that unused cells (garbage) are searched to become available for list processing again. After a while no more or to few free cells are found and the program encounters a fatal error. Typing b for break or <ENTER> returns to the top level interpreter loop and the ARG: prompt is displayed. Finally empty the list by w:=NIL. to free the cells for next use. Solution to exercise 4:

      PROCEDURE mapcar(f,x);
      (*Map the function f to the elements of
      the list x. *)
      VAR   y, e, r: ANY;
      BEGIN
      (*1*) y:=NIL; r:=x;
      (*2*) WHILE r # NIL DO
                  ADV(r, e, r);
                  e:=f(e); y:=COMP(e,y)
                  END;
            y:=INV(y); RETURN(y);
      (*9*) END mapcar.
      a:=LIST(1,2,3,4,5).
      ANS: (1 2 3 4 5)
      p:=mapcar(INEG,a).
      ANS: (-1 -2 -3 -4 -5)

Mapcar takes as arguments a function and a list and applies the function to all elements of the list. In the statement e:=f(e) the parameter f is used as function. The so constructed new list is returned. In our example the function INEG, i.e. integer negation is applied to (1 2 3 4 5) producing the list (-1 -2 -3 -4 -5) of the negated integers.

5.5 Strings

As already mentioned, character strings are internally represented as lists of β–integers. To make such number lists again visible as character sequence the procedure CLOUT can be used (Character List OUT). CLOUT writes the output to the actual output stream. Example:

       a:="123".            --> (1,2,3)
       CLOUT(a).            --> 123
       CLOUT("abc").        --> abc

By this list representation of strings it is possible to use all list processing functions also on strings. Example:

       CLOUT(INV("abc")).   --> cba

The string "abc" is first converted to the list (11,12,13). Then this list is inverted and the resulting list is written to the output stream.

5.6 Exercises

1. Write functions LEFT and RIGHT, which return the left respective right part of a string (list).

LEFT(A,i) returns the i left objects of the list A.

RIGHT(A,i) returns the objects of the list A starting from i + 1.

   So CONC( LEFT(S,i), RIGHT(S,i) ) = S holds.

2. Write a function SUBSTR which returns a sub–string of a string.

SUBSTR(A,i,j) returns a list of j objects of the list A starting from i + 1.

3. Write a function INDEX which determines the position of one string within another string.

INDEX(a,B) returns the position of the list a in the list B if a occurs in B, otherwise 0 is returned.

Solution to exercise 1:

PROCEDURE left(S,i);
(*Return the left i elements of the list S.*)
VAR   s, SP, T, k: LIST;
BEGIN
(*1*) SP:=S; T:=NIL; k:=0;
      WHILE (k < i) AND (SP # NIL) DO k:=k+1;
            ADV(SP,s,SP); T:=COMP(s,T) END;
      T:=INV(T); RETURN(T);
(*9*) END left.

To obtain the left part of a list it is necessary to copy the first i elements.

PROCEDURE right(S,i);
(*Return the right elements of the list S,
starting from position i+1.*)
VAR   SP, k: LIST;
BEGIN
(*1*) SP:=S; k:=0;
      WHILE (k < i) AND (SP # NIL) DO k:=k+1;
            SP:=RED(SP) END;
      RETURN(SP);
(*9*) END right.

The right part of a list is just the respective reductum of the list. No copying is required.

Solution to exercise 2:

  PROCEDURE sublist(S,i,j);
  (*Return j elements of the list S,
  starting from position i+1.*)
  RETURN(left(right(S,i),j)) sublist.
  a:=LIST(1,2,3,4,5,6,7,8,9,0).
  left(a,2).      --> (1,2)
  right(a,7).     --> (8,9,0)
  sublist(a,3,4). --> (4,5,6,7)

The substring (list) function can be built by combination of the LEFT and RIGHT functions.

5.7 Complexity

In this section we introduce the basic concepts of algorithm complexity. The concepts are applied to the list processing algorithms in the next section. An important point in the discussion on algorithms is the time and the space used to compute a given problem. Time and space are ‘costs’ for the usage of an algorithm. The definition for the computing time cost function is as follows: Definition: Let I_{A} denote the set of inputs for an algorithm A and let R be the real numbers. Then t_{A} : I ↦ R denotes the computing time function for algorithm A. I.e. t_{A}(i) i ∈ I gives the computing time of algorithm A for input i. When A is clear from the context, we will shortly write I for I_{A} and t for t_{A}. The space cost function c_{A} is defined analog. Since the costs may vary for different inputs it is convenient to distinguish minimal, average and maximal cost functions: Definition: Let I_{A} denote the set of inputs for an algorithm A and let n = |I_{A}|. Then

1. the minimal computing time function is t^{−} = min{t(i) : i ∈ I},

2. the average expected computing time function is t^{∗} = \frac{1}{n} ∑_{i∈I} t(i),

3. the maximal computing time function is t^{+} = max{t(i) : i ∈ I}.

The following relation holds by definition:

t^{−} ≤ t^{∗} ≤ t^{+}

If t^{−} = t^{+} we denote the computing time function by t. Computing time and memory space usage depend on the data representation, the algorithm and on the actual computer and its disks etc. The computer type is of minor interest, since the same algorithm may be implemented on different machines and we can expect that the computing time varies by a constant factor from one machine to another.

How can computing time and space usage be measured independent of a particular computer architecture ? The elementary data type in computer algebra is the list. Therefore it seems naturally to measure ’time’ as function of the list length of an object. Memory usage can be measured in terms of cell usage, which is also a function of list length. In the following we will assume that operations on atoms cost 1 time unit and that no cells are consumed during such an operation. The time cost for the retrieval of an atom from the FIRST field of a cell will be included in the cost for the operation on the atom. Also the time to store an atom after an operation will be included in the cost for an operation. List construction with COMP costs one cell. The list length of an object a will be denoted by L(a). For ’simple’ algorithms, like those for list processing or elementary arithmetic, the minimal and maximal computing time coincide. But for other algorithms the times can vary by magnitudes. E.g. polynomials may have many zero coefficients. Then the maximal computing time must take into account that possibly all coefficients are non zero whereas the minimal computing time must take into account that only a certain number of coefficients is really non zero. In complicated cases where the maximum computing time is to bad and the average computing time is not known, also the real computing time on a specific machine is taken to get an idea of the complexity of the algorithm. When the computing time functions are determined constant factors or lower order terms are usually of minor interest. The big O notation allows to ’forget’ about such details. O(f(n)) means, that there exists a constant c such that O(f(n)) < c · f(n) for all large n. E.g. 7·L(a) ∼ O(L(a)) or L(a)+3 ∼ O(L(a)). But constant and non constant exponents are of interest L(a)^{3}, L(a)^{n} or L(a)^{L(b)}.

5.8 Algorithms

In this section we give a more formal summary of list processing functions. We include also information on the complexity of the algorithms (see section 5.7). The exposition follows [Loos 76]. Let A = {x ∈ Z : |x| < β} be the set of atoms, L = {x ∈ Z : β ≤ |x| ≤ β + ν} be the set of lists (pointers to cells), O = A ∪ L be the set of objects and L_{i} the set of lists of length ≥ i. The left column contains the algorithm specification. In the right column the type specification of the algorithm inputs and outputs and the algorithm function are described. Further the algorithm complexity is discussed.

a ← F IRST (A) a ∈ O, A ∈ L_{1}. a is the first element of the non empty list A. One cell is accessed, so the computing time is t = 1, c = 0.

A′ ← RED(A) A′ ∈ L, A ∈ L_{1}. A′ is the reductum of the non empty list A, i.e. A without its first element. One cell is accessed, so the computing time is t = 1, c = 0.

ADV (A, a, A′) a ∈ O, A′ ∈ L, A ∈ L_{1}. a is the first element of the non empty list A, A′ is the reductum of A. One cell is accessed, so t = 1, c = 0.

B ← COMP (a, A) a ∈ O, A ∈ L, B ∈ L_{1}. a becomes the first element of the non empty list B, A becomes the reductum of B. One new cell is made available, so t = 1, c = 1. (Garbage collection is not taken into account.)

n ← LENGT H(A) 0 ≤ n ∈ A, A ∈ L. n is the length of A. All cells of the list are traversed, so t = L(A), c = 0.

A ← LIST (a_{1},…, a_{n}) a_{i} ∈ O (1 ≤ i ≤ n), n ≥ 0, l ∈ L. A is the list of the objects a_{1},…, a_{n}. n new cells are made available, so the computing time is t = n, c = n.

B ← INV (A) A, B ∈ L. B is the inverse list of A. The cells of A are used to restructure the list B. The pointer A remains unchanged. All cells are traversed, so t = L(A), c = 0.

B ← CINV (A) A, B ∈ L. B is the constructive inverse list of A. B is a new list, the cells of A remain unchanged. L(A) new cells are made available, so t = L(A), c = L(A).

A ← CONC(A_{1}, A_{2}) A, A_{1}, A_{2} ∈ L. A is the concatenation of the lists A_{1} and A_{2}. The cells of A_{1} are used to built the list A if A_{1} is not empty. The pointers A_{1} and A_{2} remain unchanged. L(A_{1}) cells are traversed, so t = L(A_{1}), c = 0.

A ← CCONC(A_{1}, A_{2}) A, A_{1}, A_{2} ∈ L. A is the constructive concatenation of the lists A_{1} and A_{2}. A is a new list, the cells of A_{1} and A_{2} are unchanged. L(A_{1}) new cells are made available, so t = L(A_{1}), c = L(A_{1}).

t ← EQUAL(A, B) A, B ∈ O, t ∈ {0, 1}. If A and B are equal objects, i.e. atoms or lists with the same structure and same atoms, then t = 1 otherwise t = 0. Maximal the number of cells of the smaller object are traversed, minimal one test is required: t^{+} = min{EXT ENT (A)+1, EXT ENT (B)+1}, t^{−} = 1, c^{+} = c^{−} = 0.

n ← EXT ENT (A) A ∈ O, 0 ≤ n ∈ A. n is the number of cells of the object A. Overlapping is not counted. For A ∈ A, n = 0. All cells of the object are traversed, so t = EXT ENT (A), c = 0. n ← ORDER(A) A ∈ O, 0 ≤ n ∈ A. n is the maximal nesting level of lists of the

object A. For A ∈ A, n = 0. All cells of the object are traversed, so t = EXT ENT (A), c = 0.

This concludes the summary of list processing functions.

Basic Arithmetic

The MAS system consists of a kernel with list processing, input / output facilities and an interaction part. The MAS language of the interaction part supports only ’primitive’ arithmetic operations i.e. the operators +, -, *, /, etc. are only valid on β–integers (atoms). All further arithmetic functions must be imported from Modula–2 libraries. Available basic arithmetic libraries are:

ALDES/SAC–2 Digit Arithmetic System,

ALDES/SAC–2 Integer Arithmetic System,

ALDES/SAC–2 Rational Number System,

ALDES/SAC–2 Modular Integer Arithmetic System,

ALDES/SAC–2 Integer Factorization System,

ALDES/SAC–2 Set of Integers System,

ALDES/SAC–2 Combinatorical System,

MAS Arbitrary Precision Floating Point System,

Which functions are accessible from this libraries can be determined by the MAS HELP function. The listings of the definition modules of these libraries is contained in the folder \HELP on the MAS distribution disk. In the following we will discuss the libraries for arbitrary precision integers, arbitrary precision rational numbers and arbitrary precision floating point numbers. Polynomial arithmetic will be discussed later. For further reading the following documents are recommended:

1. D. E. Knuth: The Art of Computer Programming, Vol. II: Seminumerical Algorithms, Chap. 4: Arithmetic. This book contains an in–depth treatment of most basic arithmetic algorithms.

2. G. E. Collins, M. Mignotte, F. Winkler: Arithmetic in Basic Algebraic Domains. In B. Buchberger, G. E. Collins, R. Loos: Computer Algebra, Computing Supplement 4. This article contains an overview on the computational best algebraic algorithms.

It is further recommended to look into the original ALDES / SAC–2 algorithm documentation or into the translated MAS libraries in Modula–2.

6.1 Integer Arithmetic

The arbitrary precision integers are in the following called integers. The small integers are explicitly denoted as β–integers. We will first discuss the representation of integers by lists. Although it is not required to understand the representation to use the functions on integers, it is required to understand the algorithms. Further the representation has important influence on the computing time, i.e. the complexity of the algorithm. The base for the number representation of integers is β. Note: Let A ∈ Z, A ≥ 0 then there exist unique numbers n, a_{0},…, a_{n−1} ∈ Z, with 0 ≤ a_{i} < β (i = 0,…, n − 1) and a_{n−1} ≠ 0 such that:

A = ∑_{i=0}^{n−1} a_{i}β^{i}.

For A < 0 the same representation holds under the condition −β < a_{i} ≤ 0 (i = 0,…, n − 1) and a_{n−1} ≠ 0. Definition: List representation of integers.

A = 0 is represented by the atom 0.

A ≠ 0, |A| < β, is represented by the atom a_{0}, and A ≠ 0, |A| ≥ β, is represented by the list (a_{0},…, a_{n−1}).

The ‘least significant’ β–digit is the first atom in the list representation. The ‘most significant’ digit appears as last element in the list representation. So e.g. A is even iff a_{0} (the first element in the list) is even. Example:

β = 0 · β^{0} + 1 · β^{1}, so n = 2 and the representation is (0, 1).
−β = 0 · β^{0} + (−1) · β^{1}, the list representation is (0, −1).

6.1.1 Algorithms

The programs of the most important integer algorithms and their complexity are summarized next. Therefore let A be the set of atoms, L be the set of lists, O = A ∪ L be the set of objects, I = {x ∈ O : x represents an element of Z} be the set of integers and L(I) be the set of lists over integers. Further let L(a) denote the number of β–digits of a (if a ≥ β then this is equal to the list length of the representation of a). We will also write L(a) for O(L(a)), i.e. we will not count for constant factors. The computing time functions t, t^{+}, t^{−}, t^{∗} are defined as before in section 5.7. The time analyses are due to G. E. Collins. b ← INEG(a) a, b ∈ I. b = −a is the negative of a. Every β–digit of a must be

processed to change the sign, so t = L(a), c = L(a).

s ← ISIGN(a) a ∈ I, s ∈ {−1, 0, 1}. s is the sign of a. As long as β–digits of a are zero, the list must be processed, so t^{+} = L(a), t^{−} = 1, t^{∗} = 1, c = 0.

b ← IABS(a) a, b ∈ I. b = |a| is the absolute value of a. If sign(a) = −1 then a must change the sign, so t^{+} = L(a), t^{−} = 1, c^{+} = L(a), c^{−} = 0.

s ← ICOMP (a, b) a, b ∈ I, s ∈ {−1, 0, 1}. s = sign(a − b) is the sign of a − b. At most the smaller number of digits of a and b must be compared, so t^{+} = min{L(a), L(b)}, t^{−} = 1, c = 0.

c ← ISUM(a, b) a, b, c ∈ I. c = a+b is the sum of a and b. At least the smaller number of digits of a and b must be added, so t^{−} = min{L(a), L(b)}, c^{−} = min{L(a), L(b)}. If always carrys occur, the maximal computing time is proportional to the greater number of digits of a and b, so t^{+} = max{L(a), L(b)}, c^{+} = max{L(a), L(b)}. However carrys occur ‘seldom’, so t^{∗} = t^{−}, c^{∗} = c^{−}.

c ← IDIF (a, b) a, b, c ∈ I. c = a − b is the difference of a and b. b is negated, then the sum is computed, so t^{−} = L(b), c^{−} = L(b). The maximal computing time is proportional to the maximal computing time of ISUM, so t^{+} = max{L(a), L(b)}, c^{+} = max{L(a), L(b)}.

c ← IP ROD(a, b) a, b, c ∈ I. c = a · b is the product of a and b. The product is computed by the classical method, multiplying each β–digit of a by each β–digit of b, so t^{+} = L(a) · L(b) = L(a)^{2} if L(a) = L(b). c^{+} = L(a) + L(b) since the cells of the result are reused and not taken from the available cells during summation.

c ← IP RODK(a, b) a, b, c ∈ I. c = a · b is the product of a and b. The product is computed by Karatsubas method, splitting each integer in two halves and then using only 3 multiplications, 4 summations and some shifting to obtain the product. More precisely if a = a_{1}λ+a_{0}, b = b_{1}λ + b_{0} where λ such that L(a_{1}) ≈ L(a_{0}), then

a · b = a_{1}b_{1}λ^{2} + (a_{1}b_{1} + (a_{1} − a_{0})(b_{0} − b_{1}) + a_{0}b_{0})λ + a_{0}b_{0}.

If L(a) = L(b) then t^{+} = L(a)^{log_{2}(3)} = L(a)^{1.585...}. However c^{+} = L(a) · L(b), since the summation algorithms are used explicitly. Trade–off: IP RODK is only superior to IP ROD if the length of the integers exceed 55 β–digits, i.e. the integers exceed about 500 decimal digits (= 8 lines full of decimal digits on the screen).

IQR(a, b, q, r) a, b, q, r ∈ I. b ≠ 0, q = ⌊a/b⌋, r = a − q · b. The classical division method (dividing the leading β–digits and subtracting b times the trial quotient digit) has been refined to the division of the two leading digits and subtracting b times the trial quotient digit. The advantage of this refinement is that the trial quotient digit is in nearly all cases the true quotient digit of the quotient, so seldom adjustments of the remainder are necessary. The computing time is proportional to the time for the computation of the product of b and q, so t^{+} = L(b) · L(q) and c^{+} = L(b) · L(q).

q ← IQ(a, b) a, b, q ∈ I. b ≠ 0, q = ⌊a/b⌋. Internally IQR is called, see IQR for the computing time.

r ← IREM(a, b) a, b, r ∈ I. b ≠ 0, r = a − ⌊a/b⌋ · b. Internally IQR is called, see IQR for the computing time.

c ← IEXP (a, n) a, c ∈ I, 0 ≤ n ∈ A. c = a^{n} is the n–th power of a (exponentiation). c is computed by a binary exponentiation method, i.e. c is recursively computed as (a^{⌊n/2⌋})^{2} · a^{n−⌊n/2⌋2}. The computing time is proportional to the time for the computation of the ‘biggest’ product, so t^{+} = (n · L(a))^{2}, c^{+} = 2 · n · L(a), 2 because of the classical multiplication algorithm.

c ← IGCD(a, b) a, b, c ∈ I. c = gcd(a, b) is the greatest common divisor of a and b. The classical Euclidean algorithm uses the invariant gcd(a, b) = gcd(b, rem(a, b)) for the computation of the gcd until b = 0. Assume w.l.o.g. L(a) ≥ L(b), then the maximal computing time is t^{+} = L(b)·(L(a)−L(gcd(a, b))+1). Thus if gcd(a, b) = 1 and L(a) = L(b) then t^{+} = L(a)^{2} and c^{+} = L(a)^{2}. The number of division steps is bounded by ⌈log_{ϕ}(\sqrt{5}a)⌉ − 2 ≈ 4.8 log_{10}(a) − 0.32. The average number of division steps is given by \frac{12 ln(2)}{π^{2}} ln(a) ≈ 1.9 log_{10}(a).

c ← ILCM(a, b) a, b, c ∈ I. c = lcm(a, b) is the least common multiple of a and b. c is computed as \frac{a}{gcd(a,b)} · b. So the maximal computing time is t^{+} = 2L(a)^{2}.

a ← IRAND(n) 0 ≤ n ∈ A, a ∈ I. a is a random integer with random sign and |a| < 2^{n}. t = L(a) and c = L(a).

a ← IREAD() a ∈ I. An integer a is read from the actual input stream. A conversion from decimal representation to β representation is done, so t^{+} = L(a)^{2} and c^{+} = L(a)^{2}. The syntax for integers is:

int = [ "+" | "-" ]
      [ "0" | ... | "9" ] { "0" | ... | "9" }

Note: No blanks may appear within an integer !

IW RIT E(a) a ∈ I. The integer a is written to the actual output stream. A conversion from β representation to decimal representation is done, so t^{+} = L(a)^{2} and c^{+} = L(a)^{2}. The syntax is the same as for IREAD.

ILW RIT (a) a ∈ L(I). a is a list of integers. Each element of a is written to the output stream by IW RIT E. So t^{+} = t_{IWRITE} · length(a) and

c^{+} = c_{IWRITE} · length(a).

l ← IF ACT (a) a ∈ I, l ∈ L(I). l is the list of the integer prime factors of a, multiple factors occur multiple times in l. (e.g. IF ACT (8) = (2, 2, 2).) For large L(a) the computing time has exponential growth: t^{+} = c^{L(a)}.

l ← SMP RM() l ∈ L(A). l is the list of the prime numbers between 2 and 1000.

l ← DP GEN(m, k) l ∈ L(A), m, k ∈ A, m and k positive, k ≤ 1000, m + 2 · k < β. l is the list of all prime numbers p, such that m ≤ p < m + 2 · k.

This concludes the summary of integer arithmetic functions. Examples:

      a:=LIST(0,7,3).    --> (0 7 3)
      IWRITE(a).         --> 864691132213231616
      ISIGN(a).          --> 1
      INEG(a).           --> (0 -7 -3)
      ISUM(a,a).         --> (0 14 6)
      b:=IEXP(2,29).     --> (0 1)
      IREM(a,b).         --> 0
      IQ(a,b).           --> (7 3)
      IPROD(a,b).        --> (0 0 7 3)
      ICOMP(a,b).        --> 1
      IFACT(a).          --> (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
                             2 2 2 2 2 2 2 2 2 2 2 23 70026641)

In the example an integer a is set to the list (0, 7, 3). That means a represents the integer 0 · β^{0} + 7 · β^{1} + 3 · β^{2}. The decimal representation of a is generated in the second line. Since sign(a) = sign(7) = 1 we have a > 0. −a has the representation (0, −7, −3). a + a has the representation (0, 14, 6). Next b is set to β = 2^{29}, represented by the list (0, 1). The remainder by division by b is zero, a rem b = 0, (= the first element of the list representation of a). The quotient a/b is the rest list of the representation of a i.e. (7, 3). a · b shifts a one β–digit to the left (0, 0, 7, 3). Since 7 > 1 and the list representation of a is longer than that of b we have sign(a − b) = 1, i.e. a > b.

6.1. INTEGER ARITHMETIC 81

Finally the prime factors of a are computed, since a is divisible by β we must have 29 occurrences of 2 in the prime factors. And 7 + 3β seems to have the prime factors 23 and 70026641. For illustration we list the algorithms ICOMP and IPROD in Modula–2 in MAS. The function of the algorithms should be clear from the step comments and the integer representation discussed before.

PROCEDURE ICOMP(A,B: LIST): LIST;
(*Integer comparison.  A and B are integers.  s=SIGN(A-B).*)
VAR   AL, AP, BL, BP, DL, SL, UL, VL: LIST;
BEGIN
(*1*) (*A and B single-precision.*)
      IF (A < BETA) AND (B < BETA) THEN SL:=MASSIGN(A-B);
         RETURN(SL); END;
(*2*) (*A single-precision.*)
      IF A < BETA THEN SL:=-ISIGNF(B); RETURN(SL); END;
(*3*) (*B single-precision.*)
      IF B < BETA THEN SL:=ISIGNF(A); RETURN(SL); END;
(*4*) (*compare corresponding digits.*) SL:=0; AP:=A; BP:=B;
      REPEAT ADV(AP,AL,AP); ADV(BP,BL,BP); UL:=MASSIGN(AL);
             VL:=MASSIGN(BL);
             IF UL*VL = -1 THEN SL:=UL; RETURN(SL); END;
             DL:=AL-BL;
             IF DL <> 0 THEN SL:=MASSIGN(DL); END;
             UNTIL (AP = SIL) OR (BP = SIL);
(*5*) (*same length*)
      IF (AP = SIL) AND (BP = SIL) THEN RETURN(SL); END;
(*6*) (*use sign of longer input.*)
      IF AP = SIL THEN SL:=-ISIGNF(BP); ELSE
         SL:=ISIGNF(AP); END;
      RETURN(SL);
(*9*) END ICOMP;

BETA denotes β, MASSIGN denotes the sign function for β–integers. ISIGNF denotes the sign function for integers in the libraries (for compatibility with the ALDES / SAC–2 libraries). SIL denotes the empty list.

PROCEDURE IPROD(A,B: LIST): LIST;
(*Integer product.  A and B are integers.  C=A*B.*)
VAR   AL, AP, APP, BL, BP, C, C2, CL, CLP, CP, CPP, EL, FL,
      I, ML, NL, TL: LIST;
BEGIN
(*1*) (*A or B zero.*)
      IF (A = 0) OR (B = 0) THEN C:=0; RETURN(C); END;
(*2*) (*A and B single-precision.*)
      IF (A < BETA) AND (B < BETA) THEN DPR(A,B,CLP,CL);
         IF CLP = 0 THEN C:=CL; ELSE C:=LIST2(CL,CLP); END;
         RETURN(C); END;
(*3*) (*A or B single-precision.*)
      IF A < BETA THEN C:=IDPR(B,A); RETURN(C); END;
      IF B < BETA THEN C:=IDPR(A,B); RETURN(C); END;
(*4*) (*interchange if B is longer.*) ML:=LENGTH(A); NL:=LENGTH(B);

      IF ML >= NL THEN AP:=A; BP:=B; ELSE AP:=B; BP:=A; END;
(*5*) (*set product to zero.*) C2:=LIST2(0,0); C:=C2;
      FOR I:=1 TO ML+NL-2 DO C:=COMP(0,C); END;
(*6*) (*multiply digits and add products.*) CP:=C;
      REPEAT APP:=AP; ADV(BP,BL,BP);
             IF BL <> 0 THEN CPP:=CP; CLP:=0;
                REPEAT ADV(APP,AL,APP); DPR(AL,BL,EL,FL);
                       CL:=FIRST(CPP); CL:=CL+FL; CL:=CL+CLP;
                       CLP:=CL DIV BETA; TL:=CLP*BETA; CL:=CL-TL;
                       SFIRST(CPP,CL); CLP:=EL+CLP; CPP:=RED(CPP);
                       UNTIL APP = SIL;
                SFIRST(CPP,CLP); END;
             CP:=RED(CP);
             UNTIL BP = SIL;
(*7*) (*leading digit zero*)
      IF CLP = 0 THEN SRED(C2,SIL); END;
      RETURN(C);
(*9*) END IPROD;

DPR denotes the β–digit product, IDPR denotes the integer product with a β–digit, SFIRST (Set FIRST) and SRED (Set RED) are list modifying functions not available for interactive use in MAS.

6.1.2 Exercises

1. Compute the gcd of 156562431911123 and 442677773754356 in three ways:

(a) Use the the built–in algorithm for the gcd.

(b) Write an recursive algorithm in MAS and use it for the computation.

(c) Write an iterative algorithm in MAS and use it for the computation.

(d) ∗ Write an iterative algorithm for the extended gcd.

2. Write algorithms to compute the determinant of a square matrix over the integers. Assume that the matrices are represented as lists of lists of integers. Use the Laplace method for the expansion of the determinant. Therefore write the following sub– algorithms:

(a) Deletion of an element of a vector (represented as list).

(b) Deletion of a column of a matrix (represented as list of vectors).

(c) Determinant expansion using Laplace’s method.

(d) An algorithm to generate matrices with respect to a function of the matrix entries.

(e) ∗ An algorithm with Gauss’s method for the computation of the determinant.

(f) ∗ Write the determinant algorithm for other coefficient domains, e.g. rational numbers.

The solutions to the exercises are discussed in the sequel. Exercise 1. The built–in gcd algorithm has the name IGCD. For the MAS algorithms we use the euclidean method:

gcd(a, b) = \{ \begin{matrix}a & if b = 0, \\ gcd(b, rem(a, b)) & else. \end{matrix}

With this definition the recursive gcd algorithm can be formulated as follows:

       PROCEDURE ggt(a,b);
       IF b = 0 THEN RETURN(a)
                ELSE RETURN(ggt(b,IREM(a,b)))
          END ggt.

The integer remainder is called IREM. The iterative gcd algorithm can be formulated using the WHILE–statement and an additional variable d:

       PROCEDURE GGT(a,b);
       VAR   d: ANY;
       BEGIN
       WHILE b # 0 DO d:=b;
             b:=IREM(a,b); a:=d END;
       RETURN(a) END GGT.

The numbers can be converted to internal representation by IREAD. The sample output with computing times follows:

       a:=IREAD(). 156562431911123
       b:=IREAD(). 442677773754356
       c:=IGCD(a,b).
       {0 sec} ANS: 7
       c:=ggt(a,b).
       {4 sec} ANS: 7
       c:=GGT(a,b).
       {2 sec} ANS: 7

The gcd is always 7. The built–in algorithm is the fastest: it needs unmeasurable many seconds. The recursive algorithm is the slowest: it needs about 4 seconds and the iterative algorithm need 2 seconds. Exercise 2. Let A = (a_{ij}) be a n × n matrix over a commutative ring without zero divisors. Then the determinant has the following expansion:

det(A) = ∑_{i=1}^{n}(−1)^{i+j} · a_{ij} · det(A_{ij}) for some j, (1 ≤ j ≤ n).

Where A_{ij} is the matrix A without the i–th row and the j–th column. The computing time can be estimated by the following considerations: The determinant expansion produces n! summands of products of n factors. Assume L(A) = max{L(a_{ij}), 1 ≤ i, j ≤ n}. So t^{+} = n! · L(A)^{n} and t^{−} = L(A)^{n}, e.g. if the matrix is in triangular form. In contrast it needs about n^{3} field operations and n^{5} ring operations to transform a matrix to upper triangular from by the Gauss respective the Bareiss algorithm. I.e. the Laplace expansion is very slow. The determinant expansion algorithm can be formulated as follows

   PROCEDURE det(M);
   (*Determinant. M is a matrix (i.e a list
   of row lists). The determinant of M is computed. *)
   VAR   i, d, dp, s, N, MP, V, VP, v: LIST;
   BEGIN
   (*1*) d:=0;
         IF M = NIL THEN RETURN(d) END;
   (*2*) ADV(M,V,MP);
         IF MP = NIL THEN RETURN(FIRST(V)) END;
   (*3*) s:=1; i:=0;
         WHILE V # NIL DO ADV(V,v,V); i:=i+1;
               IF v # 0 THEN
                  N:=delcolumn(MP,i); dp:=det(N);
                  dp:=IPROD(v,dp);
                  IF s < 0 THEN dp:=INEG(dp) END;
                  d:=ISUM(d,dp);
                  END;
               s:=-s; END;
   (*4*) RETURN(d);
   (*9*) END det.

Step 2 handles the recursion base of a 1×1 matrix. In step 3 the determinant is expanded w.r.t. the first row (that is j = 1 in our formula). The test if some a_{ij} = 0 (denoted by v) is important, since in this case the expansion of the sub–matrix is useless and much computing time can be saved. Since the first row of the matrix has been removed in step 2, it is only necessary to remove the i–th column of the matrix. The matrices A_{i1} are denoted by N. The factor (−1)^{i+1} is handled by a sign flag denoted by s. The vector element deletion algorithm is

   PROCEDURE delelem(V,i);
   (*Delete element in list. V is a list. The i-th
   element of V is deleted. 0 <= i <= length(V). *)
   VAR   U, VP, v, j: ANY;
   BEGIN
   (*1*) IF i <= 0  THEN RETURN(V) END;
         IF V = NIL THEN RETURN(V) END;

(*2*) VP:=V; j:=0; U:=NIL;
      REPEAT j:=j+1;
             IF VP = NIL THEN RETURN(V) END;
             ADV(VP,v,VP); U:=COMP(v,U);
             UNTIL j = i;
(*3*) U:=RED(U); U:=INV(U); U:=CONC(U,VP);
      RETURN(U);
(*9*) END delelem.

Step 1 does some precondition checks. In step 2 the beginning of the list is copied to avoid the modification of existing data. In step 3 the (new) beginning is reversed and concatenated with the rest of the vector. The column delete algorithm is straight forward: for each row the previous algorithm is called.

PROCEDURE delcolumn(M,i);
(*Delete column in matrix. M is a matrix (i.e a list
of row lists). In each row the i-th element is
deleted. *)
VAR   N, MP, V: ANY;
BEGIN
(*1*) IF i <= 0  THEN RETURN(M) END;
      IF M = NIL THEN RETURN(M) END;
(*2*) MP:=M; N:=NIL;
      WHILE MP # NIL DO ADV(MP,V,MP);
            V:=delelem(V,i); N:=COMP(V,N);
            END;
(*3*) N:=INV(N); RETURN(N);
(*9*) END delcolumn.

The sample matrices are:

1. the unit matrix E = (e_{ij}) with: e_{ij} = \{ \begin{matrix}1 & if i = j, \\ 0 & else, \end{matrix}

2. an upper triangular matrix U = (u_{ij}) with: u_{ij} = \{ \begin{matrix}j & if i ≤ j, \\ 0 & else, \end{matrix}

3. a lower triangular matrix L = (l_{ij}) with: l_{ij} = \{ \begin{matrix}j & if i ≥ j, \\ 0 & else. \end{matrix}

The generating functions for the matrices are as follows:

PROCEDURE eh(i,j);
IF i = j THEN RETURN(1) ELSE RETURN(0) END eh.

PROCEDURE ut(i,j);
IF i <= j THEN RETURN(j) ELSE RETURN(0) END ut.
PROCEDURE lt(i,j);
IF i >= j THEN RETURN(j) ELSE RETURN(0) END lt.

eh means ‘Einheitsmatrix’ = unit matrix, ut means upper triangular matrix and lt means lower triangular matrix. The matrix generation procedure takes the generating function f and the dimension k as input and delivers the appropriate matrix.

PROCEDURE mat(f,k);
VAR   i, j, V, M: LIST;
BEGIN
(*1*) M:=NIL;
      IF k <= 0 THEN RETURN(M) END;
(*2*) i:=0;
      WHILE i < k DO i:=i+1; j:=0; V:=NIL;
            WHILE j < k DO j:=j+1;
                  V:=COMP(f(i,j),V) END;
            V:=INV(V); M:=COMP(V,M);
            END;
(*4*) M:=INV(M); RETURN(M);
(*9*) END mat.

A sample output follows:

A:=mat(ut,5).
{4 sec} ANS: ((1 2 3 4 5) (0 2 3 4 5) (0 0 3 4 5)
             (0 0 0 4 5) (0 0 0 0 5))
d:=det(A). {246 sec} ANS: 120
A:=mat(lt,10).
{14 sec} ANS: ((1 0 0 0 0 0 0 0 0 0) (1 2 0 0 0 0
0 0 0 0) (1 2 3 0 0 0 0 0 0 0) (1 2 3 4 0 0 0 0 0 0)
(1 2 3 4 5 0 0 0 0 0) (1 2 3 4 5 6 0 0 0 0) (1 2 3
4 5 6 7 0 0 0) (1 2 3 4 5 6 7 8 0 0) (1 2 3 4 5 6 7
8 9 0) (1 2 3 4 5 6 7 8 9 10))
d:=det(A). {64 sec} ANS: 3628800

In the first example a 5 × 5 upper triangular matrix is generated. The determinant is 120 and the computation takes 246 seconds. In the second example a 10 × 10 lower triangular matrix is generated. The determinant is 3628800 and the computing time is 64 seconds.

The second computation is much faster, since the determinant is expanded with respect to the first row. And the lower triangular matrix has most times zero in these rows.

6.2 Rational Number Arithmetic

The elements of Q, fractions of integers are in the following called rational numbers. We will first discuss the representation of rational numbers by lists. Note: Let a ∈ Q, a = \frac{p}{q}, p, q ∈ Z, then there exist integers p′, q′ ∈ Z, with q′ > 0 and gcd(p′, q′) = 1 such that:

\frac{p}{q} = \frac{p′}{q′} .

p and p′ are called denominator and q and q′ are called numerator of the rational number a. Definition: List representation of rational numbers.

0 ∈ Q is represented by the atom 0.

\frac{p}{q} ∈ Q, is represented by the list (p′, q′), where p′, q′ are represented as integers. p′, q′ defined as before.

Example:

\frac{7}{3} is represented as (7, 3).
−\frac{1}{2} is represented as (−1, 2).
\frac{0}{3} is represented as 0.
The representation of \frac{β}{3} is ((0, 1), 3).
−\frac{β}{3} is represented as ((0, −1), 3).
\frac{4}{8} is represented as (1, 2).

6.2.1 Algorithms

The programs of the most important rational number algorithms and their complexity are summarized in the following. Let A be the set of atoms, L be the set of lists, O = A∪L be the set of objects, I = {x ∈ O : x represents an element of Z}, be the set of integers and R = {x ∈ O : x represents an element of Q} be the set of rational numbers. Further let L(a) denote the maximum of the length of the numerator and denominator of a (L(a) = max{L(p′), L(q′)}). We will also write L(a) for O(L(a)), i.e. we will not count for constant factors. The computing time functions t, t^{+}, t^{−}, t^{∗} are defined as before in section 5.7. The methods for efficient product and sum algorithms are due to P. Henrici. The time analyses are due to G. E. Collins. b ← RNINT (a) a ∈ I, b ∈ R. b = \frac{a}{1} is the embedding of the integer a into the

rational numbers. Since the list (a, 1) is built t^{+} = 2, c^{+} = 2, t^{−} = 1, c^{−} = 0.

c ← RNRED(a, b) a, b ∈ I, c ∈ R. c = \frac{a}{b} is the construction of a rational number from an integer numerator and a denominator. a and b are reduced to lowest terms. The list (a′, b′) is built with \frac{a′}{b′} = \frac{a}{b}, b′ > 0 and gcd(a′, b′) = 1. t^{+} = t_{IGCD}^{+} = L(c)^{2}, c^{+} = L(c)^{2}, t^{−} = 1, c^{−} = 0.

b ← RNDEN(a) a ∈ R, b ∈ I. a = \frac{n}{b}, b is the denominator of a. t = 1, c = 0.

b ← RNNUM(a) a ∈ R, b ∈ I. a = \frac{b}{d}, b is the numerator of a. t = 1, c = 0.

b ← RNNEG(a) a, b ∈ R. b = −a is the negative of a. The sign of the denominator must be changed, so t^{+} = t_{INEG}^{+} = L(a), c^{+} = L(a).

s ← RNSIGN(a) a ∈ R, s ∈ {−1, 0, 1}. s is the sign of a. The sign of the denominator must be determined, so t^{+} = t_{ISIGN}^{+} = L(a), c = 0.

b ← RNABS(a) a, b ∈ R. b = |a| is the absolute value of a. If sign(a) = −1 then a must change the sign, so t^{+} = L(a), t^{−} = 1, c^{+} = L(a), c^{−} = 0.

s ← RNCOMP (a, b) a, b ∈ R, s ∈ {−1, 0, 1}. s = sign(a − b) is the sign of a − b. Let a = \frac{a_{1}}{a_{2}} , b = \frac{b_{1}}{b_{2}} , then a < b ⟺ a_{1}b_{2} < b_{1}a_{2}. Therefore possibly integer products must be formed and the computing time is proportional to integer product and comparison. So if L(a) = L(b) we have t^{+} = t_{IPROD}^{+} + t_{ICOMP}^{+} = L(a)^{2}, t^{−} = 2t_{ISIGN}^{−} = 2, c^{+} = 2L(a), c^{−} = 0.

c ← RNP ROD(a, b) a, b, c ∈ R. c = a · b is the product of a and b. Let a = \frac{a_{1}}{a_{2}} , b = \frac{b_{1}}{b_{2}} . The product, defined as

c = \frac{c_{1}}{c_{2}} = \frac{a_{1}}{a_{2}} · \frac{b_{1}}{b_{2}} = \frac{a_{1} · b_{1}}{a_{2} · b_{2}} ,

is computed in a way that exploits the precondition that the denominator and numerator have gcd = 1. Therefore let d_{1} = gcd(a_{1}, b_{2}), d_{2} = gcd(a_{2}, b_{1}) and let a_{1} = d_{1}a′_{1}, b_{2} = d_{1}b′_{2}, b_{1} = d_{2}b′_{1}

and a_{2} = d_{2}a′_{2}. So c = \frac{a′_{1} · b′_{1}}{a′_{2} · b′_{2}} , and we obtain the postcondi-

tion gcd(a′_{1}b′_{1}, a′_{2}b′_{2}) = 1 without actually computing that gcd. If L(a) = L(b), the computing time is therefore only t^{+} = L(a)^{2} instead of (2L(a))^{2} for the classical method. c^{+} = L(a)^{2}, t^{−} = 2 and c^{−} = 2.

b ← RNEXP (a, n) a, b ∈ R, n ∈ N. c = a^{n} is the n–th power of a (exponentiation). Like the integer exponentiation c is computed by a binary exponentiation method. The computing time is proportional to the time for the computation of the ‘biggest’ product, so t^{+} = (n · L(a))^{2}, c^{+} = 2 · n · L(a). t^{−} = 2 and c^{−} = 2. b ← RNINV (a) a, b ∈ R. b = 1/a is the inverse of a. If a = \frac{a_{1}}{a_{2}} then 1/a = \frac{a_{2}}{a_{1}} . Only

if the denominator has negative sign, the signs of the denominator and numerator must be changed. t^{+} = 2t_{INEG}^{+} = 2L(a), c^{+} = 2c_{INEG}^{+} = 2L(a), t^{−} = 2 and c^{−} = 2.

c ← RNQ(a, b) a, b, c ∈ R. c = a/b is the quotient of a and b. The inverse of b is determined and the product of a and 1/b is computed. So the computing time is t^{+} = t_{RNINV}^{+} + t_{RNPROD}^{+} = L(a)^{2}. c^{+} = L(a)^{2}, t^{−} = 4 and c^{−} = 4.

c ← RNSUM(a, b) a, b, c ∈ R. c = a + b is the sum of a and b. Let a = \frac{a_{1}}{a_{2}} , b = \frac{b_{1}}{b_{2}} . The sum is defined as

c = \frac{c_{1}}{c_{2}} = \frac{a_{1}}{a_{2}} + \frac{b_{1}}{b_{2}} = \frac{a_{1} · b_{2} + a_{2} · b_{1}}{a_{2} · b_{2}} .

We will also exploit the preconditions that the denominator and numerator have gcd = 1 to minimize the computing time. Therefore let d = gcd(a_{2}, b_{2}) and let a_{2} = da′_{2}, b_{2} = db′_{2}. Further let t = a_{1}b_{2} + a_{2}b_{1}, t′ = a_{1}b′_{2} + a′_{2}b_{1} and e = gcd(t′, d). Now observe that

gcd(t, a_{2}b_{2}) = d · gcd(t′, a_{2}b′_{2}) = d · gcd(t′, d) = d · e.

Since d divides a_{1}b_{2} + a_{2}b_{1} and a_{2}b_{2} the first equation holds. And since both a′_{2} and b′_{2} have gcd = 1 with a_{1}b′_{2} + a′_{2}b_{1}, the second equation holds. Let t′ = t′′e and a_{2} = a′′_{2}e then the sum is

c = \frac{t′′}{a′′_{2} · b′_{2}} . The postcondition gcd(t′′, a′′_{2}b′_{2}) = 1 holds by con-

struction of t′′ and a′′_{2}. If L(a) = L(b) the computing time is t^{+} = t_{IGCD_{d}}^{+} + 2t_{IPROD_{t′}}^{+} + t_{ISUM_{t′}}^{+} + t_{IGCD_{e}}^{+}. t^{+} = L(a)(L(a) − L(d) + 1) + 2L(a)(L(a) − L(d) + 1) + 2L(a) + 2L(a)(L(d) − L(e) + 1). For L(d) = 1 we obtain t^{+} = L(a)^{2} + 2L(a)^{2} + 4L(a) = 3L(a)^{2} and for L(d) = L(a), t^{+} = L(a) + 4L(a) + 2L(a)^{2} = 3L(a)^{2}. For the classical method we get t^{+} = 3L(a)^{2} + 2L(a) + (2L(a))^{2} = 7L(a)^{2}. Further c^{+} = L(a)^{2}, t^{−} = const and c^{−} = 2.

c ← RNDIF (a, b) a, b, c ∈ R. c = a − b is the difference of a and b. b is negated, then the sum is computed, so t^{−} = L(b), c^{−} = L(b). The maximal computing time is proportional to the maximal computing time of RNSUM, so t^{+} = max{L(a), L(b)}, c^{+} = max{L(a), L(b)}.

a ← RNREAD() a ∈ R. A rational number a is read from the actual input stream. A conversion from decimal representation to β representation is done and the numerator and denominator are reduced to lowest terms, so t^{+} = L(a)^{2} and c^{+} = L(a)^{2}. The syntax accepted by RNREAD for rational numbers is:

rat = int [ "/" int ]

a ← RNDRD() a ∈ R. Same as RNREAD except for a different syntax. The syntax accepted by RNDRD for rational numbers is:

rat = int [ "/" int
          | "." unsigned-int [ "E" beta-int ] ]

Note: No blanks are allowed before "E".

RNW RIT (a) a ∈ R. The rational number a is written to the actual output stream. A conversion from β representation to decimal representation is done, so t^{+} = L(a)^{2} and c^{+} = L(a)^{2}. The syntax is the same as for RNREAD.

RNDW R(a, s) a ∈ R, s ∈ A. The rational number a is written to the actual output stream. With s digits following the decimal point. The syntax is:

rat = int "." unsigned-int [ "+" | "-" ]

A trailing "+" (or "-") indicates whether the rational number is greater (or smaller) than the written decimal approximation.

a ← RNRAND(n) 0 ≤ n ∈ A, a ∈ R. a = \frac{a_{1}}{|a_{2}|+1} reduced to lowest terms is a random rational number with a_{1,2} = IRAND(n). t^{+} = L(a)^{2} and c^{+} = L(a)^{2}.

This concludes the summary of rational number arithmetic functions. Examples:

a:=RNRED(6,-8).      --> (-3,4)
a:=RNREAD(). 3/4     --> (3,4)
a:=RNREAD(). 3/-4    --> (-3,4)
a:=RNDRD(). 3.4      --> (17,5)
a:=RNDRD(). 3.14E7   --> (31400000,1)
RNWRIT(a).           --> -3/4
RNDWR(a,10).         --> -0.7500000000
RNDWR(a,0).          --> -1.-
RNDWR(a,1).          --> -0.7+

The first statement shows the normalization of a rational number \frac{6}{−8} = \frac{−3}{4} with gcd(3, 4) = 1 and 4 > 0. In the next two statements RNREAD is used to read two rational numbers. Observe that 3/-4 has negative numerator which is normalized during input. RNDRD is able to read the 6.2. RATIONAL NUMBER ARITHMETIC 91

decimal fraction 3.4 which is 3 + \frac{4}{10} = 3 + \frac{2}{5} = \frac{15+2}{5} = \frac{17}{5} as shown. The number 3.14E7 is interpreted as (3 + \frac{14}{100}) · 10^{7}, which gives the rational number \frac{31400000}{1}. The output routine RNWRIT needs no further explanation. RNDWR writes a rational number as decimal fraction with specified number of digits after the decimal point. \frac{−3}{4} with 10 digits after the decimal point is exactly −0.7500000000. With 0 digits after the decimal point −1.− is printed, the trailing − indicates that −1. < −\frac{3}{4}. With 1 digit after the decimal point −0.7+ is printed which indicates that −0.7 > −\frac{3}{4}. For illustration we list the algorithms RNSUM and RNPROD in Modula–2 in MAS. The function of the algorithms should be clear from the step comments and the integer representation discussed before.

PROCEDURE RNPROD(R,S: LIST): LIST;
(*Rational number product.  R and S are rational numbers.  T=R*S.*)
VAR   D1, D2, R1, R2, RB1, RB2, S1, S2, SB1, SB2, T, T1, T2: LIST;
BEGIN
(*1*) (*r=0 or s=0.*)
      IF (R = 0) OR (S = 0) THEN T:=0; RETURN(T); END;
(*2*) (*obtain numerators and denominators.*) FIRST2(R,R1,R2);
      FIRST2(S,S1,S2);
(*3*) (*r and s integers.*)
      IF (R2 = 1) AND (S2 = 1) THEN T1:=IPROD(R1,S1);
         T:=LIST2(T1,1); RETURN(T); END;
(*4*) (*r or s an integer.*)
      IF R2 = 1 THEN IGCDCF(R1,S2,D1,RB1,SB2); T1:=IPROD(RB1,S1);
         T:=LIST2(T1,SB2); RETURN(T); END;
      IF S2 = 1 THEN IGCDCF(S1,R2,D2,SB1,RB2); T1:=IPROD(SB1,R1);
         T:=LIST2(T1,RB2); RETURN(T); END;
(*5*) (*general case.*) IGCDCF(R1,S2,D1,RB1,SB2);
      IGCDCF(S1,R2,D2,SB1,RB2); T1:=IPROD(RB1,SB1); T2:=IPROD(RB2,SB2);
      T:=LIST2(T1,T2); RETURN(T);
(*8*) END RNPROD;

FIRST2 accesses the first two elements of a list. LIST2 constructs a list of two elements. IGCDCF computes the gcd (4–th (VAR) parameter) together with the cofactors (5-th and 6-th parameter). IPROD is the product of two integers. The correctness of step 5 is discussed in the summary.

PROCEDURE RNSUM(R,S: LIST): LIST;
(*Rational number sum.  R and S are rational numbers.  T=R+S.*)
VAR   D, E, R1, R2, RB2, S1, S2, SB2, T, T1, T2: LIST;
BEGIN
(*1*) (*r=0 or s=0.*)
      IF R = 0 THEN T:=S; RETURN(T); END;
      IF S = 0 THEN T:=R; RETURN(T); END;
(*2*) (*obtain numerators and denominators.*) FIRST2(R,R1,R2);
      FIRST2(S,S1,S2);
(*3*) (*r and s integers.*)
      IF (R2 = 1) AND (S2 = 1) THEN T1:=ISUM(R1,S1);
         IF T1 = 0 THEN T:=0; ELSE T:=LIST2(T1,1); END;
         RETURN(T); END;
(*4*) (*r or s an integer.*)

        IF R2 = 1 THEN T1:=IPROD(R1,S2); T1:=ISUM(T1,S1);
           T:=LIST2(T1,S2); RETURN(T); END;
        IF S2 = 1 THEN T1:=IPROD(R2,S1); T1:=ISUM(T1,R1);
           T:=LIST2(T1,R2); RETURN(T); END;
  (*5*) (*general case.*) IGCDCF(R2,S2,D,RB2,SB2);
        T1:=ISUM(IPROD(R1,SB2),IPROD(RB2,S1));
        IF T1 = 0 THEN T:=0; RETURN(T); END;
        IF D <> 1 THEN E:=IGCD(T1,D);
           IF E <> 1 THEN T1:=IQ(T1,E); R2:=IQ(R2,E); END;
           END;
        T2:=IPROD(R2,SB2); T:=LIST2(T1,T2); RETURN(T);
  (*8*) END RNSUM;

ISUM denotes the sum of two integers. IGCD denotes the integer gcd. IQ is the integer quotient. The other algorithms are mentioned in the description of RNPROD. The correctness of step 5 is discussed in the summary.

6.2.2 Exercises

1. Write an algorithm to compute the exponential series exp over the rational numbers up to a desired precision ε > 0. With this algorithm compute e = exp(1) up to 50 decimal digits.

The solution to the exercise is discussed in the sequel. The exponential series is defined for complex x by

exp(x) = ∑_{n=1}^{∞} \frac{x^{n}}{n!} .

The exponential series can be approximated by ∑_{n=1}^{N} \frac{x^{n}}{n!} + r_{N+1}(x). Where for the rest we have

r_{N+1}(x) < 2\frac{|x|^{N+1}}{(N + 1)!}.

Let ε > 0 be fixed. We want to approximate exp(x) such that r_{N+1}(x) < ε, therefore the summand must satisfy \frac{|x|^{N+1}}{(N+1)!} ≤ |\frac{x^{N+1}}{(N+1)!}| < \frac{ε}{2}. With this information the algorithm can be formulated as follows:

  PROCEDURE Exp(x,eps);
  (*Exponential function. eps is the desired precision. *)
  VAR   s, xp, ep, i, y: ANY;
  BEGIN
  (*1*) y:=RNINT(1); s:=RNINT(1); i:=0;
        ep:=RNPROD(eps,RNRED(1,2));
  (*2*) REPEAT i:=i+1; xp:=RNRED(1,i);
               y:=RNPROD(y,x); y:=RNPROD(y,xp);

               s:=RNSUM(s,y)
               UNTIL RNCOMP(RNABS(y),ep) <= 0;
        RETURN(s)
  (*9*) END Exp.

The complexity can be estimated as follows: the most expensive operations in the REPEAT– loop are RNPROD(y,x), RNSUM(s,y) and RNCOMP( . ,ep), which have computing times proportional to L(.)^{2}. For the ‘biggest’ product x^{n−1} · x we have t_{RNPROD}^{+} = (nL(x))L(x). For the ‘biggest’ sum (∑_{i=1}^{n−1} \frac{x^{i}}{i!} ) + \frac{x^{n}}{n!} we have t_{RNSUM}^{+} = (nL(x))^{2}. The comparison needs also t_{RNCOMP}^{+} = (nL(x))^{2}. By this the computing time for the exponential series is t_{Exp}^{+} = (nL(x))^{2}. As an example we are going to compute e = Exp(1) with precision ε = \frac{1}{10^{50}} . The sample output follows:

  dig:=50.   Eps:=RNRED(1,IEXP(10,dig)).
  one:=RNINT(1).
  e:=Exp(one,Eps).
  {20 sec} ANS: ((119769761 450433631 444044040 360650700
                 406458113 17125896) (0338539520 159342123
                 356614372 176392732 6300265))
  BEGIN CLOUT("AbsErr = "); RNDWR(Eps,dig); BLINES(0);
        CLOUT("Result = "); RNDWR(e,dig); BLINES(0);
        CLOUT("Result = "); RNWRIT(e); BLINES(0) END.
  AbsErr = 0.000000000000000000000000000000000
             00000000000000001
  Result = 2.718281828459045235360287471352662
             49775724709369996-
  Result = 76384051975228859737656454938414688
           9815927382313633/281001223550575979
           708628521248902313987276800000000

The computation needs 20 seconds on an Atari ST. Then the absolute error, e as decimal fraction and e as rational number are printed. Observe that L(e) = 6 by counting the β–integers from the internal representation of e.

6.3 Floating Point Arithmetic

The arbitrary precision floating point numbers are called floating point numbers for short. We will first discuss the representation of floating point numbers by lists.

Note: Let a ∈ Q, then there exists an integer e ∈ Z and a rational number m ∈ Q with \frac{1}{2} ≤ |m| < 1 such that

a = m · 2^{e}.

In this case e = ⌊log_{2}(|a|)⌋ + 1. The binary precision z of a floating point number is the number of binary digits of the fraction part. We call m′ = ⌊m · 2^{z}⌋ ∈ Z the fraction part (also called mantissa) of the floating point number a and we call e the exponent of a. Definition: List representation of floating point numbers.

0 ∈ Q is represented by the list (0, 0).

a ∈ Q, a ≠ 0 with −β < e < β, is represented by the list (e′, m′). e = e′ ∈ A and m′ ∈ I are represented as atom respectively integer. e, m′ defined as before. For a ∈ Q with e ≤ −β or β ≤ e there is no representation defined.

Recall that β = 2^{ζ} is a power of 2, ζ = 29. The binary precision z is determined from the decimal precision d in the following way. Let

ρ = ⌈log_{β}(10^{d})⌉

then

z = ⌊log_{2}(β^{ρ})⌋ − 1 = \frac{ρ}{ζ} − 1.

The fraction part m′ of a floating point number is then an integer with ⌈log_{2}(|m′|)⌉ = z and so ⌈log_{β}(|m′|)⌉ = ρ. Example: Let d = 20, i.e. the desired decimal precision is 20 decimal digits. Then ⌈log_{β}(10^{20})⌉ = 3 = ρ and we have z = ζρ − 1 = 29 · 3 − 1 = 86.

\frac{1}{2} = \frac{1}{2} · 2^{0} is represented as (0, (0, 0, 134217728)), since e = 0, and ⌊\frac{1}{2} · 2^{z}⌋
= 0β^{0} + 0β^{2} + 134217728β^{2} which is represented by (0, 0, 134217728).
1 = \frac{1}{2} · 2^{1} is represented by (1, (0, 0, 134217728)),
\frac{1}{4} = \frac{1}{2} · 2^{−1} is represented by (−1, (0, 0, 134217728))
and −2 = \frac{−1}{2} · 2^{2} is represented by (2, (0, 0, −134217728)).

6.3.1 Algorithms

The programs of the most important floating point algorithms and their complexity are summarized in the following. Let A be the set of atoms, L be the set of lists, O = A ∪ L be the set of objects, I = {x ∈ O : x represents an element of Z} be the set of integers, R = {x ∈ O : x represents an element of Q} be the set of rational numbers and F = {x ∈ O : x represents a floating point number} be the set of floating point numbers. Let ρ = L(a) denote the β–length of the fraction part m′ of a floating point number a. The length of integers and rational numbers are defined as in the previous section. We will also write L(a) for O(L(a)), i.e. we will not count for constant factors. The computing time functions t, t^{+}, t^{−}, t^{∗} are defined as before in section 5.7.

AP SP RE(n) n ∈ A. The precision of floating point numbers is set to n decimal digits. t^{+} = t_{IEXP}^{+} = n^{2} = O(ρ^{2}), c^{+} = 2n = O(2ρ).

b ← AP F INT (a) a ∈ I, b ∈ F. b = m′2^{e′} is the embedding of the integer a into the floating point numbers. Since a is shifted t^{+} = L(a) + |L(a) − L(b)| = max{L(a), ρ}, c^{+} = ρ, t^{−} = L(a), c^{−} = 0.

b ← AP F RN(a) a ∈ R, b ∈ F. b = m′2^{e′} is the embedding of the rational number a into the floating point numbers. The numerator and denominator of a are converted to floating point numbers, then their quotient is formed. t^{+} = 2t_{APFINT}^{+} + t_{APQ}^{+} = 2 max{L(a), ρ} + ρ^{2}, c^{+} = 2ρ + ρ^{2}.

b ← RNF AP (a) a ∈ F, b ∈ R. b = \frac{m}{2^{−e}} is the the rational number b which corresponds to the floating point number a. b is reduced to lowest terms. t^{+} = t_{IEXP}^{+} + t_{RNRED}^{+} = e^{2} + max\{ρ, \frac{e}{ζ}\}^{2}, c^{+} = e^{2} + max\{ρ, \frac{e}{ζ}\}^{2}.

b ← AP NEG(a) a, b ∈ F. b = −a is the negative of a. The fraction part of a is negated, so t = t_{INEG} = ρ, c = ρ.

s ← AP SIGN(a) a ∈ F, s ∈ {−1, 0, +1}. s = sign(a) is the sign of a. The integer sign of the fraction part of a is determined, so t^{+} = ρ, t^{−} = 1, c = 0.

b ← AP ABS(a) a, b ∈ F. b = |a| is the absolute value of a. The fraction part of a is possibly negated, so t^{+} = t_{APNEG}^{+} = ρ, c^{+} = ρ. t^{−} = 1, c^{−} = 0.

s ← AP CMP R(a, b) a, b ∈ F, s ∈ {−1, 0, +1}. s = sign(a − b) is the sign of the difference of a and b. The fraction part of a and b must be compared if the signs of the fraction parts and the exponents are equal, so t^{+} = ρ, t^{−} = 1, c = 0.

c ← AP P ROD(a, b) a, b, c ∈ F. c = a · b is the product of a and b. The fraction parts of a and b are multiplied the result is then truncated, so t = ρ^{2}, c = ρ^{2}.

c ← AP Q(a, b) a, b, c ∈ F. c = a/b is the quotient of a and b. The fraction part of a is shifted by 2^{z} and then an integer quotient is computed, so t = 2ρ^{2}, c = ρ^{2}.

c ← AP SUM(a, b) a, b, c ∈ F. c = a+b is the sum of a and b. The fraction part of a or b is shifted to bring the decimal points in the same place, then the integers are added and normalized. Let e_{a} and e_{b} be the exponents of a and b respectively. Assume further that |e_{a} − e_{b}| < z, since otherwise nothing is to be done, then t^{+} = t_{IMP2}^{+} + t_{ISUM}^{+} + t_{APFINT}^{+} = L(2^{|e_{a}−e_{b}|}) + 2ρ + 2ρ = O(2ρ). c^{+} = 2ρ, t^{−} = ρ, c^{−} = ρ. c ← AP DIF F (a, b) a, b, c ∈ F. c = a − b is the difference of a and b. b is negated, then

the sum of a and −b is computed. t^{+} = t_{APSUM}^{+}, t^{−} = ρ.

b ← AP EXP (a, n) a, b ∈ F, n ∈ A. b = a^{n} is the n-th power of a (exponentiation). The binary exponentiation method is used as described with IEXP. Since the length of the products are always ρ we have to count the number of products and so t^{+} = log_{2}(n)ρ^{2}.

b ← AP ROOT (a, n) a, b ∈ F, n ∈ A. b = ^{n} \sqrt{a} is the n-th root of |a|. b is computed by Newtons method. The most expensive part is the computation of a^{n}, so t^{+} = log_{2}(n)ρ^{2}.

a ← AP P I() a ∈ F. a = π. π is computed by the method of Salamin using the arithmetic–geometric mean approximation for an elliptic integral representation of π. t^{+} = constρ^{2}, since square roots are computed.

a ← AP READ() a ∈ F. AP READ is be defined as AP F RN(RNDRD()) and the accepted syntax is that of RNDW R.

AP W RIT (a) a ∈ F. The floating point number a is written to the actual output stream. The syntax is:

rat = int "." unsigned-int
              [ "E" unsigned-beta-int ]

This syntax is accepted by RNDRD for input.

This concludes the summary of floating point number arithmetic functions. Note: When the precision of the floating point numbers is changed, then the already existing numbers are not automatically converted to the new precision. The conversion can be accomplished by first converting the floating point number to a rational number. Then change the precision and finally reconvert the rational number to a floating point number. Example: Assume the actual decimal precision is d_{2} and we want to convert numbers which are represented in precision d_{1}. The following algorithm does the conversion:

PROCEDURE Crep(a,d1,d2);
(*Change the representation of the
floating point number a, with precision d1 to
precision d2.*)
VAR   r: LIST;
BEGIN
(*1*) (*set old precision and convert. *)
APSPRE(d1); r:=RNFAP(a);
(*2*) (*set new precision and convert. *)

6.3. FLOATING POINT ARITHMETIC 97

           APSPRE(d2); r:=APFRN(r);
           RETURN(r);
     (*3*) END Crep.

For illustration we list the algorithms APFINT and APSUM in Modula–2 in MAS. The function of the algorithms should be clear from the step comments and the floating point number representation discussed before.

PROCEDURE APFINT(N: LIST): LIST;
(*Arbitrary precision floating point from integer.
The integer N is converted to the arbitrary precision
floating point number A.*)
VAR   A, EL, FL, ML: LIST;
BEGIN
(*1*) (*n=0.*)
      IF N = 0 THEN A:=APCOMP(0,0); RETURN(A); END;
(*2*) (*normalize.*) EL:=ILOG2(N); FL:=EL-1-APPR2; (*1=log2(2).*)
      IF FL >= 0
         THEN ML:=IDP2(N,FL); (*truncate*)
         ELSE ML:=IMP2(N,-FL); (*fill up*) END;
(*3*) (*round.*) ML:=ISUM(ML,1);
      ML:=IDP2(ML,1);
(*4*) (*finish.*) A:=APCOMP(ML,EL); RETURN(A);
(*6*) END APFINT;

APCOMP denotes the composition of an exponent and the fraction part of a floating point number. ILOG2 means the integer logarithm base 2, IDP2 denotes ‘integer division by power of 2’ and IMP2 denotes ‘integer multiplication by power of 2’. All three algorithms exploit the β representation of integers and the fact, that β is itself a power of 2. ISUM denotes integer sum. APPR2 means the number z of binary digits of the representation.

PROCEDURE APSUM(A,B: LIST): LIST;
(*Arbitrary precision floating point sum.
A, B and C are arbitrary precision floating point numbers.
C is the sum of A and B. C=A+B.*)
VAR   C, EL, EL1, EL2, ML, ML1, ML2: LIST;
BEGIN
(*1*) (*A or B zero.*)
      ML1:=APMANT(A); ML2:=APMANT(B);
      IF ML1 = 0 THEN RETURN(B) END;
      IF ML2 = 0 THEN RETURN(A) END;
(*2*) (*check exponent range.*)
      EL1:=APEXPT(A); EL2:=APEXPT(B);
      EL:=MASABS(EL1-EL2);
      IF EL > APPR2 THEN
         IF EL1 > EL2 THEN RETURN(A) ELSE RETURN(B) END;
         END;
(*3*) (*normalize mantisa and add.*)
      EL:=IMIN(EL1,EL2);
      ML1:=IMP2(ML1,EL1-EL); ML2:=IMP2(ML2,EL2-EL);
      ML:=ISUM(ML1,ML2); C:=APFINT(ML);
(*4*) (*shift.*) EL:=EL-APPR2; C:=APSHFT(C,EL);

  (*5*) (*finish.*) RETURN(C);
  (*6*) END APSUM;

APEXPT and APMANT extract the exponent and the fraction part (mantissa) of a floating point number. MASABS determines the absolute value of the argument. IMP2, IMIN and ISUM denote integer multiplication by power of 2, integer minimum and integer sum respectively. APSHFT adds the second parameter to the exponent of the floating point number and checks the exponent for overflow or underflow.

6.3.2 Exercises

1. Let R denote the real numbers. Use Newtons method to write an algorithm to approximate a zero of a function f : R ⟶ R up to a desired precision ε > 0. With this algorithm compute a zero of the function f(x) = x^{2} − 2 up to 50 decimal digits.

The Newton iteration is defined as:

x_{n+1} = x_{n} − \frac{f(x_{n})}{f′(x_{n})}, for x_{n} ∈ R, n ∈ N.

Recall the properties of the Newton iteration: Proposition: Let D = [a, b] ⊂ R be a closed and bounded interval in the real numbers and let f : D ⟶ R be a two times continuous differentiable function on D with

1. f(a) · f(b) < 0,

2. f′(ξ) ≠ 0 for all ξ ∈ D,

3. f′′(ξ) ≥ 0 or f′′(ξ) ≤ 0 for all ξ ∈ D.

If further x_{1} ∈ D, then the Newton sequence {x_{n}}_{n∈N} converges for all x_{0} ∈ (a, b) monotonous against the unique zero ξ of f. With the conditions of the proposition we obtain three terminating conditions:

1. If n is greater than a maximal allowable number of iterations, then condition 1) is not fulfilled in the neighbourhood of x_{0}, i.e. there is possibly no zero near x_{0}.

2. If f′(x_{n}) < ε, then condition 2) is not fulfilled i.e. there is possibly a singularity near x_{n}.

3. |x_{n+1} − x_{n}| < ε i.e. |\frac{f(x_{n})}{f′(x_{n})}| < ε. Then x_{n+1} is an approximation for ξ.

With this information the algorithm can be formulated as follows:

dig:=50. APSPRE(dig).
AbsErr:=APFRN(RNRED(1,IEXP(10,dig/2))).
MaxIter:=100.
PROCEDURE Newton(f,fp,x);
(*Newton iteration. f and fp are functions.
x is the starting value for iteration. A fix point
of x-f(x)/fp(x) is returned. *)
VAR   i, y, z, zp, w: ANY;
BEGIN
(*1*) i:=0; y:=x;
(*2*) WHILE i < MaxIter DO i:=i+1;
            z:=f(y); zp:=fp(y);
            IF APCMPR(APABS(zp),AbsErr) <= 0 THEN
               CLOUT("Derivation becommes zero.");
               BLINES(1); RETURN(y) END;
            w:=APQ(z,zp); y:=APDIFF(y,w);
            IF APCMPR(APABS(z),AbsErr) <= 0 THEN
               RETURN(y) END;
            END;
      CLOUT("Maximal number of iterations reached.");
      BLINES(1); RETURN(y);
(*9*) END Newton.

The maximal allowed number of iterations is set to 100 (variable MaxIter). The absolute error is to be no greater than 10^{−50} (variable AbsErr). If one of the terminating conditions 1) or 2) is reached, a message is printed and the computation is stopped. Otherwise the algorithm terminates by condition 3) and returns an approximation of the zero of f. The function f(x) = x^{2} − 2 with derivation f′(x) = 2x can be formulated as algorithm as follows:

zwei:=APFINT(2).
PROCEDURE E(x);
(*Expression function. An expression is evaluated at x. *)
VAR   y: ANY;
BEGIN
(*1*) (* x**2 - 2 *)
      y:=APEXP(x,2); y:=APDIFF(y,zwei);
      RETURN(y);
(*9*) END E.
PROCEDURE Ep(x);
(*Expression function derivation. The derivation of
an expression is evaluated at x. *)

VAR   y: ANY;
BEGIN
(*1*) (* 2 x *)
      y:=APPROD(x,zwei);
      RETURN(y);
(*9*) END Ep.

A sample output follows:

start:=APFINT(1).
{0 sec} ANS: (1 (0 0 0 0 0 134217728))
b:=Newton(E,Ep,start).
{6 sec} ANS: (1 (202854696 513744239 228305493 18243426
                 133414089 189812531))
BEGIN CLOUT("AbsErr = "); APWRIT(AbsErr); BLINES(0);
      CLOUT("Result = "); APWRIT(b); BLINES(0);
      CLOUT("W2     = "); APWRIT(APROOT(zwei,2));
      BLINES(0) END.
AbsErr = 0.100000000000000000000000000000000000
           000000000000000E-24
Result = 0.141421356237309504880168872420969807
           856967187537694E1
W2     = 0.141421356237309504880168872420969807
           856967187537694E1

First the starting point for the iteration is set to 1. Then the function Newton is called with the function E, its derivation Ep and the starting point as input. The computation needs 6 seconds on an Atari ST. Finally the absolute error, the zero and for comparison the square root of 2 are printed.

Polynomial Systems

Besides the integers and rational numbers the most important data types are polynomials. Polynomials are always represented in some (internal) canonical form and not as general LISP S–expressions. The most important canonical representations are:

• recursive representation,

• distributive (or distributed) representation,

• dense representation.

These representations will be discussed in the following sections. For every representation there are algorithms to read and write polynomials, select parts of polynomials, construct polynomials and to perform basic arithmetic of polynomials (like sum, product, remainder, evaluation, substitution). For more advanced methods like polynomial greatest common divisors or multivariate polynomial factorization there are algorithms for the recursive polynomial repesentation. For Gröbner bases and polynomial ideal decomposition or solving systems of polynomial equations there are algorithms for the distributive polynomial representation. The dense representation is mainly used for algorithms for fast univariate polynomial remainder computations. There is a varity of application dependent ‘fine tunings’ of representations to optimize space, time or programming complexity of the algorithms which are not discussed here (and which are only partly available in the current system). Program libraries are composed from the ALDES / SAC–2 computer algebra system by [Collins et. al. 82], from the DIP polynomial system, which is based on the former, by [Gebauer et. al. 83], [Gebauer et. al. 83a] and from further extensions by [Kredel 87], [Kredel 88a], [Kredel et. al. 88], [Kredel 90a]. The collection of algorithms and global variables are called ‘systems’. The systems are broken into modules according to specific characteristics of subcollections of the algorithms. The available ALDES / SAC–2 polynomial libraries are the following:

ALDES / SAC–2 Polynomial System,

ALDES / SAC–2 Algebraic Number System, ALDES / SAC–2 Polynomial GCD and Resultant System, ALDES / SAC–2 Polynomial Factorization System, ALDES / SAC–2 Real Root System.

The available DIP polynomial libraries are the following:

DIP Common Distributive Polynomial System, DIP Distributive Integral Polynomial System, DIP Distributive Rational Polynomial System, DIP Distributive Arbitrary Domain Polynomial System, DIP Buchberger Algorithm System (Gröbner bases), DIP Polynomial Ideal Dimension System, DIP Zero–dimensional Polynomial Ideal Decomposition System, DIP Zero–dimensional Polynomial Ideal Real Root System.

As extension to the DIP system there are libraries for non–commutative polynomial rings of solvable type:

DIP Non–commutative Rational Distributive Polynomial System, DIP Non–commutative Gröbner Base System, DIP Non–commutative Polynomial Center System.

7.1 Coefficient Rings

Although the representation of polynomials is independent of the representation of the coefficients the algorithms are implemented for specific coefficient rings. Programms that work independently of the coefficient ring start with the program prefix ‘P’ in case of the recursive polynomial representation and with ‘DI’ in case of the distributive polynomial representation. For the recursive representation there are algorithms for the following coefficient rings:

• integral numbers: Z, program prefix ‘IP’ for ‘integral polynomial’

• rational numbers: Q, program prefix ‘RP’ for ‘rational number polynomial’

• integral numbers modulo m: Z/_{(m)}, program prefix ‘MIP’ for ‘modular integral polynomial’

• algebraic numbers over the rational numbers: Q[X]/_{(m_{α}(X))}, where m_{α}(X) denotes the minimal polynomial of α over Q, program prefix ‘AFP’ for ‘algebraic number field polynomial’.

In the section on the recursive polynomial representation we will discuss only polynomials over the integers. For the distributive representation there are algorithms for the following coefficient rings:

• integral numbers: Z, program prefix ‘DIIP’ for ‘distributive integral polynomial’

• rational numbers: Q, program prefix ‘DIRP’ for ‘distributive rational number polynomial’

In the so called ‘distributive arbitrary domain polynomial system’ there are algorithms for further coefficient rings. The common program prefix is ‘DIP’ for ‘distributive arbitrary domain polynomial’.

• integral numbers modulo m: Z/_{(m)},

• algebraic numbers over the rational numbers: Q[X]/_{(m_{α}(X))}, where m_{α}(X) denotes the minimal polynomial of α over Q,

• polynomial functions in n variables over the integers: Z[X_{1},…, X_{n}],

• rational functions in n variables over the integers:

Quot(Z[X_{1},…, X_{n}]) ≅ Q(X_{1},…, X_{n}),

• rational polynomials in n variables modulo a polynomial ideal:

Q[X_{1},…, X_{n}]/_{(m_{1},...,m_{k})}.

In the section on the distributive polynomial representation we will discuss only polynomials over the rational numbers.

7.2 Recursive Polynomial System

Let R be a commutative ring with 1 and let S = R[X_{1},…, X_{r}] denote a (commutative) polynomial ring in r ≥ 0 variables (indeterminates) X_{1},…, X_{r}. S is isomorphic to an univariate polynomial ring over a polynomial ring with one less variable:

S′ = (… ((R[X_{1}])[X_{2}]) …)[X_{r}].

The elements of S′ are univariate polynomials in the main variable X_{r} with coefficients being polynomials in the ring (… (R[X_{1}]) …)[X_{r−1}] when r ≥ 1. Definition: Let A(X_{1},…, X_{r}) ∈ S′, A ≠ 0 and r ≥ 1, then

A(X_{1},…, X_{r}) = ∑_{i=1}^{k} A_{i}(X_{1},…, X_{r−1})X_{r}^{e_{i}}

with A_{i} ≠ 0 for i = 1,…, k and e_{k} > e_{k−1} > … > e_{2} > e_{1}. The recursive representation of A is the list

α = (e_{k}, α_{k},…, e_{2}, α_{2}, e_{1}, α_{1})

where the α_{i} denote the recursive representations of the A_{i} and the e_{i} are non–negative β–integers, i = 1,…, k. If A = 0 then α = 0 and if r = 0 then α is defined by the representation of the base coefficient ring. Notes:

1. The variables X_{1},…, X_{r} are not stored in the representing list. This is different to other computer algebra systems like REDUCE or muMATH.

2. The representation is sparse in the sence, that only coefficients ≠ 0 are stored.

Examples:

1. Let S = Z[X], that is R = Z and r = 1. Let

A = 3X^{4} + 5,

then k = 2 and e_{2} = 4, A_{2} = 3, e_{1} = 0, A_{1} = 5. The representation is then

α = (4, 3, 0, 5).

2. Let S = Z[X, Y], that is R = Z and r = 2. Let

A = (3X + 2)Y^{2} + 5X,

then k = 2 and e_{2} = 2, A_{2} = 3X + 2, e_{1} = 0, A_{1} = 5X. The representation is then

α = (2, (1, 3, 0, 2), 0, (1, 5)).

3. Let S = Q[X, Y], that is R = Q and r = 2. Let

A = \frac{1}{4}X^{2}Y − \frac{3}{5}

then k = 2 and e_{2} = 1, A_{2} = \frac{1}{4}X^{2}, e_{1} = 0, A_{1} = \frac{−3}{5}X^{0}. The representation is then

α = (1, (2, (1, 4)), 0, (0, (−3, 5))).

7.2.1 Algorithms

The programs of the most important recursive polynomial algorithms and their complexity are summarized in the following. First the main complexity numbers are defined and then integral polynomial programs are discussed. As the recursive definition of the polynomial ring and the recursive representation suggests the algorithms will be constructed in the following way:

1. Check for recursion base, case r = 0. Perform the desired operations on the base coefficients.

2. If r ≥ 1 then loop on the exponents in the main variable and call the algorithm recursively on the coefficients. Construct resulting polynomials.

3. Return the results.

The complexity of polynomial algorithms will therefore depend mainly on three factors:

1. the size of the base coefficients,

2. the degree of the polynomials and

3. the number of variables.

These quantities are defined precisely as follows. Let A ∈ S = R[X_{1},…, X_{r}], r ≥ 0, A(X_{1},…, X_{r}) = ∑_{i=1}^{k} A_{i}(X_{1},…, X_{r−1})X_{r}^{e_{i}}. Then deg_{i}(A) denotes the degree of the polynomial A in the variable X_{i} for i = 1,…, r. That is

deg_{i}(A) = \{ \begin{matrix}0 & if A = 0 or r = 0 \\ e_{k} & if i = r \\ max\{deg_{i}(A_{j}) | j = 1,…, k\} & otherwise. \end{matrix}

Further define d = deg(A) = max{deg_{i}(A) | i = 1,…, r}. With L(A) we will denote the maximum of the length of the base coefficients. That is

L(A) = \{ \begin{matrix}L(A_{1}) & if r = 0 \\ max\{L(A_{j}) | j = 1,…, k\} & otherwise. \end{matrix}

The length of integers and rational numbers are defined as in section 5.7. Further let L(A, B) = max{L(A), L(B)}. Since only coefficients ≠ 0 are stored in the polynomials one would like to measure the number of terms in the polynomials. This gives a more precise indication of the complexity in view of the size of the base coefficients. So we define

term(A) = \{ \begin{matrix}1 & if r = 0 \\ ∑_{j=1}^{k} term(A_{j}) & otherwise. \end{matrix}

Clearly it is bounded by

term(A) ≤ deg(A)^{r} = d^{r}.

We will continue to write L(a) for O(L(a)), i.e. we will not count for constant factors. The computing time functions t, t^{+}, t^{−}, t^{∗} are defined as before in section 5.7. Let A be the set of atoms, L be the set of lists, O = A ∪ L be the set of objects, I = {x ∈ O : x represents an element of Z} be the set of integers, P_{r} = {x ∈ O : x represents a multivariate polynomial in r variables } be the set of recursive polynomials, IP_{r} = {x ∈ O : x represents a multivariate polynomial over Z in r variables } be the set of integral polynomials. We will first summarize selector functions which are independent of the base coefficient ring and then turn to the algorithms for integral polynomials. For decomposition and construction of polynomials the list processing functions ADV 2, F IRST 2 and COMP 2 are used and will not be discussed here.

e ← P DEG(A) A ∈ P_{r}, e ∈ A. e = deg_{r}(A) = e_{k} is the degree of A in the main variable. In recursive representation t = 1, c = 0. a ← P LDCF (A) A ∈ P_{r}, a ∈ P_{r−1}. a = ldcf(A) = A_{k} is the leading coefficient

of A. In recursive representation t = 2, c = 0.

A′ ← P RED(A) A ∈ P_{r}, A′ ∈ P_{r}. A′ = red(A) = ∑_{i=1,...,k−1} A_{i}X_{r}^{e_{i}} is the polynomial reductum of A. t = 2, c = 0.

a ← P T RCF (A) A ∈ P_{r}, a ∈ P_{r−1}. a = trcf(A) = A_{1} is the trailing coefficient of A. t^{+} = 2 deg_{r}(A), c = 0. The factor 2 comes in because also the exponents are stored in the representing list of a polynomial.

a ← P LBCF (r, A) A ∈ P_{r}, a ∈ P_{0}. a is the leading base coefficient of A defined

as

a = lbcf(r, A) = \{ \begin{matrix}ldcf(A) & if r = 1 \\ lbcf(ldcf(A)) & if r > 1. \end{matrix}

t = 2r, c = 0.

a ← P T BCF (r, A) A ∈ P_{r}, a ∈ P_{0}. a is the trailing base coefficient of A defined

as

a = tbcf(r, A) = \{ \begin{matrix}trcf(A) & if r = 1 \\ tbcf(trcf(A)) & if r > 1. \end{matrix}

t^{+} = 2r deg(A), c = 0.

We turn now to the discussion of polynomial algorithms which depend on the base coefficient field. Only integer base coefficients will be treated.

s ← IP SIGN(r, A) A ∈ IP_{r}, s ∈ {−1, 0, +1}. s = ISIGN(lbcf(A)) is the sign the leading base coeficient of A. In recursive representation t^{+} = 2r +t_{ISIGN}^{+} = r +L(A), c = 0; t^{−} = 2r +t_{ISIGN}^{−} = r +1 = O(r).

A′ ← IP NEG(r, A) A, A′ ∈ IP_{r}. A′ = −A is the negation of A. t^{+} = term(A) · t_{INEG}^{+} ≤ deg(A)^{r}L(A) = d^{r}L(A), c^{+} = d^{r}L(A).

A′ ← IP ABS(r, A) A, A′ ∈ IP_{r}. If sign(lbcf(A)) = −1 then A′ = −A else A′ = A. t^{−} = t_{IP SIGN}^{−} = r, c^{−} = 0; t^{+} = t_{IP NEG}^{+} ≤ d^{r}L(A), c^{+} = c_{IP NEG}^{+} ≤ d^{r}L(A).

C ← IP SUM(r, A, B) A, B, C ∈ IP_{r}. C = A + B is the sum of A and B. Let l = max{term(A), term(B)}, d = max{deg(A), deg(B)} then t^{+} = l · t_{ISUM}^{+} ≤ d^{r}L(A, B), c^{+} = d^{r}L(A, B).

C ← IP DIF (r, A, B) A, B, C ∈ IP_{r}. C = A − B is the difference of A and B. The computing times are the same as for IP SUM.

C ← IP P ROD(r, A, B) A, B, C ∈ IP_{r}. C = A ∗ B is the product of A and B. Let l = max{term(A), term(B)}, d = max{deg(A), deg(B)} then t^{+} = l^{3} · t_{IP ROD}^{+} ≤ d^{2r}L(A, B)^{2}, c^{+} = d^{2r}L(A, B)^{2}.

IP QR(r, A, B; C, D) A, B, C, D ∈ IP_{r}. C = A/B is the quotient of A and B if it exists, in this case D = 0 and A = CB. (A sufficient condition is that ldcf(B) is a unit in the coefficient ring.) If the quotient does not exist, then D is a polynomial of minimal degree (not neccessarily deg_{r}(D) < deg_{r}(B), but deg_{r}(D) ≤ deg_{r}(A)) such that A = CB + D. Assume that the quotient exists, then the computing time is proportional to that of the product of C and B. The method used is also called trial division, since it is not a priori guaranteed that it succeeds.

C ← IP P SR(r, A, B) A, B, C ∈ IP_{r}. C is the pseudo remainder of A and B. The pseudo remainder allways exists and is defined as

ldcf(B)^{δ} · A = Q · B + C

where δ ≥ deg_{r}(A) − deg_{r}(B) and deg_{r}(C) < deg_{r}(B). The computing time is proportional to that of the product of Q and B.

IP READ(; r, A, V) A ∈ IP_{r}, V a variable list. The polynomial A, the number of variables r and the variable list V are read from the input stream. The accepted syntax is:

coeff = ( integer | poly )
term  = coeff "*" identifier "**" atom
poly  = "(" term { ( "+" | "-" ) term } ")"

With the context conditions:

1. all identifiers in the terms of a polynomial must be equal,

2. the atoms must be non–negative and given in strictly decreasing order.

Note further that there are no optional parts in this definition ! Due to this restricted syntax it is often more convienient to use distributed representation for input and output and to convert the polynomials between the representations.

IP W RIT (r, A, V) A ∈ IP_{r}, V a variable list. The polynomial A is written to the output stream. The output syntax is equal to the input syntax of IP READ.

This concludes the summary of integral polynomial arithmetic functions. For illustration we list the algorithms IPPROD and IPPGSD in Modula–2 in MAS. The function of the algorithms should be clear from the step comments and polynomial representation discussed before.

108 CHAPTER 7. POLYNOMIAL SYSTEMS

PROCEDURE IPPROD(RL,A,B: LIST): LIST;
(*Integral polynomial product.  A and B are integral
polynomials in r variables, r ge 0.  C=A*B.*)
VAR  AL, AP, AS, BL, BS, C, C1, CL, EL, FL, RLP: LIST;
BEGIN
(*1*) (*a or b zero.*)
      IF (A = 0) OR (B = 0) THEN C:=0; RETURN(C); END;
(*2*) (*rl=0.*)
      IF RL = 0 THEN C:=IPROD(A,B); RETURN(C); END;
(*3*) (*general case.*) AS:=CINV(A); BS:=CINV(B); C:=0;
      RLP:=RL-1;
      REPEAT ADV2(BS, BL,FL,BS); AP:=AS; C1:=SIL;
             REPEAT ADV2(AP, AL,EL,AP);
                    IF RLP = 0 THEN CL:=IPROD(AL,BL);
                       ELSE CL:=IPPROD(RLP,AL,BL); END;
                    C1:=COMP2(EL+FL,CL,C1);
                    UNTIL AP = SIL;
             C:=IPSUM(RL,C,C1);
             UNTIL BS = SIL;
      RETURN(C);
(*6*) END IPPROD;

The constructors and selectors for polynomials are the list processing functions COMP2 and ADV2. CINV means the constructive inverse list of its argument. IPROD denotes the integer product. IPSUM is the polynomial sum.

PROCEDURE IPPGSD(RL,A: LIST): LIST;
(*Integral polynomial primitive greatest squarefree divisor.
A is an integral polynomial in r variables.  If A=0 then B=0.
Otherwise B is the greatest squarefree divisor of the primitive
part of A.*)
VAR  B, BP, C, D: LIST;
BEGIN
(*1*) (*a=0.*)
      IF A = 0 THEN B:=0; RETURN(B); END;
(*2*) (*a ne 0.*) B:=IPPP(RL,A);
      IF FIRST(B) > 0 THEN BP:=IPDMV(RL,B);
         IPGCDC(RL,B,BP, C,B,D); END;
      RETURN(B);
(*5*) END IPPGSD;

IPPP denotes the algorithm which computes the primitive part of its argument. IPDMV stands for derivation in the main variable and IPGCDC means greatest common divisor and cofactors. In abuse FIRST is used to determine the degree of the polynomial B.

7.2.2 Exercises

Since in the recursive polynomial system are only clumsy input / output facilities, we defer the exercises to the next section. There we will discuss also the conversions between the polynomial representations.

7.3 Dense Polynomial System

A short description of the data structures of the dense polynomial system is contained in this section. No algorithms and no exercises will be presented. Again let R be a commutative ring with 1 and let S = R[X_{1},…, X_{r}] denote a (commutative) polynomial ring in r ≥ 0 variables (indeterminates) X_{1},…, X_{r}. S is isomorphic to an univariate polynomial ring over a polynomial ring with one less variable:

S′ = (… ((R[X_{1}])[X_{2}]) …)[X_{r}].

The elements of S′ are univariate polynomials in the main variable X_{r} with coefficients being polynomials in the ring (… (R[X_{1}]) …)[X_{r−1}] when r ≥ 1. Definition: Let A(X_{1},…, X_{r}) ∈ S′, A ≠ 0 and r ≥ 1, then

A(X_{1},…, X_{r}) = ∑_{i=0}^{k} A_{i}(X_{1},…, X_{r−1})X_{r}^{i}

with A_{k} ≠ 0. The dense representation of A is the list

α = (k, α_{k},…, α_{1}, α_{0})

where the α_{i} denote the dense representations of the A_{i}, i = 0,…, k. If A = 0 then α = 0 and if r = 0 then α is defined by the representation of the base coefficient ring. Notes:

1. The variables X_{1},…, X_{r} are not stored in the representing list. This is different to other computer algebra systems.

2. The representation is dense in the sence, that all coefficients, even those which are = 0, are stored.

Examples:

1. Let S = Z[X], that is R = Z and r = 1. Let

A = 3X^{4} + 5,

then k = 4, A_{4} = 3, A_{0} = 5 the other A_{i} = 0. The representation is then

α = (4, 3, 0, 0, 0, 5).

2. Let S = Z[X, Y], that is R = Z and r = 2. Let

A = (3X + 2)Y^{2} + 5X,

then k = 2, A_{2} = 3X + 2, A_{1} = 0, A_{0} = 5X. The representation is then

α = (2, (1, 3, 2), 0, (1, 5, 0)).

3. Let S = Q[X, Y], that is R = Q and r = 2. Let

A = \frac{1}{4}X^{2}Y − \frac{3}{5}

then k = 1, and A_{1} = \frac{1}{4}X^{2}, A_{0} = \frac{−3}{5}X^{0}. The representation is then
α = (1, (2, (1, 4), 0, 0), (0, (−3, 5))).

We will not discuss algorithms for the dense polynomial representation since they are only used in special situations.

7.4 Distributive Polynomial System

Again let R be a commutative ring with 1 and let S = R[X_{1},…, X_{r}] denote a (commutative) polynomial ring in r ≥ 0 variables (indeterminates) X_{1},…, X_{r}. The elements of S are sums of monomials, where each monomial is a product of a base coefficient and a term (power product). Definition: Let A(X_{1},…, X_{r}) ∈ S, A ≠ 0 and r ≥ 1, then

A(X_{1},…, X_{r}) = ∑_{i=1}^{k} a_{i}X_{1}^{e_{i1}} ·. . . · X_{r}^{e_{ir}} = ∑_{i=1}^{k} a_{i}X^{e_{i}}

with a_{i} ≠ 0 for i = 1,…, k and natural numbers e_{ij} for i = 1,…, k and j = 1,…, r. X^{e_{i}} is an abreviation for X_{1}^{e_{i1}} ·. . . · X_{r}^{e_{ir}}. k is the number of terms of A. For r > 0 the representation of an exponent vector e_{i} = (e_{i1},…, e_{i,r−1}, e_{ir}) is the list

ϵ_{i} = (e_{ir},…, e_{i2}, e_{i1}).

For r = 0 let ϵ = (), the empty list. The distributive representation of A is the list

α = (ϵ_{k}, α_{k},…, ϵ_{2}, α_{2}, ϵ_{1}, α_{1})

where the α_{i} denote the representations of the a_{i} and the ϵ_{i} are the representation of the exponent vectors, i = 1,…, k. If A = 0 then α = 0 and if r = 0 then α = ((), α_{1}). Notes:

1. The variables X_{1},…, X_{r} are not stored in the representing list. This is different to other computer algebra systems like REDUCE or muMATH.

2. The representation is sparse in the sence, that only base coefficients ≠ 0 are stored.

3. The representation of the exponent vectors is dense in the sence, that also exponents = 0 are stored.

4. The number of variables r can be determined from the length of an exponent vector (representation).

Examples:

1. Let S = Z[X], that is R = Z and r = 1. Let

A = 3X^{4} + 5,

then k = 2 and e_{2} = (4), a_{1} = 3, e_{1} = (0), a_{2} = 5. The representation is then

α = ((4), 3, (0), 5).

2. Let S = Z[X, Y], that is R = Z and r = 2. Let

A = (3X + 2)Y^{2} + 5X = 3XY^{2} + 2Y^{2} + 5X,

then k = 3 and e_{3} = (1, 2), a_{3} = 3, e_{2} = (0, 2), a_{2} = 2, e_{1} = (1, 0), a_{1} = 5. The representation is then

α = ((2, 1), 3, (2, 0), 2, (0, 1), 5).

3. Let S = Q[X, Y], that is R = Q and r = 2. Let

A = \frac{1}{4}X^{2}Y − \frac{3}{5},

then k = 2 and e_{2} = (2, 1), a_{1} = \frac{1}{4}, e_{1} = (0, 0), a_{1} = \frac{−3}{5}. The representation is then

α = ((1, 2), (1, 4), (0, 0), (−3, 5)).

4. Let S = Z[X_{1}, X_{2}, X_{3}, X_{4}, X_{5}], that is R = Z and r = 5. Let

A = 5X_{2}X_{3} + 7X_{1}^{2},

then k = 2 and e_{2} = (0, 1, 1, 0, 0), a_{2} = 5, e_{1} = (2, 0, 0, 0, 0), a_{1} = 7. The representation is then

α = ((0, 0, 1, 1, 0), 5, (0, 0, 0, 0, 2), 7).

Up to now we have assumed that there is a unique way to determine the ordering and the sequence of the terms in a polynomial. In general there are many (contiuum many) total orderings of the set of terms, which are in addition compatible with the multiplication of terms. Such term orders are called admissible. We will no turn to the explicit definition of some important term orders and then give a general characterization by linear forms.

7.4.1 Term Orders

Recall that T denotes the set of terms u = X_{1}^{e_{1}} ·. . . · X_{r}^{e_{r}} = X^{e} where the e_{i}, (i = 1,…, r) are nonnegative integers.

The degree of a term u = X_{1}^{e_{1}} · . . . · X_{r}^{e_{r}} is defined as deg(u) = ∑_{i=1}^{r} e_{i}. For exponent vectors e and l define e − l = (e_{1} − l_{1},…, e_{r} − l_{r}) (an vector of integers). The degree of an exponent vector is defined as deg(e) = deg(X^{e}). For an arbitrary ordering >_{T} on power products we define u >_{T} v ⟺ X^{e} >_{T} X^{l} ⟺ e >_{T} l ⟺ e − l >_{T} 0 = (0,…, 0). We write u <_{T} v if v >_{T} u. The term orderings are called admissible, if they are monoton with respect to multiplication of power products and if 1 = X^{0} is the smallest element. That is

1. For u ∈ T, u ≠ 1 it holds 1 <_{T} u.

2. For u, v, t ∈ T with u <_{T} v it holds ut <_{T} vt.

In the sequel > denotes the natural ordering on the integers.

Buchberger’s Term Order

In 1965 Buchberger gave the definiton of the term ordering used by him for Gröbner bases calculation [Buchberger 65, Buchberger 70]. It can be defined as:

e >_{B} 0 ⟺ deg(e) > 0 or \{ \begin{matrix}deg(e) = 0 \\ and \\ e >_{BL} 0 \end{matrix}

Where >_{BL} is defined in the following way:

e >_{BL} 0 ⟺ \{ \begin{matrix}∃k ∈ \{1,…, r\} \\ with e_{j} = 0 for j = 1,…, k − 1 \\ and e_{k} < 0 \end{matrix}

This ordering was implemented by Winkler in the SAC–1 computer algebra system [Winkler et. al. 85].

DIP Term Order

If the ordering on the power products in distributed representation is choosen to be compatible with the ordering induced by recursive representation one arrives at the so called ’inverse lexicographical’ term order [Gebauer et. al. 83].

e >_{L} 0 ⟺ \{ \begin{matrix}∃k ∈ \{1,…, r\} \\ with e_{j} = 0 for j = r, r − 1,…, k + 1 \\ and e_{k} > 0 \end{matrix}

From this we derive the ‘inverse graduated’ ordering:

e >_{G} 0 ⟺ deg(e) > 0 or \{ \begin{matrix}deg(e) = 0 \\ and \\ e >_{L} 0 \end{matrix}

Which is the same as:

e >_{G} 0 ⟺ (e, deg(e)) >_{L} (0, deg(0))

The examples in [Böge et. al. 86] are based on these orderings. And they are also used in REDUCE 3.3 Gröbner basis package, and by Trinks, [Hearn 87, Trinks 78].

Scratchpad II Term Order

The ‘newdistributed polynomial’ representation in the Scratchpad II System uses the following ‘lexicographical’ termordering:

e >_{S} 0 ⟺ \{ \begin{matrix}∃k ∈ \{1,…, r\} with \\ e_{j} = 0 for j = 1,…, k − 1 \\ and e_{k} > 0 \end{matrix}

[Jenks et. al. 84]. This termordering is also used by Robbiano [Robbiano 85]. With a ‘graduation’ it was also implemented by Schrader [Schrader 76] in ALGOL 60.

e >_{SG} 0 ⟺ deg(e) > 0 or \{ \begin{matrix}deg(e) = 0 \\ and \\ e >_{S} 0 \end{matrix}

Which is the same as:

e >_{SG} 0 ⟺ (deg(e), e) >_{S} (deg(0), 0)

Example

We include an example from Jenks [Jenks et. al. 84], to illustrate the different Gröbner bases with respect to the different term orderings. The computation was done using the SAC–2 computer algebra system on an IBM 3090–200 VF. Let R = Q(A, B) and let S = R[X, Y, Z, T]. Consider the following set of polynomials

 ( ( (A+1)/B X**2 Y - 1 ),
   ( (-B-1)/A X**2 Z + Y**3 ),
   ( - 12 X**2 T + Z**3 ) ).

The Gröbner bases with respect to different term orderings are:

inverse lexicographical term order

            (  X**2 Y -  B /(  A +1 ) )
            (  Z -(  A**2 + A )/(  B**2 + B ) Y**4 )
            (  T -(  A**7 +4 A**6 +6 A**5 +4 A**4 + A**3 )/
                  ( 12 B**7 +36 B**6 +36 B**5 +12 B**4 ) Y**13 )
            executed in 750 milliseconds, 16058 cells used.

inverse graduated term order

            (  X**2 Y -  B /(  A +1 ) )
            (  X**2 Z -  A /(  B +1 ) Y**3 )
            (  X**2 T - 1 / 12  Z**3 )
            (  Y**4 -(  B**2 + B )/(  A**2 + A ) Z )
            (  Y Z**3 - 12 B /(  A +1 ) T )
            (  Y**3 T -(  B +1 )/ 12 A  Z**4 )
            (  Z**7 - 144 A B /(  A B + B + A +1 ) Y**2 T**2 )
            executed in 960 milliseconds, 17154 cells used.

Buchberger total degree term order

            (  X**2 Y -  B /(  A +1 ) )
            (  Y**3 -(  B +1 )/  A  X**2 Z )
            (  Z**3 - 12  X**2 T )
            (  X**4 Z -  A B /(  A B + B + A +1 ) Y**2 )
            (  X**6 T -  A B /( 12 A B +12 B +12 A +12 ) Y**2 Z**2 )
            executed in 530 milliseconds, 7965 cells used.

Note also that the computing times vary for different term orders. A rule of thumb how to obtain ‘optimal’ term orders will be discussed in a seperate section.

7.4.2 Description of Term Orders by Linear Forms

The explicit characterizations of admissible term orders in the previous section are easy to implement and run fast. However there exist much more admissible orders on the set of terms. In this section a uniform way to describe all admissible term orders will be discussed. Although the implementation is much more involved, the running time is still acceptable. The increase of computing time is ‘only’ 50 % in typical examples. Observe that the admissible linear orders <N on exponent vectors e ∈ N^{n} can be extended to admissible linear orders <Q on Q^{n} such that <N=<Q ∩N^{n}.

Let S = R[t] be the polynomial ring in one variable t over the real numbers R. Define a linear order on S by

f > 0 ⟺ ldcf(f) >_{R} 0 and f > g ⟺ f − g >_{R} 0,

for f, g ∈ S. For this order t ∈ S is larger than all elements of R, that is t > a for all a ∈ R. Let AL = {a = (a_{1},…, n) ∈ S^{n}} such that the a_{i}, i = 1,…, n are strictly positive and linear independent over the rational numbers Q (⊂ R). Then it has been shown by Robbiano and Weispfenning that any a ∈ AL induces an admissible linear order < on Q^{n} and any addmissible linear order on Q^{n} is induced by such an a ∈ AL in the following way

x < y ⟺ a · x < a · y,

where x = (x_{1},…, x_{n}), y = (y_{1},…, y_{n}) ∈ Q^{n} and

a · x = ∑_{i=1}^{n} a_{i}x_{i} ∈ S.

[Robbiano 85, Weispfenning 87] For the term orders <_{T} defined in the previous section the correspending a_{T} ∈ AL are as follows:

1. Buchberger’s lexicographical term order <_{BL}:

a_{BL} = (−t^{n−1}, −t^{n−2},…, −t^{2}, −t, −1).

2. Buchberger’s graduated (total degree) lexicographical term order <_{B}:

a_{B} = (t^{n} − t^{n−1}, t^{n} − t^{n−2},…, t^{n} − t^{2}, t^{n} − t, t^{n} − 1).

3. Inverse lexicographical term order <_{L}:

a_{L} = (1, t, t^{2},…, t^{n−2}, t^{n−1}).

4. Inverse graduated (total degree) term order <_{G}:

a_{G} = (1 + t^{n}, t + t^{n}, t^{2} + t^{n},…, t^{n−2} + t^{n}, t^{n−1} + t^{n}).

5. Scratchpad II lexicographical term order <_{S}:

a_{S} = (t^{n−1}, t^{n−2},…, t^{2}, t, 1).

6. Scratchpad II graduated (total degree) lexicographical term order <_{SG}:

a_{SG} = (t^{n−1} + t^{n}, t^{n−2} + t^{n},…, t^{2} + t^{n}, t + t^{n}, 1 + t^{n}).

7. Splitted inverse lexicographical term orders <_{T} = (<_{T_{1}}, <_{T_{2}}) with a_{T_{1}} = (a_{1},…, a_{i}) and a_{T_{2}} = (a_{i+1},…, a_{n}) for some 1 ≤ i ≤ n:

a_{T} = (a_{1} + t^{n′},…, a_{i} + t^{n′}, a_{i+1} + t^{n′+1},…, a_{n} + t^{n′+1}),

where n′ > deg(a_{j}), j = 1,…, n.

8. Varying term orders for <_{T} with a_{T} = (a_{1},…, a_{n}) and where n′ > deg(a_{j}), j = 1,…, n: for i = 0,…, n′ let

a_{T_{i}} = (a_{1} + b_{i}t^{i},…, a_{n} + b_{i}t^{i}),

where b_{i} ∈ R such that a_{T_{i}} ∈ AL. Then we have a_{T_{0}} = a_{T} (b_{0} = 0) and a_{T_{n′}} a total degree term order (b_{n′} = 1).

How these term orders can be specified in MAS is discussed in the next section.

7.4.3 Algorithms

The programs of the most important distributive polynomial algorithms and their complexity are summarized in the following. The main complexity numbers are as defined in the previous section. Only rational polynomial programs are discussed. As the definition of the polynomial ring and the distributive representation suggests the algorithms will be constructed in the following way:

1. Loop on the monomials in the polynomials:

(a) perform operations on the base coefficients,

(b) perform operations on exponent vectors,

Construct resulting polynomials.

2. Return the results.

The complexity of polynomial algorithms will therefore depend mainly on three factors:

1. the size of the base coefficients,

2. the number of terms,

3. the number of variables.

These quantities are as defined in the section on the recursive representation algorithms. The number of terms is now easily determined as half of the length of the polynomial in distributive representation. We will continue to write L(a) for O(L(a)), that means we will not count for constant factors. The computing time functions t, t^{+}, t^{−}, t^{∗} are defined as before in section 5.7. Let A be the set of atoms, L be the set of lists, O = A ∪ L be the set of objects, R = {x ∈ O : x represents an element of Q} be the set of rational numbers, B = {x ∈ O : x represents an element of a base coefficient ring } be the set of base coefficients, D_{r} = {x ∈ O : x represents a multivariate polynomial in r variables } be the set of distributive polynomials, DR_{r} = {x ∈ O : x represents a multivariate polynomial over Q in r variables } be the set of distributive rational polynomials. We will first summarize selector functions which are independent of the base coefficient ring and then turn to the algorithms for rational polynomials.

e ← DIP DEG(A) A ∈ D_{r}, e ∈ A. e = deg_{r}(A) = e_{kr} is the degree of A in the main variable. In distributive representation t = 2, c = 0.

e ← DIP EV L(A) A ∈ D_{r}, e ∈ A^{r}. e is the exponent vector of the highest term. In distributive representation t = 1, c = 0.

a ← DIP LBC(A) A ∈ D_{r}, a ∈ B. a = a_{k} is the leading base coefficient. t = 2, c = 0.

DIP MAD(A; a, e, A′) A, A′ ∈ D_{r}, e ∈ A, a ∈ B. Monomial advance. e = e_{k} is the exponent vector of the highest term. a = a_{k} is the leading base coefficient. t = 2, c = 0.

A′ ← DIP MCP (a, e, A) A, A′ ∈ D_{r}, e ∈ A, a ∈ B. Monomial composition. e beomes the exponent vector of the highest term of A′. a becomes the leading base coefficient of A′. t = 2, c = 2.

A ← DIP F MO(a, e) A ∈ D_{r}, e ∈ A, a ∈ B. Polynomial from monomial. e beomes the exponent vector of the highest term of A. a becomes the leading base coefficient of A. t = 2, c = 2.

DIP BSO(A) A ∈ D_{r}. Polynomial (bubble) sort. The terms (which must be distinct) in A are sorted by the actual term order, the representing list is modified. There are other sorting algorithms which also allow for equal terms in A, but then coefficient arithmetic is required.

We turn now to the discussion of polynomial algorithms which depend on the base coefficient field. Only rational numbers as base coefficients will be treated.

s ← DIRP SG(A) A ∈ DR_{r}, s ∈ {−1, 0, +1}. s is the sign of the leading base coefficient of A. In our representation t^{+} = 2 + t_{RNSIGN}^{+} = 2 + L(A), t^{−} = 2 + t_{RNSIGN}^{−} = 2 + 2 = 4 , c = 0.

A′ ← DIRP NG(A) A, A′ ∈ DR_{r}. A′ = −A is the negative of A. t^{+} = term(A) · t_{RNNEG}^{+} = kL(A), c^{+} = term(A) · c_{RNNEG}^{+} = kL(A). (In distributive representation no operations on exponent vectors are required.)

A′ ← DIRP AB(A) A, A′ ∈ DR_{r}. A′ = |A| is the absolute value of A, that is sign(A′) ≥ 0. t^{+} = t_{DIRP NG}^{+} = kL(A), c^{+} = c_{DIRP NG}^{+} = kL(A); t^{−} = 2 + t_{RNSIGN}^{−} = 2 + 1 = 3, c^{−} = 0.

C ← DIRP SM(A, B) A, B, C ∈ DR_{r}. C = A + B is the sum of A and B. Let l = max{term(A), term(B)}. t^{+} = 2l·t_{RNSUM}^{+} +t_{expon}^{+} = 2lL(A, B)^{2}+ 2lr, c^{+} = 2l · c_{RNSUM}^{+} + c_{expon}^{+} = 2lL(A, B)^{2} + 2l. t_{ecomp}^{+} denotes the time for comparing exponent vectors for term merge. If the set of terms of A and B are disjoint a pure merge is performed. In this case no operations on base coefficients are required and then t^{+} = 2lr, c^{+} = 2l. Although the exponent vectors are processed, they need not be reconstructed, thus c^{+} = 2l instead of 2lr.

C ← DIRP DF (A, B) A, B, C ∈ DR_{r}. C = A − B is the difference of A and B. The computing times are the same as for DIRP SM.

C ← DIRP P R(A, B) A, B, C ∈ DR_{r}. C = A ∗ B is the product of A and B. Let l = max{term(A), term(B)}. t^{+} = l^{2}·t_{RNP ROD}^{+}+t_{expon}^{+} = l^{2}L(A, B)^{2}+ l^{2}r, c^{+} = l^{2}·c_{RNP ROD}^{+}+c_{expon}^{+} = l^{2}L(A, B)^{2}+l^{2}r. The summations of intermediate polynomials are aranged to need only l log_{2}(l) summations of terms.

B ← DIRP NF (P, A) A, B ∈ DR_{r}, P ∈ LDR_{r}. B = normal form_{P} (A) is the normal form or completely reduced from of A with respect to P. Let l = term(A). If A is irreducible then t^{−} = l, c^{−} = l. A one step reduction requires a monomial with polynomial product and one polynomial difference, thus t_{1}^{+} = 2lL(A, P)^{2} + lr, c_{1}^{+} = 2lL(A, P)^{2} + lr. The maximal computing time depends strongly on the used term order. As a worst case estimate consider d = max{deg(HT(p)) | p ∈ P }, d′ = max{deg(p) | p ∈ P } and let d′′ = deg(A). Then B will conatain at most d^{r} terms. In case of a total degree term order probably m = d^{′′r} − d^{r} terms will need reduction. So t^{+} = mt_{1}^{+} = m2lL(A, P) ≤ d^{′′r}2lL(A, P), c^{+} ≤ d^{′′r}2lL(A, P). In case of a lexicographical termorder after each reduction step d′′ may increase so only termination can be assured by Noetherian induction.

Q ← DIRLIS(P) P, Q ∈ LDR_{r}. Q is the irreducible set of P, that is every p ∈ Q is irreducible with respect to Q \ {p}.

G ← DIRP GB(P, t) P, G ∈ LDR_{r}, t ∈ {0, 1, 2}. G is the Gröbner base of P. t is the ‘trace flag’, t = 0 if no intermediate output is requred, t = 1 if the reduced S–polynomials are to be listed and t = 2 for maximal information.

This concludes the summary of distributive rational polynomial arithmetic functions. Finally we will summarize input / output functions and some often needed conversion functions.

P ← P READ() P ∈ LDR_{r}. A list of distributive rational polynomials together with the variable list and a term order are read from the actual input stream. The accepted syntax (with start symbol bunch) is:

bunch    = varlist termord polylist
varlist  = "(" ident { "," ident } ")"
termord  = ( "L" | "G" | linform )
linform  = "(" univpoly { "," univpoly } ")"
polylist = "(" poly { "," poly } ")"
poly     = "(" term { ("+"|"-") term } ")"
term     = power { [ "*" ] power }
power    = factor [ "**" atom ]
factor   = ( rational | ident | "(" poly ")" )

With the context conditions:

1. the atoms must be nonnegative,

2. idents appearing in poly must be declared in varlist,

3. the right most variable in the variable list denotes the main variable,

4. univpoly must be an univariate poly in the variable "T" (=ident) over the rational numbers,

5. linform must be a valid linear form ∈ AL,

6. the number of univariate polynomials must be equal to the number of variables in the variable list.

Examples will be discussed in the exercise section.

P W RIT E(P) P ∈ LDR_{r}. A list of distributive rational polynomials together with the variable list and a term order are written to the actual output stream. The output syntax of the polynomial list is equal to the input syntax of P READ.

B ← DIIF RP (A) A ∈ DR_{r}, B ∈ D_{r}. B = d · A is converted to integral distributive representation, where d is the least common multiple of all denominators of base coefficients of A. Let l = term(A). t^{+} = l · t_{ILCM}^{+} + l · t_{RNP ROD}^{+} = l2L(A)^{2} + lL(A)^{2} = 3lLA()^{2}, c^{+} = l · c_{ILCM}^{+} + l · c_{RNP ROD}^{+} = l2L(A)^{2} + lL(A)^{2} = 3lLA()^{2}.

B ← DIRF IP (A) A ∈ D_{r}, B ∈ DR_{r}. B = \frac{1}{d} · A is converted to rational distributive representation, where d = lbcf(A). Let l = term(A). t^{+} = l · t_{RNRED}^{+} = lL(A)^{2}, c^{+} = l · c_{RNRED}^{+} = lL(A)^{2}.

B ← DIP F P (r, A) A ∈ P_{r}, B ∈ D_{r}. A in recursive representation is converted to B in distributive representation. Let l = term(A). t^{+} = 2lr, c^{+} = 2lr since no operations on base coefficients are required.

P F DIP (A; r, B) A ∈ D_{r}, B ∈ P_{r}. A in distributed representation is converted to B in recursive representation. Let l = term(A). t^{+} = 2lr, c^{+} = 2lr since no operations on base coefficients are required.

This concludes the summary of distributive polynomial functions. For illustration we list the algorithms DIRPNF and DIRLIS in Modula–2 in MAS. The function of the algorithms should be clear from the step comments and the polynomial representation discussed before.

PROCEDURE DIRPNF(P,S: LIST): LIST;
(*Distributive rational polynomial normal form. P is a list
of non zero polynomials in distributive rational
representation in r variables. S is a distributive rational

polynomial. R is a polynomial such that S is reducible to R
modulo P and R is in normalform with respect to P. *)
VAR  AP, APP, BL, FL, PP, Q, QA, QE, QP, R, SL, SP, TA, TE: LIST;
BEGIN
(*1*) (*s=0. *)
      IF (S = 0) OR (P = SIL) THEN R:=S; RETURN(R); END;
(*2*) (*reduction step.*) R:=SIL; SP:=S;
      REPEAT DIPMAD(SP, TA,TE,SP);
             IF SP = SIL THEN SP:=0; END;
             PP:=P;
             REPEAT ADV(PP, Q,PP); DIPMAD(Q, QA,QE,QP);
                    SL:=EVMT(TE,QE);
                    UNTIL (PP = SIL) OR (SL = 1);
             IF SL = 0 THEN R:=DIPMCP(TE,TA,R);
                ELSE
                IF QP <> SIL THEN FL:=EVDIF(TE,QE);
                   BL:=RNQ(TA,QA);
                   AP:=DIPFMO(BL,FL); APP:=DIRPPR(QP,AP);
                   SP:=DIRPDF(SP,APP); END;
                END;
             UNTIL SP = 0;
(*3*) (*finish.*)
      IF R = SIL THEN R:=0; ELSE R:=INV(R); END;
(*6*) RETURN(R); END DIRPNF;

In the outer REPEAT–loop all terms of the polynomial S are considered for reduction. In the inner REPEAT–loop the head terms of polynomials in P are tested if they divide (EVMT exponent vector multiple test) the actual term of S. The IF–statement checks if a divisor was found, in which case the reduction is applied, or if the term was irreducible, in which case the term is copied to the result polynomial R.

PROCEDURE DIRLIS(P: LIST): LIST;
(*Distributive rational polynomial list irreducible set.
P is a list of distributive rational polynomials,
PP is the result of reducing each p element of P modulo P-(p)
until no further reductions are possible. *)
VAR  EL, FL, IRR, LL, PL, PP, PS, RL, RP, SL: LIST;
BEGIN
(*1*) (*initialise. *) PP:=P; PS:=SIL;
      WHILE PP <> SIL DO ADV(PP, PL,PP); PL:=DIRPMC(PL);
            IF PL <> 0 THEN PS:=COMP(PL,PS); END;
            END;
      RP:=PS; PP:=INV(PS); LL:=LENGTH(PP); IRR:=0;
      IF LL <= 1 THEN RETURN(PP); END;
(*2*) (*reduce until all polynomials are irreducible. *)
      LOOP ADV(PP, PL,PP); EL:=DIPEVL(PL); PL:=DIRPNF(PP,PL);
           IF PL = 0
              THEN LL:=LL-1;
                   IF LL <= 1 THEN EXIT END;
              ELSE FL:=DIPEVL(PL); SL:=EVSIGN(FL);
                   IF SL = 0 THEN PP:=LIST1(PL); EXIT END;
                   SL:=EQUAL(EL,FL);
                   IF SL = 1 THEN IRR:=IRR+1; ELSE IRR:=0;

                        PL:=DIRPMC(PL); END;
                     PS:=LIST1(PL); SRED(RP,PS); RP:=PS; END;
             IF IRR = LL THEN EXIT END;
             END;
  (*3*) (*finish. *) RETURN(PP);
  (*6*) END DIRLIS;

In the first step the polynomials in P are made monic (DIRPMC), that is their leading base coefficient is 1. In the main loop in step 2 all polynomials are reduced with respect to the rest of the polynomials. Then several case distinctions are made to check if the polynomial reduced to 0 or if its head term EL, FL was reduced or not. The loop terminates if the number of head term irreducible polynomials (IRR) is equal to the total number of polynomials (LL). (The correctness proof is not totally trivial.)

7.4.4 Exercises

Let S = Q[X_{1}, X_{2}, X_{3}, X_{4}] and let p_{1} = X_{1} + X_{2} + X_{3} + X_{4} ∈ S.

1. Read the polynomial p_{1} in distributive rational representation (using the inverse lexicographical term order).

2. Compute p_{2} = p_{1}^{3} and print the result.

3. Convert p_{1} to distributive integral representation and then to integral recursive representation q_{1}.

4. Compute q_{2} = q_{1}^{3}. Compute the polynomial gcd q of q_{1} and q_{2}. Is q equal to q_{1} ?

5. Convert q_{2} to distributive integral representation and then to distributive rational representation p_{3}. Is p_{2} equal to p_{3} ?

Solution to step 1: We use the function PREAD to input a list of polynomials, namely (p_{1}), in distributive rational representation. Then we take the first element of this list p_{1}. In addition we print the polynomial list. For the term order we use the inverse lexicographical term order L. The polynomial list can be printed by PWRITE. The variable list and the term order are remembered from the last call of PREAD.

  P:=PREAD().
  (x1,x2,x3,x4) L
  (
  ( x1 + x2 + x3 + x4 )
  )
  PWRITE(P).
  p1:=FIRST(P).

The result shows also the polynomials in distributive representation.

Enter polynomial list:
ANS: (((1 0 0 0) (1 1) (0 1 0 0) (1 1)
       (0 0 1 0) (1 1) (0 0 0 1) (1 1)))
Polynomial in the variables: (x1,x2,x3,x4)
Term ordering:  inverse lexicographical.
Polynomial list:
     (  x4 + x3 + x2 + x1 )
ANS: ((1 0 0 0) (1 1) (0 1 0 0) (1 1) (0 0 1 0) (1 1)
      (0 0 0 1) (1 1))

Solution to step 2: The polynomial exponentiation function is called DIRPEX, t is the desired power. To print the result we reconstruct a polynomial list and use PWRITE.

t:=3.
p2:=DIRPEX(p1,t).
Q:=LIST(p2).
PWRITE(Q).

And this is the output of the second and fourth statement:

ANS: ((3 0 0 0) (1 1) (2 1 0 0) (3 1) (2 0 1 0) (3 1)
    (2 0 0 1) (3 1) (1 2 0 0) (3 1) (1 1 1 0) (6 1)
    (1 1 0 1) (6 1) (1 0 2 0) (3 1) (1 0 1 1) (6 1)
    (1 0 0 2) (3 1) (0 3 0 0) (1 1) (0 2 1 0) (3 1)
    (0 2 0 1) (3 1) (0 1 2 0) (3 1) (0 1 1 1) (6 1)
    (0 1 0 2) (3 1) (0 0 3 0) (1 1) (0 0 2 1) (3 1)
    (0 0 1 2) (3 1) (0 0 0 3) (1 1))
 Polynomial in the variables: (x1,x2,x3,x4)
 Term ordering:  inverse lexicographical.
 Polynomial list:
    (  x4**3 +3 x3 x4**2 +3 x2 x4**2 +3 x1 x4**2 +3 x3
    **2 x4 +6 x2 x3 x4 +6 x1 x3 x4 +3 x2**2 x4 +6 x1 x
    2 x4 +3 x1**2 x4 + x3**3 +3 x2 x3**2 +3 x1 x3**2 +
    3 x2**2 x3 +6 x1 x2 x3 +3 x1**2 x3 + x2**3 +3 x1 x
    2**2 +3 x1**2 x2 + x1**3 )

Solution to step 3: DIIFRP converts a distributive rational polynomial into a distributive integral polynomial. PFDIP converts then to a recursive integral polynomial. Since PFDIP is no function, we must use the sequence r:=r. q1:=q1. to display the results.

q1:=DIIFRP(p1).
PFDIP(q1,r,q1). r:=r. q1:=q1.

The resulting output is:

7.4. DISTRIBUTIVE POLYNOMIAL SYSTEM 123

ANS: ((1 0 0 0) 1 (0 1 0 0) 1 (0 0 1 0) 1 (0 0 0 1) 1)
ANS: 4
ANS: (1 (0 (0 (0 1))) 0 (1 (0 (0 1)) 0 (1 (0 1) 0 (1 1))))

Solution to step 4: IPEXP denotes the integral polynomial exponentiation function. r is the number of variables as determined by PFDIP. The polynomial gcd function is called IPGCDC. It computes the gcd(q_{1}, q_{2}) = q and the cofactors of the gcd (that is q_{1} = qy and q_{2} = qz). To display the results we need the sequence q:=q. y:=y. z:=z.

q2:=IPEXP(r,q1,t).
IPGCDC(r,q1,q2,q,y,z).
q:=q. y:=y. z:=z.

The output shows that gcd(q_{1}, q_{2}) = q_{1} as expected. The cofactors are z = p_{1}^{2} and y = 1.

ANS: (3 (0 (0 (0 1))) 2 (1 (0 (0 3)) 0 (1 (0 3)
      0 (1 3))) 1 (2 (0 (0 3)) 1 (1 (0 6) 0 (1 6))
      0 (2 (0 3) 1 (1 6) 0 (2 3))) 0 (3 (0 (0 1))
      2 (1 (0 3) 0 (1 3)) 1 (2 (0 3) 1 (1 6) 0 (2 3))
      0 (3 (0 1) 2 (1 3) 1 (2 3) 0 (3 1))))
ANS: (1 (0 (0 (0 1))) 0 (1 (0 (0 1)) 0 (1 (0 1) 0 (1 1))))
ANS: (0 (0 (0 (0 1))))
ANS: (2 (0 (0 (0 1))) 1 (1 (0 (0 2)) 0 (1 (0 2)
      0 (1 2))) 0 (2 (0 (0 1)) 1 (1 (0 2) 0 (1 2)) 0
      (2 (0 1) 1 (1 2) 0 (2 1))))

Solution to step 5: To suppress unwanted output we use a BEGIN–block. DIFIP converts a recursive polynomial to a distributive polynomial and DIRFIP converts to distributive rational representation. The resulting polynomial is put into a list and writen by PWRITE. Finally we test the equality of p_{2} and q_{3} with the function EQUAL.

BEGIN p3:=DIPFP(r,q2);
      p3:=DIRFIP(p3);
      Q:=LIST(p3);
      PWRITE(Q);
      IF EQUAL(p2,p3) = 1 THEN CLOUT("equal")
                          ELSE CLOUT("not equal") END;
      END.

The resulting output is as follows:

Polynomial in the variables: (x1,x2,x3,x4)
Term ordering:  inverse lexicographical.
Polynomial list:
        (  x4**3 +3 x3 x4**2 +3 x2 x4**2 +3 x1 x4**2 +3 x3
        **2 x4 +6 x2 x3 x4 +6 x1 x3 x4 +3 x2**2 x4 +6 x1 x
        2 x4 +3 x1**2 x4 + x3**3 +3 x2 x3**2 +3 x1 x3**2 +
        3 x2**2 x3 +6 x1 x2 x3 +3 x1**2 x3 + x2**3 +3 x1 x
        2**2 +3 x1**2 x2 + x1**3 )
equal

This concludes the discussion of the exercises.

7.5 Interface to the MAS Language

In section 7.4.3 on algorithms for distributive polynomials we introduced the procedures P READ and P W RIT E. These procedures perform conversions between strings (input / output streams) and (lists) of distributive rational polynomials. In this section we will discuss mainly two other conversion procedures:

• P OLY converts a list of MAS expressions to a list of distributive rational polynomials, if the MAS expressions have a meaning as polynomials.

• T ERM converts a list of distributive rational polynomials to a (quoted) MAS expression, if the polynomials have a meaning as MAS expression.

These two procedures improve the interactive usage of the distributive polynomial system. As a distinguishing feature the user of P OLY need no more worry about specifying a variable list, since all variables in the expessions are automaticaly added to the variable list, if not allready there. Acompanying procedures are available which set the desired term order and the variable list. Recall some definitions: Let L be the set of lists, O be the set of objects, S = {x ∈ O : x represents a S–expression } be the set of S–expressions (they are the output of the MAS parser), DR_{r} = {x ∈ O : x represents a multivariate polynomial over Q in r variables } be the set of distributive rational polynomials. The interface functions are defined as follows:

P ← P OLY (p_{1},…, p_{n}) p_{i} ∈ S for i = 1,…, n and P ∈ LDR_{r}. The MAS expressions p_{i} are converted to distributive rational polynomials. All variables occuring in the p_{i}’s, which are not in the system variable list are added to it as small variables. The actual defined term order is used. The syntax definition of P OLY is:

                     ident ":=" "POLY(" expr { "," expr } ")"

Where expr is an ordinary MAS expression which is interpretable as a polynomial over the rational numbers. That is the following context conditions apply:

1. Only the operators "+", "-", "*", "**", "^" and "/" may appear.

2. The division operator "/" may only by used between numbers (atoms).

3. String constants may occur and (the string contents) are interpreted as rational numbers.

4. The identifiers occuring in expr are per definition disjoint to identifiers used as MAS variables even if they have the same name.

5. No function names may apear in the MAS expressions.

P OLY is implemented by DIP 2SY M.

T ← T ERM(P) P ∈ LDR_{r} and T ∈ S. P is a list of distributive rational polynomials. T is a quoted list of S–expressions, that is a list of terms, which are marked that they are not to be evaluated by the MAS interpreter. For the variable names the names from the actual variable list are used. T ERM is implemented by SY M2DIP.

V′ ← DIP V DEF (V) V, V′ ∈ L. V and V′ are variable lists. The variable list is stored in the global variable V ALIS. V becomes the new variable list, the old variable list V′ is returned.

t′ ← DIP T ODEF (t) t, t′ ∈ L. t and t′ are term order indicators as defined in the global variable EV ORD. t becomes the new term order, the old term order t′ is returned. Possible values for t are:

1 invers lexicographical term order ascending order,

2 invers lexicographical term order descending order, 2 corresponds to the term order letter "L" in P READ,

3 invers graded lexicographical term order ascending order,

4 invers graded lexicographical term order descending order, 4 corresponds to the term order letter "G" in P READ,

5 lexicographical term order ascending order,

6 lexicographical term order descending order,

7 total degree Buchberger lexicographical term order ascending order,

8 total degree Buchberger lexicographical term order descending order,

L a linear form, L is a list L = (l_{1},…, l_{n}) where each l_{i} ∈ IP_{1}, i = 1,…, n is an univariate recursive integral polynomial.

Since the argument expressions to P OLY are not evaluated, there is no way substitute a value for a variable in such an expression. (Substitution in polynomials can only performed by the library functions like DIRP SM or DIRP SV.) This is different to other computer algebra systems like REDUCE where the polynomial variables are identified with the programming language variables. The reason for this behavior lies in the MAS view of polynomials: they are constants from some algebraic structure and do not belong to the programming (meta) language. Examples: Let S = Q[X_{1}, X_{2}, X_{3}, X_{4}] and let p, q ∈ S, p = X_{1} + X_{2} + X_{3} + X_{4}, q = 3/4X1^{2}. We will first discuss some examples for the use of P OLY, then of T ERM and finaly some examples for DIP V DEF and DIP T ODEF.

       P:=POLY(x1+x2+x3+x4).
       Variable(s) added to VALIS:  x4, x3, x2, x1
       ANS: (((1 0 0 0) (1 1) (0 1 0 0) (1 1)
              (0 0 1 0) (1 1) (0 0 0 1) (1 1)))
       p:=FIRST(POLY( x1 + x2 + x3 + x4 )).
       ANS: ((1 0 0 0) (1 1) (0 1 0 0) (1 1)
             (0 0 1 0) (1 1) (0 0 0 1) (1 1))
       q:=SECOND(POLY( x1 + x2 + x3 + x4, 3/4 x1^2 )).
       ANS: ((0 2 0 0) (3 4))

In the first example the variables x1, x2, x3, x4 have not been in the variable list. A message is printed that they are added to the variable list. Note that the order of the (self detected) variables can not be precisely determined, since it depends on the experssion tree structure od the parsed MAS expression. If the order is important use DIP V DEF to set the variables explicitly. Observe that P OLY allways produces a list of distributive polynomials. So in order to obtain one polynomial any list selector function can be used. The operands of "/" must be atoms, so 3/4 is ok.

       P:=POLY( "11111/33" ).
       ANS: (((0 0 0 0) (11111 33)))

String constants can be used in P OLY. The string contents are interpreted as rational numbers (read by RNDRD).

       P:=POLY( (x1+x2)^2 ).
       ANS: (((2 0 0 0) (1 1) (1 1 0 0) (2 1)
              (0 2 0 0) (1 1)))

During the conversion from MAS expressions the distributive polynomials are expanded (or distributed as their name suggests). In the opposite direction we will convert P back to a MAS expression.

       T:=TERM(P).
       ANS: QUOTE(((x1^2+2*x1*x2)+x2^2))

Observe that the MAS expressions have a tree structure, which is visible by the (useless) inner parenthesis around the first two summands.

       T:=TERM( POLY( 3/4 ) ).
       ANS: QUOTE((3/4))

This shows, that atoms are printed correctly, however integers are not printed correctly:

       T:=TERM( POLY( "111111111111111111111111111111/2" ) ).
       ANS: QUOTE(((197423559 458992985 3)/2))

Lists of atoms are not printed as integers but as lists of atoms. Some further examples for the use of DIP V DEF and DIP T ODEF.

       DIPVDEF(LIST("x4", "x9", "x12", "x3")).
       ANS: ((62 1) (62 2) (62 3) (62 4))

Polynomial variable names can be specified as character strings. "x3" now becomes the new main variable. The old variable list is returned. To extend (or modify) an existing variable list any list processing function can be used.

       V:=DIPVDEF(SIL).
       ANS: ((62 4) (62 9) (62 1 2) (62 3))
       V:=CCONC(V,LIST("x5", "x6", "x7", "x8")).
       ANS: ((62 4) (62 9) (62 1 2) (62 3)
             (62 5) (62 6) (62 7) (62 8))
       DIPVDEF(V).
       ANS: ()

A final example is concerned with selection of term orders.

       DIPTODEF(6).
       ANS: 2

This call of DIP T ODEF switches to lexicographical term order. The old term order was 2 = inverse lexicographical. Setting a linear form defined term order is a bit more involved since there is at the moment no function witch converts a list of rational distributive polynomials into a list of integral recursive polynomials. But this will soon be available. This concludes the overview of the MAS language to distributive polynomial interface.

7.6 Appendix: Optimization of the Term Order

In most applications the computating time for a Gröbner Basis is strongly dependend on the chosen variable ordering and term ordering. (See the example below, table 7.6.) To find an ‘optimal’ variable ordering one looks at the reduced univariate polynomials:

Definition: Let f(x_{1},…, x_{r}) ∈ R, then the reduced univariate polynomial corresponding to f for the variable x_{i}(1 ≤ i ≤ r) is defined by:

p_{i}(x_{i}) = g(1, ..., 1, x_{i}, 1, ..., 1) ∈ N[x_{i}]

with g = ∑ x^{(i)} when f = ∑ a_{(i)}x^{(i)}. The reduced polynomial for a set of polynomials is the sum over all reduced polynomials corresponding to the elements of the set. Experience: Tests for computing times of Gröbner bases and factorizing of multivariate polynomials have shown: The variable ordering is optimal if

p_{1}(x) ≥ … ≥ p_{r}(x).

where the univariate polynomials are ordered according to the inverse lexicographical ordering of their coefficient vectors, that means:

h(x) > 0 ⟺ ldcf(h) > 0 and h(x) > k(x) ⟺ h(x) − k(x) > 0

The computation of the reduced univariate polynomials itself and the reordering of the variables is not much time consuming. So this optimization will in many cases lead to faster Gröbner bases computation. There is an algorithm DIP V OP in the distributive polynomial system which does this kind of term order optimization. Its specification is

DIP V OP (P, V; P′, V′) with P, P′ ∈ D_{r} and V, V′ are variable lists. The representation of the polynomials in P and the variable list V are changed according to the optimization heuristics. P′ is the new polynomial list and V′ is the new variable list.

M ← DIP DEM(p) for one polynomial p ∈ D_{r}, and

M ← DIP LDM(P) for a list of polynomials P ∈ LD_{r} determine the tuples of reduced univariate polynomials M ∈ LIP_{1}.

Example: To demonstrate the influence of the term order on the computation of Gröbner bases we include the following example of an ideal generated by 7 polynomials in 6 variables [Trinks 78]. Let R = Q, S = R[B, S, T, Z, P, W] and let the polynomials be

      ( + 45 P + 35S -165B -36 ,
        + 35 P +40 Z + 25 T -27 S ,
        + 15 W + 25 P S + 30 Z - 18 T - 165 B**2 ,
        - 9 W + 15 P T + 20 Z S ,
          W P + 2 Z T - 11 B**3 ,
        99 W - 11 S B + 3 B**2 ,
        B**2 + 33/50 B + 2673/10000   )

variable  time  time
ordering term order = L term order = G
BSTZPW  1.95  10.92
SBTZPW  27.99  16.37
STBZPW  110.27  18.74
STZPBW  115.35  16.37
STZPWB  247.03  20.81
SZPWBT  67.68  19.78
PWBTSZ  103.16  20.61
ZWBSTP  > 3 600.00  32.31
TZPWBS  tfc  50.50
ZPWBST  > 3 600.00  39.32
PWBSTZ  37.18  20.88
WBSTZP  34.98  10.81

Computing time in seconds on IBM 370/168. ’tfc’ = ’to few cells reclaimed’, that means not enough storage was available. From [Böge et. al. 86].

Table 7.1: Computing Times for Different Term Orders

In table 7.6 the dependence is clearly visible. The reduced univariate polynomial for variable B has degree 3, so a term order where B is smaller than all other variables will be most desirable. Observe that as more right B stands in the variable list as worst become the computing times. Note that especially the inverse lexicograpbical term order is very sensitive against reordering of variables, the inverse graduated term order is less sensitive. However in some applications (like ideal elimination theory) Gröbner bases are required with respect to the inverse lexicographical term order .

The ALDES Language

This chapter contains the ALDES language description. The ALDES language has been defined by R. Loos in [Loos 76]. We describe the revised version as distributed in 1988. The parser has been implemented by K. Rieger. Only the the syntax of the language and notes on differencies to the FORTRAN implementation of ALDES are given. The ALDES parser is invoked via the PRAGMA(ALDES). switch. Then a collection of ALDES algorithms is read until the ALDES end of file mark ‘||’ is encountered. ALDES algorithms can be executed as normal MAS algorithms from the MAS interpreter. In the following sections we discuss first the lexical conventions and then the language syntax.

8.1 Lexical Conventions

The ’atomic’ constituents of the language are characters and tokens (character sequences with special meaning).

8.1.1 Character Set

The character set of ALDES is the same as the MAS character set. It consists of the

 digits 0123456789
 letters aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
 others .,=+-*/$()␣!"#%&':;<>?@[\]^_`{}|~

The number of characters is denoted by χ (= 95 here).

8.1.2 Tokens

Lexical tokens of the language are:

     #  <  >  =  <=  >=
     +  -  *  /  ^
     ~  \/  /\
     (  )  [  ]  {  }  ,  .  ;  :
     $  :=  ,...,  ||
     keyword  number  identifier
     string  char  comment

Characters not contained in this list of tokens may only appear in strings and comments. The keywords are:

if, then, else, while, do, for, repeat, until, case, of,

return, print, goto, go to,

safe, global, array, const, pragma, intrinsic.

The meanings of most of the tokens and keywords should be ’as expected’ and are discussed later. At this place we will only say some words on numbers, identifiers, strings and comments.

8.1.3 Numbers

Numbers may be only so called β–integers as in the MAS language.

8.1.4 Identifiers

Identifiers are used as names of variables and names of procedures. The character sequence of an identifier must start with a letter and may be followed by digits and letters. Identifiers are case sensitive, i.e. upper case and lower case letters are distinct. The length of identifiers is restricted by the requirement that they must fit on one input line. Example: NIL, p123, AL9, XSH, AlongName. Ornamented identifiers are not supported by the ALDES parser. Naming conventions are as discussed in the MAS language section.

8.1.5 Strings

Character sequences enclosed in double or single quotes are called strings. Within the quotes any character from the character set may appear. Example:

     "this is a string" denotes the string this is a string,

"'" denotes the string ', '"' denotes the string ", "x'7""'" denotes the string x'7"'

Strings are internally represented as lists of numbers (β–integers). So all list operations are applicable to strings, e.g. concatenating, reversing etc.

8.1.6 Comments

Comments are sequences of characters enclosed in [ and ]. Comments may be nested, i.e. the comment character sequence may contain pairs of [, ]. Comments can appear everywhere except in other tokens.

8.1.7 Blanks

Blanks can appear everywhere except in numbers, identifiers, keywords or multiple letter tokens. Characters in input lines which do not belong to the MAS character set are converted to blanks. ASCII characters like CR (return), LF (line–feed), EOL (end–of–line) are ignored during input form data sets.

8.2 Syntax

In this section we discuss the ALDES language syntax. First we give the complete syntax diagram and the list of syntax errors.

8.2.1 Syntax Diagram

The syntax definition is given in extended BNF notation. That means name denotes syntactic entities, {} denotes (possibly empty) sequences, () denotes required entities, | denotes case selection and [] denotes optional cases. Terminal symbols are enclosed in double quotes and productions are denoted by =. The syntax diagram is listed in table 8.2.1. For ALDES program constructs, which have no or a different meaning in the MAS environment, a syntax warning message is generated. These are intrinsic, pragma, const, global and safe. global declarations in algorithms are completely ignored since the parser checks for lexicalscope of the variables. safe declarations are treated as VAR declarations in MAS. There is no distingtion between ‘safe’ and ‘unsafe’ variables. For undeclared variables VAR declarations are generated. The syntax errors and syntax warnings detected by the parser are summarized in tables 8.2.1 and 8.3. If a syntax error is detected one of the error messages is displayed followed by the actual input line where the last character read is underscored. However this last character is one character and one lexical token to far. That means the syntax error is caused by one token behind. Error repair is limited to skipping tokens until something meaningful is found. In case syntax errors are detected, the execution of the program is totally suppressed, that means no executable code is generated. If a syntax warning is given execution proceeds.

8.2. SYNTAX 133

program      = { declaration | algorithm } "||"
algorithm    = header { declaration } "(" number ")" statementseq
               { "." "(" number ")" statementseq } "||"
header       = ident ( "(" identlist [ ";" identlist ] ")" |
                       ":=" ident "(" identlist ")" )
statementseq = statement { ";" statement }
statement    = ( "print" string |
               ident [ [ "[" termlist "]" ] ":=" expression |
                       "(" termlist [ ";" termlist ] ")" ] |
               "if" expression "then" statement
                             [ "else" statement ] |
               "while" expression "do" statement |
               "repeat" ( statementseq "until" expression |
                "{" statementseq "}" [ "until" expression ] ) |
               "for" ident ":=" expression [ "," expression ]
                     ",...," expression "do" statement |
               "case" expression "of" "{"
                   { termlist "do" statement ";" } "}" |
               "return" [ "(" [ expression ] ")" ] |
               ( "goto" | "go to" ) ( number | "(" number ")" ) |
               "{" statementseq "}" )
expression    = [ prefixop ] part { oper part }
prefixop      = ( "~" | "+" | "-" )
oper          = ( "+" | "-" | "*" | "/" | "^" |  "=" | "#" |
                  "<" | ">" | "<=" | ">=" | "\/" | "/\" )
part          = ( number | string | char | "$" ident |
                  ident [ ( "(" [ termlist ] ")" |
                            "[" termlist "]" ) ] |
                "(" expression  { "," expression } ")" )
termlist      = expression { "," expression }
identlist     = ident { "," ident }
variable      = ident [ "[" termlist "]" ]
declaration   = ( "global"    variable { "," variable } |
                  "safe"      variable { "," variable } |
                  "array"     ident "[" termlist "]"
                              { "," ident "[" termlist "]" } |
                  "const"     variable "=" expression }
                              { "," variable "=" expression } |
                  "pragma"    variable "=" expression
                              { "," variable "=" expression } |
                  "intrinsic" identlist ) "."
string        = ('"' {character} '"' | "'" {character} "'")
char          = "'" character "'"
ident         = letter { letter | digit }
number        = digit { digit }

Table 8.1: ALDES Syntax Diagram

1 identifier expected
2 ) expected
4 factor expected
8 declaration expected
9 = expected
10 , or . expected
11 [ expected
12 ] expected
13 string expected
14 number expected
15 to expected
16 then expected
17 of expected
18 { expected
19 ; or } expected
20 do expected
22 ,..., expected
23 , or ,..., expected
24 ( expected
25 || expected
26 statement expected
27 } expected
29 ; or until expected
30 and or or un–expected
31 / un–expected
32 | un–expected
33 = or := expected
34 expression expected
35 , or identifier expected
36 declaration or algorithm expected
37 . expected

Table 8.2: ALDES Syntax Error Messages

2 intrinsic declaration unsupported
3 pragma declaration unsupported
6 . in header unsupported
7 array as function unsupported
8 global declaration in algorithm unsupported
9 const declaration unsupported

Table 8.3: ALDES Syntax Warning Messages 8.3. EXAMPLE 135

The program constructs goto and arrays are only simulated, so they will be interpreted slowly. There exists no ALDES main program; any ALDES procedure can be executed as a MAS procedure, can call MAS procedures and can be called from MAS procedures.

8.3 Example

We list a sample ALDES input:

PRAGMA(ALDES).
                    b:=AFINV(M,a)
[Algebraic number field inverse.  a is a nonzero
element of q(alpha) for some algebraic number alpha.  M is the
rational minimal polynomial for alpha.  b=1/a.]
(1)  a1:=M;  a2:=a;  v1:=0;  r:=RNINT(1);
     v2:=LIST2(0,r);  repeat {  c:=RNINV(PLDCF(a2));
     v2:=RPRNP(1,c,v2);  if PDEG(a2) = 0 then { b:=v2;
     return };  a2:=RPRNP(1,c,a2);  RPQR(1,a1,a2;q,a3);
     v3:=RPDIF(1,v1,RPPROD(1,q,v2));  a1:=a2;  a2:=a3;
     v1:=v2;  v2:=v3  }||
                    c:=AFPROD(M,a,b)
[Algebraic number field element product.  a and b are elements of
q(alpha) for some algebraic number alpha.  M is the minimal
polynomial of alpha.  c=a+b.]
(1)  cP:=RPPROD(1,a,b);  RPQR(1,cP,M;q,c)||
                    s:=AFSIGN(M,I,a)
[Algebraic number field SIGN.  M is the integral minimal polynomial
of a real algebraic number alpha.  I is an acceptable isolating
interval for alpha.  a is an element of q(alpha).  s=SIGN(a).]
     safe sS,sP,n,sH,s.
(1)  [a rational.]  if a = 0 then { s:=0;  return};
     if PDEG(a) = 0 then { s:=RNSIGN(SECOND(a));
     return }.
(2)  [Obtain the greatest squarefree divisor of an integral
     polynomial similiar to a.]  IPSRP(1,a;r,aP);  sS:=RNSIGN(r);
     aS:=IPPGSD(1,aP);  IS:=I;  FIRST2(IS;u,v);  sP:=0.
(3)  [Obtain an isolating interval for alpha containing no roots
     of als.  RETURN SIGN(a(alpha)). ]
     repeat {  n:=IUPVSI(aS,IS);  w:=RIB(u,v);
     if n = 0 then {s:=IUPBES(aP,w);
     s:=sS  *  s;  return };  if sP = 0 then sP:=IUPBES(M,v);
     sH:=IUPBES(M,w);  if sH # sP then u:=w
     else { v:=w;  sP:=sH };  IS:=LIST2(u,v)  }||
                    c:=AFSUM(a,b)
[Algebraic number field element sum.  a and b are elements of

  q(alpha) for some algebraic number alpha.  c=a+b.]
  (1)  c:=RPSUM(1,a,b);  return||
  || (* *)

The PRAGMA(ALDES) statement switches to the ALDES parser. Then commes a sequence of ALDES algorithms. The ALDES parser is terminated by the end of file mark ||. The dummy (MAS) comment might be neccessary in some situations to stop the scanner from reading the next token. The ornamented identifiers are denoted according to the implementation ALDES transliteration scheme. For example a* = aS, s^= sH and s' = sP. The used library functions (like RNINT or RPRNP) must be accessible from the MAS interpreter to be executable.

System Commands

In this chapter we summarize display commands, pragmas, how to access the operating system and command line parameters.

9.1 Information Display

The first important system commads are concerned with displaying information on the system configuration and what is going on during computations. There are tree groups of commands: 1) for configuration display, 2) for specification display and 3) for environment display. Configuration display commands show which external functions or predefined functions are available. Specification display commands show defined units, sorts, variables, signatures and generic items. Environment display commands show storage usage, stream usage, symbol table contents, and top level variable bindings. A summary of this commands follows:

HELP lists all information available on defined and accessible functions. That is all compiled procedures and functions, all interpreter procedures and functions and all signature definitions.

EXTPROCS lists all accessible external compiled functions and procedures.

SIGS lists all signature definitions of functions.

GENERICS lists all generic function definitions.

VARS lists all defined variables together with the type information.

SORTS lists all defined sorts names.

UNITS lists all defined unit names.

BIOS displays information on stream I/O usage, GCM displays information on the storage usage,

SYMTB displays the LISP symbol table including properties,

DUMPENV lists all variable bindings, that is all variables in the top level environment together with their current value. The output is in LISP syntax:

                    (SETQ var value)

so it should be possible to dump the variables to a disk file, and later read them in again. Declarations are lost.

LISTENV same as DUMPENV except output is in Modula–2 like syntax. Note that probably some constructs can not be read in again.

PRAGMA(SHOW) displays the actual pragma settings.

Note that all display information can be printed to a file using output stream setting.

9.2 Pragmas

Besides displaying information the MAS system provides commands to modify the state of the running MAS program. These settings are organized by the PRAGMA command. The pragmas come in two groups, one for the selection of the actual parser and one for debuging purposes. The general syntax of the pragma command is as follows:

       PRAGMA(subcommand).

Where subcommand is one of the commands discussed in the sequel. If an unknown subcommand is entered, then a list of all available pragmas is displayed. A list of the actual pragma settings is available with the SHOW subcommand. The subcommands which modify and select the parser are as follows:

MODULA input / output is in Modula–2 like syntax, that means the MAS parser for the MAS language is used.

LISP input / output is in LISP syntax.

ALDES input is in ALDES–2 syntax, that means the ALDES parser is used to read the next input until the ALDES end of file mark ‘||’ is encountered.

GENPARSE for the artihmetical operators the generic names or LISP names are generated. The correspondence is as shown in figure 9.1.

The following subcommands turn flags ON and OFF:

operator LISP name generic name

                       +     ADD        SUM
                       -     SUB        DIF
                       -     SUB        NEG
                       *     MUL        PROD
                       /     QUOT       Q
                       %     REM        REMAIN

                                        REZIP

                       ^POW        EXP

Figure 9.1: Generic Operators and Functions

TIME if ON the times for parsing, evaluation and printing are shown (initial OFF),

TRACE if ON the arguments of the evaluator are displayed, may produce messy output (initial OFF),

DEBUG if ON prints the result produced by the actual parser (initial OFF)

FUSSY switches to strong(er) type checking as usual.

SLOPPY switches to weak(er) type checking.

The actual setting of these flags can be displayed with the SHOW subcommand.

9.3 Operating System

With EXIT it is possible to leave the MAS main program and return to the operating system. On some computers the MAS system further provides access to the operating system during a running MAS session. Most important is the possibility to call an editor from within MAS. The commands are summarized as follows:

EXIT Leaves the MAS system.

DOS("prog parms") Calls the program ‘prog’ with the parameters ‘parms’. The meaning of the string depends on the operating system.

EDIT("data set name") Edits the specified data set. The editor is expected to be ‘EDITOR.PRG’ on the current directory. The editor on disk is ‘microEMACS 3.9’. The data set name string is prefixed by the string "␣@MAS.RC␣" which specifies the startup file for EMACS to be ‘MAS.RC’.

USEEMS Activates the usage of the EMS storage on IBM PC’s if available.

9.4 Input / Output

The MAS input / output is organized in so called streams. A discussion of streams and their usage is conatined in the chapter on the MAS language 3. In this section we give only a summary of the functions. The stream switching functions are:

IN("stream") the current input stream is switched to the stream ‘stream’,

OUT("stream") the current output stream is switched to the stream ‘stream’,

SHUT("stream") the specified stream is closed.

The ‘stream’ name may be prefixed by a ‘device name’ to specify non–disk data sets:

CON: is the terminal

WIN: is a window (not yet implemented)

RAM: is an internal memory stream, ‘RAM–disk’

GRA: is a graphic window (not yet implemented)

NUL: is a dummy stream to suppress output, always empty on input, never full on output,

Other ‘device names’ are passed to the operating system and are usually interpreted as disk data sets.

9.5 Command Line Parameters

The executable MAS program accepts several command line parameters to configure the running system. The parameters available on all systems are:

  1. -m number-of-KB

The memory option ‘-m’ gives the number of Kilo-Byte storage, requested from the operating system. This number includes the space reserved for the editor and other system calls. The number should be larger than about 250-300 on an Atari ST with microEMACS.

  2. -f data-set-name

The file name option ‘-f’ can be used to overwrite the default file name ‘MAS.INI’ during startup. With this option MAS can be run in batch mode if the EXIT statement is contained in the data set.

The parameters may appear in any order. On multiple occurrences of parameters, the last occurrence is used. An additional parameter available on IBM PC Topspeed Modula–2 version is:

  1. -t data-set-name

This parameter defines an temporary data set name used for storing MAS memory during external command invocation. The default for data-set-name is ‘CELL-MEM.TMP’. i.e the temporary data set is created in the actual directory. If you have a RAM-Disk installed, say on drive ‘R’, then with ‘MAS -t R:\temp.tmp’ MAS will use the RAM-Disk for the temorary data set.

For the IBM PC version at least 512 KB memory is required, but it is recomended to have at least 640 KB. In case of problems starting MAS you should remove any additional device drivers from CONFIG.SYS and AUTOEXEC.BAT or any other program that needs memory. The MAS version compiled with the Topspeed Modula-2 Compiler uses EMS if present. Memory from EMS will be activated after 10 Garbage Collections or by the MAS function USEEMS().

The LISP Interpreter

This chapter describes some issues of the LISP interpreter which are not covered elsewhere. It is usually not required for the use of the MAS system. LISP whizzards may find some background information regarding the MAS LISP implementation. The idea of combining an ALGOL like programming language with LISP is borrowed from A.C. Hearn’s RLISP, which is part of the Reduce computer algebra system [Hearn 87]. Our LISP interpreter is also influenced by SLISP (Standard LISP) [Marti et. al. 78]. The actual implementation of the interpreter followed the book ‘LISP’ of H. Stoyan and G. Goerz [Stoyan et. al. 84]. A similar approach, implementing LISP in BCPL, was persuaded by Fitch and Norman [Fitch et. al. 77]. Since in LISP everything is a function and there is no special syntax beyond the S– expression syntax we describe the MAS LISP by the functions. In the second section we will discuss some implementation dependend issues.

10.1 Functions and Variables

The semantics of the functions is as expected from other LISP systems. The list of all available LISP functions is as follows:

List Processing:

CAR, CDR, CONS, REVERSE, JOIN, NIL (LISP like versions) FIRST, RED, COMP, INV, CONC, ADV (SAC–2 like versions).

For convenience both the LISP names and the ALDES /SAC–2 names are available. The names are in corresponding order. NIL is the empty list. The ALDES constant ‘()’ is not parsed, so NIL must be used. The next functions correspond to the operators +, -, *, /, % in the MAS language.

Arithmetic:

ADD, SUB, MUL, QUOT, REM.

Relations:

EQ, NE, LE, LT, GE, GT, NOT, AND, OR.

These functions are generated from the MAS relations =, #, <=, <, >=, >. The following is a complete list of the intrinsic LISP functions. The functions with Standard LISP names have the same meaning as in SLISP. Others are described elsewhere.

Functions:

DE, DF, DM, DG, LAMBDA, FLAMBDA, MLAMBDA, GLAMBDA, VAR, SORT, SIG, MAP, RULE, UNIT, SPEC, IMPL, MODEL, AXIOMS, SETQ, ASSIGN, QUOTE, COND, PROGN, LIST, IF, WHILE, REPEAT, PROGA, GOTO, ARRAY, LABEL,

The VAR, SIG, MAP, RULE, UNIT, SPEC, IMPL, MODEL and AXIOMS functions are used by the specification component. The PROGA, GOTO, LABEL and ARRAY functions are used for the interpretation of ALDES algorithms.

10.1.1 What is Not Contained

Several functions which are normally available from LISP interpreters are not accessible in MAS LISP, but they are normally available (probably with different name) at the Modula–2 programming level:

CATCH, THROW, ASSOC, PUT, GET, EXPLODE, IMPLODE, GENSYM, SUBLIS.

Definitely not available are:

DO–loops or FOR–loops, a LISP compiler.

Of course a FOR–loop construct can be defined as macro, if one accepts an ugly syntax. GOTO is only available in PROGA for ALDES sequential statements. Probably available in future releases will be:

LOOP–EXIT–END, CASE, graphics, …

A CASE construct is available in ALDES, it is simulated using the COND function. Not contained as primitive but definable are

APPLY, MAP, EVAL.

Here MAP means the LISP MAP function family and not the specification component MAP function. The MAP function family can be defined as procedures, as explained in the section ‘Talking LISP’.

10.2 Implementation Issues

The current implementation uses the MAS storage management and input /output management which have their origin in the ALDES /SAC–2 Basic and List Processing System by G.E. Collins and R. Loos [Collins et. al. 82], [Loos 76]. The symbol handling was first done by the ALDES / SAC–2 Symbol System, which uses an unbalanced tree for the symbol table. In the present version (≥ 0.6) we use a hash table with balanced symbol tree entries. Therefore the generation of alphabetical lists (as in the HELP command) needs some more time as in the previous system. Without the specification component there are typically less than 100 – 200 symbols defined, since sub–procedures in compiled code which are not accessible from the interpreter do not count. With the specifications of algebraic structures loaded about 700 – 1000 symbols are defined. In contrast in a running Reduce system about 4000 symbols and 2000 functions are defined. The variable binding mechanism is the so called ‘deep access’ binding using a linear list for the symbols and values (ALIST). At the moment there are typically less than 50 values bound to symbols, since variables in compiled code are not stored in the ALIST. The MAS parser performs static scope anlysis and declares textualy local variables, but at LISP level dynamic scope is implemented. The minimal MAS executable module is about 90 KB code. This includes storage management, input / output, symbol handling, LISP interpreter, specification component and the parser. Not included are the arithmetic routines. In contrast XLISP is about 76 KB, microEMACS 3.8 is about 80KB, muSIMP-86 is about 57 KB, the muLISP-87 kernel is about 50 KB and SLISP/370 is about 50 KB of code. A full fledged MAS including arbitrary precision arithmetic, a polynomial system, two Gröbner bases packages, a numerical differential equation solver is about 176 KB. In contrast Derive is about 209 KB, the Reduce savefile is about 610 KB ( + 213 KB for PSL) and the bare Reduce (without factorizer and integrator) is reported to be about 459 KB.

Internal Structure of MAS

In this chapter we will provide some background on the internal structure of MAS. First we discuss the components of MAS, then the program layout, the configuration and available libraries.

11.1 System Components

[figure: Editor; MAS input; compiler; Parse; Lisp; Call; Print; Decla-; rations; MAS output; MAS; Specification; Modula–2; M–2 libraries; M–2 source]

Figure 11.1: System Components

The MAS system components are identified in figure 11.1. Active components (programs) are enclosed in square boxes and passive components (data) are enclosed in oval boxes. Arrows indicate flow of data and lines between boxes show that the components are related in some way. As allready mentioned MAS itself is a Modula–2 program. Thus the MAS program can be recompiled and linked together with other symbolic and numberical libraries by a suitable Modula–2 compiler. This is shown as an arrow from the compiler box on the right to the enclosing MAS box on the left. On the top line the editor box both acts on the Modula–2 source code (on the right) and the MAS input data (on the left). The input is processed by the following internal components:

1. The parser for the MAS language (Parse box): character strings in concrete syntax are transformed into abstract syntax trees. Static syntax check together with variable scope analysis is performed.

2. The specification processor (Specification box) with an attached data base of declarations (Declarations box): declarations are extracted from the parse tree and stored in the declaration base, information is retrieved during interpretation. The declarations reflect the Modula–2 source code and the library structure.

3. The LISP interpreter (LISP box): according to the type or the function name of an S–expression inner most (that is eager) evaluation is performed.

4. The interface to the compiled library procedures (Call box): if external functions are encountered then compiled procedures are restored and called with the appropriate parameters.

5. Finally the results are displayed by the (pretty) printing part (Print box).

11.2 Module Layout of MAS

In this section we will discuss the internal structure of MAS as a Modula–2 program. The principal module structure shown in figure 11.2. The MAS interpreter main program uses the parser module ‘MAS Language’ and the LISP evaluator module. Various library modules can then be connected to the LISP interpreter. All list processing modules use the MAS kernel with its storage management system and basic input/output system. MAS is an open system. Beside the ALDES /SAC–2 and the MAS libraries other libraries can be connected to the interpreter. In a first test we used a numerical library developed at the Technische Hochschule Aachen by Prof. G. Engeln-Müllges and Prof. F. Reutter [Engeln et. al. 88]. It was not only possible to call numerical programs from MAS, but moreover it was also possible to call MAS routines from the numerical programs. In a differential equation solver we called the LISP evaluator from within the function which computes the right hand side of the differential equation. This might not be the

Interpreter MAS Language LISP Evaluator Modula-2 Subroutine Libraries

SAC–2 Libraries MAS Libraries

Others

Integer

Floating Point

Rational Number

Others

Others MAS Kernel

Figure 11.2: Module Structure

fastest way to do it but it was possible to define different right hand sides interactively as MAS procedures and then integrate them numerically. The design of the garbage collector allows arbitrary mixtures of list processing programs with numerical or other programs. It also allows mixtures with other Modula–2 data types such as real numbers, vectors, arrays or records. However it only collects garbage produced by the MAS list processing system, not any other dynamically allocated data structures. The collector uses a mark and sweep technique and is not compacting despite of the open system design. Restriction: MAS list pointers may not be part of other dynamically allocated data structures, since then the garbage collector can not get information about them. This restriction can be overcome in the following way: Dynamically allocated data structures must be linked together in some way, so use the MAS list processing for the links and put pointers to the dynamically allocated data in the FIRST fields of the MAS lists. If no list pointers are stored in other dynamically allocated data structures, then no restrictions exist.

11.3 Program Dependencies

A simplified list of the dependencies of the program modules is contained in the following list. Modules with smaller numbers depend on those with higher numbers.

1. MAS.MOD main program.

2. SACSYM, MASSPEC, MASLISP, MASPARSE, MASLOAD, (.DEF and .MOD), symbol system, interpreter and parser.

3. SACD, SACI, SACM, SACRN, SACPRIM, MASAPF, MASF (.DEF and .MOD), arithmetic system, or various other programs which are connected to the interpreter.

4. SACBIOS, SACLIST (.DEF and .MOD), rest of ALDES /SAC-2 basic system.

5. MASELEM, MASSTOR, MASBIOS (.DEF and .MOD), basic system adapted for Modula–2 compiler and Atari computer, containing a garbage collector and file handling.

Modules under 3 and 4 belong to the MAS kernel, modules under 1 and 2 constitute the MAS interpreter and parser. Under 3 only an example configuration is given. The MAS configuration set up is discussed in the next section.

11.4 LISP to Modula–2 Interface

The interface between LISP and the compiled code is realized with the Modula–2 procedure types. The procedure code pointers are stored in the property list of a symbol together with some signature information. Upon application of such a function symbol, the procedure is restored, the actual parameters are supplied and the procedure is called. A simplified example of this mechanism is explained by the following Modula–2 code piece:

       TYPE procf1 = PROCEDURE(LIST): LIST;
       PROCEDURE name(a: LIST): LIST;
                 BEGIN  ... RETURN(x) END;
       VAR   f: procf1;
             a: ADDRESS;
             l: LIST;
       BEGIN a:=ADDRESS(name); ...
             f:=procf1(a);
             l:=f(2); ...

With a:=ADDRESS(name) the code pointer of the function ‘name’ is saved in a, and can further be stored in the property list of a symbol. Later an executable function can be restored with f:=procf1(a) and can then be executed like any other function: l:=f(2). In this example the user himself is responsible for using the correct type conversion procf1. For execution it is absolutely necessary that the number and types of the actual and formal arguments are identical. For this MAS exports type dependent functions for the declaration of compiled code for interactive usage. Such a declaration looks like

       FROM MASLISPU IMPORT Compiledf1;
       FROM MASSTOR IMPORT FIRST;
       Compiledf1(FIRST,"CAR");

here the compiled function FIRST (with 1 input parameter) is made available as LISP function CAR. And provisions are made to prevent CAR from being called with the wrong number of arguments. The Modula–2 compiler itself checks that the type of the function FIRST matches the type of the first parameter of ‘Compiledf1’. So the procedure types are an incredibly helpful feature of Modula–2.

11.5 Configuration Management

Despite of the large amount of available procedures it seems necessary to provide some mechanisms to select only the ones which one is actually interested in. The Modula–2 procedure types together with the MAS interpreter design allow for a transparent configuration management. The association of a compiled procedure with a function symbol of the MAS language is accomplished in a way described in the section on LISP implementation. In this section we will first discuss some key aspects of the MAS configuration management and then we will give a sample listing of a ‘load module’. In the MAS main program a procedure named InitExternals is called, which in turn activates several other InitExternals␣ procedures. The name externals indicates code that is not required to run the LISP kernel. With the InitExternals procedures any desired configuration of the MAS system can be achieved. For example if no arithmetic routines are required their declaration can be left out from the InitExternals. Or if only Gröbner bases are to be studied, one can include declarations of the respective procedures. Four points should be observed: first, the complete type checking mechanism of Modula–2 is in effect. The compiler will detect discrepancies between the declaration of the procedures and their usage. Consider the procedure IWRITE. In the import list it is specified from which module IWRITE is to be taken, here SACI. Then it is used as input to the Compiledp1 procedure. If accidentally some other procedure is used (p.e. Compiledp2) then the compiler will complain about a type mismatch error. second, the linker will take care that all subroutines used in the IWRITE procedure are collected together for the executable program. So if only a top level procedure is made accessible to LISP, the linker looks for all lower level routines required to execute the top level routine. third, the configuration of the MAS system can be done using a familiar program development system. It is not necessary to learn about a special configuration manager. Simply specify all required routines in the InitExternals and re–link the MAS main program and you have a fitting MAS system. fourth, only the minimal number of procedures is packed together. On other LISP systems or LISP based computer algebra systems the whole packages (or modules) are put together, since it is not distinguished between used (accessible) and unused (not accessible) procedures.

150 CHAPTER 11. INTERNAL STRUCTURE OF MAS

A listing of part of the arithmetic InitExternals is shown:

IMPLEMENTATION MODULE MASLOADA;
FROM MASLISPU IMPORT Compiledp1, ...
FROM SACI IMPORT IWRITE, IREAD, INEG, IPROD, ISUM, IDIF,
           IQ, IREM, IQR, ISIGNF, IABSF, IEXP,
           ICOMP, IGCD, ILCM, IRAND, ILWRIT;
FROM SACRN IMPORT RNWRIT, RNDWR, RNREAD, RNSIGN, RNCOMP,
            RNNEG, RNABS, RNINT, RNRED,
            RNSUM, RNDIF, RNPROD, RNQ;
PROCEDURE InitExternalsA;
(*Tell Modula about external compiled procedures. *)
BEGIN
(*1*) (*from SACI. *)
Compiledp1(IWRITE,"IWRITE");
Compiledp1(ILWRIT,"ILWRIT");
Compiledf0(IREAD,"IREAD");
Compiledf1(ISIGNF,"ISIGN");
Compiledf2(ICOMP,"ICOMP");
Compiledf1(INEG,"INEG");
...
Compiledf2(IGCD,"IGCD");
Compiledf2(ILCM,"ILCM");
Compiledf1(IRAND,"IRAND");
(*2*) (*from SACRN. *)
Compiledp2(RNDWR,"RNDWR");
Compiledp1(RNWRIT,"RNWRIT");
Compiledf0(RNREAD,"RNREAD");
Compiledf2(RNRED,"RNRED");
...
Compiledf1(RNSIGN,"RNSIGN");
Compiledf2(RNDIF,"RNDIF");
Compiledf2(RNPROD,"RNPROD");
Compiledf2(RNQ,"RNQ");
(*3*) (*from MASAPF. *) ...
(*4*) (*from SACPRIM. *) ...
(*5*) (*from MASF. *) ...
(*9*) END InitExternalsA;
END MASLOADA.

11.6 Libraries

Currently available libraries are: Kernel and interpreter:

MAS Storage Management System MAS Basic Input/Output System MAS LISP Interpreter System MAS SPEC Specification Component MAS Parser System ALDES Parser System ALDES/SAC–2 List Processing System ALDES/SAC–2 Symbol System

Basic arithmetic:

ALDES/SAC–2 Digit Arithmetic System, ALDES/SAC–2 Integer Arithmetic System, ALDES/SAC–2 Rational Number System, ALDES/SAC–2 Modular Integer Arithmetic System, ALDES/SAC–2 Integer Factorization System, ALDES/SAC–2 Set of Integers System, ALDES/SAC–2 Combinatorical System, MAS Arbitrary Precision Floating Point System,

Polynomial arithmetic, ring theory, algebraic geometry:

ALDES/SAC–2 Polynomial System, ALDES/SAC–2 GCD and Resultant System, ALDES/SAC–2 Polynomial Factorization System, ALDES/SAC–2 Algebraic Number System, ALDES/SAC–2 Real Root Isolation System, DIP Distributive Polynomial System, DIP Buchberger Algorithm and Groebner Base System, DIP Ideal Real Root Isolation System, DIP Ideal Decomposition System,

and further algorithms for Computer Algebra. Also any other Modula–2 program libraries can be interfaced to the MAS system.

Appendix A

Distribution

In this appendix we summarize several distribution ways of MAS and include some notes on the actual releases of MAS. MAS is distributed in several ways. One way is by anonymous ftp from an internet node. Other ways are directly by floppy disks or by electronic mail.

A.1 Anonymous FTP

The code and executable versions for the MAS System are available via anonymous FTP:

 MAS site  alice.fmi.uni-passau.de
 internet node 132.231.10.1

There are several directories of the MAS System: mas/ibmpc executable IBM PC-AT versions (e.g. MAS*.EXE) mas/atari executable Atari ST version mas/amiga executable Commodore Amiga version mas/src source code (e.g. MAS*.* SAC*.* DIP*.*) of the Atari ST version There are *.ARC and *.UUE versions of the programs. MASMAN.* contains a TEX version of the MAS manual. (called MASTUT in some places) How to use ftp:

1. logon to a computer with internet access

2. enter

     -> ftp␣132.231.10.1

A.2. DISTRIBUTION DISK 153

3. wait for

-> 220 alice FTP server (...) ready

4. enter user identification

-> ftp or anonymou

5. enter password (= name )

6. wait for

-> ftp> prompt

7. enter -> dir or ls or cd as desired

8. choose the stuff you are interested in

9. enter

-> get␣stuff.bla to transfer the data set stuff.bla

10. repeat steps 7 - 9 as desired

11. finaly enter -> quit to close the connection

If this procedure fails, the data sets can probably be sent by e-mail.

A.2 Distribution Disk

The contents of the distribution disk are:

MAS.PRG or MAS.EXE execuable MAS program
MAS.INI  start up data set for MAS
HELP directory  Modula-2 definition modules
SPEC directory  specifications of algebraic objects
EDITOR.PRG  microEMACS 3.9
MAS.RC  start up data set for microEMACS

with system browser macros

BROWSE.RC  procedure to module cross reference

used from system browser

.IN  input data sets for MAS
.OUT  output data sets from MAS
MASMAN.ARC  MAS manuals in TEX
READ.ME  read this before using MAS
RELNOTES.TXT  notes on the actual release of MAS

A.3 Installation

No special installation procedures are required. Just copy the MAS data sets to an appropriate directory. For customization modify the MAS.INI data set as required.

A.4 Release Notes

We summarize the changes between different releases of MAS. The changes between release 0.03 and 0.30 are:

1. The MAS parser has been changed for better Modula-2 compatibility.

2. MAS LISP has been made more robust against incorrect user input.

3. The MAS main program has been enhanced to recognize the following command line parameters:

   -m number-of-KB
   -f data-set-name

• the memory option ‘-m’ gives the number of Kilo-Byte storage, requested from the operating system. This number includes the space reserved for the editor and other system calls. The number should be larger than about 250-300 on an Atari ST with microEMACS.

• the file name option ‘-f’ can be used to overwrite the default file name ‘MAS.INI’ during startup. With this option MAS can be run in batch mode if the EXIT statement is contained in the data set.

• the parameters may appear in any order. On multiple occurrences of parameters, the last occurrence is used.

4. Additional commandline parameter for the IBM PC Topspeed Modula–2 version:

• -t data-set-name This parameter defines an temporary data set name used for storing MAS memory during external command invocation. The default for data-set-name is ‘CELLMEM.TMP’. i.e the temporary data set is created in the actual directory. If you have a RAM-Disk installed, say on drive ‘R’, then with ‘MAS -t R:\temp.tmp’ MAS will use the RAM-Disk for the temorary data set.

5. The macros for microEMACS have been modified for version 3.9+ of microEMACS.

• F3: function key Shift-f3 opens a system browser window with a list of all algorithm names of MAS. Use search-string to locate algorithm names.

• F4: function key Shift-f4 switches to a window containing the definition module where the algorithm description is located.

A.4. RELEASE NOTES 155

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

Bibliography

[Appel et. al. 88] A. W. Appel, R. Milner, R. W. Harper, D. B. MacQueen, Standard ML Reference Manual (preliminary draft), University of Edinburgh, LFCS Report, 1988.

[Buchberger 65] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Dissertation, University of Insbruck 1965.

[Buchberger 70] B. Buchberger. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequ. Math. 4, 1970, pp 374–383.

[Buchberger et. al. 82] B. Buchberger, G. E. Collins, R. G. Loos, Computer algebra – symbolic and algebraic computation Computing Supplement, Vienna: Springer, 1982.

[Buchberger 85] B. Buchberger. Gröbner bases: An algorithmic method in polynomial ideal theory, In:(N.K.Bose ed.) Progress, directions and open problems in multidimensional systems theory. pp 184–232. Dordrecht: Reidel Publ. Comp. (1985)

[Böge et. al. 85] W. Böge, R. Gebauer, H. Kredel. Gröbner bases using SAC–2, Proc. EUROCAL ’85 European Conference on Computer Algebra. Linz 1985, Springer Lect. Notes Comp. Sci. 204, pp 272–274, 1986.

[Böge et. al. 86] W. Böge, R. Gebauer, H. Kredel. Some Examples for Solving Systems of Algebraic Equations by Calculating Gröbner Bases. J. Symbolic Computation (1986) 1, pp 83–98.

[Calmet et. al. 87] J. Calmet, D. Lugiez, A knowledge–based system for Computer Algebra, SIGSAM Bulletin 1987, 21 / 1, pp 7–13, February 1987.

[Collins et. al. 82] G.E. Collins, R. Loos, ALDES / SAC–2 now available, SIGSAM Bulletin 1982, and several reports distributed with the ALDES / SAC–2 system.

[Davenport et. al. 90] J. H. Davenport, B. M. Trager, Scratchpad’s View of Algebra I: Basic Commutative Algebra, Proc. DISCO 90 Capri, LNCS 429, pp 40– 54, Springer, 1990.

[Engeln et. al. 88] G. Engeln–Müllges, F. Reutter, Formelsammlung zur Numerischen Mathematik mit Modula–2 Programmen, BI–Wissenschaftsverlag, Mannheim 1988.

[Fitch et. al. 77] J.P. Fitch, A.C. Norman, Implementing LISP in a High–level Language, Software–Practice and Experience Vol.7, pp 713–725 (1977).

[Gebauer et. al. 83] R. Gebauer, H. Kredel. Distributive Polynomial System. Several Technical Reports, Institut für Angewandte Mathematik, Universität Heidelberg, 1983.

[Gebauer et. al. 83a] R. Gebauer, H. Kredel. Buchberger algorithm system. Technical Report, Institut für Angewandte Mathematik, Universität Heidelberg, 1983. (see also SIGSAM Bulletin Vol. 18, No. 1, p 19.)

[Char et. al. 86] B. W. Char, G. J. Fee, K. O. Geddes, G. H. Gonnet, M. B. Monagan, A Tutorial Introduction to Maple, J. Symbolic Computation 2, pp 179–200, 1986.

[Goldberg 81] A. Goldberg, Introducing the Smalltalk–80 System, Byte 6, 8 pp 14–35, (August 1981).

[Hearn 87] A.C. Hearn, REDUCE 3.3, The Rand Corporation, 1987.

[Jenks et. al. 84] R. D. Jenks et al. SCRATCHPAD II, An Experimental Computer Algebra System, Abbreviated Primer and Examples, Mathematical Sciences Department, IBM, Yorktown Heights, 1984.

[Jenks et. al. 85] R. D. Jenks et al., Scratchpad II Programming Language Manual, Computer Algebra Group, IBM, Yorktown Heights, NY, 1985.

[Kredel 87] H. Kredel, Primary Ideal Decomposition, Proc. EUROCAL ’87 Leipzig, Lecture Notes Computer Science 378, pp 270–281, 1989.

[Kredel 88] H. Kredel, From SAC–2 to Modula–2, Proc. ISSAC ’88 Rome, Lecture Notes Computer Science 358, pp 447–455, 1989.

[Kredel 88a] H. Kredel, Real Roots of Zero Dimensional Ideals, MIP–8824, FMI, University of Passau, 1988.

[Kredel et. al. 88] H. Kredel, V. Weispfenning, Computing Dimension ans Independent Sets for Polynomial Ideals, J. Symbolic Computation (1988) 6, pp 231– 247.

[Kredel 90] H. Kredel, MAS Modula–2 Algebra System, Proc. DISCO 90 Capri, LNCS 429, pp 270–271, Springer, 1990.

[Kredel 90a] H. Kredel, Computing in Polynomial Rings of Solvable Type, Proc. IV. Int. Conf. Computer Algebra in Physical Research, JINR Dubna, UdSSR, May 1990.

158 BIBLIOGRAPHY

[Kredel 91] H. Kredel, Semantics of the MAS Language, Proc. ISSAC’ 91, to appear. [Lawrence 87] D.M. Lawrence, micro EMACS 3.8 Editor, 1987. [Loos 76] R. G. K. Loos. The Algorithm Description Language ALDES (Report),

SIGSAM Bulletin 14/1, pp 15–39, 1976.

[Marti et. al. 78] J. B. Marti, A. C. Hearn, M. L. Griss, C. Griss. Standard Lisp Report.

University of Utah, Salt Lake City, 1978.

[Mateti 88] P. Mateti, Guläm Shell, 1987. [Pavelle et. al. 85] R. Pavelle, P. R. Wang, MACSYMA From F to G, J. Symbolic Com-

putation 1, pp 69–100, 1985.

[Rich et. al. 88] A. Rich, J. Rich, D. R. Stoutemyer. DERIVE A Mathematical Assistant,

The Soft Warehouse. Honolulu, Hawaii, 1988.

[Robbiano 85] L. Robbiano, Term orderings on the polynomial ring. Proc. EUROCAL ’85 European Conference on Computer Algebra. Linz 1985, Springer Lect. Notes Comp. Sci. 204, pp. 513–517, 1986.

[Schrader 76] R. Schrader. Zur konstruktiven Idealtheorie.

Diplomarbeit, Mathematisches Institut II, Universität Karlsruhe, 1976.

[Stoutemyer 86] D. R. Stoutemyer. μ–MATH–86, The Soft Warehouse. Honolulu, Hawaii,

1986.

[Stoyan et. al. 84] H. Stoyan, G. Goerz, LISP, Springer Verlag, Heidelberg, 1984. [TDI 86] TDI, Modula–2/ST Compiler, Clifton, Bristol, UK, 1986. [Trinks 78] W. Trinks, Über Buchbergers Verfahren Systeme algebraischer Gleichun-

gen zu lösen. J. Number Theory, Vol. 10, pp 475–488, 1978.

[Weispfenning 87] V. Weispfenning, Admisible orders and linear forms. ACM SIGSAM

Bulletin, Vol. 21, No. 2, pp 16–18, May 1987.

[Winkler et. al. 85] F. Winkler, B. Buchberger, F. Lichtenberg, H. Rolletschek. An algorithm for constructing canonical bases (Gröbner bases) of polynomial ideals. ACM/TOMS 11, pp 66–78, 1985.

[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 85a] N. Wirth, Programming in Modula–2, Springer, Berlin, Heidelberg, New

York, 1985.

[Wirth 85b] N. Wirth, Compilerbau, Teubner Verlag, Stuttgart, 1985.

[Wirth 88] N. Wirth, From Modula to Oberon, pp 661–670, The Programming Language Oberon, pp 670–690, Software–Practice and Experience Vol. 18(7) (July 1988).

[Wirth et. al. 89] N. Wirth, J. Gutknecht, The Oberon System, pp 857–893, Software– Practice and Experience Vol. 19(9) (September 1989).

[Wolfram 88] Wolfram Research Inc., Mathematica, Addison–Wesley, Reading, 1988.

Index

/ 32 70 147 /\ 147 \/ 147 . 32 147 < 32 147 <> 32 <= 32 147 (* 35 ( 32 147 + 32 70 147 || 147 $ 147 *) 35 * 32 70 147 ) 32 147 ; 32 147 ^70 147 - 32 70 147 -> 32 -f 158 -m 158 -t 158 174 ,..., 147 , 32 147 % 32 > 32 147 >= 32 147 : 32 147 := 32 147 # 32 147 ' 34 148 = 32 147 => 32 " 34 148 ~ 147 [ 147 148 ] 147 148 {} 147

A

abelian group 62 abelian monoid 62 abstract objects 21 56 actual parameter 39 41 49 ADD 160 ADV 74 82 159 ALDES syntax error 150 ALDES syntax warning 150 ALDES 146 156 algebraic number 170 algebra 21 56 ALGOL 159 algorithm 12 17 ALIST 161 AmigaDOS 2 AND keyword 32 AND 160 and 26 APABS 106 APCMPR 106 APDIFF 106 APEXP 106 APFINT 105 108 APFRN 105 107 APNEG 106 APPI 14 107 APPLY 161 APPROD 106 approximation 103 APQ 106 APREAD 107 APROOT 107 APSIGN 106 APSPRE 105 APSUM 106 APWRIT 14 107 arithmetic 18 84 161 165 169 array keyword 147 array 150 ARRAY 160 ASCII 32 147 ASSIGN 160 assignment 13 14 41 ASSOC 160 atom 18 33 average computing time 80 AXIOMS keyword 32 AXIOMS 160 axioms 57 67

B

back track 68 basic arithmetic 84 169 BCPL 159 BEGIN keyword 32 BEGIN–END statement 46 big O notation 81 binding 43 BIOS 155 165 blank 35 148 bool 26 browse 23 24 Buchberger algorithm 170 Buchbergers graduated term order 126

C

CAR 159 166 case keyword 147 CASE 161 CATCH 160 category theory 21 56 CCONC 74 82 CDR 159 cell 80 character set 31 146 CINV 74 82 C 29 closure 63 CLOUT 78 command line 158 173 command 28 comment 13 32 35 147 148 compiled code 161 166 compiled function 14 compiled procedure 167 compiler 17 160 165 COMP 73 82 159 complexity 80 97 105 118 130 computing time 80 CONC 74 82 159 concrete objects 21 56 conditional rewriting 68 condition 40 COND 160 configuration 166 167 confluence 68 confusion 28 CON 53 158 CONS 159 const keyword 147 const 150 construction 73 cross reference 24

D

data type 165 debugging 28 DEBUG 156 declaration 13 definition 23 DE 160 denotational semantics 56 dependencies 165 Derive 12 161 DESC 66 descriptor 65 design 165 destruction 74 determinant 91 det 93 DF 160 DG 160 diagram 75 digit 19 20 32 84 147 169 DIIFRP 133 DIPBSO 131 DIPDEG 130 DIPEVL 131 DIPFMO 131 DIPFP 134 DIPLBC 131 DIPMAD 131 DIPMCP 131 DIPTODEF 141 DIPVDEF 140 DIP2SYM 140 directory 13 55 157 DIRFIP 134 DIRLIS 132 DIRPAB 131 DIRPDF 132 DIRPGB 132 DIRPNF 132 DIRPNG 131 DIRPPR 132 DIRPSG 131 DIRPSM 132 distribution 172 distributive polynomial 130 139 170 do keyword 147 DO keyword 32 DOS 2 157 DPGEN 89 DUMPENV 155 dynamic scope 50

E

EBNF 35 57 148 EDIT 157 editor 17 24 55 157 else keyword 147 ELSE keyword 32 EMACS 157 emergency 28 EMS 157 158 END keyword 32 EQ 160 EQUAL 26 82 error 27 28 38 151 EVAL 161 evaluation 17 57 70 71 executable program 167 EXIT 28 157 161 Exp 103 EXP 26 65 EXPLODE 160 exponential series 102 EXPOSE keyword 32 EXPOSE 63 66 68 70 expression 37 EXTENT 82 external function 42 EXTPROCS 22 154

F

factor 39 fatal error 28 field 61 FIELD 62 field 67 FIRST 74 81 159 166 FLAMBDA 160 floating point algorithms 105 floating point representation 104 floating point syntax 107 floating point 14 84 105 169 fluid variable 50 for keyword 147 FOR 29 formal parameter list 49 formal parameter 49 FORTRAN 146 function overload 66 function 39 FUSSY 156

G

GCM 155 GEM 2 17 generic function 66 generic operators 156 generic parse 70 generic 22 154 GENERICS 22 25 154 GENPARSE 156 GENSYM 160 GET 160 GLAMBDA 160 global keyword 147 global variable 50 global 150 goto keyword 147 goto 150 GOTO 160 GRA 53 158 graphic 53 157 161 greatest common divisor 91 170

H

header 59 help facilities 22 HELP 14 22 23 42 84 154

I

IABS 86 IBM PC 157 158 IBM–370 2 ICOMP 86 90 ideal decomposition 170 identifier list 48 49 identifier 32 33 34 147 IDIF 86 IEXP 87 if keyword 147 IF keyword 32 IF statement 46 IFACT 88 IF 14 160 IGCD 88 ILCM 88 ILWRIT 88 IMPLEMENTATION keyword 32 implementation 2 17 56 62 159 161 IMPL 160 IMPLODE 160 IMPORT keyword 32 IMPORT 60 63 66 68 INEG 86 infinite loop 44 InitExternals 167 IN 157 input 12 17 27 28 52 161 169 integer algorithms 86 integer factorization 84 169 integer representation 85 integer syntax 88 integer 19 84 86 118 169 integral polynomial 118 interactive 31 165 166 internal function 42 interpretation 71 interpreter 167 169 INT 23 intrinsic keyword 147 intrinsic 150 inverse graduated term order 126 inverse lexicographical term order 126 INV 74 82 159 IPABS 119 IPDIF 119 IPNEG 119 IPPGSD 122 IPPROD 119 121 IPPSR 120 IPQR 120 IPREAD 120 IPROD 19 87 91 IPRODK 87 IPSIGN 119 IPSUM 119 IPWRIT 121 IQ 87 IQR 87 IRAND 88 IREAD 88 IREM 87 ISIGN 86 ISUM 86 IWRITE 19 88

J

join specifications 60

JOIN 159 join 21 56

K

kernel 167 169 keyword 32 147 knowledge 12 17

L

LABEL 160 lambda calculus 57 LAMBDA 160 language 14 28 29 31 159 167 left 79 LENGTH 74 82 letter 32 147 lexical conventions 31 library 17 164 169 linker 167 LISP 13 16 17 28 156 159 173 list processing 13 73 81 169 list representation 85 96 104 LISTENV 22 155 LIST 73 82 160 local variable 50 LOOP 161 lower level routine 167 LT 160

M

macro 24 28 29 160 Macsyma 12 MAP keyword 32 mapcar 77 161 MAP 66 160 161 Maple 12 MAS expression 139 MAS.INI 158 173 MAS.RC 157 Mathematica 12 maximal computing time 80 memory 80 microEMACS 174 minimal computing time 80 MLAMBDA 160 MODEL keyword 32 model theory 21 56 MODEL 160 model 57 65 MODULA 28 155 modular integer 84 169 modular integers 67 module structure 164 muLISP 161 MUL 160

N

NE 160 NIL 159 Noetherian relation 68 NOT keyword 32 NOT 160 NUL 53 158 number 32 147 numeric 161 164 165 169

O

OBJECT 61 of keyword 147 operating system 17 18 53 158 operator overloading 70 156 optimal variable ordering 143 optimized linking 168 OR keyword 32 ORDER 83 OR 160 OUT 157 output 14 17 52 53 158 161 169 overflow 109 overload 66

P

package 168

parameter 23 29 39 41 parser ALDES 146 parser 13 17 28 31 70 156 165 169 173 PDEG 118 Peano arithmetic 72 Peano axioms 69 Peano structure 69 PFDIP 134 PL/0 31 PLBCF 119 PLDCF 118 POLY 140 polynomial ideals 170 polynomial 118 130 139 power 39 pragma keyword 147 pragma 150 PRAGMA 28 70 146 155 PREAD 133 PRED 118 print keyword 147 procedure call 41 PROCEDURE declaration 49 PROCEDURE keyword 32 procedure type 16 166 167 PROCEDURE 64 procedure 71 PROD 26 PROGA 160 PROGN 160 program 37 58 PSL 161 PTBCF 119 PTRCF 118 PUT 160 PWRITE 133

Q

quote character 34 148 QUOTE 160 QUOT 160

R

RAM–disk 158 RAM 53 158 rational number algorithms 97 rational number representation 96 rational number syntax 100 rational number 61 62 64 67 84 97 130

139 169 rational polynomial 130 139 rational 19 20 read 52 real root isolation 170 recursive polynomial 170 RED 74 81 159 reduced univariate polynomial 143 Reduce 12 159 161 release notes 173 release 0.3 173 release 0.6 174 relink 167 REM 160 rename 21 56 repeat keyword 147 REPEAT keyword 32 REPEAT statement 48 REPEAT 160 representation 85 96 104 resultant 170 return keyword 147 RETURN statement 49 REVERSE 159 rewrite rule 71 right 79 RLISP 159 RNABS 20 98 RNCOMP 20 23 98 RNDEN 97 RNDIF 99 RNDRD 100 RNDWR 20 100 107 RNEXP 98 RNFAP 106 RNINT 20 97 RNINV 98 RNNEG 97 RNNUM 97 RNPROD 20 98 101 RNQ 99 RNRAND 100 RNREAD 100 RNRED 20 97 RNSIGN 98 RNSUM 20 99 102 RNWRIT 20 100 roots of ideals 170 RULE keyword 32 RULE 68 160

S

S–expression 13 17 73 139 safe keyword 147 safe 150 scope 50 175 Scratchpad II term order 127 Scratchpad II 21 56 Scratchpad 12 semantics 56 set of integer 84 169 SETQ 29 160 SHOW 155 SHUT 157 SIG 160 signature definition 154 SIGNATURE keyword 32 signature 14 22 SIGNATURE 60 SIGS 22 25 154 SLISP 159 161 SLOPPY 156 SML 57 SMPRM 88 SORT keyword 32 sort name 154 SORT 22 60 63 65 68 160 SORTS 22 27 154 space 80 specification component 56 SPECIFICATION keyword 32 specification syntax 58 specification 14 56 59 SPEC 160 statement sequence 46 statement 40 static scope 50 storage management 169 storage 13 17 155 161 string 32 34 78 147 148 structure 12 165 SUB 160 SUBLIS 160 sublist 79 substitution 68 substr 79 Sun 2 symbol handling 169 symbol 12 34 155 161 165 SYMTB 155 SYM2DIP 140 syntax diagram 58 149 syntax disgram 36 syntax error ALDES 150 syntax error 37 38 151 syntax warning ALDES 150 syntax warning 37 38 152 syntax 13 27 28 29 35 36 57 88 100 107

148 149 155 system components 163 systems of equations 170

T

term algebra 68 term rewriting 68 TERM 140 term 37 then keyword 147 THEN keyword 32 THROW 160 TIME 156 time 80 token 32 147 TOS 2 17 TRACE 156 transliteration 34 153 type checking 167 type 16 17 166

U

underflow 109 unification 68 71 unit name 155 UNIT 160 unit 59 UNITS 155 universal algebra 21 56 Unix 2 until keyword 147 UNTIL keyword 32 USEEMS 157

V

VAL 66

VAR declaration 48 VAR keyword 32 VAR parameter 45 49 variable 14 17 22 23 34 39 41 68 154 155 VAR 63 160 VARS 22 154 VAX 2 VM/CMS 2 VMS 2

W

warning 38 152 WHEN keyword 32 WHEN 66 68 while keyword 147 WHILE keyword 32 WHILE statement 47 WHILE 14 160 WIN 53 158 write 52

Z

ZERO 23