Record Details

Higher-Order Rewriting and Partial Evaluation

BRICS Report Series

View Archive Info
 
 
Field Value
 
Title Higher-Order Rewriting and Partial Evaluation
 
Creator Danvy, Olivier
Rose, Kristoffer H.
 
Description We demonstrate the usefulness of higher-order rewriting techniques for specializing programs, i.e., for partial evaluation. More precisely, we demonstrate how casting program specializers as combinatory reduction systems (CRSs) makes it possible to formalize the corresponding program transformations as meta-reductions, i.e., reductions in the internal "substitution calculus." For partial-evaluation problems, this means that instead of having to prove on a case-by-case basis that one's "two-level functions" operate properly, one can concisely formalize them as a combinatory reduction system and obtain as a corollary that static reduction does not go wrong and yields a well-formed residual program.We have found that the CRS substitution calculus provides an adequate expressive power to formalize partial evaluation: it provides sufficient termination strength while avoiding the need for additional restrictions such as types that would complicate the description unnecessarily (for our purpose). We also review the benefits and penalties entailed by more expressive higher-order formalisms. In addition, partial evaluation provides a number of examples of higher-order rewriting where being higher order is a central (rather than an occasional or merely exotic) property. We illustrate this by demonstrating how standard but non-trivial partial-evaluation examples arehandled with higher-order rewriting.
 
Publisher Aarhus University
 
Date 1997-06-16
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
 
Format application/pdf
 
Identifier https://tidsskrift.dk/brics/article/view/19267
10.7146/brics.v4i46.19267
 
Source BRICS Report Series; No 46 (1997): RS-46 Higher-Order Rewriting and Partial Evaluation
BRICS Report Series; Nr. 46 (1997): RS-46 Higher-Order Rewriting and Partial Evaluation
1601-5355
0909-0878
 
Language eng
 
Relation https://tidsskrift.dk/brics/article/view/19267/16894
 
Rights Copyright (c) 2014 BRICS Report Series