R. Klatte U. Kulisch M. Neaga D. Ratz Ch. Ullrich PAS CAL-XS C Language Reference with Examples Translated by G. R Corliss R. Klatte U. Kulisch D. Ratz C. Wolff Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Budapest Prof. Dr. Ulrich Kulisch Dr. Michael Neaga Dr. Rudi Klatte Numerik Software GmbH Dipl.-Math. techno Dietmar Ratz P. O. Box 2232 Dipl.-Dbers. Carola Wolff W-7570 Baden-Baden, FRG Institut ftir Angewandte Mathematik Universitat Karlsruhe Prof. Dr. Christian Ullrich KaiserstraBe 12 Institut ftir Informatik W-7500 Karlsruhe, FRG Universitat Basel Mittlere StraBe 142 Prof. George F. Corliss CH-4056 Basel Mathematics and Computer Science Division Argonne National Laboratory 9700 S. Cass Ave. Argonne, IL 60439-4844, USA Title of the original German edition: PASCAL-XSC Sprachbeschreibung mit Beispielen © Springer-Verlag Berlin Heidelberg 1991 Mathematics Subject Classification (1991): 65-XX, 65-04, 65G-XX, 65G-05, 65G-1O, 68-XX, 68B99 ISBN-13:978-3-540-55137-9 e-ISBN-13:978-3-642-77277-1 DOl: 10.1007/978-3-642-77277-1 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcast ing, reproduction on microfilm or in any other ways, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1992 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Disclaimer: Springer-Verlag and the authors make no representation or warranty with respect to the adequacy of this book or the programs which it describes for any particular purpose or with respect to its adequacy to produce any particular result. In no event shall Springer-Verlag or the authors be liable for special, direct, indirect or consequential damages,losses, costs, charges, claims, demands or claim for lost profits, fees or expenses of any nature of kind. Typesetting: Camera ready by authors 41/3140-543210 -Printed on acid-free paper Preface This manual describes a PASCAL extension for scientific computation with the short title PASCAL-XSC (PASCAL eXtension for Scientific Computation). The language is the result of a long term effort of members of the Institute for Applied Mathematics of Karlsruhe University and several associated scientists. PASCAL XSC is intended to make the computer more powerful arithmetically than usual. It makes the computer look like a vector processor to the programmer by providing the vector/matrix operations in a natural form with array data types and the usual operator symbols. Programming of algorithms is thus brought considerably closer to the usual mathematical notation. As an additional feature in PASCAL-XSC, all predefined operators for real and complex numbers and intervals, vectors, matrices, and so on, deliver an answer that differs from the exact result by at most one rounding. Numerical mathematics has devised algorithms that deliver highly accurate and automatically verified results by applying mathematical fixed point theorems. That is, these computations carry their own accuracy control. However, their imple mentation requires arithmetic and programming tools that have not been available previously. The development of PASCAL-XSC has been aimed at providing these tools within the PASCAL setting. Work on the subject began during the 1960's with the development of a general theory of computer arithmetic. At first, new algorithms for the realization of the arithmetic operations had to be developed and implemented. The design and devel opment of appropriate programming languages began around 1975 with preliminary implementation studies first on the basis of PASCAL and also as an extension of FORTRAN. As the next step, complete compilers for the extended language had to be developed. Since about 1980, algorithms for standard problems of numeri cal analysis with automatic result verification and for many applications have been systematically developed. Many colleagues and scientists closely related with the Institute have contributed to the project by useful discussions, by a long term collaboration, or other kinds of support. The main participants of this developement are: U. Allendorfer, J. H. BIe her, H. Bohm, G. Bohlender, K. Braune, D. M. Claudio, D. Cordes, G. F. Corliss, A. Davidenkoff, H. C. Fischer, S. Georg, K. Gruner, R. Hammer, E. Kaucher, R. Kelch, R. Kirchner, R. Klatte, W. Klein, W. Kramer, U. Kulisch, R. Lohner, M. Metzger, W. L. Miranker, M. Neaga, L. B. Rall, D. Ratz, S. M. Rump, R. Saier, L. Schmidt, G. Schumacher, D. Shiriaev, Ch. Ullrich, W. Walter, M. Weichelt, H. W. Wippermann, and J. Wolff von Gudenberg. The authors would like to ex press sincere and cordial thanks to each one for his cooperation. Thanks are also due to the many students who used and applied PASCAL-XSC in an early stage of vi the development and thus helped to stabilize both the language and the compiler. This manual provides a complete description of PASCAL-XSC. The part dealing with ISO Standard PASCAL is only briefly discussed, while the extensions marked by I PAscAL-xscl are presented in full detail. A detailed chapter with exercises and solutions is included in this manual to help the reader to get familiar with the new language constructs. A full set of syntax diagrams, appendices, and indices complete the book. Finally, we would like to mention that a programming language is never com plete. Improvements are always possible and often necessary. The main concern developing this language was to provide a useful and appropriate tool for numerical applications in the field of engineering and scientific computation. Benevolent and critical comments for improvements of the language are very welcome. This book is a translation of a German version also published by Springer-Verlag. The authors are very grateful to George Corliss who helped to polish the text and the contents. Karlsruhe, October 1991 The Authors The Realization of this Book This manual was completely written in the text system U-TEX or 'lEX. Co-Author Dietmar Ratz gathered the text, designed the necessary macros and environments, developed the syntax diagrams, carried out corrections, and drew up the final version including the appendices and indices. He was also responsible for the final layout of this book. The Authors Table of Contents 1 Introduction............... 1 1.1 Typography............. 1 1.2 Historical Remarks and Motivation 2 1.3 Advanced Computer Arithmetic . . 4 1.4 Connection with Programming Languages 7 1.5 Survey of PASCAL-XSC . . . . . . . . . . 8 1.5.1 Universal Operator Concept and Arbitrary Result Type. 9 1.5.2 Overloading of Procedures, Functions, and Operators 11 1.5.3 Module Concept ........ 11 1.5.4 Dynamic Arrays and Subarrays 12 1.5.5 String Concept . . . . . . 14 1.5.6 Arithmetic and Rounding 14 1.5.7 Accurate Expressions. 14 2 Language Reference . 15 2.1 Basic Symbols. . . 17 2.2 Identifiers . . . . . 18 2.3 Constants, Types, and Variables . 20 2.3.1 Simple Types . . 21 2.3.2 Structured Types . 25 2.3.2.1 Arrays.. 25 2.3.2.2 Subarrays 27 2.3.2.3 Access to Index Bounds 28 2.3.2.4 Dynamic Arrays 28 2.3.2.5 Strings...... 30 2.3.2.6 Dynamic Strings 30 2.3.2.7 Records..... 31 2.3.2.8 Records with Variants 32 2.3.2.9 Sets... 33 2.3.2.10 Files ......... . 34 2.3.2.11 Text Files ...... . 35 2.3.3 Structured Arithmetic Standard Types 36 2.3.3.1 The Type complex. 36 2.3.3.2 The Type interval ..... . 37 2.3.3.3 The Type cinterval . . . . . . 37 2.3.3.4 Vector Types and Matrix Types. 38 2.3.4 Pointers . . . . . . . . . . . . . . . . . . . 38 viii Table of Contents 2.3.5 Compatibility of Types . . . . . . . . . 40 2.3.5.1 Compatibility of Array Types 41 2.3.5.2 Compatibility of Strings 43 2.4 Expressions ............ . 44 2.4.1 Standard Expressions .... . 44 2.4.1.1 Integer Expressions. 46 2.4.1.2 Real Expressions . . 47 2.4.1.3 Boolean Expressions 51 2.4.1.4 Character Expressions 52 2.4.1.5 Enumeration Expressions 53 2.4.2 Accurate Expressions (#-Expressions) 54 2.4.3 Expressions for Structured Types and Pointer Expressions 57 2.4.3.1 Array Expressions 57 2.4.3.2 String Expressions 58 2.4.3.3 Record Expressions . 59 2.4.3.4 Set Expressions ... 59 2.4.3.5 Pointer Expressions 60 2.4.4 Extended Accurate Expressions (#-Expressions) . 60 2.4.4.1 #-Expressions for the Arithmetic Types 61 2.4.4.2 #-Expressions for Vectors ...... . 63 2.4.4.3 #-Expressions for Matrices ..... . 64 2.4.4.4 List of the Operands in #-Expressions 66 2.4.4.5 Review of General #-Expressions 69 2.5 Statements. . . . . . . . . . . . . 71 2.5.1 Assignment Statement . . 71 2.5.2 Input/Output Statements 72 2.5.3 Empty Statement . . 76 2.5.4 Procedure Statement . 76 2.5.5 goto-Statement.... 77 2.5.6 Compound Statement 78 2.5.7 Conditional Statements. 78 2.5.7.1 if-Statement 78 2.5.7.2 case-Statement. 78 2.5.8 Repetitive Statements .. 79 2.5.8.1 while-Statement 79 2.5.8.2 repeat-Statement 80 2.5.8.3 for-Statement . 80 2.5.9 with-Statement. 81 2.6 Program Structure 83 2.7 Subroutines . . . . . . . 85 2.7.1 Procedures .... 85 2.7.2 List of Predefined Procedures and Input/Output Statements 88 2.7.3 Functions ............... . 89 2.7.4 Functions with Arbitrary Result Type 90 2.7.5 List of Predefined Functions ..... . 91 Table of Contents ix 2.7.6 Operators . . . . . . . . . . . . . . . 93 2.7.7 Table of Predefined Operators . . . . 97 2.7.8 forward- and external-Declaration 98 2.7.9 Modified Call by Reference for Structured Types. 98 2.7.10 Overloading of Procedures, Functions, and Operators . 100 2.7.11 Overloading of read and write. . . . . . . . . 102 2.7.12 Overloading of the Assignment Operator := . 105 2.8 Modules . . . . . . . . . . . . . . . . . . 107 2.9 String Handling and Text Processing . . 111 2.9.1 Input of Characters and Strings . 115 2.10 How to Use Dynamic Arrays. . 120 3 The Arithmetic Modules . . 125 3.1 The Module C_ARI . . 131 3.2 The Module LARI . . . 135 3.3 The Module CLARI . . 140 3.4 The Module MV -ARI . . 146 3.5 The Module MVC-ARI . . 151 3.6 The Module MVI-ARI . . 156 3.7 The Module MVCI-ARI . 162 3.8 The Hierarchy of the Arithmetic Modules. . 171 3.9 A Complete Sample Program . 172 4 Problem-Solving Routines . 179 5 Exercises with Solutions . . 183 5.1 Test of Representability . 184 5.2 Summation of Exponential Series . 186 5.3 Influence of Rounding Errors. . 188 5.4 Scalar Product ....... . 190 5.5 Boothroyd/Dekker Matrices . . 192 5.6 Complex Functions . . . . . . . 194 5.7 Surface Area of a Parallelepiped. . 197 5.8 Parallelism and Intersection of Lines . 200 5.9 Transposed Matrix, Symmetry. . 203 5.10 Rail Route Map. . . . . . . . . . . . . 206 5.11 Inventory Lists ............ . 209 5.12 Complex Numbers and Polar Representation . . 212 5.13 Complex Division. . . . . . . . . . . . . 215 5.14 Electric Circuit . . . . . . . . . . . . . .217 5.15 Alternating Current Measuring Bridge . 221 5.16 Optical Lens. . . . . . . . . . . . . . 224 5.17 Interval Evaluation of a Polynomial . 227 5.18 Calculations for Interval Matrices . . 230 5.19 Differentiation Arithmetic . . . . . . 233 5.20 Newton's Method with Automatic Differentiation . 237 x Table of Contents 5.21 Measurement of Time. .239 5.22 Iterative Method ... . 241 5.23 Trace of a Product Matrix .245 5.24 Calculator for Polynomials .248 5.25 Interval Newton Method .253 5.26 Runge-Kutta Method .. . .255 5.27 Rational Arithmetic .. . .258 5.28 Evaluation of Polynomials .263 A Syntax Diagrams . .269 B Indices and Lists . .297 B.1 Syntax Diagrams .297 B.2 Reserved Words . .299 B.3 Predefined Identifiers .300 BA Operators ..... . .302 BA.1 Basic Operators. .302 BA.2 Arithmetic Operators . .303 BA.3 Relational Operators for the Arithmetic Types. .304 BAA Assignment Operators .305 B.5 Predefined Functions . .307 B.6 Transfer Functions . . .320 B.7 Predefined Procedures .323 B.8 #-Expressions ..... .328 B.8.1 Real and Complex #-Expressions .328 B.8.2 Real and Complex Interval #-Expressions .329 Bibliography 331 Index . .... 335 Chapter 1 Introduction This book describes the language PASCAL-XSC. The core of the language de scription consists of three chapters: language description, arithmetic modules, and exercises. In chapter 1 (Introduction), we describe the notation used in this book. We sketch the historical development of PASCAL-XSC, the axiomatic definition of com puter arithmetic, and its embedding in programming languages. The last section is a short survey of the language PASCAL-XSC. Chapter 2 (Language Reference) comprises the formal language definition. The ISO PASCAL Standard is only touched upon. The extensions of PASCAL-XSC are described in detail. PASCAL-XSC supports arithmetic on real, complex, interval, or complex inter val objects, as well as on vectors and matrices over these types. Chapter 3 (The Arithmetic Modules) describes the modules supporting these types with their op erators, functions, and procedures. The succeeding chapter 4 (Problem Solving Routines) summarizes the routines which have been developed in PASCAL-XSC for solving frequently occurring numerical problems. The closing chapter 5 (Exercises with Solutions) encourages the reader to ap ply the new language elements to easy exercises to extend his or her knowledge. Solutions are provided. Finally, the Appendix contains the syntax diagrams of PASCAL-XSC, as well as complete lists of reserved words, predefined identifiers, operators, functions, and procedures of the language core and the arithmetic modules. This book does not deal with implementation details of the language. For all implementation-dependencies in the following chapters, we refer to the correspond ing user manual supplied with the special compiler version. 1.1 Typography To mark or emphasize certain words, names, or paragraphs, we use the following type faces: italics serves to emphasize certain words in the text. boldface is used to mark reserved words of PASCAL-XSC (e.g. begin, module) in the text or in excerpts of programs.