Existential Quantification Encoding with RankNTypes

Question

In several places, I read that the equivalent ExistentialQuantification functionality can be used with RankNTypes . Can someone give an example of why this is possible or impossible?

Answer 1

Usually, all type variables in Haskell are implicitly universally quantified in the farthest type field. RankNTypes allows the universal forall quantifier to appear nested, for example. type forall a b. (a -> a) -> b -> b forall a b. (a -> a) -> b -> b very different from forall b. (forall a. a -> a) -> b -> b forall b. (forall a. a -> a) -> b -> b .

There is a sense in which the types on the left side of the function arrow are logically “denied”, in approximately the same sense that (->) is a logical implication. Logically universal and existential quantifiers are related by the De Morgan duality: (∃x. P (x)) is equivalent to ¬ (∀x. ¬P (x)), or, in other words, "there is x such that P (x)" corresponds to " , this does not mean that for all x P (x) is false. "

So, forall to the left of the arrow function is “denied” and behaves as existential. If you put all this to the left of the other arrow of the function, it will be a double negation and again will look like a universal quantifier, modulo some details, detailed.

The same idea of ​​negation also applies to values, therefore, for encoding of type exists x. x exists x. x we want:

• forall x. in contravariant (negative) position
• the value of this type x in the covariant (positive) position.

Since the value must be within the scope of the quantifier, our only choice is double negation - CPS conversion, basically. To avoid restrictions otherwise, we will then quantify the type to the right of the function arrows. So there exists x. x exists x. x translates to forall r. (forall x. x -> r) -> r forall r. (forall x. x -> r) -> r . Compare the placement of types and quantifiers here with the above requirements to make sure it meets the requirements.

In more operational terms, this means that if a function with the type indicated above is given, because we give it a function with a universal quantized argument type, it can apply this function to any type x that it likes, and since it has no other way to get a value of type r , we know that it will apply this function to something. Thus, x will refer to some type, but we do not know that - in essence, the essence of existential quantification.

In more practical, everyday conditions, any universal quantitative variable of a type can be regarded as existential if you look at it from the “other side” of a function type. Since unification performed as part of type inference is beyond the scope of quantization, you may sometimes find yourself in a situation where the GHC will need to combine a type variable in the outer region with a quantified type from the nested region, i.e. how do you get compiler errors about type acceleration and skolems and whatnot, the latter (I suppose) is associated with the normal form of Skolem .

The way this relates to data types using existences is that although you can declare a type of type:

 data Exists = forall a. Exists a 

This is an existential type, to get an "existential type", you need to expand it according to the pattern:

 unexist :: Exists -> r unexist (Exists x) = foo x 

But if you consider what type foo should be in this definition, you will get something like forall a. a -> r forall a. a -> r , which is equivalent to the CPS style encoding above. There is a close connection between CPS conversions and church coding of data types, so the CPS form can also be seen as an updated version of pattern matching.

Finally, by connecting things with logic - starting from where the term "existential quantifier" comes from, note that if you think that it is left from the arrow as a negation and a kind of squint to ignore forall r. ... forall r. ... CPS cruft, these existential type encodings exactly coincide with the dualized De Morgan form ¬ (∀x. ¬P (x)), which was the starting point. So all these are just different ways to look at the same concept.

Answer 2

Something that I thought was useful for understanding CA McCann indicates that the left side of the arrow function is “denied” - it is to look at it from the point of view of game semantics . For example, here is a very simple semantics of a game for first-order logic (stated very informally):

• There are two players: # 1 and # 2
• There are two roles: Protector and Opponent.
• Player # 1 is the Original Protector, Player # 2 is the original Opponent.
• For the sentence ∀xA opponent chooses t , and we play A[x := t] ( A with all free copies of x replaced by t ).
• For an A && B offer, the Adversary chooses against one of the conjunctions.
• To offer not A players switch roles and lose A
• For an atomic proposal, we will consult its meaning of truth; A supporter wins if he is faithful; an adversary wins if he is mistaken.

The point of such games is that the proposal is logically fair if player No. 1 (the initial initiator) has a winning strategy for the corresponding game, i.e. if player # 1 has a winning move no matter what option Player # 2 makes.

Note the switch role in the denial rule. The effect of this rule should be intuitive.

Due to the correspondence of sentences as a type, this can be translated into type theory. Let's reformulate the game in terms of types formed in terms of a certain set of atoms, ∀ , type variables, → , ⊤ and ⊥ :

• Two players; but we will call them Runner and Crasher
• The runner is the initiator, Crasher is the original Opponent
• ∀xA : The adversary chooses the atom P , and we play a[x := P] ( A with all free copies of x replaced by P ]
• a → b : The proponent chooses whether to oppose A ( role switch ) or offer b .
• Atomic type: Winners win if the type is populated, Opponent win if it is uninhabited. (I believe that we have predefined for all atoms, also, that ⊤ inhabit and ⊥ not.)

Note that in the rule for a → b , if Proponent chooses A , then role switches: the initial Initiator should become an Adversary for A This corresponds to the fact that the left side of the arrow is “denied”. (The idea is that ⊥ → b populated no matter what b may be, therefore, if the Initiator a → b has a winning strategy to counter A , then a → b must be populated, so its Supporter wins.)

Again, the idea is that a type is populated if Runner has a winning strategy and if uninhabited iff Crasher has a winning strategy.

Example game: ∀r. (∀a. (a → Int) → a → r) → r ∀r. (∀a. (a → Int) → a → r) → r

• The adversary (Crasher) chooses r := ⊥ : (∀a. (a → Int) → a → ⊥) → ⊥
• Supporter (Runner) chooses opposition to antecedent: ∀a. (a → Int) → a → ⊥ ∀a. (a → Int) → a → ⊥
• The adversary (Runner) chooses a := String : (String → Int) → String → ⊥
• Supporter (Crasher) decides to confront the entrepreneur: String → Int
• Proponent (Runner) selects a sentence: Int
• Int inhabited; Winner (Runner) wins .

Suppose we add a rule for ∃ . The rule should be like this:

• ∃xa : the initiators choose x := P , and we play a[x := P]

Now we can use this to analyze McCann’s claim that ∀r. (∀a. a → r) → r ∀r. (∀a. a → r) → r equivalent to ∃aa , analyzing the corresponding game trees. I'm not going to show a complete game tree (or carefully prove equivalence, really), but I will show two illustrative games:

First game: ∃aa

• Supporter (Runner) chooses a := ⊤ .
• ⊤ inhabited; Winner (Runner) wins .

Second game: ∀r. (∀a. a → r) → r ∀r. (∀a. a → r) → r

• The adversary (Crasher) chooses r := ⊥ : (∀a. a → ⊥) → ⊥
• Supporter (Runner) chooses opposition to antecedent: ∀a. a → ⊥ ∀a. a → ⊥
• Opponent (Runner) chooses a := ⊤ : ⊤ → ⊥
• The adversary (Crasher) loses because he must choose between opposing ⊤ or sentence ⊥ .

Now the unofficial observation I'm going to make here is that in both games, Runner is the one who gets the type that will be used for A Equivalence between ∃aa and ∀r. (∀a. a → r) → r ∀r. (∀a. a → r) → r really comes down to the following: the strategy does not allow Crasher to be the one who chooses for A