4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ The title of your question talks about linearity, but the body allows affine. Is that deliberate? $\endgroup$
    – Martin Berger
    Commented Sep 15, 2018 at 9:27
  • $\begingroup$ @MartinBerger no, that was a mistake. $\endgroup$
    – MaiaVictor
    Commented Sep 15, 2018 at 17:11
  • $\begingroup$ 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? $\endgroup$
    – Henning Basold
    Commented Sep 19, 2018 at 8:15
  • $\begingroup$ @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... $\endgroup$
    – MaiaVictor
    Commented Sep 19, 2018 at 14:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – Henning Basold
    Commented Sep 19, 2018 at 17:17

1 Answer 1

Reset to default
2
$\begingroup$

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
Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there an explanation of how to apply fix/unfix to mutually recursive definitions? $\endgroup$
    – MaiaVictor
    Commented Sep 27, 2018 at 13:40
  • $\begingroup$ I don't know. That would be a good stackexchange question :) $\endgroup$
    – Łukasz Lew
    Commented Sep 27, 2018 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.