Efficient Reductions with Director Strings

Sinot, François-Régis, Fernández, Maribel and Mackie, Ian (2003) Efficient Reductions with Director Strings. In: Lecture Notes in Computer Science.

Full text not available from this repository.


We present a name free λ-calculus with explicit substitutions based on a generalized notion of director strings: we annotate a term with information about how each substitution should be propagated through the term. We first present a calculus where we can simulate arbitrary β-reduction steps, and then simplify the rules to model the evaluation of functional programs (reduction to weak head normal form). We also show that we can derive the closed reduction strategy (a weak strategy which, in contrast with standard weak strategies allows certain reductions to take place inside λ-abstractions thus offering more sharing). Our experimental results confirm that, for large combinator based terms, our weak evaluation strategies out-perform standard evaluators. Moreover, we derive two abstract machines for strong reduction which inherit the efficiency of the weak evaluators.

Item Type: Conference or Workshop Item (Paper)
Schools and Departments: School of Engineering and Informatics > Informatics
Depositing User: Ian Mackie
Date Deposited: 06 Feb 2012 20:30
Last Modified: 12 Apr 2012 09:08
URI: http://sro.sussex.ac.uk/id/eprint/26223
📧 Request an update