Abstraction and Verification in Alphard: Defining and Specifying Iteration and Generators The Alphard "form" provides the programmer with a great deal of control over the implementation of abstract data types. In this paper the abstraction techniques are extended from simple data representation and function definition to the iteration statement, the most important poin t of interaction between data and the control structure of the language itself. A means of specializing Alphard's loops to operate on abstract entities without explicit dependence on the representation of those entities is in troduced. Specification and verification techniques that allow the properties of the generators for such iterations to be expressed in the form of proof rules are developed. Results are obtained that for common special cases of these loops are essentially identical to the corresponding constructs in other languages. A means of showing that a generator will terminate is also provided. CACM August, 1977 Shaw, M. Wulf, W. A. abstraction and representation, abstract data types, assertions, control specialization, correctness, generators,invariants, iteration statements, modular decomposition, program specifications, programming languages, programming methodology, proofs of correctness, types, verification 4.20 5.24 CA770803 JB December 28, 1977 7:59 AM 2940 5 2940 2940 5 2940 2940 5 2940 3150 5 2940 2060 6 2940 2704 6 2940 2842 6 2940 2939 6 2940 2940 6 2940 2941 6 2940 2943 6 2940 3073 6 2940 3148 6 2940