ELP(ID:1138/elp002)
- Country: us
- Began: 1975
- Published: 1975
- Sammet:SPC
Equational Logic Programming
O'Donnell Semantically pure, fully lazy
Related languages
References:
O'Donnell, M J "Computing systems described by equations" in Compunng and Systems Described by Equations, Lecture Notes in Computer Science 58, G Goos and J Hartmarns, Eds, Sprmger-Verlag, 1977 view details
Hoffmann, C. M. and O'Donnell, M. I. "Interpreter generation using tree pattern matching" pp169-179 view details
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.
in [ACM SIGACT-SIGPLAN] Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas view details
O'Donnel, Michael "A programming language theorem which is independent of Peano arithmetic" 11th Annual ACM Symposium on Theory of Computing, 176-186, May 1979 view details
in [ACM SIGACT-SIGPLAN] Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas view details
O'Donnell, M. A "Programming Language Theorem which is Independent of Peano Arithmetic" Purdue University Dept. of Computer Sciences Technical Report #299 1979 view details
in [ACM SIGACT-SIGPLAN] Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas view details
Huet G. and D. Oppen. "Equations and rewrite rules: a survey" in R. Book, editor. Formal Languages: Perspectives and Open Problems. Academic Press, 1980
view details
in [ACM SIGACT-SIGPLAN] Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas view details
Hoffman, Christoph M. and O'Donnell, Michael J. "Programming with Equations", ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.83-112, Jan. 1982 view details
Abstract: Equations provide a convenient notation for defining many computations, for example, for programming language interpreters. This paper illustrates the usefulness of equational programs, describes the problems involved in implementing equational programs, and investigates practical solutions to those problems. The goal of the study is a system to automatically transform a set of equations into an efficient program which exactly implements the logical meaning of the equations. This logical meaning may be defined in terms of the traditional mathematical interpretation of equations, without using advanced computing concepts.
in [ACM SIGACT-SIGPLAN] Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas view details
Hoffmann, Christoph M. and O'Donnell, Michael J. "Pattern Matching in Trees" p68-95 view details
Abstract: Tree pattern matching is an interesting special problem which occurs as a crucial step m a number of programmmg tasks, for instance, design of interpreters for nonprocedural programming languages, automatic implementations of abstract data types, code optimization m compilers, symbolic computation, context searching in structure editors, and automatic theorem provmg. As with the sorting problem, the variations in requirements and resources for each application seem to preclude a uniform, umversal solution to the tree-pattern-matching problem. Instead, a collection of well-analyzed techmques, from which specific applications may be selected and adapted, should be sought. Five new techniques for tree pattern matching are presented, analyzed for time and space complexity, and compared with previously known methods. Particularly important are applications where the same patterns are matched against many subjects and where a subject may be modified incrementally Therefore, methods which spend some tune preprocessmg patterns in order to improve the actual matching time are included
in [ACM] JACM 29(01) January 1982 view details
Hoffmann, Christoph M. and O`Donnell, Michael J. "Implementation of an interpreter for abstract equations" pp111-121
view details
Abstract: This paper summarizes a project, introduced in [HO79, HO82b], whose goal is the implementation of a useful interpreter for abstract equations that is absolutely faithful to the logical semantics of equations. The Interpreter was first distributed to Berkeley UNIX VAX sites in May, 1983. The main novelties of the interpreter are (1) strict adherence to semantics based on logical consequences; (2) ?lazy? (outermost)evaluation applied uniformly; (3) an implementation based on table-driven pattern matching, with no run-time penalty for large sets of equations; (4) strict separation of syntactic and semantic processing, so that different syntaxes may be used for different problems.
in [ACM SIGACT-SIGPLAN] Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages POPL 84 1984 , Salt Lake City, Utah, United States view details
O'Donnell, M.J. "Equational Logic as a Programming Language", MIT Press 1985 view details
in [ACM SIGACT-SIGPLAN] Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages POPL 84 1984 , Salt Lake City, Utah, United States view details
O'Donnell, Michael J. "Survey of the equational logic programming project" In Colloquium on Resolution of Equations in Algebraic Structures, 1987 view details
Abstract: In 1975 I started a small project to explore the consequences of implementing equational programs with no semantic compromises. Latest results include a compiler that executes exactly the logical consequences of an equational program, with run-time speed comparable to compiled Franz LISP. This paper surveys the development of the project, through theoretical foundations, algorithm development, design and implementation, application, and directions for the future.
External link: Online copy
in [ACM SIGACT-SIGPLAN] Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages POPL 84 1984 , Salt Lake City, Utah, United States view details
O'Donnell, Michael J. "Term-rewriting implementation of equational logic programming" pp1-12 view details
in Lescanne, P. (ed) Proc. of Rewriting Techniques and Applications, Bordeaux, France, 1987. Springer-Verlag view details
Resources
|