Implementing X
Steffen van Bakel, Jayshan Raghunandan · Electronic Notes in Theoretical Computer Science · 2005
This paper presents a term graph rewriting system as an implementation for the X-calculus, a substitution-free language that can be used to describe the behaviour of functional programming languages at a very low level of granularity, and has first been defined in [Stéphane Lengrand. Call-by-value, call-by-name, and strong normalization for the classical sequent calculus. In Bernhard Gramlich and Salvador Lucas, editors, Electronic Notes in Theoretical Computer Science, volume 86. Elsevier, 2003; S. van Bakel, S. Lengrand, and P. Lescanne. The language X: circuits, computations and classical logic. Submitted, 2004]. Since the calculus has a notion of binding, in the context of sharing a notion of rebinding is introduced that helps avoid double binding of names.