License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-28085
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2808/
Benton, Nick ; Hur, Chung-Kil

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

pdf-format:
Dokument 1.pdf (344 KB)

Abstract

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

@InProceedings{benton_et_al:DSP:2010:2808,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2010/2808},
  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 Published by LZI