Program Equivalence through Trace Equivalence
Abstract: Often when programmers modify source code they intend to preserve some parts of the program behaviour. We propose a formal criterion by which to characterise the preserved part of the program behaviour. Two program versions are equivalent up to a set of affected objects A, if executions of the two versions correspond at each execution step when we do not consider the objects in A. We propose a sufficient condition for this criterion. It suffices to establish that traces of method calls and returns between A objects and other objects are equivalent. Examining the stack and heap at each execution step is not necessary. We give a proof of the sufficiency of this condition, much of which we have automatically verified using Dafny. We also discuss our experiences with Dafny and detail how some interesting parts of our Dafny proof work.
(fool2014-traceequivalence.pdf) | 392KiB |
(traceEquivalenceSlides.pdf) | 381KiB |
Mon 20 OctDisplayed time zone: Tijuana, Baja California change
10:30 - 12:00 | |||
10:30 30mTalk | Program Equivalence through Trace Equivalence FOOL File Attached | ||
11:00 30mTalk | The Problem of Structural Type Tests in a Gradual-Typed Language FOOL John Boyland University of Wisconsin, Milwaukee File Attached | ||
11:30 30mTalk | Managing Gradual Typing with Message-Safety in Dart FOOL File Attached |