An APL Compiler - Budd, Timothy

. .

Résumé :
Presents the results of an investigation into the issues raised by the development of a compiler for APL, a very high level computer programming language. APL presents a number of novel problems for a compiler writer: weak variable typing, run time changes in variable shape, and a host of primitive operations. Through the integration of several recently developed compiler construction techniques, such as data flow analysis, and a novel and space efficient demand driven or lazy evaluation approach to code generation, the author has been able to produce a true compiler for the language while still maintaining the felxibility and ease that are the hallmarks of APL.

Sommaire:
1. Why A Compiler ?.- 1.1. APL Terminology.- 1.2. The Disadvantages of a Compiler.- 1.3. The Compiler Passes.- 1.3.1. The Parsing Pass.- 1.3.2. The Inferencing Pass.- 1.3.3. The Access Determination Pass.- 1.3.4. The Resource Allocation Pass.- 1.3.5. The Code Generation Pass.- 1.4. Compiling for a Vector Machine.- 2. The Inferencing Pass.- 2.1. A Hierarchy of Attributes.- 2.2. Expression Flow Analysis.- 2.3. Intraprocedural Dataflow Analysis.- 2.4. Interprocedural Dataflow Analysis.- 2.5. An Example - The Spiral of Primes.- 2.5.1. Statement Analysis.- 2.5.2. Intraprocedural Analysis.- 2.5.3. Interprocedural Analysis.- 2.5.4. The Importance of Declarations.- 2.5.5. The Size of the Generated Programs.- 3. Code Generation Overview.- 3.1. Demand Driven Evaluation.- 3.2. Boxes.- 3.3. When Not to use Space Efficient Evaluation.- 3.4. A Note on Notation.- 4. Simple Space Efficient Functions.- 4.1. Assignment.- 4.1.1. Nested Assignment.- 4.1.2. Assignment to Quad.- 4.2. Leaves.- 4.2.1. Constants.- 4.2.2. Identifiers.- 4.3. Primitive Scalar functions.- 4.4. Ravel, Reshape and Iota.- 4.5. Outer Product.- 4.6. Subscripting.- 4.7. Mod and Div.- 5. Further Space Efficient Functions.- 5.1. Expansion Vectors.- 5.2. Reduction.- 5.3. Scan.- 5.4. Compression and Expansion.- 5.5. Catenation.- 5.6. Dyadic Rotation.- 5.7. Inner Product and Decode.- 6. Structural Functions.- 6.1. Computing the Stepper.- 6.1.1. Monadic Transpose.- 6.1.2. Take.- 6.1.3. Drop.- 6.1.4. Reversal.- 6.1.5. Dyadic Transpose.- 6.2. The Accessor.- 6.3. Sequential Access.- 6.4. A Nonobvious Optimization.- 7. Space Inefficient Functions.- 7.1. Semi Space Efficient Functions.- 7.2. Collectors.- 7.3. Branching.- 8. Compiling for a Vector Machine.- 8.1. Machine Model.- 8.2. Columns and Request Forms.- 8.3. Code Generation.- 8.3.1. Reduction.- 8.3.2. Scan.- 8.3.3. Compression and Expansion.- 8.3.4. Catenation.- 8.3.5. Dyadic Rotation.- 8.3.6. Structural Functions.- 8.3.7. Outer Product and Subscript.- 9. Epilogue.- Appendix 1. The Language of the APL Compiler.- Appendix 2. A Simple Example.- A Critique.- Appendix 3. A Longer Example.- References.