Implementing first-order rewriting with constructor systems
type: Item
instance of: scholarly article
title: Implementing first-order rewriting with constructor systems
zbMATH Open document ID: 0659.68048
DOI: 10.1016/0304-3975(88)90109-0
author: S. H. Smith
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/2027.42/27107
review text: 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.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 03B40
zbMATH DE Number: 4078787
zbMATH Keywords: canonical systems
zbMATH Keywords: term rewriting systems
zbMATH Keywords: functional programming
zbMATH Keywords: constructor
describes a project that uses: Miranda
MaRDI profile type: Publication
OpenAlex ID: W2011986039
cites work: Programming with Equations
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q5581665
cites work: On the correspondence between two classes of reduction systems
cites work: A refinement of strong sequentiality for term rewriting with constructors
cites work: A new implementation technique for applicative languages
description: scientific article; zbMATH DE number 4078787