Formal program construction by transformations is a method of software development in which a program is derived from a formal problem specification by manageable, controlled transformation steps which guarantee that the final product meets the initial specification. This methodology has been investigated in the Munich project CIP (computer-aided intuition-guided programming). The research includes the design of a wide-spectrum language specifically tailored to the needs of transformational programming, the construction of a transformation system to support the methodology, and the study of transformation rules and other methodological issues. Particular emphasis has been laid on developing a sound theoretical basis for the overall approach.>

The report gives a complete defining description of the international algorithmic language ALGOL 60. This is a language suitable for expressing a large class of numerical processes in a form sufficiently concise for direct automatic translation into the language of programmed automatic computers. The introduction contains an account of the preparatory work leading up to the final conference, where the language was defined. In addition the notions reference language, publication language, and hardware representations are explained. In the first chapter a survey of the basic constituents and features of the language is given, and the formal notation, by which the syntactic structure is defined, is explained. The second chapter lists all the basic symbols, and the syntactic units know as identifiers, numbers, and strings are defined. Further, some important notions such as quantity and value are defined. The third chapter explains the rules for forming expressions, and the means of these expressions. Three different types of expressions exist: arithmetic, Boolean (logical), and designational. The fourth chapter describes the operational units of the language, known and statements. The basic statements are: assignment statements (evaluation of a formula), go to statements (explicit break of the sequence of execution of statements), dummy statements, and procedure statements (call for execution of a closed process, defined by a procedure declaration). The formation of more complex structures, having statement character, is explained. Thes include: conditional statements, for statements, compound statements, and blocks. In the fifth chapter the units known as declarations, serving for defining permanent properties of the units entering into a process described in the language, are defined. The report ends with two detailed examples of the use of the language, and an alphabetic index of definitions.

Iteration processes may be classified according to their asymptotic behavior.In particular a process is said to be linearly or quadratically convergent to a stationary solution if, for the error f~ = x, -x of the ith approximation x~, using a convenient norm, the respective bounds fl L+, ][ < 71 JJ fL Jl (0<7< D, [I f,+l [[ <~ 72 I1 f, I[ 2 are valid in a certain neighborhood of x.This definition states nothing concerning the behavior in the large, which is, in practice at least, as important as the asymptotic behavior.For matrix problems, however, there exist special classes of iterative procedures which are linearly or quadratically convergent in the large, that is, for almost any choice of the trial solution; the word "almost" is used in its classical meaning.These procedures, as we shall show explicitly later on, are based theoretically-but not numerically---on the step-by-step forward solution of certain linear difference equations with constant coefficients, like Bernoulli's equation; therefore we call them procedures of Bernoulli type.As is well known, these solutions are weighted power sums of certain characteristic quantities dp : a¢ --~ e, d~'; for the sake of simplicity we disregard confluent solutions.All essential iteration quantities are certain ratios of such power sums, differing for example in the index i or in the weights e,.This means that the convergence behavior in the large is not more difficult to discuss than for the classical method of D. Bernoulli for the determination of zeros of a polynomial.As one may expect, the characteristic quantities d~ are the eigenvalues ~,1, ~2, • • • , X, of the matrix involved or, in more general eases, the (:)products of m eigenvalues (m = 2, 3, ... , n).These processes of Bernoulli type are obviously linearly convergent.Quad-• Presented at the Conference on Matrix Computations, Detroit, Mich., Sept. 3--6, 1957.The preparation of this paper was sponsored in part by the Office of Naval Research, U. S. Navy.Reproduction in whole or in part is permitted for any purpose of the United States Government.