A Sound Definitional Interpreter for a Simply Typed Functional Language

Abstract

In this paper, we develop, in the proof assistant Coq, a definitional interpreter and a type-checker for a simply typed functional language, and formally prove that the mentioned type-checker is sound with respect to the definitional interpreter via progress and preservation. To represent binders, we embark on the choice of “concrete syntax” in which parameters are just names (or strings).

Keywords

• definitional interpreters
• simply typed functional languages
• formal soundness proofs
• the Coq proof assistant