Context information for lazy code generation

ABSTRACT

Functional languages like Miranda and Haskell employ a non-strict semantics. This is important for the functional programming style as it allows one to compute with infinite data structures. However, a straightforward implementation of the language will result in a rather inefficient implementation and therefore it is often combined with strictness analysis. A sticky version of the analysis is used to collect the information and annotate the program so that the information can be used by the subsequent passes of the compiler. The strictness analysis and its correctness properties are well understood by means of abstract interpretation whereas its sticky version is more subtle. — The purpose of the present paper is therefore to investigate how far one can go without introducing a sticky version of the analysis and thereby avoid the correctness problems connected with it.

REFERENCES

• 1: G.L.Burn, C.Hankin, S.Abramsky: Strictness analysis for higher-order functions, Science of Computer Programming 7, 1986.
• 2: G. Cousineau , P.-L. Curien, The categorical abstract machine, Science of Computer Programming, v.8 n.2, p.173-202, April 1, 1987 [doi>10.1016/0167-6423(87)90020-7]
• 3: C L Hankin , G L Burn , S L Peyton Jones, A safe approach to parallel combinator reduction, Proc. of the European symposium on programming on ESOP 86, p.99-110, March 1986, Saarbru:9Aicken, Germany
• 4: P.Hudak, P.Wadler: Report on the functional programming language I-Iaskell, Technical Report, Glasgow University, 1988.
• 5: P. Hudak , J. Young, A collecting interpretation of expressions, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-118, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73570]
• 6: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• 7: F. Nielson, Strictness analysis and denotational abstract interpretation, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.120-131, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41636]
• 8: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 9: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures; Procedures, functions, and subroutines

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

General Terms:
Design, Languages