Operational Semantics with Hierarchical Abstract Syntax Graphs

Dan R. Ghica
(Huawei Research, Edinburgh; University of Birmingham, UK)

This is a motivating tutorial introduction to a semantic analysis of programming languages using a graphical language as the representation of terms, and graph rewriting as a representation of reduction rules. We show how the graphical language automatically incorporates desirable features, such as alpha-equivalence and how it can describe pure computation, imperative store, and control features in a uniform framework. The graph semantics combines some of the best features of structural operational semantics and abstract machines, while offering powerful new methods for reasoning about contextual equivalence.

All technical details are available in an extended technical report by Muroya and the author and in Muroya's doctoral dissertation.

Invited Paper in Patrick Bahr: Proceedings 11th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2020), Online, 5th July 2020, Electronic Proceedings in Theoretical Computer Science 334, pp. 1–10.
Published: 8th February 2021.

ArXived at: http://dx.doi.org/10.4204/EPTCS.334.1 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org