Leibniz and Liskov
Leibniz equality of two types a
and b
is the proposition that in any context, one can be substituted for the other:
f a -> f bA value of this type brings to the value level the proof that two types are equal. The only value of this type is the identity function.
The Liskov substitution principle is very similar to Leibniz equality, but only in the contravariant position: If a function takes an argument of type b
and a
is a subtype of b
, then the function must accept an argument of type a
. If f
is a type constructor that uses its argument only negatively, then a
is a subtype of b
if there is a value of type
f b -> f aFor example,
λx . x -> b
uses x
negatively, and any b -> b
is also trivially an a -> b
when a
is a subtype of b
. The only value of type f b -> f a
is the cast
function.
Let's write the kind for type constructors that use their argument negatively as * -(-)-> *
rather than just * -> *
, and the kind for type constructors that use their argument positively as * -(+)-> *
. Then, the following terms should validate our understanding that supertyping is dual to subtyping:
dual : ∀ a:* . ∀ b:* . ∀ g: * -(+)-> * . (∀ f: * -(-)-> * . f b -> f a) -> g a -> g b dual |a |b |g less bot = less [λx:* . g x -> g b] (λy:g b . y:g b) bot dual' : ∀ a:* . ∀ b:* . ∀ f: * -(-)-> * . (∀ g: * -(+)-> * . g a -> g b) -> f b -> f a dual' |a |b |f more top = more [λx:* . f x -> f a] (λy:f a . y:f a) topSo subtyping, like type equality, can be brought to the value domain. I now have two questions:
No comments:
Post a Comment