Program transformation in the presence of errors

ABSTRACT

Language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. This is apparently because being forced to preserve error behavior severely limits the scope of program optimization, even for correct programs. However, preserving error behavior is desirable for debugging, and error behavior must be preserved in any language that permits user-generated exceptions. This paper presents a technique for preserving the power of general program transformations in the presence of a rich collection of distinguishable error values. This is accomplished by introducing an annotation, “Safe”, to mark occurrences of functions that cannot produce errors. Succinct and general algebraic laws can be expressed using Safe, giving program transformations in a language with many error values the same power and generality as program transformations in a language with only a single error value.

REFERENCES

• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Bac78: 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]
• BWW86: J. Backus, J. H. Williams, and E. L. Wimmers. The FL Language Man~tal. Technical Report 1LI 5339 (54809), IBM, 1986.
• CF89: E. Cartwright , M. Felleisen, The semantics of program dependence, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.13-27, June 19-23, 1989, Portland, Oregon, United States
• Hen81: John Hennessy, Program optimization and exception handling, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.200-206, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567554]
• HMT89: R. Harper, R. Milner, and M. ToRe. The Definition of Standard ML--Version 3. Technical Report ECFS-LFCS-89-81, Laboratory for Foundations of Computer Science, University of Edinburgh, 1989.
• HWA*88: P. Hudak, P. Wadler, Arvind, B. Boutel, J. Fairbairn, J. Fasel, J. Hughes, T. Johnsson, D. Kicburtz, S. P. Jones, R. Nikhil, M. Reeve, D. Wise, and J. Young. Report on the Functiortal Programming Language Haskell. Technical Report DCS/RR-666, Yale University, December 1988.
• Ste84: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• Tur85: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
• WH87: Philip Wadler , R. J. M. Hughes, Projections for strictness analysis, Proc. of a conference on Functional programming languages and computer architecture, p.385-407, October 1987, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

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

          Nouns: FP
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

General Terms:
Design, Languages