Lambda the Ultimate

This wasn't posted yet, that I could find. Sorry if this is a dupe. Neelk doesn't self-promote, I guess. :-)

Abstract

In this paper, we show how to integrate linear types with type dependency, by extending the linear/non-linear calculus of Benton to support type dependency. Next, we give an application of this calculus by giving a proof-theoretic account of imperative programming, which requires extending the calculus with computationally irrelevant quantification, proof irrelevance, and a monad of computations. We show the soundness of our theory by giving a realizability model in the style of Nuprl, which permits us to validate not only the B laws for each type, but also the n laws.

These extensions permit us to decompose Hoare triples into a collection of simpler type-theoretic connectives, yielding a rich equational theory for dependently-typed higher-order imperative programs. Furthermore, both the type theory and its model are relatively simple, even when all of the extensions are considered.

Personally I find the abstract a little over my head, but am excited when I read stuff like, "We would like to fully integrate dependent and linear type theory. Linear type theory would permit us to extend the Curry-Howard correspondence to (for example) imperative programs, and type dependency permits giving very precise types to describe the precise functional behavior of those programs."

Funny how the 'Fair Reactive' paper was just recently mentioned on the ATS list.