**A Programming Language**

Kenneth E. Iverson

Preface | ||

Chapter 1 The Language | ||

1.1 | Introduction | |

1.2 | Programs | |

1.3 | Structure of the language | |

• | Conventions | |

• | Literals and variables | |

• | Domain and range | |

1.4 | Elementary operations | |

• | Arithmetic operations | |

• | Logical operations | |

• | Residues and congruence | |

1.5 | Structured operands | |

• | Elementary operations | |

• | Matrices | |

• | Index systems | |

1.6 | Rotation | |

1.7 | Special vectors | |

1.8 | Reduction | |

1.9 | Selection | |

• | Compression | |

• | Mesh, mask, and expansion | |

1.10 | Selection vectors | |

1.11 | The generalized matrix product | |

1.12 | Transpositions | |

1.13 | Special logical matrices | |

1.14 | Polynomials and positional number systems | |

1.15 | Set operations | |

1.16 | Ranking | |

1.17 | Mapping and permutation | |

• | Reordering operations | |

• | Permutations | |

• | Function mapping | |

• | Ordering vector | |

1.18 | Maximization | |

1.19 | Inverse functions | |

1.20 | Levels of structure | |

1.21 | Subroutines | |

1.22 | Files | |

1.23 | Ordered trees | |

• | Directed graphs | |

• | Ordered trees | |

• | Right and left list matrices | |

• | Well formation | |

• | The index matrix as a function of the degree vector | |

• | Tree, path, and level compression | |

• | Extension of other operations to trees | |

• | Homogeneous trees | |

References | ||

Notes | ||

Exercises | ||

Chapter 2 Microprogramming | ||

2.1 | Instruction preparation | |

• | Additive indexing | |

• | Indirect addressing | |

• | Dynamic relocation | |

• | Branching, interruption, and trapping | |

• | Complete instruction fetch | |

2.2 | Instruction execution | |

• | Load and store | |

• | Branch instructions | |

• | Logical instructions | |

• | Arithmetic instructions | |

• | Shift instructions | |

• | Convert instructions | |

• | Input-output instructions | |

2.3 | Detailed logical design | |

References | ||

Exercises | ||

Chapter 3 Representation of Variables | ||

3.1 | Allocation and encoding | |

3.2 | Representation of structured operands | |

• | The grid matrix | |

• | Linear representations | |

• | Nonlinear representations | |

• | Chained representations | |

• | Partitions | |

• | Pools | |

• | Summary | |

3.3 | Representation of matrices | |

3.4 | Representation of trees | |

• | Simplified list matrices | |

• | The use of left lists | |

• | Chain list matrices | |

References | ||

Notes | ||

Exercises | ||

Chapter 4 Search Techniques | ||

4.1 | Scanning methods for ranking | |

• | Directed scan | |

• | Controlled scan | |

4.2 | Key transformations | |

• | Nonunique key transformations | |

4.3 | Multiple keys | |

References | ||

Exercises | ||

Chapter 5 Metaprograms | ||

5.1 | Compound statements | |

5.2 | Lukasiewicz notation | |

5.3 | The minimax form of an L-formula | |

5.4 | Translation from complete parenthesis to Lukasiewicz notation | |

5.5 | Translation from Lukasiewicz to complete parenthesis notation | |

References | ||

Exercises | ||

Chapter 6 Sorting | ||

6.1 | Serial sorting methods | |

• | Copy operations | |

• | Simple classification and merge | |

• | Classification and simple merge | |

• | Partial pass methods | |

6.2 | Evaluation of serial sorting methods | |

• | Simple classification and merge | |

• | Classification and simple merge | |

• | Partial pass methods | |

6.3 | Aids to serial sorting processes | |

6.4 | Internal sorting methods | |

• | Simple classification and merge | |

• | Classification and simple merge | |

• | Special internal sorting methods | |

6.5 | Evaluation of internal sorting methods | |

• | Expected number of transpositions | |

• | Bubble sort | |

• | Ranking sort | |

• | Odd-even transposition sort | |

• | Repeated selection sort | |

• | Sorting with replacement | |

• | Comparison of internal sorting methods | |

Appendix to Chapter 6 | ||

References | ||

Notes | ||

Exercises | ||

Chapter 7 The Logical Calculus | ||

7.1 | Elementary identities | |

7.2 | Canonical forms | |

• | Intrinsic vector | |

• | Characteristic vectors | |

7.3 | Decomposition | |

• | Disjunctive canonical form | |

• | Other canonical forms | |

References | ||

Exercises | ||

Summary of Notation | ||

S.1 | Conventions | |

• | Basic conventions | |

• | Branching conventions | |

• | Operand conventions used in summary | |

S.2 | Structural Parameters, Null | |

S.3 | Relations | |

S.4 | Elementary Operations | |

S.5 | Vector Operations | |

S.6a | Row Generalizations of Vector Operations | |

S.6b | Column Generalizations of Vector Operations | |

S.7 | Special Matrices | |

S.8 | Transposition | |

S.9 | Set Operations | |

S.10 | Generalized Matrix Product | |

S.11 | Files | |

S.12 | Trees |