The new math of computer programming

ABSTRACT

Structured programming has proved to be an important methodology for systematic program design and development. Structured programs are identified as compound function expressions in the algebra of functions. The algebraic properties of these function expressions permit the reformulation (expansion as well as reduction) of a nested subexpression independently of its environment, thus modeling what is known as stepwise program refinement as well as program execution. Finally, structured programming is characterized in terms of the selection and solution of certain elementary equations defined in the algebra of functions. These solutions can be given in general formulas, each involving a single parameter, which display the entire freedom available in creating correct structured programs.

REFERENCES

• 1: Ashcroft, E., and Manna, Z. The translation of go to' programs to 'while' programs, information, Processing 71, North- Holland, Amsterdam, 1972, pp. 250-255.
• 2: Bauer, F.L. "A Philosophy of Programming", U. of London Special Lectures in Computer Science, Oct. 1973: lecture notes published by Math. Inst., Tech. U. Munchen.
• 3: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 4: David C. Cooper, Böhm and Jacopini's reduction of flow charts, Communications of the ACM, v.10 n.8, p.463, Aug. 1967 [doi>10.1145/363534.363539]
• 5: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 6: Dijkstra, E.W. A constructive approach to the problem of program correctness. BIT 8 (1968), 174-186.
• 7: Herman H. Goldstine, The computer from Pascal to von Neumann, Princeton University Press, Princeton, NJ, 1980
• 8: Henrici, P. Discrete Variable Methods i , Ordi,arv Differential Equations. Wiley, New York, 1962.
• 9: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 10: Householder, A.S. The Theory of Matrices in Numerical Analysis. Blaisdell, New York, 1964.
• 11: Donald E. Knuth, A review of "Structured Programming"., Stanford University, Stanford, CA, 1973
• 12: Kosaraju, S.R. Analysis of structured programs. J. Comput. Syst. Sci. (Dec. 1974) to appear.
• 13: McCarthy, J. A Basis for a Mathematical Theory of Computation. In Computer Programming and Formal Systems, P. Braffort and D. Hirschberg (Eds.), North-Holland, Amsterdam, 1963, pp. 33-70.
• 14: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 15: Allen Newell, Human Problem Solving, Prentice-Hall, Inc., Upper Saddle River, NJ, 1972
• 16: yon Neumann, J., and Goldstine, H.H. Numerical inverting of matrices of high order. Bull. Amer. Math. Soc. 53 (1947), 1021- 1099.
• 17: Wilkes, M.V. Automatic Digital Computers. London, 1956.
• 18: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 19: Niklaus Wirth, Systematic Programming: An Introduction, Prentice Hall PTR, Upper Saddle River, NJ, 1973

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Structured programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs

General Terms:
Design, Performance, Reliability, Theory

Keywords:
algebra of functions, program correctness, stepwise refinement, structured programming