Handbook for Automatic Computation : Volume I Part a

Automatic computing has undergone drastic changes since the pioneering days of the early Fifties, one of the most obvious being that today the majority of computer programs are no longer written in machine code but in some programming language like FORTRAN or ALGOL. However, as desirable as the time-saving achieved in this way may be, still a high proportion of the preparatory work must be attributed to activities such as error estimates, stability investigations and the like, and for these no programming aid whatsoever can be of help. In this respect, ALGOL, as an internationally standardized notation which avoids computer-oriented concepts, provides another advantage, not often mentioned, but one which was already the guiding principle at the very beginning of the programming language venture: indeed, a correct ALGOL program is the abstractum of a computing process for which the necessary analyses have already been performed. It is the very purpose of this Handbook to establish such abstract formulations of certain computing processes. Therefore, numerical methods given in this Hand­ book in the form of ALGOL procedures may be put to immediate use wherever ALGOL is known and understood; in fact, application of such a method reduces to little more than calling the corresponding procedure.

I Introduction.- § 1. The Concept of Automatic Programming.- § 2. Historical Remarks on Algorithmic Languages.- § 3. The Algol Conferences of 1958, 1960, 1962.- 3.1. Algol 58.- 3.2. Algol 60.- 3.3. The Rome amendments of 1962.- § 4. Algol Dialects and the IFIP Subset of Algol 60.- § 5. Preliminary Definition of Algol.- 5.1. Arithmetic expressions and assignment statements.- 5.2. For-statements.- 5.3. Compound statements.- 5.4. Labels and goto-statements.- 5.5. The if-statement.- 5.6. If-else-statements.- 5.7. Declarations.- 5.8. Complete programs.- II Basic Concepts.- § 6. Auxiliary Conventions.- 6.1. Syntactic forms.- 6.2. French quotes.- 6.3. The ellipsis.- 6.4. The syntactic diagram.- 6.5. Undefined situations.- § 7. The Basic Symbols of Algol.- 7.1. Set of basic symbols.- 7.2. Delimiters.- 7.3. Typography.- 7.4. Hardware representations.- § 8. Values.- 8.1. Types of values.- 8.2. Computer limitations.- 8.3. Consequences of computer limitations.- § 9. Quantities and their Names.- 9.1. Kinds of quantities.- 9.2. Identifiers.- 9.3. Scope of a quantity.- § 10. Numerical Constants.- 10.1. Examples of unsigned numbers.- 10.2. Syntax.- 10.3. Semantics.- 10.4. Types.- 10.5. Negative constants.- § 11. Labels.- 11.1. Syntax.- 11.2. Source-and destination labels.- 11.3. Semantics.- 11.4. Scopes of labels.- § 12. Strings.- 12.1. Examples.- 12.2. Syntax.- 12.3. Semantics.- § 13. Comments.- 13.1. The comment convention.- 13.2. Examples.- 13.3. Conflicting situations.- III Expressions.- § 14. Variables.- 14.1. Examples.- 14.2. Syntax.- 14.3. Semantics.- 14.4. Types.- § 15. Function Designators.- 15.1. Examples.- 15.2. Syntax.- 15.3. Semantics.- 15.4. Types.- § 16. Simple Arithmetic Expressions.- 16.1. Examples.- 16.2. Syntax.- 16.3. Semantics.- 16.4. Type of the value of a simple arithmetic expression.- 16.5. Confrontation of examples with conventional notation.- § 17. Relations.- 17.1. Examples.- 17.2. Syntax.- 17.3. Semantics.- § 18. Simple Boolean Expressions.- 18.1. Examples.- 18.2. Syntax.- 18.3. Semantics.- § 19. Conditional Expressions.- 19.1. Examples.- 19.2. Syntax of conditional arithmetic expressions.- 19.3. Semantics.- 19.4. Conditional Boolean expressions.- 19.5. Influence of types.- 19.6. Syntax of general expressions.- 19.7. Further examples involving conditional expressions.- § 20. Subscript Expressions.- 20.1. Syntax.- 20.2. Semantics (Rounding rule for subscript expressions).- 20.3. On the use of subscript expressions.- IV Statements.- § 21. Assignment Statements.- 21.1. Examples.- 21.2. Syntax.- 21.3. Semantics.- 21.4. Influence of types.- § 22. Sequences of Statements.- 22.1. Examples.- 22.2. Syntax.- 22.3. Semantics.- § 23. Labelled Statements.- 23.1. Examples.- 23.2. Syntax.- 23.3. Semantics.- § 24. The Dummy Statement.- 24.1. Syntax.- 24.2. Semantics.- 24.3. Examples.- 24.4. Applications.- § 25. Goto-Statements.- 25.1. Examples.- 25.2. Syntax.- 25.3. Semantics.- 25.4. Applications.- 25.5. Closed loops.- § 26. Procedure Statements I.- 26.1. Examples.- 26.2. Syntax.- 26.3. Semantics.- § 27. Compound Statements and Blocks.- 27.1. Examples.- 27.2. Syntax.- 27.3. Semantics of compound statements.- § 28. The If-Statement.- 28.1. Examples.- 28.2. Syntax.- 28.3. Semantics.- 28.4. Applications.- § 29. The If-Else-Statement.- 29.1. Examples.- 29.2. Syntax.- 29.3. Semantics.- 29.4. Efficiency considerations.- § 30. The For-Statement.- 30.1. Examples.- 30.2. Syntax.- 30.3. Semantics.- 30.4. For-statements and conditional statements.- 30.5. Consequences drawn from the semantic rules.- 30.6. Efficiency considerations.- V Miscellaneous Applications.- § 31. Algebraic Problems.- 31.1. Gauss elimination.- 31.2. Newton’s method for algebraic equations.- 31.3. The Dandelin-Graeffe method.- 31.4. The stability criterion of Routh.- § 32. Interpolation and Numerical Quadrature.- 32.1. Neville-Lagrange interpolation.- 32.2. Hermite interpolation with equidistant abscissae.- 32.3. Newton interpolation in an equidistant table.- 32.4. Romberg Quadrature.- § 33. Numerical Integration of Differential Equations.- 33.1. Runge-Kutta method, Nystroem modification.- 33.2. The Adams-Bashforth method.- 33.3. Laplace’s equation.- § 34. Least Square Problems.- 34.1. Orthogonalisation.- 34.2. Generation of orthogonal polynomials.- 34.3. Chebychev series development.- §35. Computations Related to Continued Fractions.- 35.1. Introduction.- 35.2. Evaluation by the forward recurrence relation.- 35.3. Transformation of a power series into a continued fraction.- 35.4. The epsilon algorithm.- § 36. Considerations Concerning Computer Limitations.- 36.1. Quadratic equations.- 36.2. Newton’s method.- 36.3. Monotonicity as a termination criterion.- 36.4. Overflow in continued fraction evaluation.- 36.5. Underflow in orthonormalisation processes.- 36.6. Bandmatrices.- §37. Data Processing Applications.- 37.1. Pseudostring representation.- 37.2. Format handling.- 37.3. Sorting.- 37.4. Differentiation of an arithmetic expression.- 37.5. Operations performed upon packed data.- VI Declarations.- § 38. Type Declarations.- 38.1. Examples.- 38.2. Syntax.- 38.3. Semantics.- § 39. Array Declarations.- 39 Examples.- 39.2. Syntax.- 39.3. Semantics.- 39.4. Unused components of an array.- § 40. Switch Declarations.- 40.1. Examples.- 40.2. Syntax.- 40.3. Semantics.- 40.4. Influence of scopes.- § 41. Procedure Declarations I.- 41.1. Examples.- 41.2. Syntax.- 41.3. Semantics.- §42. Semantics of Blocks.- 42.1. Block structure.- 42.2. Scope of a quantity.- 42.3. Restrictions for declarations.- 42.4. Dynamic effects of declarations.- 42.5. Operands of a block.- §43. Entire Programs.- 43.1. Rules for Algol programs.- 43.2. Examples.- 43.3. Block structure and storage economy.- VII Procedures.- § 44. Procedure Declarations II.- 44.1. Introduction.- 44.2. Operands of a procedure.- 44.3. Rules for global parameters.- 44.4. Rules for formal parameters.- 44.5. Scopes and procedure declarations.- 44.6. The value part.- 44.7. Further examples of procedure declarations I8l.- §45. Procedure Statements II.- 45.1. The actual-formal correspondence.- 45.2. Execution of a procedure statement.- 45.3. Restrictions for actual parameters.- 45.4. Additional rules for arrays, procedures, switches.- 45.5. Gauss-Seidel effects.- 45.6. Further examples of procedure statements and their interpretation.- § 46. Function Procedures and their Use.- 46.1. Function procedure declarations.- 46.2. Further examples of function procedure declarations.- 46.3. Rules for function designators.- 46.4. Evaluation of a function designator.- 46.5. The side effect question.- § 47. Code Procedures.- 47.1. Independent procedures.- 47.2. Pseudodeclarations.- 47.3. Code procedures.- 47.4. Economisation of Algol programs with aid of code procedures.- § 48. Parameter Procedures.- 48.1. Examples involving arbitrary functionals.- 48.2. Execution of parameter procedures.- 48.3. Interference with the execution of a procedure.- 48.4. Some programming problems.- VIII Input and Output.- § 49. The Standard I/O-Procedures of Algol.- 49.1. Syntax.- 49.2. Semantics.- 49.3. Further remarks.- 49.4. Control operations.- 49.5. The I/O-procedures of §43.- § 50. Applications of Procedures insymbol, outsymbol.- 50.I. Input and output of pseudostrings.- 50.2 Punched card reading.- 50.3. Simulation of an output buffer.- §51. Use of inarray, outarray for Auxiliary Storage.- 51.1. Choleski decomposition of a large matrix.- 51.2. High order qd-algorithm.- 51.3. Matrix inversion by the escalator method.- Appendix A.- § 52. The Jensen Device.- 52.1. The full name-concept.- 52.2. The Jensen device.- 52.3. Bound variables.- § 53. Conclusion.- 53.1. Church’s lambda notation.- 53.2. The lambda notation for arrays.- 53.3. Syntax of the proposed extension.- 53.4. Semantics of the proposed extension.- 53.5. Applications of the proposed extension.- Appendix B. The IFIP-Reports on Algol.- References.