Breaking Through the Normalization Barrier: A Self-Interpreter for F-omega
According to conventional wisdom, a self-interpreter for a strongly normalizing lambda-calculus is impossible. We call this the normalization barrier. The normalization barrier stems from a theorem in computability theory that says that a total universal function for the total computable functions is impossible. In this paper we break through the normalization barrier and define a self-interpreter for System F_omega, a strongly normalizing lambda-calculus. After a careful analysis of the classical theorem, we show that static type checking in F_omega excludes the proof’s diagonalization gadget and leaves open the possibility for a self-interpreter. Along with the self-interpreter, we program four other operations in F_omega, including a continuation-passing style transformation. Our operations rely on a new approach to program representation that may be useful in theorem provers and compilers.
Poster (poster.pdf) | 264KiB |
Wed 20 Jan Times are displayed in time zone: Guadalajara, Mexico City, Monterrey change
10:30 - 12:10: Track 2: Types and FoundationsResearch Papers at Grand Bay South Chair(s): Robert AtkeyUniversity of Strathclyde | |||
10:30 - 10:55 Talk | Breaking Through the Normalization Barrier: A Self-Interpreter for F-omega Research Papers Media Attached File Attached | ||
10:55 - 11:20 Talk | Type Theory in Type Theory using Quotient Inductive Types Research Papers Media Attached File Attached | ||
11:20 - 11:45 Talk | System Fω with Equirecursive Types for Datatype-generic Programming Research Papers Yufei CaiUniversity of Tübingen, Germany, Paolo G. GiarrussoUniversity of Tübingen, Germany, Klaus OstermannUniversity of Tübingen, Germany Media Attached | ||
11:45 - 12:10 Talk | A Theory of Effects and Resources: Adjunction Models and Polarised Calculi Research Papers Pierre-Louis CurienUniv. Paris Diderot and INRIA Paris-Rocquencourt, Marcelo FioreComputer Laboratory, University of Cambridge, Guillaume Munch-MaccagnoniComputer Laboratory, University of Cambridge |