28572 articles – 22062 Notices  [english version]

hal-00150978, version 1

A very modal model of a modern, major, general type system

Andrew W. Appel 12, paul-andré melliès 3, Christopher D. Richards 1, Jérôme Vouillon () 3

Annual Symposium on Principles of Programming Languages (2007) 109-122

Résumé : We present a model of recursive and impredicatively quantified types with mutable references. We interpret in this model all of the type constructors needed for typed intermediate languages and typed assembly languages used for object-oriented and functional languages. We establish in this purely semantic fashion a soundness proof of the typing systems underlying these TILs and TALs---ensuring that every well-typed program is safe. The technique is generic, and applies to any small-step semantics including λ-calculus, labeled transition systems, and von Neumann machines. It is also simple, and reduces mainly to defining a Kripke semantics of the Gödel-Löb logic of provability. We have mechanically verified in Coq the soundness of our type system as applied to a von Neumann machine.

  • 1 :  Department of Computer Science
  • Princeton University
  • 2 :  MOSCOVA (INRIA Rocquencourt)
  • INRIA
  • 3 :  Preuves, Programmes et Systèmes (PPS)
  • CNRS : UMR7126 – Université Paris VII - Paris Diderot
  • Domaine : Informatique/Langage de programmation
 
  • hal-00150978, version 1
  • oai:hal.archives-ouvertes.fr:hal-00150978
  • Contributeur : 
  • Soumis le : Vendredi 1 Juin 2007, 11:35:58
  • Dernière modification le : Vendredi 1 Juin 2007, 11:35:58