License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2019.8
URN: urn:nbn:de:0030-drops-105159
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10515/
Go to the corresponding LIPIcs Volume Portal

Biernacka, Malgorzata ; Charatonik, Witold

Deriving an Abstract Machine for Strong Call by Need

pdf-format:
LIPIcs-FSCD-2019-8.pdf (0.5 MB)

Abstract

Strong call by need is a reduction strategy for computing strong normal forms in the lambda calculus, where terms are fully normalized inside the bodies of lambda abstractions and open terms are allowed. As typical for a call-by-need strategy, the arguments of a function call are evaluated at most once, only when they are needed. This strategy has been introduced recently by Balabonski et al., who proved it complete with respect to full beta-reduction and conservative over weak call by need.
We show a novel reduction semantics and the first abstract machine for the strong call-by-need strategy. The reduction semantics incorporates syntactic distinction between strict and non-strict let constructs and is geared towards an efficient implementation. It has been defined within the framework of generalized refocusing, i.e., a generic method that allows to go from a reduction semantics instrumented with context kinds to the corresponding abstract machine; the machine is thus correct by construction. The format of the semantics that we use makes it explicit that strong call by need is an example of a hybrid strategy with an infinite number of substrategies.

BibTeX - Entry

@InProceedings{biernacka_et_al:LIPIcs:2019:10515,
  author =	{Malgorzata Biernacka and Witold Charatonik},
  title =	{{Deriving an Abstract Machine for Strong Call by Need}},
  booktitle =	{4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-107-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{131},
  editor =	{Herman Geuvers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10515},
  URN =		{urn:nbn:de:0030-drops-105159},
  doi =		{10.4230/LIPIcs.FSCD.2019.8},
  annote =	{Keywords: abstract machines, reduction semantics}
}

Keywords: abstract machines, reduction semantics
Collection: 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)
Issue Date: 2019
Date of publication: 18.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI