An interpreter generator using tree pattern matching

ABSTRACT

Equations provide a rich, intuitively understandable notation for describing nonprocedural computing languages such as LISP and Lucid. In this paper, we present techniques for automatically generating interpreters from equations, analagous to well-known techniques for generating parsers from context-free grammars. The interpreters so generated are exactly faithful to the simple traditional mathematical meaning of the equations-no lattice-theoretic or fixpoint ideas are needed to explain the correspondence. The main technical problem involved is the extension of efficient practical string matching algorithms to trees. We present some new efficient table-driven matching techniques for a large class of trees, and point out unsolved problems in extending this class. We believe that the techniques of this paper form the beginnings of a useful discipline of interpreting, comparable to the existing discipline of parsing.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: {AW76} Ashcroft, E. and W. Wadge, Lucid-A Formal System for Writing and Proving Programs. SIAM J on Computing 5:3, 336-354.
• 3: 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]
• 4: Gérard Berry , Jean-Jacques Lévy, Minimal and optimal computations of recursive programs, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.215-226, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512971]
• 5: Jean-Marie Cadiou, Recursive definitions of partial functions and their computations, 1972
• 6: {Car76} Cargill, T., Deterministic Operational Semantics for Lucid, Res. Rept. CS-76-19, Univ. of Waterloo.
• 7: {DS76} Downey, P., and R. Sethi, Correct Computation Rules for Recursive Languages. SIAM J on Computing 5:3, 378-401.
• 8: Mansour Farah, Correct compilation of a useful subset of lucid., 1977
• 9: {FW76,1} Friedman, D., and D. Wise, Cons should not evaluate its arguments, 3rd Int. Colloq. on Automata, Languages and Programming, Edinburgh.
• 10: {FW76,2} Friedman, D., and D. Wise, Output Driven Interpretation of Recursive Programs, or Writing Creates and Destroys Data Structures. Inf. Proc. Letters 5:6, 85-89.
• 11: {GHM76} Guttag, J., E. Horowitz and D. Musser, Abstract Data Types and Software Validation, Inf. Sci. Inst. Res. Rept. ISI/RR-76-48, Univ. of Southern Cal.
• 12: {Go77} Goguen, J., Abstract E-rors for Abstract Data Types, IFIP Working Conf. on Formal Descr. of Progr. Concepts, J. Dennis, ed., North-Holland.
• 13: 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]
• 14: {Ho78} Hoffmann, C., Matching Tree Patterns, Technical Rept. 291, Dept. of Comp. Sci., Purdue University, 1978.
• 15: {Jo77} Johnson, S. D., An Interpretive Model for a Language Based On Suspended Construction, Tech. Rept. 68, Dept. of Comp. Sci., Indiana University.
• 16: {KB70} Knuth, D., and P. Bendix, Simple Word Problems in Universal Algebras. Computational Problems in Abstract Algebra, J. Leech, ed., Pergamon Press, Oxford, 263-297.
• 17: {KMP77} Knuth, D., J. Morris, and V. Pratt, Fast Pattern Matching in Strings, SIAM J on Computing 6:2, 323-350.
• 18: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 19: Michael J. O'Donnell, Computing in Systems Described by Equations, Springer-Verlag New York, Inc., Secaucus, NJ, 1977
• 20: {Sta77} Staples, J., A Class of Replacement Systems with Simple Optimality Theory, Bull. of the Australian Math. Soc., to appear.
• 21: {Wa76} Wand, M., First Order Entities as Defining Language. Techn. Rept. 29, Dept. of Comp. Science, Indiana University.
• 22: Barry K. Rosen, Tree-Manipulating Systems and Church-Rosser Theorems, Journal of the ACM (JACM), v.20 n.1, p.160-187, Jan. 1973 [doi>10.1145/321738.321750]
• 23: {Vu74} Vuillemin, J., Correct and Optimal Implementations of Recursion in a Simple Programming Language. JCSS 9:3, 332-354.