Sunday, February 17, 2008

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 b
A 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 a
For 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) top
So subtyping, like type equality, can be brought to the value domain. I now have two questions:
  1. Is there an analogue of FC (mirror) for F<: (mirror 1, mirror 2, mirror 3)?
  2. Is there a problem similar to decomposition for Liskov substitutability?

No comments: