Article ID Journal Published Year Pages File Type
4662874 Journal of Applied Logic 2016 29 Pages PDF
Abstract

There are two versions of type assignment in the λ  -calculus: Church-style, in which the type of each variable is fixed, and Curry-style (also called “domain free”), in which it is not. As an example, in Church-style typing, λx:A.xλx:A.x is the identity function on type A  , and it has type A→AA→A but not B→BB→B for a type B different from A  . In Curry-style typing, λx.xλx.x is a general identity function with type C→CC→C for every type C. In this paper, we will show how to interpret in a Curry-style system every Pure Type System (PTS) in the Church-style without losing any typing information. We will also prove a kind of conservative extension result for this interpretation, a result which implies that for most consistent PTSs of the Church-style, the corresponding Curry-style system is consistent. We will then show how to interpret in a system of the Church-style (a modified PTS, stronger than a PTS) every PTS-like system in the Curry style.

Related Topics
Physical Sciences and Engineering Mathematics Logic
Authors
, , ,