Defunctionalized Interpreters for Call-by-Need Evaluation

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Olivier Danvy
  • Kevin Millikin, Denmark
  • Johan Munk, Arctic Lake Systems, Denmark
  • Ian Zerny, Denmark
  • Department of Computer Science
Starting from the standard call-by-need reduction for the λ-calculus that is common to Ariola, Felleisen, Maraist, Odersky, and Wadler, we inter-derive a series of hygienic semantic artifacts: a reduction-free stateless abstract machine, a continuation-passing evaluation function, and what appears to be the first heapless natural semantics for call-by-need evaluation. Furthermore we observe that a data structure and a judgment in this natural semantics are in defunctionalized form. The refunctionalized counterpart of this evaluation function is an extended direct semantics in the sense of Cartwright and Felleisen. Overall, the semantic artifacts presented here are simpler than many other such artifacts that have been independently worked out, and which require ingenuity, skill, and independent soundness proofs on a case-by-case basis. They are also simpler to inter-derive because the inter-derivational tools (e.g., refocusing and defunctionalization) already exist.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)240-256
Number of pages16
Publication statusPublished - 2010
EventInternational Symposium on Functional and Logic Programming - Sendai, Japan
Duration: 19 Apr 201021 Apr 2010
Conference number: 10


ConferenceInternational Symposium on Functional and Logic Programming

Bibliographical note

Title of the vol.: Functional and logic programming : 10th International Symposium, FLOPS 2010 / ed. by Matthias Blume, Naoki Kobayashi, Germán Vidal.
ISBN: 3642122507; 9783642122507

See relations at Aarhus University Citationformats

ID: 18797490