"Bagatelle in C arranged for VDM SoLo"

José N. Oliveira (Universidade do Minho, Braga, Portugal, Senior R&D Partner, Portugal)

Abstract:

This paper sketches a reverse engineering discipline which combines formal and semi-formal methods. Central to the former is denotational semantics, expressed in the ISO/IEC 13817-1 standard specification language (VDMSL). This is strengthened with algebra of programming, which is applied in "reverse order" so as to reconstruct formal specifications from legacy code. The latter include code slicing, a "shortcut" which trims down the complexity of handling the formal semantics of all program variables at the same time.

A key point of the approach is its constructive style. Reverse calculations go as far as absorbing auxiliary variables, introducing mutual recursion (if applicable) and reversing semantic denotations into standard generic programming schemata such as cata/paramorphisms.

The approach is illustrated for a small piece of code already studied in the code-slicing literature: Kernighan and Richtie's word count C programming "bagatelle".

Keywords: algebra of programming, denotational semantics, reverse engineering, slicing

Categories: D.2.1, F.3.1