# Is the church-style affine calculus of constructions with unrestricted recursion consistent?

Suppose we take the church-style calculus of constructions, except with affine functions (variables must occur at most once) and mutual recursive definitions. For example:

Nat =
∀ P : *
∀ S : Nat -> P
∀ Z : P
P

Zer =
λ P : *
λ S : Nat -> P
λ Z : Nat
Z

Suc =
λ x : Nat
λ P : *
λ S : Nat -> P
λ Z : Nat
S x

two =
Suc (Suc Zer)


If we built an eager type-checker and asked it to infer Zer, it'd not halt, as Zer's type is infinite:

two : ∀ (P : *) -> ∀ S : (∀ (P : *) -> ∀ S : (∀ (P : *) -> ∀ S : ...


But if we do it lazily, then it'd output:

Zer :
∀ P : *
∀ S : Nat -> P
∀ Z : Nat
Z


Which is the same as Nat and correct, since Zer is indeed a proof of Nat. One could wonder if it could accept "wrong" proofs such as false : ∀ (P : *) -> P, for some construction of false. The obvious approach, though, seems not to work:

false = (λ (x : ∀ (P : *) -> P) -> x) false


If we had top-level type-annotations (such as false : ∀ (P : *) -> P), the checker would indeed accept this term. But, because of curry-style, the only way to infer the type of false is by inferring the type of false: it'll be stuck in an infinite loop and never output anything.

In other words, it seems that, for the subset of terms that this type-inferencer halts, it behaves as a consistent proof assistant. Of course, it works a bit differently from usual as it has infinite types and whatnot, but, intuitively, it seems to be a functional system for mathematical proofs, since it seems to be unable to accept false or other incorrect proofs. If one is able to prove that this type-checker could never accept false, would it indeed be well suited for mathematical proofs?

• The title of your question talks about linearity, but the body allows affine. Is that deliberate? Sep 15 '18 at 9:27
• @MartinBerger no, that was a mistake. Sep 15 '18 at 17:11
• I am not totally sure what the intention of the recursive types you present is. To me, it seems that two styles are mixed, which makes things unnecessarily complex: There are the equi-recursive types, see Part IV of Types and Programming Languages by Pierce, and the second-order encoding of inductive types, see the work by Mendler or Herman Geuvers. It would be helpful if you could clarify how exactly your recursively types should behave. Also, what is the role of affinity here? Sep 19 '18 at 8:15
• @HenningBasold there is just equi-recursive types, which are then used to define what you identify as second-order encoding of inductive types. (Or did I make some mistake?) The rule of affinity was just to make it less complex and avoid different ways to define false that I hadn't predicted... Sep 19 '18 at 14:35
• @MaiaVictor My confusion mainly arises by the fact that the second-order encoding in, say, System F does not need (equi-)recursive types because it is impredicative. But maybe your intention is to remove impredicativity? About affinity: Fair enough. I merely asked about this to understand where you think affinity is important in your example and question. Sep 19 '18 at 17:17

Let me first state that I'm not sure what are you getting at, I'm not sure how linearity/affinity is relevant. I'll answer the question in 'standard' setting.

How would you define how to compare two infinite types lazily?

It seems to me that it can't be done automatically since they can eventually diverge.

[Checking for nominal equality ("pointer quality", exactly same identifier) seems shortsighted since you could define two identical infinite structures Nat and Nat2 and they would not be equal nominally while they should.]

But in some cases it can be done, its just that the programmer needs to lead the checker on how the equality should be verified.

In your case, think about Nat as a type-level fix point:

natF =
∀ nat : *
∀ P : *
∀ S : nat -> P
∀ Z : P
P

Nat = fix nat . natF nat


That gives Nat and the two functions:

fix : Nat -> natF Nat
unfix : natF Nat -> Nat


You can use these functions as annotations that control the infinity and allow the checker to work with finite structures all the time.

This article has a nice intro (there are plenty of similar tutorials): Gentle introduction to the general technique of F-algebras

For Nat, you would use this functor:

data Nat nat = Z | S nat

• Is there an explanation of how to apply fix/unfix to mutually recursive definitions? Sep 27 '18 at 13:40
• I don't know. That would be a good stackexchange question :) Sep 27 '18 at 22:05