C, Lambda Calculus and Compiler Verification - a study in Haskell of purely-functional techniques for a formal specification of imperative programming languages and an epistemically-sound verification of their compilers

摘要

Formal verification of a compiler is a long-standing problem in computer science and,although recent years have seen substantial achievements in the area, most of the proposedsolutions do not scale very well with the complexity of modern software developmentenvironments. In this thesis, I present a formal semantic model of the popularC programming language described in the ANSI/ISO/IEC Standard 9899:1990, in theform of a mapping of C programs to computable functions expressed in a suitable variantof lambda calculus. The specification is formulated in a highly readable functionalstyle and is accompanied by a complete Haskell implementation of the compiler, coveringall aspects of the translation from a parse tree of a C program down to the actualsequence of executable machine instructions, resolving issues of separate compilation,allowing for optimising program transformations and providing rigorous guarantees ofthe implementation's conformance to a formal definition of the language.In order to achieve these goals, I revisit the challenge of compiler verificationfrom its very philosophical foundations. Beginning with the basic epistemic notions ofknowledge, correctness and proof, I show that a fully rigorous solution of the problemrequires a constructive formulation of the correctness criteria in terms of the translationprocess itself, in contrast with the more popular extensional approaches to compilerverification, in which correctness is generally defined as commutativity of the systemwith respect to a formal semantics of the source and target languages, effectively formalisingvarious aspects of the compiler independently of each other and separatelyfrom its eventual implementation. I argue that a satisfactory judgement of correctnessshould always constitute a direct formal description of the job performed by the softwarebeing judged, instead of an axiomatic definition of some abstract property suchas commutativity of the translation system, since the later approach fails to establish acrucial causal connection between a judgement of correctness and a knowledge of it.The primary contribution of this thesis is the new notion of linear correctness,which strives to provide a constructive formulation of a compiler's validity criteria byderiving its judgement directly from a formal description of the language translationprocess itself. The approach relies crucially on a denotational semantic model of thesource and target languages, in which the domains of program meanings are unifiedwith the actual intermediate program representation of the underlying compiler implementation.By defining the concepts of a programming language, compiler and compilercorrectness in category theoretic terms, I show that every linearly correct compileris also valid in the more traditional sense of the word. Further, by presenting a completeverified translation of the standard C programming language within this framework, Idemonstrate that linear correctness is a highly effective approach to the problem ofcompiler verification and that it scales particularly well with the complexity of modernsoftware development environments.