[TYPES] Parametricity with subtyping and a Top type

Tim Sweeney Tim.Sweeney at epicgames.com
Wed May 11 14:45:26 EDT 2005


Does subtyping and the existance of a Top type necessarily break
parametricity?

Parametricity guarantees that every function of type forall a.
a->a->Bool is a constant function.  The same derivation appears
applicable to forall a. a->a->Top also, implying that it too must be
constant.  But \x.\y.x and \x.\y.y are distinct functions inhabiting
forall a. a->a->Top.

What has gone wrong here?

Pierce's thesis touches on Top in F/\ but doesn't seem to address
parametricity.

Does there exist a systematic study of type system extensions known to
be compatible or incompatible with parametricity?

Tim Sweeney


More information about the Types-list mailing list