Files in this item
|(no description provided)|
|Title:||Implementation techniques for rewriting and narrowing|
|Author(s):||Josephson, Norman Alan|
|Doctoral Committee Chair(s):||Dershowitz, Nachum|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||Rewrite systems are directed equations that can be used to compute by repeatedly rewriting an initial term until a final form is obtained. Such systems provide a nondeterministic programming language having convenient mathematical properties. Programs are easy to understand, as they have very simple syntax and semantics, based on equalities, with no explicit control. By allowing variables within the initial term, the term may be thought of as a logical query. It is possible to solve queries by narrowing, i.e. using the left-hand sides of rules to identify subterms with instances to which rules apply, and repeating the process until instantiations of the variables are constructed that can be shown by rewriting to satisfy the query.
In this dissertation, we explore a class of optimizations relating to the repeated rewriting or normalization of a term. By maintaining more and more detailed information about the rewriting process, successive refinements of a basic normalization algorithm are possible which accelerate the discovery of a simplest form at the expense of the space required to store the information about the computation. In addition, we describe implementation techniques for enforcing an eager rewriting/lazy narrowing approach within the context of these optimizations. Rather than backtracking over narrowing steps to capture all solutions to a query, we demonstrate structure sharing techniques that allow us to make use of shared computation paths during the enumeration of solutions. We investigate extensions to the methods that allow us to handle conditional rules. An implementation, R scITE, is described and its performance on several examples is demonstrated.
|Rights Information:||Copyright 1989 Josephson, Norman Alan|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI8924855|