Strictness optimization for graph reduction machines (why id might not be strict)

ABSTRACT

Strictness optimizations in the implementation of lazy functional languages are not always valid. In nonoptimized graph reduction, evaluation always takes place at the request of case analysis or a primitive operation. Hence, the result of a reduction is always a data value and never a function. This implies that in an implementation no argument satisfaction check is required. But in the presence of strict arguments, “premature” reduction may take place outside the scope of a case or primitive operation. This causes problems in graph reducers that use an aggressive take. Two solutions are presented, one based on a run-time argument satisfaction check, the other on a weakened strictness analyzer. Experimental results are used to compare the two solutions and show that the cost of the aggressive take can be arbitrarily high for specific programs. The experimental results enable a trade-off to be made by the reduction machine designer.

REFERENCES

• 1: Guy Argo, Improving the three instruction machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.100-115, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99378]
• 2: L. Augustsson , T. Johnsson, The Chalmers lazy ML-compiler, The Computer Journal, v.32 n.2, p.127-141, April 1989 [doi>10.1093/comjnl/32.2.127]
• 3: BEEMSTER, M. 1993. Optimizing transformations for a lazy functional language. In the 7th Computer Systems, W.-J. Withagen, Ed. Eindhoven Univ. of Technology, The Netherlands, (Nov.), 17-40.
• 4: BEEMSTER, M. 1992. The lazy functional intermediate language STOFFEL. Tech. Rep. CS-92-16, Dept of Computer Systems, Univ. of Amsterdam, The Netherlands.
• 5: 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]
• 6: Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
• 7: Kei Davis , Philip Wadler, Backwards Strictness Analysis: Proved and Improved, Proceedings of the 1989 Glasgow Workshop on Functional Programming, p.12-30, August 21-23, 1989
• 8: John Fairbairn , Stuart Wray, TIM: A simple, lazy abstract machine to execute supercombinators, Proc. of a conference on Functional programming languages and computer architecture, p.34-45, October 1987, Portland, Oregon, United States
• 9: THE GRASP TEAM. 1992. The glorious HASKELL compilation system user's guide. Tech. Rep. Dept. of Computer Science, Univ. of Glasgow, Scotland.
• 10: Pieter H. Hartel , Hugh Glaser , John M. Wild, Compilation of functional languages using flow graph analysis, Software—Practice & Experience, v.24 n.2, p.127-173, Feb. 1994 [doi>10.1002/spe.4380240202]
• 11: HowE, D.B. 1992. Experiments with strict STG code. In the 4th international Workshop on the Parallel Implementation of Functional Languages, H. Kuchen, and R. Loogen, Eds. Aachener Informatik-Berichte 92-19, Fachgruppe Informatik, RWTH Aachen, Germany, 1-8.
• 12: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 13: Thomas Johnsson, Efficient compilation of lazy evaluation, ACM SIGPLAN Notices, v.19 n.6, p.58-69, June 1984
• 14: Paul H. Kelly, Functional Programming for Loosely-Coupled Multiprocessors, MIT Press, Cambridge, MA, 1989
• 15: MULLER, H. L. 1992. Simulating computer architectures. Ph.D. thesis, Dept of Computer Systems, Univ. of Amsterdam, (Feb.), The Netherlands.
• 16: N0CKER, E. G. J. M.H. 1990. Strictness analysis using abstract reduction. Implementation of functional languages on parallel architectures. Tech. Rep. 90-16, Dept. of Computer Science, Univ. of Nijmegen, The Netherlands, (June), 171-201.
• 17: PEYTON JONES, S.L. 1992. Implementing lazy functional languages on stock hardware: The spineless tag}ess G-machine. J. Funct. Program. 2, 2 (Apr.) 127-202.
• 18: 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
• 19: VREE, W.G. 1989. Design considerations for a parallel reduction machine. Ph.D. thesis, Dept of Computer Systems, Univ of Amsterdam, The Netherlands, Dec.
• 20: VREE, W. G. AND HARTEL P. H. 1992. Communication lifting: Fixed point computation for parallelism. Tech. Rep. CS-92-07, Dept of Computer Systems, Univ. of Amsterdam, The Netherlands, Dec.
• 21: H. H. Wang, A Parallel Method for Tridiagonal Equations, ACM Transactions on Mathematical Software (TOMS), v.7 n.2, p.170-183, June 1981 [doi>10.1145/355945.355947]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.4 Processors
          Subjects: Run-time environments; Code generation; Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

General Terms:
Languages, Performance

Keywords:
graph reduction, lazy evaluation, strictness analysis