History Variables - The Semantics, Formal Correctness, and Implementation of History Variables in an Imperative Programming Language

Storing the history of objects in a program is a common task. Maintaining the history of an object in a program has traditionally required programmers either to write specific code for handling the historical data, or to use a library which supports history logging. History variables are variables in a programming language which store not only their current value, but also the values they have contained in the past. Some existing languages do provide support for history variables. However these languages typically have many limits and restrictions on use of history variables. In this thesis we discuss a complete implementation of history variables in an imperative programming language. We discuss the semantics of history variables for scalar types, arrays, pointers, strings, and user defined types. Using the mathematical system of Hoare logic we formally prove the correctness of our informal semantics. We also develop an experimental compiler with support for history variables. The compiler allows us to investigate the practical aspects of implementing history variables and to compare the performance of history variables with their non-history counterparts.