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 MackieWe 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
SpringerExternal DOI
Pages
15.0Presentation Type
- paper
Event name
Lecture Notes in Computer ScienceEvent type
conferenceISBN
3-540-40254-3Department affiliated with
- Informatics Publications
Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC