Towards a Trustworthy Semantics-Based Language Framework via Proof Generation
Open Access
- 15 July 2021
- book chapter
- Published by Springer Nature
- p. 477-499
Abstract
We pursue the vision of anideal language framework, where programming language designers only need to define the formalsyntaxandsemanticsof their languages, and all language tools are automatically generated by the framework. Due to the complexity of such a language framework, it is a big challenge to ensure its trustworthiness and to establish the correctness of the autogenerated language tools. In this paper, we propose an innovative approach based onproof generation. The key idea is to generate proof objects as correctness certificates for each individual task that the language tools conduct, on a case-by-case basis, and use a trustworthy proof checker to check the proof objects. This way, we avoid formally verifying the entire framework, which is practically impossible, and thus can make the language framework bothpracticalandtrustworthy. As a first step, we formalize program execution as mathematical proofs and generate their complete proof objects. The experimental result shows that the performance of our proof object generation and proof checking is very promising.Keywords
This publication has 12 references indexed in Scilit:
- A complete formal semantics of x86-64 user-level instruction set architecture2019
- The Rewrite Engines Competitions: A RECtrospective2019
- KEVM: A Complete Formal Semantics of the Ethereum Virtual Machine2018
- Semantics-based program verifiers for all languagesACM SIGPLAN Notices, 2016
- RV-Match: Practical Semantics-Based Program Analysis2016
- KJS: a complete formal semantics of JavaScript2015
- K-Java2015
- RV-Monitor: Efficient Parametric Runtime Verification with Simultaneous Properties2014
- An executable formal semantics of C with applicationsACM SIGPLAN Notices, 2012
- Results on the propositional μ-calculusTheoretical Computer Science, 1983