ABSTRACT
Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor--the yon Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.
An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining forms can use high-level programs to build still higher level ones in a style not possible in conventional languages.
Associated with the functional style of programming is an algebra of programs whose variables range over programs and whose operations are combining forms. This algebra can be used to transform programs and to solve equations whose "unknowns" are programs in much the same way one tranforms equations in high school algebra. These transformations are given by algebraic laws and are carried out in the same language in which programs are written. Combining forms are chosen not only for their programming power but also the power of their associated algebraic laws. General theorems of the algebra give the detailed behavior and termination conditions for large classes of programs.
A new class of computing systems uses the functional programming style both in its programming language and in its stage transition rules. Unlike von Neumann languages, these systems have semantics loosely coupled to states --- only one state transition occurs per major computation.
- Arvind, and Gostelow, K. P. A new interpreter for data flow schemas and its implications for computer architecture. Tech. Rep. No. 72, Dept. Comptr. Sci., U. of California, Irvine, Oct. 1975.Google Scholar
- Backus, J. Programming language semantics and closed applicative languages. Conf. Record ACM Symp. on Principles of Programming Languages, Boston, Oct. 1973, 71--86. Google ScholarDigital Library
- Berkling, K. J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft für Mathematik und Datenverarbeitung MBH, Bonn, Sept. 1976.Google Scholar
- Burge, W. H. Recursive Programming Techniques. Addison-Wesley, Reading, Mass., 1975.Google Scholar
- Church, A. The Calculi of Lambda-Conversion. Princeton U. Press, Princeton, N.J., 1941. Google ScholarDigital Library
- Curry, H. B., and Feys, R. Combinatory Logic, Vol. I. North-Holland Pub. Co., Amsterdam, 1958.Google Scholar
- Dennis, J. B. First version of a data flow procedure language. Tech. Mem. No. 61, Lab. for Comptr. Sci., M.I.T., Cambridge, Mass., May 1973.Google Scholar
- Dijkstra, E. W. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976. Google ScholarDigital Library
- Friedman, D. P., and Wise, D. S. CONS should not evaluate its arguments. In Automata, Languages and Programming, S. Michaelson and R. Milner, Eds., Edinburgh U. Press, Edinburgh, 1976, pp. 257--284.Google Scholar
- Henderson, P., and Morris, J. H. Jr. A lazy evaluator. Conf. Record 3rd ACM Symp. on Principles of Programming Languages, Atlanta, Ga., Jan. 1976, pp. 95-103. Google ScholarDigital Library
- Hoare, C. A. R. An axiomatic basis for computer programming. Comm. ACM 12, 10 (Oct. 1969), 576--583. Google ScholarDigital Library
- Iverson, K. A Programming Language. Wiley, New York, 1962. Google ScholarDigital Library
- Kosinski, P. A data flow programming language. Rep. RC 4264, IBM T. J. Watson Research Ctr., Yorktown Heights, N.Y., March 1973.Google Scholar
- Landin, P. J. The mechanical evaluation of expressions. Computer J. 6, 4 (1964), 308--320.Google ScholarCross Ref
- Magó, G. A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptt and Inform. Sci.Google Scholar
- Manna, Z., Ness, S., and Vuillemin J. Inductive methods for proving properties of programs. Comm. ACM 16, 8 (Aug. 1973), 491--502. Google ScholarDigital Library
- McCarthy, J. Recursive functions of symbolic expressions and their computation by machine, Pt. 1. Comm. ACM3, 4 {April 1960}, 184--195. Google ScholarDigital Library
- McJones, P. A Church-Rosser property of closed applicative languages, Rep. RJ 1589, IBM Res. Lab., San Jose, Calif., May 1975.Google Scholar
- Reynolds, J. C. GEDANKEN--a simple typeless language based on the principle of completeness and the reference concept. Comm. ACM 13, 5 {May 1970}, 308--318. Google ScholarDigital Library
- Reynolds, J. C. Notes on a lattice-theoretic approach to the theory of computation. Dept. Syst. and Inform. Sci., Syracuse U., Syracuse, N.Y., 1972.Google Scholar
- Scott, D. Outline of a mathematical theory of computation. Proc. 4th Princeton Conf. on Inform. Sci. and Syst., 1970.Google Scholar
- Scott, D., Lattice-theoretic models for various types-free calculi. Proc. 4th Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972.Google Scholar
- Scott, D., and Strachey, C. Towards a mathematical semantics for computer languages. Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn, 1971.Google Scholar
Index Terms
- Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs
Recommendations
Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs
Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor—...
The Art of Teaching Computer Science: Niklaus Wirth
With a goal of improving how computer science is taught, Niklaus Wirth created some of the field's most influential programming languages, including Pascal, Modula, and Oberon. An audio recording of author Charles Severance's Computing Conversations ...
Comments