Lazy rewriting on eager machinery

ABSTRACT

The article introduces a novel notion of lazy rewriting. By annotating argument positions as lazy, redundant rewrite steps are avoided, and the termination behavior of a term-rewriting system can be improved. Some transformations of rewrite rules enable an implementation using the same primitives as an implementation of eager rewriting.

REFERENCES

• 1: Torben Amtoft, Minimal Thunkification, Proceedings of the Third International Workshop on Static Analysis, p.218-229, September 22-24, 1993
• 2: Lennart Augustsson , Thomas Johnsson, Parallel graph reduction with the (v , G)-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.202-213, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99386]
• 3: Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
• 4: J. C. M. Baeten , J. A. Bergstra , J. W. Klop , W. P. Weijland, Term-rewriting systems with rule priorities, Theoretical Computer Science, v.67 n.2-3, p.283-301, Oct. 1989 [doi>10.1016/0304-3975(89)90006-6]
• 5: Stephen Wilson Bailey, Help, a fast interactive lazy functional language system, University of Chicago, Chicago, IL, 1995
• 6: 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
• 7: T. H. Brus , C. J. D. van Eekelen , M. O. van Leer , M. J. Plasmeijer, CLEAN: A language for functional graph rewriting, Proc. of a conference on Functional programming languages and computer architecture, p.364-384, October 1987, Portland, Oregon, United States
• 8: Geoffrey Burn, Lazy functional languages: abstract interpretation and compilation, MIT Press, Cambridge, MA, 1991
• 9: CHEW, L. P. 1980. An improved algorithm for computing with equations. In Proceedings, 21st IEEE Symposium on Foundations of Computer Science. IEEE, 108-117.
• 10: 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]
• 11: Irène Durand, Bounded, strongly sequential and forward-branching term rewriting systems, Journal of Symbolic Computation, v.18 n.4, p.319-352, Oct. 1994 [doi>10.1006/jsco.1994.1050]
• 12: Iréne Durand , Bruno Salinier, Constructor equivalent term rewriting systems, Information Processing Letters, v.47 n.3, p.131-137, Sept. 14, 1993 [doi>10.1016/0020-0190(93)90236-3]
• 13: Wan Fokkink , Jasper Kamperman , Pum Walters, Within ARM's reach: compilation of left-linear rewrite systems via minimal rewrite systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.679-706, May 1998 [doi>10.1145/291889.291903]
• 14: Wan Fokkink , Jaco van de Pol, Simulation as a Correct Transformation of Rewrite Systems, Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, p.249-258, August 25-29, 1997
• 15: FRIEDMAN, U. P. AND WISE, U. S. 1976. CONS should not evaluate its arguments. In Proceedings, 3rd Colloquium on Automata, Languages and Programming, S. Michaelson and R. Milner, Eds. Edinburgh University Press, Edinburgh, 257-284.
• 16: Jürgen Giesl , Aart Middeldorp, Transforming Context-Sensitive Rewrite Systems, Proceedings of the 10th International Conference on Rewriting Techniques and Applications, p.271-287, July 02-04, 1999
• 17: GOGUEN, J. A., WINKLER, T., MESEGUER, J., FUTATSUGI, K., AND JOUANNAUD, J.-P. 1993. Applications of Algebraic Specifications using OBJ. Cambridge University Press, Cambridge, UK.
• 18: Albert Gräf, Left-to-right tree pattern matching, Proceedings of the 4th international conference on Rewriting techniques and applications, p.323-334, March 1991, Como, Italy
• 19: HARTEL, P. H., FEELEY, M., ALT, M., AUGUSTSSON, L., BAUMANN, P., BEEMSTER, M., CHAILLOUX, E., FLOOD, C. H., GRIESKAMP, W., VAN GRONINGEN, J. H. G., HAMMOND, K., HAUSMAN, B., IVORY, M. Y., JONES, R. E., KAMPERMAN, J. F. T., LEE, P., LEROY, X., LIDS, R. D., LOOSE- MORE, S., RJEMO, N., SERRANO, M., TALPIN, J.-P., THACKRAY, J., THOMAS, S., WALTERS, H. R., WEIS, P., AND WENTWORTH, P. 1996. Benchmarking implementations of functional languages with "pseudoknot", a float-intensive benchmark. J. Funct. Program. 6, 4, 621-655.
• 20: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 21: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 22: Christoph M. Hoffman , Michael J. O'Donnell, Programming with Equations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.83-112, Jan. 1982 [doi>10.1145/357153.357158]
• 23: HUET, G. AND LI~VY, J.-J. 1991. Computations in orthogonM rewriting systems, parts i and ii. In Computational Logic: Essays in Honor of Alan Robinson, J.-L. Lassez and G. Plotkin, Eds. HIT Press, Cambridge, Mass., 395-443.
• 24: P. Z. Ingerman, Thunks: a way of compiling procedure statements with some comments on procedure declarations, Communications of the ACM, v.4 n.1, p.55-58, Jan. 1961 [doi>10.1145/366062.366084]
• 25: Thomas Johnsson, Efficient compilation of lazy evaluation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.58-69, June 17-22, 1984, Montreal, Canada
• 26: JONES, M. P. 1994. The implementation of the Gofer functional programming systern. Tech. Rep. YALEU/DCS/RR-1030, Yale University, New Haven. Available at http://www.cse.ogi.edu/ mpj/pubs/goferimp.html.
• 27: KAMPERMAN, J. F. T. 1996. Compilation of term rewriting systems. Ph.D. thesis, University of Amsterdam, Amsterdam. Available at http://www.babelfish.nl.
• 28: J. F. Th. Kamperman , H. R. Walters, Lazy Rewriting and Eager Machinery, Proceedings of the 6th International Conference on Rewriting Techniques and Applications, p.147-162, April 05-07, 1995
• 29: J. F. Th. Kamperman , H. R. Walters, Minimal Term Rewriting Systems, Selected papers from the 11th Workshop on Specification of Abstract Data Types Joint with the 8th COMPASS Workshop on Recent Trends in Data Type Specification, p.274-290, September 19-23, 1995
• 30: R. Kennaway, The specificity rule for lazy pattern-matching in ambiguous term rewrite systems, Proceedings of the third European symposium on programming on ESOP '90, p.256-270, May 1990, Copenhagen, Denmark
• 31: J. R. Kennaway , J. W. Klop , M. R. Sleep , F. J. de Vries, On the adequacy of graph rewriting for simulating term rewriting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.493-523, May 1994 [doi>10.1145/177492.177577]
• 32: Salvador Lucas, Fundamentals of Context=Sensitive Rewriting, Proceedings of the 22nd Seminar on Current Trends in Theory and Practice of Informatics, p.405-412, November 23-December 01, 1995
• 33: LUTTIK, S. P., RODENBURG, P. H., AND VERMA, R. M. 1996. Correctness criteria for transformations of rewrite systems with an application to Thatte's transformation. Technical Report P9615, University of Amsterdam, Amsterdam.
• 34: 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
• 35: Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
• 36: Michael J. O'Donnell, Computing in Systems Described by Equations, Springer-Verlag New York, Inc., Secaucus, NJ, 1977
• 37: Michael J. O'Donnell, Equational logic as a programming language, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 38: O'DONNELL, M. J. 1998. Introduction: logic and logic programming languages. In Handbook of Logic in Artificial Intelligence and Logic Programming, D. M. Gabbay, Ed. Vol. 5. Oxford University Press, New York, 1-67.
• 39: Kazuhiro Ogata , Kokichi Futatsugi, Implementation of Term Rewritings with the Evaluation Strategy, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.225-239, September 03-05, 1997
• 40: Chris Okasaki , Peter Lee , David Tarditi, Call-by-need and continuation-passing style, Lisp and Symbolic Computation, v.7 n.1, p.57-82, Jan. 1994 [doi>10.1007/BF01019945]
• 41: 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
• 42: 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]
• 43: PLASMEIJER, M. J. August 1998. Personal communication.
• 44: Rinus Plasmeijer , Marko Van Eekelen, Functional Programming and Parallel Graph Rewriting, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 45: PLOTKIN, G. D. 1975. Call-by-name, call-by-value and the A-calculus. Theor. Comput. Sci. 1, 1, 125-159.
• 46: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 47: Bruno Salinier , Robert Strandh, Efficient simulation of forward-branching systems with constructor systems, Journal of Symbolic Computation, v.22 n.4, p.381-399, Oct. 1996 [doi>10.1006/jsco.1996.0058]
• 48: R. Sekar , I. V. Ramakrishnan , P. Mishra, On the power and limitations of strictness analysis, Journal of the ACM (JACM), v.44 n.3, p.505-525, May 1997 [doi>10.1145/258128.258212]
• 49: David Sherman , Robert Strandh , Irène Durand, Optimization of equational programs using partial evaluation, ACM SIGPLAN Notices, v.26 n.9, p.72-82, Sept. 1991
• 50: STAPLES, J. 1980. Computation on graph-like expressions. Theor. Cornput. Sci. 10, 2, 171-185.
• 51: STECKLER, P. AND WAND, M. 1994. Selective thunkification. In Proceedings, 1st Symposium on Static Analysis, B. L. Charlier, Ed. Lecture Notes in Computer Science, vol. 864. Springer- Verlag, Berlin, 162-178.
• 52: R. Strandh, Optimizing equational programs, on Rewriting techniques and applications, p.13-24, May 1987, Bordeaux, France
• 53: R. I. Strandh, Compiling equational programs into efficient machine code, Johns Hopkins University, Baltimore, MD, 1988
• 54: R. I. Strandh, Classes of equational programs that compile into efficient machine code, Proceedings of the 3rd international conference on Rewriting Techniques and Applications, p.449-461, January 1989
• 55: Satish R. Thatte, On the correspondence between two classes of reduction systems, Information Processing Letters, v.20 n.2, p.83-85, Feb. 1985 [doi>10.1016/0020-0190(85)90068-7]
• 56: Satish Thatte, Implementing first-order rewriting with constructor systems (Note), Theoretical Computer Science, v.61 n.1, p.83-92, Oct. 1988 [doi>10.1016/0304-3975(88)90109-0]
• 57: TURNER, D. A. 1979. A new implementation technique for applicative languages. Softw. Pract. Exper. 9, 1, 31-49.
• 58: Rakesh M. Verma, Transformations and confluence for rewrite systems, Theoretical Computer Science, v.152 n.2, p.269-283, Dec. 25, 1995 [doi>10.1016/0304-3975(94)00255-0]
• 59: H. R. Walters, Epic and ARM -- user''s guide --, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1997
• 60: H. R. Walters , J. F. Th. Kamperman, EPIC: An Equational Language -Abstract Machine Supporting Tools-, Proceedings of the 7th International Conference on Rewriting Techniques and Applications, p.424-427, July 27-30, 1996
• 61: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 62: S. C. Wray , J. Fairbairn, Non-strict languages-programming and implementation, The Computer Journal, v.32 n.2, p.142-151, April 1989 [doi>10.1093/comjnl/32.2.142]

INDEX TERMS

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

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

General Terms:
Languages

Keywords:
innermost reduction, lazy rewriting, specificity ordering