We explore a class of models of polymorphism, subtyping and resucrsion based on a combination of traditional recursion theory and simple domain theory. A significant propety of our primary model is that types are coded by natural numbers using any index of their supremum oeprator. This leads to a distinctive view of polymorphic functions that has many of jthe usual parametricity properties. It also gives a distinctive but entirely coherent interpretatiob of subtyping. An alternate onstruction points out some peculiarities of ocmputability theory based on natural number codings. Specifically, the polymorphic fixed point is computable by a single algorithm at all types when we consttruct the madel over untryped call-by-value lambda terms, but not when we use Godel numbers for ocmputable functins. This is consistent with trends away from natural numbers in the field of abstract resusion theory. Although our development and analysis of each structure is completely elementary, both structures may be obtained as the result of interpreting standard domain consructions in effective models of ocnstructive logic.
展开▼
