Proving the correctness of unfold/fold program transformations using bisimulation

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

  • Geoff W. Hamilton
  • Neil Jones

This paper shows that a bisimulation approach can be used to prove the correctness of unfold/fold program transformation algorithms. As an illustration, we show how our approach can be use to prove the correctness of positive supercompilation (due to Sørensen et al). Traditional program equivalence proofs show the original and transformed programs are contextually equivalent, i.e., have the same termination behaviour in all closed contexts. Contextual equivalence can, however, be difficult to establish directly. Gordon and Howe use an alternative approach: to represent a program's behaviour by a labelled transition system whose bisimilarity relation is a congruence that coincides with contextual equivalence. Labelled transition systems are well-suited to represent global program behaviour. On the other hand, unfold/fold program transformations use generalization and folding, and neither is easy to describe contextually, due to use of non-local information. We show that weak bisimulation on labelled transition systems gives an elegant framework to prove contextual equivalence of original and transformed programs. One reason is that folds can be seen in the context of corresponding unfolds.

Original languageEnglish
Title of host publicationPerspectives of Systems Informatics : 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers
EditorsEdmund Clarke, Irina Virbitskaite, Andrei Voronkov
Number of pages17
PublisherSpringer
Publication date2012
Pages153-169
ISBN (Print)978-3-642-29708-3
ISBN (Electronic)978-3-642-29709-0
DOIs
Publication statusPublished - 2012
Event8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics - Novosibirsk, Russian Federation
Duration: 27 Jun 20111 Jul 2011
Conference number: 8

Conference

Conference8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics
Nummer8
LandRussian Federation
ByNovosibirsk
Periode27/06/201101/07/2011
SeriesLecture notes in computer science
Volume7162
ISSN0302-9743

ID: 172847872