Using projection analysis of evaluation-order and its application

ABSTRACT

Projection analysis is a technique for finding out information about lazy functional programs. We show how the information obtained from this analysis can be used to speed up sequential implementations, and introduce parallelism into parallel implementations. The underlying evaluation model is evaluation transformers, where the amount of evaluation that is allowed of an argument in a function application depends on the amount of evaluation allowed of the application. We prove that the transformed programs preserve the semantics of the original programs. Compilation rules, which encode the information from the analysis, are given for sequential and parallel machines.

REFERENCES

• 1: H P Barendregt , M C J D Eekelen , J R W Glauert , J R Kennaway , M J Plasmeijer , M R Sleep, Term graph rewriting, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.141-158, March 1987, Eindhoven, The Netherlands
• 2: A. Bloss, P. Hudak, and J. Young. Code optimisat. ions for lazy evaluation. Ill Proceedings of the Workshop on the Implementation of Lazy Functional Languages, Aspen~is, GSteborg, Sweden, 5-8 September 1988.
• 3: Geoffrey L. Burn, Evaluation transformers—a model for the parallel evolution of functional languages, Proc. of a conference on Functional programming languages and computer architecture, p.446-470, October 1987, Portland, Oregon, United States
• 4: G.L. Burn. Abstrac~ Interpretation and ~he Parallel Evaluation of Functional Languages. PhD thesis, Imperial College, University of London, March 1987.
• 5: G.L. Burn. A shared memory parallel G-machine based on the evaluation transformer model of computation. In Proceedings of lh~ Workshop on the Implementation of Lazy Functional Languages, pages 301-330, Aspen~s, GSteborg, Sweden, 5-8 September 1988.
• 6: Geoffrey Burn, A relationship between abstract interpretation and projection analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.151-156, December 1989, San Francisco, California, United States [doi>10.1145/96709.96724]
• 7: G.L. Burn, C.L. Hankin, and S. Abramsky. Strictness analysis of higher-order functions. Science of Computer Programming, 7:249-278, November 1986.
• 8: G. L. Burn , S. L. Peyton Jones , J. D. Robson, The spineless G-machine, Proceedings of the 1988 ACM conference on LISP and functional programming, p.244-258, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62717]
• 9: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 10: P. Dybjer, Inverse image analysis, 14th International Colloquium on Automata, languages and programming, p.21-30, July 1987, Karlsruhe, Germany
• 11: C. V. Hall , D. S. Wise, Compiling strictness into streams, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.132-143, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41637]
• 12: Paul Hudak , Jonathan Young, Higher-order strictness analysis in untyped lambda calculus, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-109, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512653]
• 13: H. Kingdon, D.R. Lester, and G.L. Burn. A transputer-based HDG-machine. Technical report, GEC Hirst Research Centre, East Lane, Wembley, Middx HA9 7PP, UK, September 1989. Draft Manuscript.
• 14: D.R. Lester. Combinator Graph Reduction: A Congruence and its Applications. Dphil thesis, Oxford University, 1988. Also published as Technical Monograph PRG-73.
• 15: D.R. Lester and G.L. Burn. An executable specification of the HDG-Machine. In Workshop on Massive Parallelism: Hardware, Programming and Applications, Amalfi, Italy, 9-15 October 1989.
• 16: Rita Loogen , Herbert Kuchen , Klaus Indermark , Werner Damm, Distributed Implementation of Programmed Graph Reduction, Proceedings of the Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, p.136-157, June 12-16, 1989
• 17: Dieter Maurer, Strictness computation using special &lgr;-expressions, on Programs as data objects, p.136-155, April 1986, Copenhagen, Denmark
• 18: A. Mycroft. Abstract Interpretation and Optiraising Transformations for Applicative Programs. PhD thesis, University of Edinburgh, Department of Computer Science, December 1981. Also published as CST- 15-81.
• 19: F. Nielson. Abstract Interpretation Using Domain Theory. PhD thesis, Department of Computer Science, University of Edinburgh, October 1984. Also CST-31-84.
• 20: F. Nielson, Two-level semantics and abstract interpretation, Theoretical Computer Science, v.69 n.2, p.117-242, Dec. 11, 1989 [doi>10.1016/0304-3975(89)90091-1]
• 21: Simon L. Peyton Jones , Jon Salkild, The spineless tagless G-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.184-201, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99385]
• 22: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Languages, Performance, Verification