The VLISP Verified PreScheme Compiler. Oliva, D. P., Ramsdell, J. D., & Wand, M. Lisp and Symbolic Computation, 8(1/2):111-182, 1995.
The VLISP Verified PreScheme Compiler [link]Paper  abstract   bibtex   
This paper describes a verified compiler for PreScheme, the implementation language for the ľisp run-time system. The compiler and proof were divided into three parts: A transformational front end that translates source text into a core language, a syntax-directed compiler that translates the core language into combinator-based tree-manipulation language, and a linearizer that translates combinator code into code for an abstract stored-program machine with linear memory for both data and code. This factorization enabled different proof techniques to be used for the different phases of the compiler, and also allowed the generation of good code. Finally, the whole process was made possible by carefully defining the semantics of ľisp PreScheme rather than just adopting Scheme's. We believe that the architecture of the compiler and its correctness proof can easily be applied to compilers for languages other than PreScheme.
@Article{OlivaRamsdellWand95,
  author = 	"Dino P. Oliva and John D. Ramsdell and Mitchell Wand",
  title = 	"The VLISP Verified PreScheme Compiler",
  journal = 	"Lisp and Symbolic Computation",
  year = 	"1995",
  URL = {ftp://ftp.ccs.neu.edu/pub/people/wand/vlisp/lasc/prescheme.dvi},
  volume = 	"8",
  number = 	"1/2",
  pages = 	"111-182",
  abstract =   "This paper describes a verified compiler for PreScheme, the
implementation language for the {\vlisp} run-time system.  The
compiler and proof were divided into three parts: A transformational
front end that translates source text into a core language, a
syntax-directed compiler that translates the core language into
combinator-based tree-manipulation language, and a linearizer that
translates combinator code into code for an abstract stored-program
machine with linear memory for both data and code.  This factorization
enabled different proof techniques to be used for the different phases
of the compiler, and also allowed the generation of good
code. Finally, the whole process was made possible by carefully
defining the semantics of {\vlisp} PreScheme rather than just
adopting Scheme's.  We believe that the architecture of the compiler
and its correctness proof can easily be applied to compilers for
languages other than PreScheme."
}

Downloads: 0