Correct by Construction Language Implementations

Abstract

Programming language implementations bridge the gap between what the program developer sees and understands, and what the computer executes. Hence, it is crucial for the reliability of software that language implementations are correct. Correctness of an implementation is judged with respect to a criterion. In this thesis, we focus on the criterion type correctness, striking a balance between the difficulty of the assessment of the criterion and its usefulness to rule out errors throughout a programming language implementation. If both the front- and the back-end fulfill their role in maintaining the type contract between the programmer and the language implementation, then unexpected type errors will not occur when the program is executed. To verify type correctness throughout a language implementation, we want to establish it formally. That is, we aim to give a specification of program typing in a formal language, and to give a mathematical proof that every part of the language implementation satisfies the necessary property to make the whole implementation type-correct. Type checkers ought to be sound and only accept programs that are indeed typeable according to the specification of the language. Interpreters should be type safe, and reduce expressions to values of the same type. Program compilers should preserve well-typing when they transform programs. These properties are essential for implementations of typed programming languages, ensuring that the typing of the source program is a meaningful notion that can be trusted by the programmer to prevent certain errors from occurring during program execution. A conventional formal type-