Search

Abstract: Genericity is the idea that the same program can work at many different data types. Longo, Milstead and Soloviev proposed to capture the inability of generic programs to probe the structure of their instances by the following equational principle: if two generic programs, viewed as terms of type , are equal at any given instance , then they are equal at all instances. They proved that this rule is admissible in a certain extension of System F, but finding a semantically motivated model satisfying this principle remained an open problem. In the present paper, we construct a categorical model of polymorphism, based on game semantics, which contains a large collection of generic types. This model builds on two novel constructions: •A direct interpretation of variable types as games, with a natural notion of substitution of games. This allows moves in games to be decomposed into the generic part from , and the part pertaining to the instance . This leads to a simple and natural notion of generic strategy. •A “relative polymorphic product” which expresses quantification over the type variable in the variable type with respect to a “universe” which is explicitly given as an additional parameter . We then solve a recursive equation involving this relative product to obtain a universe in a suitably “absolute” sense. Full Completeness for ML types (universal closures of quantifier-free types) is proved for this model. [Copyright &y& Elsevier]

The main topic of this paper is the investigation of generalized amalgamation properties for simple theories. That is, we are trying to answer the question of when a simple theory has the property of n-dimensional amalgamation, where two-dimensional amalgamation is the Independence Theorem for simple theories. We develop the notions of strong n-simplicity and n-simplicity for 1≤n≤ω, where both “1-simple” and “strongly 1-simple” are the same as “simple”. For strong n-simplicity, we present examples of simple unstable theories in each subclass and prove a characteristic property of strong n-simplicity in terms of strong n-dividing, a strengthening of the dependence relation called dividing in simple theories. We prove a strong three-dimensional amalgamation property for strongly 2-simple theories, and, under an additional assumption, a strong (n+1)-dimensional amalgamation property for strongly n-simple theories. In the last section of the paper we comment on why strong n-simplicity is called strong. [Copyright &y& Elsevier]