Handbook for Automatic Computation : Volume I · Part b

Problem oriented programming languages as they have developed over the last ten years essentially serve two purposes which somewhat crudely can be described by the terms man-man communication and man-machine communication, respectively. As a carrier of information between humans, the problem oriented programming language is designed to express the essence of an algorithm in a way which is un­ ambiguous and concise as well as independent of (and therefore meaning­ ful without any reference to) the changing details of computing machine­ ry. As a carrier of information from man to computer, the language permits the human programmer to express his computational needs in a compact way adapted to the general characteristics of computers, but freed from the burdening details of specific computer facilities. This presupposes the existence of algorithms, or programs, which permit the computer itself to transform efficiently programs written in the problem oriented language into machine programs. Thus the entire computing community profits from the work of the individual programmer. The primary purpose of the Handbook is to present a set of algorithms of broad utility from the domain of numerical mathematics written in the problem oriented language ALGOL 60. Therefore, volumes I a and I b are in a sense supplementary as they serve to introduce this language. Volume I a gives a description of the language proper and of its use for writing correct programs. Thus, volume I a primarily covers the aspect of man-man communication by means of ALGOL 60.

1. Introduction.- 2. Principles of Algol translation.- 2.1. Basic linguistic definitions.- 2.2. The Backus normal form.- 2.3. The analyzing process.- 2.4. The method of the “Klammergebirge”.- 2.5. Recursive sequential methods and push down lists.- 2.5. 1. The decoding matrix.- 2.5.2. Precedence rules and orders.- 2.6. Example for the use of two push down lists and of precedence rules.- 2.7. The concept of recursive translation.- 2.8. Organization of the translator.- 3. Languages involved in the translation process.- 3.1. Source language.- 3.2. Target language.- 3.3. Meta-language for describing the translator.- 4. Correspondence between elements of source and target language.- 4.1. Declarations in general.- 4.2. Declaration of variables and arrays and data storage allocation in the main program.- 4.2.1. Simple variables.- 4.2.2. Arrays and their information vectors.- 4.2.2.1. Static arrays.- 4.2.2.2. Dynamic arrays.- 4.3. Handling of types.- 4.4. Assignment statements.- 4.4.1. Simple arithmetic variables.- 4.4.2. Name variables, function designators, and type procedure identifiers.- 4.4.3. Subscripted variables.- 4.5. Boolean expressions.- 4.5.1. Truth values.- 4.5.2. Relations.- 4.5.3. Boolean operators.- 4.6. Conditional statements and expressions.- 4.6.1. The if clause.- 4.6.2. Conditional statements.- 4.6.3. Conditional expressions.- 4.7. For statements.- 4.8. Go to statement and switch declaration.- 4.9. Procedures and dynamic storage.- 4.9.1. Variables in procedures.- 4.9.2. Dynamic storage.- 4.10. Procedure calls and declarations.- 4.10.1. Procedure calls.- 4.10.1.1. Actual parameters in procedure calls.- 4.10.1.2. Procedure calls after transformations of actual parameters.- 4.10.1.3. Name calls.- 4.10.2. Procedure declarations.- 4.10.2.1. Value listed formal variables.- 4.10.2.2. Formal arrays.- 4.10.2.3. Function procedures.- 4.10.2.4. Normal procedure exit.- 5. Recursive address calculation.- 5.1. Introduction.- 5.2. Assumptions necessary for the use of recursive address calculation.- 5.3. Use of recursive address calculation for one loop.- 5.3.1. Method I: Difference method.- 5.3.2. Method II: Decomposition method.- 5.4. Nested loops.- 5.4.1. Method I: Difference method.- 5.4.2. Method II: Decomposition method.- 5.4.3. An example.- 5.4.3.1. Difference method.- 5.4.3.2. Decomposition method.- 5.5. Loops with more than one list element.- 5.6. Further optimization possibilities.- 5.6.1. Identification of subscripted variables.- 5.6.2. Generated variables.- 5.6.3. Use of index registers.- 5.6.4. Program organization.- 5.6.5. The example of 5.4.3.- 5.6.5.1. Difference method.- 5.6.5.2. Decomposition method.- 6. Run time organization.- 6.1. The instruction storage allocation.- 6.2. The instruction procedure call.- 6.3. The instruction formal procedure call.- 6.4. The instruction normal procedure exit.- 6.5. The instruction jump to.- 6.6. The instruction formal procedure exit.- 6.7. The instructions name address and name call.- 6.8. The instruction name procedure exit.- 7. Model translator. Description.- 7.1. Introduction.- 7.2. Pass 1. The preparatory pass.- 7.2.1. Input.- 7.2.1.1. Delimiters.- 7.2.1.2. Entities.- 7.2.2. Output.- 7.2.2.1. The modified input program ?1.- 7.2.2.2. The identifier list.- 7.2.2.3. The for list.- 7.3. Pass 2. The implementation of recursive address calculation.- 7.3.1. Output.- 7.3.1.1. Program.- 7.3.1.2. The identifier list.- 7.3.2. Lists used in pass 2.- 7.3.3. Program survey.- 7.4. Pass 3. Decomposition and production of target program.- 7.4.1. Output.- 7.4.2. Program survey.- 7.5. Editorial functions.- 7.5.1. Syntax checking.- 7.6. Run time system. The target language program interpreter.- 8. Algol 60 model translator. Formal part.- Pass 1: preparatory pass.- Pass 2: recursive address calculation pass.- Pass 3: decomposition and generation pass.- Check routine: check procedure calls and substitutions of formal parameters by actuals.- Check routine: check agreeability of actual parameter and specification.- Run time system: target language program interpreter.- START TRANSLATION.- Appendix: Correspondence matrix for actual and formal parameters.