A Model of Computation for Source Code Analysis and Transformations

Abstract – Detailed information needed by algorithms that operate on source code is hidden in the code and hard to find. To support the algorithms, various ad hoc code models have been proposed, but the resulting tools are still limited and have language dependencies and poor interoperability. Some contain bugs, perhaps a consequence of the difficulty in developing a tool and a model simultaneously. To address the problem, we propose the Relational Model of Computation (RMC). The RMC consists of two sparse matrices, each representing a set of relations where each tuple is in turn an RMC sub-model of finer granularity. The model is a virtual machine, a relational database, and a container for code at the same time. The concept originated in mathematical notation. The RMC is strongly typed and can model OO entities and concepts such as user types, subtypes, single and multiple inheritance for types and behavior, classes of objects, methods, and overloading and overriding. Polymorphism can be described as conditional logic in one of the matrices. Using the hierarchy of submodels, the RMC can model program entities at any detail, including UML designs, functions, three-address code, statements, tokens, even architecture or machine instructions should the need arise. Partial models are possible for local algorithms such as refactoring. In this paper, we formally define the RMC, prove its Turing completeness, discuss its modeling capabilities and possible applications, and illustrate the mechanics of modeling and analysis with examples. Index Terms – Virtual machines, program representation and analysis, coding tools and techniques, object-oriented design, software maintenance and evolution, refactoring.