From Big-Step to Small-Step Semantics and Back with Interpreter Specialisation

John P. Gallagher
(Roskilde University, Denmark and IMDEA Software Institute, Spain)
Manuel Hermenegildo
( IMDEA Software Institute, Spain)
Bishoksan Kafle
( IMDEA Software Institute, Spain)
Maximiliano Klemen
( IMDEA Software Institute, Spain)
Pedro López García
( IMDEA Software Institute, Spain)
José Morales
( IMDEA Software Institute, Spain)

We investigate representations of imperative programs as constrained Horn clauses. Starting from operational semantics transition rules, we proceed by writing interpreters as constrained Horn clause programs directly encoding the rules. We then specialise an interpreter with respect to a given source program to achieve a compilation of the source language to Horn clauses (an instance of the first Futamura projection). The process is described in detail for an interpreter for a subset of C, directly encoding the rules of big-step operational semantics for C. A similar translation based on small-step semantics could be carried out, but we show an approach to obtaining a small-step representation using a linear interpreter for big-step Horn clauses. This interpreter is again specialised to achieve the translation from big-step to small-step style. The linear small-step program can be transformed back to a big-step non-linear program using a third interpreter. A regular path expression is computed for the linear program using Tarjan's algorithm, and this regular expression then guides an interpreter to compute a program path. The transformation is realised by specialisation of the path interpreter. In all of the transformation phases, we use an established partial evaluator and exploit standard logic program transformation to remove redundant data structures and arguments in predicates and rename predicates to make clear their link to statements in the original source program.

In Laurent Fribourg and Matthias Heizmann: Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis (VPT/HCVS 2020), Dublin, Ireland, 25-26th April 2020, Electronic Proceedings in Theoretical Computer Science 320, pp. 50–64.
Published: 7th August 2020.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: