License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10351.7
URN: urn:nbn:de:0030-drops-28085
Go to the corresponding Portal

Benton, Nick ; Hur, Chung-Kil

Step-Indexing: The Good, the Bad and the Ugly

10351.BentonNick.Paper.2808.pdf (0.3 MB)


Over the last decade, step-indices have been widely used for the
construction of operationally-based logical relations in the presence
of various kinds of recursion. We first give an argument that
step-indices, or something like them, seem to be required for defining
realizability relations between high-level source languages and
low-level targets, in the case that the low-level allows egregiously
intensional operations such as reflection or comparison of code
pointers. We then show how, much to our annoyance, step-indices also
seem to prevent us from exploiting such operations as aggressively as
we would like in proving program transformations.

BibTeX - Entry

  author =	{Benton, Nick and Hur, Chung-Kil},
  title =	{{Step-Indexing: The Good, the Bad and the Ugly}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-28085},
  doi =		{10.4230/DagSemProc.10351.7},
  annote =	{Keywords: Step-Indexing, Logical Relations, Low-Level Languages, Compiler Correctness}

Keywords: Step-Indexing, Logical Relations, Low-Level Languages, Compiler Correctness
Collection: 10351 - Modelling, Controlling and Reasoning About State
Issue Date: 2010
Date of publication: 04.11.2010

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