TermGraph '04

Abstract

Explicit Alpha Conversion and Garbage Collection in X
by S. van Bakel and J. Raghunandan.

In this paper we study the calculus of circuits $\X$, as first presented in \cite{Lengrand'03} and studied in detail in \cite{vBLL'05}. We will present improvements on the implementation for $\X$ using term graph rewriting techniques that was presented in \cite{vBR-TermGraph'04}, which result in a far more efficient running of the reduction engine. We show that alpha conversion can be dealt with `on the fly', by implementing the avoidance of capture by modifying the rewrite rules. We then study two different approaches to garbage collection, and compare the various implementations by presenting benchmarks.

Submitted:

ps pdf