When quoting this document, please refer to the following
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 =	{Nick Benton and Chung-Kil Hur},
  title =	{Step-Indexing: The Good, the Bad and the Ugly},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  year =	{2010},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  number =	{10351},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Step-Indexing, Logical Relations, Low-Level Languages, Compiler Correctness}

Keywords: Step-Indexing, Logical Relations, Low-Level Languages, Compiler Correctness
Seminar: 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