University of Sussex
Browse

File(s) not publicly available

Efficient Reductions with Director Strings

presentation
posted on 2023-06-08, 06:29 authored by François-Régis Sinot, Maribel Fernández, Ian MackieIan Mackie
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.

History

Publication status

  • Published

Publisher

Springer

Pages

15.0

Presentation Type

  • paper

Event name

Lecture Notes in Computer Science

Event type

conference

ISBN

3-540-40254-3

Department affiliated with

  • Informatics Publications

Full text available

  • No

Peer reviewed?

  • Yes

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC