Deriving incremental implementations from algebraic specifications
Emma van der Meulen · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1990
We present a technique for deriving incremental implementations for a subclass of algebraic specifications, namely, conditional well-presented primitive recursive schemes .We use concepts of the translation of well-presented primitive recursive schemes to strongly non-circular attribute grammars, storing results of function applications and their parameters as attributes in an abstract syntax tree of the first argument of the function in question.An attribute dependency graph is used to guide incremental evaluation.The evaluation technique is based on a leftmost innermost rewrite strategy.The technique is extended to conditional well-presented primitive recursive schemes.Whereas in the non-conditional case attribute dependency graphs are constructed before evaluating a term, when working with conditional equations we construct the attribute dependency graph upon evaluation.The class of wellpresented primitive recursive schemes is a very natural one for specifying the static semantics of languages.Allowing conditions to equations in a primitive recursive scheme is the first step in extending this class to one in which the dynamic semantics of languages can be described as well.