Sacrificing simplicity for convenience: Where do you draw the line?

ABSTRACT

The designers of (functional) programming languages are faced with two occasionally conflicting goals: programmer convenience and semantic simplicity. For example, it is convenient to treat I/O operations as primitive “functions” with side effects, but doing so destroys referential transparency. FL is a functional language that is designed to trade some of the semantic simplicity of a pure language for some of the convenience of a procedural language, by treating I/O operations as primitives with “side effects”, but by using a structuring technique that localizes the scope of those effects. In this way, surprisingly little of the semantic simplicity is lost, as can be seen by comparing the underlying algebraic laws of FL with those of its pure counterpart. FP. This paper describes that comparison and shows that, in fact, for programs involving I/O, the structures of the algebraic laws of the two languages are identical! It concludes by showing that this technique cannot be extended to allow assignment statements without incurring a massive loss in the expressiveness and simplicity of the underlying algebra.

REFERENCES

• Backus 78: 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]
• BWW 86: J. Baokus, J.H. Williams, and E.L. Wimmers, FL Language Manual (Preliminary version), RJ 5339, IBM Almaden Research Center (November, 1986).
• Cartwright 82: 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]
• HW1 85: Joseph Y. Halpern , John H. Williams , Edward L. Wimmers , Timothy C. Winkler, Denotational semantics and rewrite rules for FP, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.108-120, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318623]
• HW2 86: J.Y. Halpern, J.H. Williams, and E.L. Wimmers, Good rewrite strategies for FP, Proceedings of the S3m~posium on Logic in Computer Science (1986), pp. 149-162.
• HW3 87: J.Y. Halpern, and E.L. Wimmers, Full Abstraction and Expressive Completeness for FP, Proceedings of the Symposium on Logic in Computer Science (198"/), pp. 25"/-271.
• Henderson 83: P. Henderson, G. A. Jones, and S. B. Jones, The LispKit Manual, Technical Monograph PRG-32, Oxford University Computing Laboratory, Oxford, England (1983).
• Milner 84: Robin Milner, A proposal for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.184-197, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802035]
• Steele 78: G. L. Steele, Jr. and G. J. Sussman, The revised report on SCHEME: A dialect of Lisp, A.I. Memo 452, MIT Artificial Intelligence Laboratory (1978).
• Stoy 77: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• Stoye 85: W. Stoye, A new scheme for writing functional operating systems, Technical Report No. 56, University of Cambridge Computer Laboratory (1985).
• Turner 82: D.A. Turner, Recursive equations as a programming language, Functional Programming and its Applications, Darlington et al. (editors), Cambridge University Press (1982).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FP

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Design, Languages, Theory