Busy and lazy FP with infinite objects

ABSTRACT

The paper introduces a variant of Backus' functional programming language FP that has non-strict basic operations as well as non-strict language constructs. The basic data structure of FP, finite nested sequences, is generalized to infinite trees by allowing a non-strict sequence constructor. Then infinite objects can be described as least solutions of recursion equations. For this language variant we give a structured mathematical and operational semantics which employs rewriting rules on finite terms. Infinite objects are evaluated by repeated unfolding of their recursive definitions and subsequent simplifications according to a confluent and Noetherian rewriting system on the level of objects. Two algorithms are given that formalize the ideas of busy (data-driven) and lazy (demand-driven) evaluation. Throughout the paper the semantic concepts of FP are explained; special emphasis is laid on the notion and the proper algebraic treatment of infinite objects.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: John Backus, The Algebra of Functional Programs: Function Level Reasoning, Linear Equations, and Extended Definitions, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.1-43, April 19-25, 1981
• 3: J. Backus: Is computer science based on the wrong fundamental concept of 'program'? An extended concept. In: J.W. de Bakker, J.C. van Vliet (eds.): Algorithmic languages. Proceedings of the International Symposium on Algorithmic Languages. Amsterdam-New York-Oxford: North-Holland 1981, 133-165
• 4: John Backus, Function level programs as mathematical objects, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.1-10, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806757]
• 5: J. Backus: Function-level computing. IEEE Spectrum 19:8, 22-27 (1982)
• 6: Friedrich L. Bauer, Detailization and Lazy Evaluation, Infinite Objects and Pointer Representation, Program Construction, International Summer Schoo, p.406-420, July 26-August 06, 1978
• 7: Friedrich Ludwig Bauer , H. Woessner, Algorithmic Language and Program Development, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 8: F.L. Bauer, M. Broy, W. Dosch, F. Geiselbrechtinger, R. Gnatz, W. Hesse, B. Krieg-Brückner, A. Laut, T. Matzner, B. Möller, F. Nickl, H. Partsch, P. Pepper, K. Samelson (@@@@), M. Wirsing, H. Wössner: The wide spectrum language 84. Technische Universität Monchen, Institut für Informatik, December 1983
• 9: M. Broy: A fixed point approach to applicative multiprogramming. In: M. Broy, G. Schmidt (eds.): Theoretical foundations of programming methodology. Dordrecht: Reidel 1982, 565-622
• 10: V.J. Bush, J.N.F. Oliveira, J.R. Gurd: FP as a basis for dataflow program transformation. University of Manchester, Department of Computer Science, Dataflow Research Project, October 1983
• 11: Robert Cartwright , James Donahue, The semantics of lazy (and industrious) evaluation, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.253-264, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802157]
• 12: B. Courcelle, M. Nivat: Algebraic families of interpretations. Proc. 17th Annual IEEE Symposium on Foundations of Computer Science, 1976, 137-146
• 13: Walter Dosch , Bernhard Möller, An Algebraic Semantics for Bachus' Functional Programming Language with Infinite Objects, GI - 13. Jahrestagung, p.67-85, October 03-07, 1983
• 14: D.P. Friedman, D.S. Wise: CONS should not evaluate its arguments. In: S. Michaelson, R. Milner (eds.): Automata, languages and programming. Edinburgh: Edinburgh University Press 1976, 257-285
• 15: J. A. Goguen , J. W. Thatcher , E. G. Wagner , J. B. Wright, Initial Algebra Semantics and Continuous Algebras, Journal of the ACM (JACM), v.24 n.1, p.68-95, Jan. 1977 [doi>10.1145/321992.321997]
• 16: John Vogel Guttag, The specification and application to programming of abstract data types., 1975
• 17: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 18: G. Huet, D.C. Oppen: Equations and rewrite rules - a survey. In: R.V. Book (ed.): Formal language theory - perspectives and open problems. London: Academic Press 1980, 349-405
• 19: S.C. Kleene: Introduction to metamathematics. New York: Van Nostrand 1952
• 20: G.A. Magó: A network of microprocessors to execute reduction languages. International Journal on Computer and Information Systems 8:5, 349-385, 8:6, 435-471 (1979)
• 21: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 22: B. Möller: Unendliche Objekte und Geflechte. Fakultät für Mathematik und Informatik der Technischen Universität München, Dissertation. TUM-I8213, September 1982. English excerpt: On the algebraic specification of infinite objects - ordered and continuous models of algebraic types. Institut für Informatik, Technischen Universität München, June 1984
• 23: Bernhard Möller, An Algebraic Semantics for Busy (Data-Driven) and Lazy (Demand-Driven) Evaluation and its Application to a Functional Language, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.513-526, July 18-22, 1983
• 24: D. Scott: Lectures on a mathematical theory of computation. In: M. Broy, G. Schmidt (eds.): Theoretical foundations of programming methodology. Dordrecht: Reidel 1982, 145-292
• 25: A. Tarski: A lattice theoretical fixed point theorem and its applications. Pacific J. Math. 5, 285-309 (1955)
• 26: Philip C. Treleaven , David R. Brownbridge , Richard P. Hopkins, Data-Driven and Demand-Driven Computer Architecture, ACM Computing Surveys (CSUR), v.14 n.1, p.93-143, March 1982 [doi>10.1145/356869.356873]
• 27: J. Vuillemin: Correct and optimal implementations of recursion in a simple programming language. Journal of Computer and Systems Science 9, 332-354 (1974)
• 28: John H. Williams, On the Development of the Algebra of Functional Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.733-757, Oct. 1982 [doi>10.1145/69622.357193]
• 29: M. Wirsing, P. Pepper, H. Partsch, W. Dosch, M. Broy: On hierarchies of abstract data types. Acta Informatica 20, 1-33 (1983)

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FP

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Algebraic approaches to semantics; Operational semantics

General Terms:
Languages