Optimizing term rewriting using discrimination nets with specialization
Kazuhiro Ogata, Shigenori Ioroi, Kokichi Futatsugi · 1999
TRAM is an abstract machine for order-sorted conditional term rewriting systems and its rewriting strategy is the E strategy.The straightforward implementation led to the similar performance of interpreters of lazy functional languages.In this paper, some optimization for term rewriting using discrimination nets is described, which can improve the performance of TRAM.The optimization specializes a pattern matcher wrt a discrimination net of rewrite rules and procedures that instantiate the right sides of rewrite rules wrt each of them.The preliminary experiment using rewrite rules to compute Fibonacci numbers showed the specialized implementation was five times faster than the straightforward one.The optimization can be applied to TRAM without difficulty.