In Types and Programming Languages by Pierce, how does the following achieve the definition of an existential type in terms of universal type, by polymorphic version of Church encoding of pairs?
24.3 Encoding Existentials
The encoding of pairs as a polymorphic type in §23.4 suggests a similar encoding for existential types in terms of universal types, using the intuition that an element of an existential type is a pair of a type and a value:
{∃X,T} := ∀Y. (∀X. T→Y) → Y.
That is, an existential package is thought of as a data value that, given a result type and a continuation, calls the continuation to yield a final result. The continuation takes two arguments—a type X and a value of type T—and uses them in computing the final result.
To complete the quote, the polymorphic version of Church encoding of pairs of numbers is given in Exercise 23.4.8 (p349 p546):
pairNat = λn1:CNat. λn2:CNat.
λX. λf:CNat→CNat→X. f n1 n2;
fstNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n1);
sndNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n2);
which is further generalized to pairs of elements of any types, on p352
we use the abbreviation Pair X Y (generalizing the PairNat type from Exercise 23.4.8) for the Church encoding of pairs with first component of type X and second component of type Y:
Pair X Y = ∀R. (X→Y→R) → R;
The operations on pairs are simple generalizations of the operations on the type PairNat above:
> pair : ∀X. ∀Y. X → Y → Pair X Y fst : ∀X. ∀Y. Pair X Y → X snd : ∀X. ∀Y. Pair X Y → Y
Thanks.
Pair X Y
is an encoding of a variant typeX + Y
? Because it isn't. $\endgroup$