Implementing first-order rewriting with constructor systems
Most first-order term rewriting systems used in functional programming require argument patterns to be built from constructor symbols in order to allow simple efficient implementations, although more general classes such as linear nonambiguous systems [\textit{G. Huet} and \textit{J.-J. Levy}, ``Computations in nonambiguous linear term rewriting systems, Tech. Rep. 359, INRIA, France (1979)] have greater expressive power. In Inf. Process. Lett. 20, 83-85 (1985; Zbl 0566.68036) we presented a technique for implementing linear nonambiguous systems with an underlying engine that uses constructor-based definitions and showed that the required translation causes an expansion in system size that is quadratic in the worst case, but relatively small in realistic cases such as the LISP interpreter of \textit{C. M. Hoffmann} and \textit{M. O'Donnell} [ACM Trans. Program. Lang. Syst. 4, 83-112 (1982; Zbl 0481.68008)]. We show that the technique is applicable to three other classes - where applicability means preservation of defining characteristics and normal forms - if rewriting in the translated system respects a weak ordering on the new equations. The three classes are semi-regular (confluent non- overlapping), canonical (confluent terminating) and confluent call-by- value systems.
- On the correspondence between two classes of reduction systems
- Constructor equivalent term rewriting systems
- Constructor equivalent term rewriting systems are strongly sequential: A direct proof
- Comparison of priority rules in pattern matching and term rewriting
- Transformations and confluence for rewrite systems
- A new implementation technique for applicative languages
- A refinement of strong sequentiality for term rewriting with constructors
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- scientific article; zbMATH DE number 3299786 (Why is no real title available?)
- On the correspondence between two classes of reduction systems
- Programming with Equations
- On the correspondence between two classes of reduction systems
- Full abstraction and limiting completeness in equational languages
- Remarks on Thatte's transformation of term rewriting systems
- Rewriting conversions implemented with continuations
- On constructor rewrite systems and the lambda calculus
- A Fully Abstract Semantics for Constructor Systems
- scientific article; zbMATH DE number 512772 (Why is no real title available?)
- Complexity hierarchies and higher-order cons-free term rewriting
- Complexity hierarchies and higher-order cons-free rewriting
- Rewriting and narrowing for constructor systems with call-time choice semantics
- Compiling collapsing rules in certain constructor systems
- Transformations and confluence for rewrite systems
- Comparison of priority rules in pattern matching and term rewriting
This page was built for publication: Implementing first-order rewriting with constructor systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112601)