Charles Farnum

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-431
July 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-431.pdf

Tree rewrite with typed variables can be used to represent many tree transformations in a more compact form than systems with untyped variables. By building on the work of Eduardo Pelegri-Llopart, it is possible to generate linear-time optimal solutions to SET-REACHABILITY -- a generalization of REACHABILITY with a possibly infinite goal set -- for a useful class of typed rewrite systems. The algorithms developed can also handle some untyped systems that are not in BURS, such as systems with rules of the form X --> a( X).

An experiment involving a rewrite system for instruction selection for the Motorola 68000 produced table sizes an order of magnitude larger than those produced by an untyped rewrite system for the same task. It is not clear whether this table size can be limited, or if it is an inherent cost of the power given by types. Although discouraging for the instruction selection application, the table sizes are small enough (under 100k bytes) that the techniques may be useful for smaller applications, or in cases where the added expressability of typed variables outweighs the size explosion of the tables.

BibTeX citation:

@techreport{Farnum:CSD-88-431,
    Author = {Farnum, Charles},
    Title = {A tree transformation facility using typed rewrite systems},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1988},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5754.html},
    Number = {UCB/CSD-88-431},
    Abstract = {Tree rewrite with typed variables can be used to represent many tree transformations in a more compact form than systems with untyped variables. By building on the work of Eduardo Pelegri-Llopart, it is possible to generate linear-time optimal solutions to SET-REACHABILITY -- a generalization of REACHABILITY with a possibly infinite goal set -- for a useful class of typed rewrite systems. The algorithms developed can also handle some untyped systems that are not in BURS, such as systems with rules of the form <i>X</i> --> <i>a</i>(<i>X</i>). <p>An experiment involving a rewrite system for instruction selection for the Motorola 68000 produced table sizes an order of magnitude larger than those produced by an untyped rewrite system for the same task. It is not clear whether this table size can be limited, or if it is an inherent cost of the power given by types. Although discouraging for the instruction selection application, the table sizes are small enough (under 100k bytes) that the techniques may be useful for smaller applications, or in cases where the added expressability of typed variables outweighs the size explosion of the tables.}
}

EndNote citation:

%0 Report
%A Farnum, Charles
%T A tree transformation facility using typed rewrite systems
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-431
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5754.html
%F Farnum:CSD-88-431