- authors: Noam Zeilberger
- year: 2008
- url: https://noamz.org/papers/unity-duality.pdf
- publisher: Elsevier BV
- abstract: Most type systems are agnostic regarding the evaluation strategy for the underlying languages, with the value restriction for ML which is absent in Haskell as a notable exception. As type systems become more precise, however, detailed properties of the operational semantics may become visible because properties captured by the types may be sound under one strategy but not the other. For example, intersection types distinguish between call-by-name and call-by-value functions, because the subtyping law (A→B)∩(A→C)≤A→(B∩C) is unsound for the latter in the presence of effects.In this paper we develop a proof-theoretic framework for analyzing the interaction of types with evaluation order, based on the notion of polarity. Polarity was discovered through linear logic, but we propose a fresh origin in Dummett’s program of justifying the logical laws through alternative verificationist or pragmatist “meaning-theories”, which include a bias towards either introduction or elimination rules. We revisit Dummett’s analysis using the tools of Martin-Löf’s judgmental method, and then show how to extend it to a unified polarized logic, with Girard’s “shift” connectives acting as intermediaries. This logic safely combines intuitionistic and dual intuitionistic reasoning principles, while simultaneously admitting a focusing interpretation for the classical sequent calculus.Then, by applying the Curry–Howard isomorphism to polarized logic, we obtain a single programming language in which evaluation order is reflected at the level of types. Different logical notions correspond directly to natural programming constructs, such as pattern-matching, explicit substitutions, values and call-by-value continuations. We give examples demonstrating the expressiveness of the language and type system, and prove a basic but modular type safety result. We conclude with a brief discussion of extensions to the language with additional effects and types, and sketch the sort of explanation this can provide for operationally sensitive typing phenomena.