A complete characterization of complete intersection-type preorders.
We characterize those type preorders which yield complete intersection-type assignment systems for -calculi, with respect to the three canonical set-theoretical semantics for intersection-types: the inference semantics, the simple semantics, and the F-semantics. These semantics arise by taking as interpretation of types subsets of applicative structures, as interpretation of the preorder relation, &leq;, set-theoretic inclusion, as interpretation of the intersection constructor, , set-theoretic intersection, and by taking the interpretation of the arrow constructor, &rightarrow;  la Scott, with respect to either any possible functionality set, or the largest one, or the least one.These results strengthen and generalize significantly all earlier results in the literature, to our knowledge, in at least three respects. First of all the inference semantics had not been considered before. Second, the characterizations are all given just in terms of simple closure conditions on the preorder relation, &leq;, on the types, rather than on the typing judgments themselves. The task of checking the condition is made therefore considerably more tractable. Last, we do not restrict attention just to -models, but to arbitrary applicative structures which admit an interpretation function. Thus we allow also for the treatment of models of restricted -calculi. Nevertheless the characterizations we give can be tailored just to the case of -models.
INTRODUCTION
Intersection-types disciplines originated in [Coppo and Dezani-Ciancaglini 1980] to
overcome the limitations of Curry's type assignment system and to provide a char-
Author addresses: M. Dezani-Ciancaglini, Dipartimento di Informatica, Universita di Torino,
Italy dezani@di.unito.it. F. Honsell and F.Alessi, Dipartimento
di Matematica ed Informatica, Universita di Udine, Via delle Scienze 208, 33100 Udine,
Italy honsell, alessi@dimi.uniud.it
Partially supported by MURST Con '99 TOSCA Project, FGV '99 and CNR-GNSAGA.
Permission to make digital/hard copy of all or part of this material without fee for personal
or classroom use provided that the copies are not made or distributed for prot or commercial
advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and
notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish,
to post on servers, or to redistribute to lists requires prior specic permission and/or a fee.
c
ACM Transactions on Computational Logic, Vol. TBD, No. TBD, TBD TBD, Pages 1{27.
M. Dezani et al.
acterization of strongly normalizing terms of the -calculus [Pottinger 1980]. But
very early on, the issue of completeness became crucial. Intersection-type preorders
and lter -models have been introduced, in [Barendregt et al. 1983], precisely
to achieve the completeness for the type assignment system '
, with respect to
Scott's simple semantics. And this result, together with the conservativity of '
with respect to Curry's simple types, was used in [Barendregt et al. 1983] to prove
Scott's conjecture concerning the completeness of the set-theoretic semantics for
simple types.
The number of type preorders of interest in the literature has grown considerably
over the years (e.g. [Coppo et al. 1984; Coppo et al. 1987; Honsell and Ronchi della
Rocca 1992; Egidi et al. 1992; Abramsky and Ong 1993; Plotkin 1993; Honsell
and Lenisa 1999], etc.), especially in connection with the study of domain models
for -calculi in the perspective of Abramsky's \domain theory in logical form"
1991]. Furthermore new semantics have been proposed for intersection-
types [Hindley 1983a].
The problem of characterizing syntactically the sound and adequate (complete)
type preorders, with respect to the various set-theoretic semantics, appears therefore
rather natural. Moreover, we feel that the very existence of completeness
results with respect to set-theoretic semantics, such as the one in [Barendregt et al.
1983], is probably one of the most signicant features of intersection-types.
In this paper we solve completely the characterization problem as far as the three
canonical set-theoretical semantics for intersection-types: the inference semantics,
the simple semantics [Scott 1975] and the F-semantics [Scott 1980b]. These are
the semantics which arise by interpreting types as subsets of applicative structures,
and by taking as interpretation of the preorder relation, , set-theoretic inclusion,
as interpretation of the intersection constructor, \, set-theoretic intersection, and
by taking the interpretation of the arrow constructor, ! a la Scott, as a logical
predicate, with respect to either any possible functionality set, or the largest one, or
the least one.
More precisely, the simple semantics of types associates to each arrow type A !
B the set of elements which applied to an arbitrary element in the interpretation
of A return an element in the interpretation of B.
As Scott has pointed out in [Scott 1980b], however, the key to a lambda model is
the set of elements in the domain which are canonical representatives of functions,
i.e. the elements which are meanings of terms starting with an initial abstraction.
The F-semantics of types takes therefore as meaning of an arrow type only those
elements which behave as expected with respect to application and which are also
canonical representatives of functions.
The inference semantics is the counterpart of the inference semantics for polymorphic
types introduced in [Mitchell 1988], generalized to suitable applicative
structures with an interpretation function, called -applicative structures. Here
the interpretation of arrows is taken with respect to an arbitrary set which includes
the canonical representatives of functions.
The results in this paper strengthen and generalize signicantly all earlier results
in the literature, to our knowledge, in at least four respects. First of all we consider a
general denition of type preorders which allow to represent not only all inverse limit
models [Coppo et al. 1984], but also all graph models [Berline 2000]. Secondly the
A Complete Characterization of Complete Intersection-Type Preorders  3
inference semantics had not been considered before. Thirdly the characterizations
are all given just in terms of simple closure conditions on the preorder relation , ,
on the types, rather than on the typing judgments themselves, as had been done
earlier [Dezani-Ciancaglini and Margaria 1986]. The task of checking the condition
is made therefore considerably more tractable. Lastly we do not restrict attention
just to -models, but to the more general class of -applicative structures. Thus
we allow also for the treatment of models of restricted -calculi, and most notably
models of Plotkin's call-by-value  v -calculus [Plotkin 1975], and models of the -I-
N-calculus of [Honsell and Lenisa 1999]. Nevertheless the characterizations we give
can be tailored just to the case of -models.
The paper is organized as follows. In Section 2 we introduce type preorders,
various kinds of type assignment systems, and we prove Generation Lemmata for
these systems. In Section 3 we introduce the basic semantical structures, with
respect to which we shall discuss soundness and completeness of type preorders. In
Section 4 we study lter structures and prove the crucial property satised by the
interpretation function over them. Section 5 is the main section of the paper. After
introducing the notions of type interpretation domain and semantic satisability
for the three semantics under consideration, we give the characterization results.
Finally in Section 6 we discuss related results and give some nal remarks.
2. INTERSECTION-TYPE PREORDERS AND TYPE ASSIGNMENT SYSTEMS
Intersection-types are syntactical objects which are built inductively by closing a
given set C of type atoms (constants) under the function type constructor ! and
the intersection type constructor \.
Denition 2.1 Intersection-type Languages. An intersection-type language, over
C, denoted by dened by the following abstract syntax:
Notice that in the denition above the cardinality of C is the only varying parameter

Notation 2.2. Upper case Roman letters arbitrary types.
In writing intersection-types we shall use the following convention: the constructor
\ takes precedence over the constructor ! and it associates to the right. Moreover
be short for A !    ! A
| {z }
Much of the expressive power of intersection-type disciplines comes from the
fact that types can be endowed with a preorder relation, , which induces the
structure of a meet semi-lattice with respect to \. This appears natural especially
in the semantical setting of the present paper, where the intended meaning of
types are sets of denotations, \ is interpreted as set-theoretic intersection, and
is interpreted as set inclusion.
Moreover sometimes we want the maximal element of all types or the maximal
element of all arrow types to be atoms: we call these atoms
respectively
and .
The corresponding axioms are (
and ().
is particularly meaningful when used in combination with the
e ype
assignment system, which essentially
treats
as the universal type of all -terms
4  M. Dezani et al.
(see Denition 2.9).
Axiom () states that  includes any arrow type. This axiom agrees with the
-type assignment system, which treats  as the universal type of all -abstractions
(see Denition 2.10).
Denition 2.3 Intersection-type Preorders. An (intersection)-type preorder (C;
) is a binary relation  on the intersection-type language T(C) satisfying the following
set of axioms and rules:
A  A (re
if
A  C
Notation 2.4. We will write A  B for A  B and B  A.
Notice that associativity and commutativity of \ (modulo ) follow easily from the
above axioms and rules.
Notation 2.5. Being \ commutative and associative, we will write
in A i for
An . Similarly we will write \ i2I A i where we convene that I denotes
always a nite non-empty set.
All the type preorders considered so far in the literature are dened for languages
over nite or countable sets of atoms and they are generated by recursive sets 5
of atoms and rules of the shape A  B. \Generation" is in the sense that A  B
is true if and only if it can be derived from the axioms and rules of 5 together
with those in Denition 2.3. Such preorders will be denoted by (C 5 ; 5 ). Note
that there are only countably many possible 5; hence, there are uncountably many
preorders which cannot be represented this way. Note also that the correspondence
5 7!5 is not
lazy)
Fig. 1. Some special purpose axioms and rules concerning .

Figure

1 gives examples of some special purpose axioms and rules, and Figure 2
presents the most traditional sets 5. The names 5 are the initials of the authors
who have rst considered the -model induced by the preorder (C 5 ; 5 ). The
A Complete Characterization of Complete Intersection-Type Preorders  5
f
lazy)g
f
Fig. 2. Examples of nitely generated preorders: atoms, axioms and rules.
order is logical, rather than historical: Ba [van Bakel 1992], EHR [Egidi et al. 1992],
AO [Abramsky and Ong 1993], BCD [Barendregt et al. 1983].
The symbol C1 denotes an innite set of fresh atoms, i.e. dierent
from
.
The meaning of the axioms and rules of Figure 1 can be grasped easily if we
consider the intended set-theoretic semantics, whereby types denote subsets of a
domain of discourse, and we interpret A ! B as the set of functions which map
each element of A into an element of B.
For instance, in combination with
the fact
that all the objects in our domain of discourse are total functions, i.e.
that
is
equal
to
[Barendregt et al. 1983].
However, if we want to capture only those terms which truly represent
as it is necessary, for instance, in discussing the lazy -calculus [Abramsky and
Ong 1993], we cannot assume
) in order to ensure that all functions are
total. To this end we can postulate instead the weaker
property(
lazy). According
to the set theoretic semantics, this axiom states, in eect, simply that an element
which is a function, (since it maps A into B) maps also the whole universe into
itself. Notice that, when the type denoting the whole
universe,
is in C, the role
of  could be played also by the
type
provided that
lazy) is in
5. For this reason it is of no use to have at the same time in the language both
and
Hence we impose that the two constants do not occur together in any C.
The set-theoretic meaning of Axiom (!-\) is immediate: if a function maps A
into B, and also A into C, then, actually, it maps the whole A into the intersection
of B and C (i.e. into B \ C), see [Barendregt et al. 1983].
Rule () is also very natural set-theoretically: it asserts the arrow constructor is
contravariant in the rst argument and covariant in the second one. Namely, if a
function maps A into B, and we take a subset A 0 of A and a superset B 0 of B, then
this function will map also A 0 into B 0 , see [Barendregt et al. 1983].
Now that we have introduced type preorders we have to explain how to capitalize
eectively on their expressive power. This is achieved via the crucial notion of
intersection type assignment system. This is a natural extension of Curry's type
assignment type to intersection types. First we need some preliminary denitions
and notations.
Notation 2.6.  will be short for (C; ) and  5 for (C 5 ; 5 ).
Denition 2.7. (1) A basis over C is a set of statements of the shape x:B, where
whose variables are distinct.
(2) An intersection-type assignment system relative to denoted by \  ,
6  M. Dezani et al.
is a formal system for deriving judgments of the form '  M : A, where the
subject M is an untyped -term, the predicate A is in T(C), and is a basis
over C.
(3) We will write x 2 as short for 9A: occurs as the subject of
an assertion in .
We say that a term M is typable in \  , for a given basis , if there is a type
A 2 T(C) such that the judgment '  M : A is derivable.
We dene three kinds of type assignment systems, which correspond to the presence
or the absence of the
atoms
.
The rst ones, the Basic Type Assignment Systems, deal with sets of atoms not
including
.
Denition 2.8 Basic Type Assignment Systems.
preorder
with
C. The basic type assignment system
for , denoted by \
B , is a formal system for deriving judgments of the shape
A. Its rules are the following:
(! E)
If
2 C, in line with the intended set-theoretic interpretation
of
as the universe,
we extend the Basic Type Assignment System with a suitable axiom
for
Denition-type Assignment Systems.
preorder
with
C. The axioms and rules of
the
-type
assignment system (denoted \
deriving judgments of the shape '
are those of the Basic type Assignment System, together with the further axiom
(Ax-
M: :Similarly, if  2 C, in line with the intended interpretation of  as the universe
of abstractions, we dene:
Denition 2.10 -type Assignment Systems.
preorder with  2 C. The axioms and rules of the -type
assignment system (denoted \
), for deriving judgments of the shape '
are those of the Basic Type Assignment System, together with the further axiom
A Complete Characterization of Complete Intersection-Type Preorders  7
Notation 2.11. In the following \  will range over \
and \
. More
precisely we assume that \  stands for \
whenever
whenever
otherwise. Similarly for '  .
We refer to [Barendregt and al. 200X] for a detailed account on the interest and
dierences of the three kinds of intersection-type assignment systems introduced
above. Here we just recall a few suggestive facts. Thanks to the intersection-
type constructor, general self-application can be typed in the systems \
this was not the case in Curry's type assignment. In fact it is easy to prove that
whilst x:xx cannot receive any type in the Curry
system. Actually, all strongly normalizing terms are typeable in \
B for all . All
solvable terms can be typed in \
for all  with some type not equivalent to
For instance, using
2 the term (yx:x)(), where   x:xx, can be
A. The systems \
are appropriate for dealing with Plotkin's call-
by-value  v -calculus [Plotkin 1975]. Also these systems allow to type non-strongly
normalizing terms. For instance, one can prove that the term (yx:x)(z:) may
receive type A ! A for all A. Anyway, notice that, as proved in [Egidi et al. 1992],
(yx:x)() cannot be typed in \  EHR
.
Notice that the structural rules of (weakening) and (strengthening) are admissible
in all \  s:
(weakening)
Notice also that the intersection elimination rules
can be proved immediately to be derivable in all \  s.
Moreover, by a straightforward induction on the structure of derivations, one can
prove that the rule
is admissible in all \  s.
We conclude this section by proving a crucial technical result concerning
type preorders, which will be useful in Section 5. It is a form of generation (or
which provides conditions for \reversing" some of the rules of
the type assignment systems \  .
Notation 2.12. When we write \.assume
33 we mean that this condition
is always true when we deal with '
, while it must be checked for '
.
Similarly, the condition 6A must be checked just for '
.
Moreover we write \the type preorder validates 5" to mean that
Theorem 2.13 Generation Lemma. Let preorder.
. Then the following conditions are equivalent:
8  M. Dezani et al.
(a) '  x : A
. Then the following conditions are equivalent:
(a) '  MN : A
i2I C i  A for some I and
(3
and let  validate Ba. Then the following conditions are equivalent

(a) '  MN : A
(4 ) Assume 6A. Then the following conditions are equivalent:
(a) '  x:M : A
Proof. The proof of each (b) ) (a) is easy. So we only treat (a) ) (b).
(1) Easy by induction on derivations, since only the axioms
(Ax),(Ax-
8 and
the rules (\I), () can be applied. Notice that the condition
implies that
cannot be obtained just using axioms (Ax-
(2) By induction on derivations. The only interesting case is when A  A 1 \ A 2
and the last rule applied is (\I):
The condition
implies that we cannot have A 1 A 2
We do the proof for
6
and A 2 6
the other cases can be treated similarly. By induction there are
and moreover
. So we are done since (
be as in (2). Applying rule (\I) to '
derive
since
by rule () and axiom (!-\).
We can choose
since
A
we can choose B  C
Otherwise
and 6A. The proof is by
induction on derivations. Notice that '  x:M : A cannot be obtained just using
axioms (Ax-
or (Ax-). The only interesting case is again when A  A 1 \ A 2
and the last rule applied is (\I):
As in the proof of (2) we only consider the case A 1 6
and 6A 2 .
A Complete Characterization of Complete Intersection-Type Preorders  9
By induction there are I
So we are done since (
Special cases of this theorem have already appeared in the literature, see [Baren-
dregt et al. 1983; Coppo et al. 1984; Coppo et al. 1987; Honsell and Ronchi della
Rocca 1992; Egidi et al. 1992].
3. APPLICATIVE STRUCTURES SUITABLE FOR LAMBDA CALCULUS
In this section we introduce the semantical structures which we will consider in
our investigation of soundness and completeness of intersection-type assignment
systems.
Denition 3.1 -applicative structure. A -applicative structure is a triple
is an applicative structure;
(2) D], is a mapping (interpretation
function for -terms) which satises the following properties
(a)
(b)
if y 62 FV(M );
(c) (8d 2 D: [[M
.
If we compare our denition of -applicative structures with that of -models
(rst given in [Hindley and Longo 1980], see also Denition 5.3.1 of [Barendregt
1984] and Denition 11.3 of [Hindley and Seldin 1986]) three conditions are missed:
(1)
[x:=d] .
The absence of conditions (1) and (2) allows us to dene the interpretation function
on lter structures in such a way it coincides with the set of derivable types (see
proposition 4.5 and Theorem 4.6). We omit conditions (3) for considering also
models of restricted -calculus (Denition 3.2).
One can easily see that Plotkin's -structures, as dened in [Plotkin 1993], are -
applicative structures. In the next section we will introduce lter structures, which
are again -applicative structures.
Models of, possibly restricted, -calculi, as we commonly know them, can be
viewed as special -applicative structures.
First we need to give the denition of restricted -calculus.
Denition 3.2 Restricted -calculus. Let
The restricted -calculus R is the calculus obtained from the standard -calculus,
by restricting the  rule to the redexes in R.
M. Dezani et al.
is the standard -calculus. The main examples of truly
restricted -calculi are Plotkin's call-by-value  v -calculus [Plotkin 1975] and the
-I-N-calculus of [Honsell and Lenisa 1999]. Finally we give the crucial denition
Denition 3.3 (Restricted) -model. A (restricted) -model for the (restricted)
-calculus R , is a -applicative structure, hD; ; which moreover satises
for h(x:M)N; M [x := N ]i 2 R:
It is easy to see that all notions of models for, possibly restricted, -calculi, based
on applicative structures, can be cast in the above setting.
4. FILTER STRUCTURES AND INTERPRETATION OF LAMBDA TERMS
In this section we introduce lter structures. These are the basic tool for building
-applicative structures, in eect -models, which realize completeness for type
preorders.
Filter structures arise naturally in the context of those generalizations of Stone
duality that are used in discussing domain theory in logical form (see [Abramsky
1991], [Coppo et al. 1984], [Vickers 1989]).
This approach provides a conceptually independent semantics to intersection-
types, the lattice semantics. Types are viewed as compact elements of domains.
The
type
denotes the least element, intersections denote joins of compact ele-
ments, and arrow types allow to internalize the space of continuous endomorphisms.
Following the paradigm of Stone duality, type preorders give rise to lter structures ,
where the interpretation of -terms can be given through a nitary logical description

We start by introducing the notion of lter of types. Then we show how to
associate to each type preorder its lter structure. This is a -applicative structure
where the interpretation of a -term is given by the lter of the types which can
be assigned to it.
Denition 4.1. Let preorder.
(1) A -lter (or simply lter) is a set X  T(C) such that
(a)
if
then
(b) if A  B and A 2 X , then
(c) if
denotes the set of -lters;
denotes the lter generated by X ;
(4) a lter is principal if it is of the shape " fAg, for some type A. We shall denote
" fAg simply by " A.
Notice that " ; is the lter "
if
It is not di-cult to prove that F  , ordered by subset inclusion, is a complete
lattice, whose bottom element is " ; and whose top element is T(C). Moreover if
. The sup of a directed set of
lters is the set-theoretic union of lters. The nite 1 elements are exactly the lters
1 An element X is nite i for any directed subset Y, X v
F Y implies that there exists Y 2 Y
such that X v Y .
A Complete Characterization of Complete Intersection-Type Preorders  11
generated by nite sets of types.
Actually F  is !-algebraic, i.e. its set of nite elements is denumerable, and
moreover for each lter X , the set K(X) of nite elements below X is directed,
with sup X itself:
The next step is to dene application over sets of lters.
Denition 4.2 Filter structure. Let preorder.
(1) Application  : F  F  ! F  is dened as
(2) The maps F  are dened by 2
G
The triple hF  ; F  ; G  i is called the lter structure over .
Notice that if fA is non-empty and  2 C then it follows
The denition of G  , above, appears natural once we recall that axiom (Ax-)
entails that  is the universal type of functions.
Arrow types correspond to step functions, and they allow to describe the functional
behaviour of lters, in the following sense:
proposition 4.3. Let preorder. For all X 2 F  we get
G
is the step function X: if A 2 X then "
Proof. We show
G
Let D6
otherwise the thesis is trivial.
by denition of application and of lter
by denition of step function
since " C )" D is compact and the right-hand side is directed
The next proposition provides a useful tool for relating arrow types to application.
2  is an informal -notation used to dene functions, see [Barendregt 1984] page xiii and [Hindley
and Seldin 1986] page 130.
12  M. Dezani et al.
proposition 4.4. Let preorder which validates Ba, and let
if
Proof. ())
If
then
Otherwise, by denition of application (Denition 4.2(1)),
Then there is I and C i ; D i such that
A  T
by denition of lter (Denition 4.1). So we get A
rule ().
Trivial.
Filter structures induce immediately -applicative structures.
proposition 4.5. Let hF  ; F  ; G  i be a lter structure.
Let  range over the set of term environments the
interpretation function:
|if there exists x 2 Var such that
|otherwise put inductively:
The triple hF  is a -applicative structure.
The interpretation function of a term coincides with the set of types which are
derivable for it. This will be a crucial property in showing completeness using lter
structures.
Theorem 4.6. Let preorder and T(C). For any -term
M and environment
where only if for all x 2 Var, (x) 6= ;, and moreover
implies
Proof. The thesis is trivial if some x. In such a case
since for no it holds
Otherwise we prove the thesis by induction on M . Dene
if
else ;;
A Complete Characterization of Complete Intersection-Type Preorders  13
If M  x, then
Ag by Theorem 2.13(1)
If M  NL, then
by denition of application
A
by induction, (weakening) and ( L)
by Theorem 2.13(2) and
3 rule ():
If M  x:N , then
by denition of G
by induction, (weakening) and ( L)
by Theorem 2.13(4), axiom (Ax-), and rule ():
5. SET-THEORETIC SEMANTICS OF INTERSECTION-TYPES
This is the main section of the paper. Here, we discuss completeness for the three
set-theoretic semantics of intersection-types mentioned in the introduction. In par-
ticular, we characterize those type preorders which induce complete type assignment
systems for the inference, the simple and the F-semantics, over -applicative struc-
tures. As we will see these conditions apply also to the preorders which induce
complete systems with respect to the three semantics, over -models. We recall
that according to these semantics the meaning of types are subsets of the universe
of discourse, i.e. the applicative structure. The \intersection" type constructor is
always interpreted as the set-theoretic intersection. While, the \arrow" is interpreted
as the set of those points, which belong to a suitable distinguished set, and
whose applicative behavior is that of mapping the antecedent of the arrow into the
consequent.
As we remarked earlier, the very existence of complete type assignment systems
for such semantics over applicative structures is one of the strongest motivations
for the whole enterprise of developing a theory of intersection-types.
In discussing completeness, soundness is not really an issue, since all type preorders
are sound. To achieve adequacy and hence completeness we have to restrict
14  M. Dezani et al.
to two disjoint classes of type preorders, namely the natural preorders and the strict
preorders. Filter structures are essential to showing adequacy. In such structures,
in fact, the set-theoretic interpretation of a type, as an appropriate subset, is in
one-to-one correspondence with the principal lter generated by that type.
Denition 5.1.
if
2 C and it validates AO as dened
in

Figure

2.
if
2 C and it validates Ba as dened in

Figure

2.
Notice that a strict type preorder containing the constant  validates EHR. All the
preorders appearing in Figure 2 are natural, if they
contain
and strict otherwise.
Type interpretations can be given on -applicative structures once we have xed
a distinguished set of functional objects, . There are various choices for this set.
Amongst these there is a maximal one and a minimal one. The former determines
the simple semantics, the latter the F-semantics.
Denition 5.2 Type Interpretation Domain.
interpretation domain is a quadruple I
| is a -applicative structure;
|  is a subset of D, called the functionality set, such that [[x:M
all x; M; .
is a simple interpretation domain
is an F-interpretation domain
g.
Denition 5.3 Type Interpretation. Let I
domain. The type interpretation induced by the type
environment
(1)
I
This denition is the counterpart for intersection-types of the inference semantics
for polymorphic types of [Mitchell 1988], generalized by allowing hD; ; to be
just a -applicative structure instead of a -model.
Once we x an applicative structure hD; i, and an interpretation function
the above denition depends on the choice of the functionality set  and the type
environment V . The interpretation of the constants
f
takes into account the
corresponding axioms of the type assignment systems.
As we remarked above (see page 9), in the denition of -applicative structure,
we do not postulate, in general, that Nevertheless the class of environments
which have this property will be of particular signicance (provided that
A Complete Characterization of Complete Intersection-Type Preorders  15
they do not induce trivial interpretations, i.e. interpretations in which all terms
are equated). Hence we put
Denition 5.4 Good environments. Let hD; ; be a -applicative structure.
The term environment  : Var ! D is good if for all x 2 Var, we have
and moreover there exist two terms M;N such that [[M
In discussing sound type assignment systems we consider only type interpretation
domains and type environments which are good (the notion of goodness will depend
on the current type preorder and on which kind of semantics we are considering)
and which agree with the inclusion relation between types in the following sense:
Denition 5.5. Let preorder. A type interpretation domain
(1) are -good if for all
(a) for all good environments  and d 2
(b) for all good environments , terms M and variables x,
(2) are F -good if they are -good and moreover for all good environments ,
variables x, and A 2 T(C)
(3) agree with  i for all
Condition (2) of Denition 5.5 is true in particular when I is an F-interpretation
domain such that for all good  we get that (x) 2  implies
Remark that the conditions (1) and (2) of Denition 5.5 are true for all known
models of (restricted) -calculus ([Hindley and Longo 1980], [Plotkin 1975], [Egidi
et al. 1992], [Honsell and Lenisa 1999]).
One can easily see that the following holds:
proposition 5.6.
domains and all type environments agree with AO and
with EHR.
simple interpretation domains and all type environments agree with BCD.
We now introduce formally the three semantics. The denitions follow in a
natural way from how we have argued informally so far, but for the restriction (in
the denition of those type interpretation domains and type environments
which are -good (F-good in the case of F-semantics) and which agree with .
Denition 5.7. Let I
Denition 5.8 Semantic Satisability.
M. Dezani et al.
interpretation domains I and type environments V which moreover agree with
, and for all good term environments ;
(2)
A for all -good simple
interpretations domains I and type environments V which moreover agree with
, and for all good term environments ;
interpretations domains I and type environments V which moreover agree with
, and for all good term environments .
For example 6j=
and 6j=
In view of the above denition, we can say that the inference semantics is given
by
i , the simple semantics by
s , and the F-semantics by
F . The following
proposition is immediate:
proposition 5.9. If
then we have both
F
A.
Notation 5.10. We shall denote with any of the three
s , and
F .
Derivability in the type system implies semantic satisability, as shown in the
next theorem. Its proof by induction on derivations is straightforward.
Theorem 5.11 Soundness. '  M : A implies A.
Proof. By induction on the derivation of '  M : A using the denition of
type interpretation (Denition 5.3).
Rule (! E) is sound by denition of -applicative structure (Denition 3.1).
The soundness of rule (! I) follows from the restriction to -good type interpretation
domains and type environments (Denition 5.5(1)) and from the denition
of functionality set (Denition 5.2(1)).
Rule () is sound since we consider only type interpretation domains and type
environments which agree with  (Denition 5.5(3)).
The soundness of the other rules is immediate.
As regards to adequacy, rst we observe that only natural or strict type preorders
can be adequate. In particular the model P! [Scott 1976], Engeler models [Engeler
1981] and those graph models which do not satisfy rule () (see [Berline 2000] for
a description of these models as webbed models and [Barendregt and al. 200X] for
their presentation via type preorders), cannot be adequate.
Remark 5.12. Following a referee's suggestion, we conjecture that all graph models
would be complete when using more general notions of type interpretation domain
and of type interpretation. More precisely the following extensions are worthy
|dening the fourth components  of type interpretation domains as functions
from arrow types to subsets of D such that [[x:M
|replacing condition (4) of Denition 5.3 with
A Complete Characterization of Complete Intersection-Type Preorders  17
proposition 5.13. (Adequacy implies naturality or strictness) If
implies then  is a natural or a strict type preorder.
Proof. It is easy to verify that the hypothesis forces a type preorder to validate
rule () and axiom (!-\), and also
lazy)
when
when  2 C. For instance, as regards to axiom (!-\), consider the basis
C)g. From Denition 5.3 we get
Hence, by hypothesis, we have ' B\C. From Theorem 2.13(1) it must
hold must hold.
Now we shall discuss adequacy for each of the three semantics separately.
First we consider the inference semantics. Our goal is to show that all natural
and all strict type preorders are adequate for the inference semantics.
For this proof, we focus on the applicative structure induced by the lter structure
and we put:
Denition 5.14. Let be a natural or strict type preorder. Let:
(1)   be the functionality set dened by
=<
if
F  otherwise.
(2) I  be the type interpretation domain hF
be the type environment dened by
be the mapping
Because of (4) of previous denition, the symbol is overloaded, since it refers
both to the term interpretation in a lter structure (see proposition 4.5) and to the
type interpretation induced by a type preorder . Anyway no confusion may arise,
since the arguments select the interpretation.
Notice that
|
when
2 C we get
and
| when  2 C we get
The mapping has the property of associating to each type
A the set of lters which contain A (thus preserving the property through which
in the basic case of type constants).
Lemma 5.15. Let  be a natural or strict type preorder then
Proof. By induction on A. The only interesting case is when A is an arrow
type. Remark that if X 2 F  but
2   then all types in X are intersections of
constant types. In fact if X contains an arrow type, then it contains
also
M. Dezani et al.
when
lazy)), or  when  2 C (by rule ()), so X belongs to   .
If A
by denition
by induction
proposition 4.4
and the denition of
above.
Lemma 5.16. Let be a natural or strict type preorder. Then I  , V
are -good and they agree with .
Proof. I  , V  satisfy condition (1a) of Denition 5.5 since
For condition (1b) of Denition 5.5 let X 2  be such that [[M
Then, by Lemma 5.15, B 2 [[M
[x:=X] . Notice that:
proposition 4.3
by denition of G
by denition of step function.
We are done since F  (G
Lastly notice that as an immediate consequence of the Lemma 5.15 we get
and therefore I  ; V  agree with .
Finally we can prove the desired adequacy result.
Theorem 5.17. (Naturality or strictness imply adequacy) Let
natural or a strict type preorder. Then
A.
Proof. We consider the type interpretation domain I  . Let  be the term
environment dened by  Ag. It is easy to verify that
I and that for all 0 A.
Hence we have:
by Lemma 5.15
A by Theorem 4.6 and the above property.
Hence, by proposition 5.13 and Theorem 5.17, all and only the natural or strict
type preorders turn out to be complete with respect the inference semantics. There
are of course many preorders of interest which do not belong to these classes. For
instance the type preorder which induces the lter structure isomorphic to Scott's
P! [Scott 1976] is such a preorder. The reader can see [Barendregt and al. 200X]
for more examples.
Notice that the preorders  AO ,  BCD induce lter structures which are -models
[Barendregt et al. 1983], the preorder  EHR induces a model for the  v -calculus
A Complete Characterization of Complete Intersection-Type Preorders  19
[Egidi et al. 1992], and the preorder  Ba induces a model for the -I-N-calculus
[Honsell and Lenisa 1999]. Hence we have that natural preorders, which induce
-models, are complete also for the class of -models, and strict preorders, which
induce models of the other two restricted -calculi, are complete for the corresponding
classes of models.
Now we characterize those preorders which are complete with respect to the
simple semantics.
Theorem 5.18. (Adequacy for the simple semantics) Let
preorder.
is a natural type preorder which
validates
-) or a strict type preorder such that
Proof. ()) From proposition 5.13 it follows that  is natural or strict.
It is easy to check that
if
6
then simple adequacy fails for \
. We
have
since D. By
Theorem 2.13(1) we can deduce '
x
only
if
Let  2 C. We have, for any type interpretation domain I
type environment: Hence
never holds '
Theorem 2.13(1), hence simple adequacy fails if  2 C.
This proves ()).
To prove that
under the given conditions
we use the simple type interpretation domain hF  which is just I  as
dened in Denition 5.14, with  being either
or
By
Lemma 5.15 it follows Xg. So we have that
implies A 2 [[M
and we conclude '  M : A as in the last step of the proof of
Theorem 5.17.
Among the type preorders of Figure 2, those adequate for the simple semantics
are  Ba and  BCD . Other adequate type preorders in the literature are those of
[Honsell and Lenisa 1999; Scott 1972; Park 1976; Coppo et al. 1987; Honsell and
Ronchi della Rocca 1992]. Non adequate type preorders are all those inducing
computationally adequate models for the lazy -calculus, e.g.  AO , or for the
call-by-value -calculus, e.g.  EHR . The same argument used for the inference
semantics allows to show that the natural preorders mentioned in Theorem 5.18,
which induce -models, are precisely those which are complete also for the class
of -models, and the strict preorders, which induce  v -models and -I-N-models,
are complete for the corresponding classes of models. The completeness for the
simple semantics of \
whenever  validates BCD and hF
was proved in [Coppo et al. 1984] using lter models and in [Coppo et al. 1987]
using the term model of -equality.
Finally we turn to the F-semantics. The following denition singles out the type
preorders which are adequate for the F-semantics as proved in Theorem 5.28.
Denition 5.19. A type preorder is an F-preorder i
(1) either  is a natural or a strict type preorder such that
2 C and for all 2 C,
there are I ; A
M. Dezani et al.
(2) or  is a strict type preorder such that  2 C and for all 2 C either   or
there are I ; A
For example  Ba ,  EHR , and  AO are F-preorders.
Notice that a natural type preorder  which validates
) is an F-preorder
i for all 2 C we get
Next lemma shows that all types of an F-preorder satisfy the conditions of previous
denition.
Lemma 5.20. Let
either   C or C \
Proof. We just prove the more di-cult case, namely (2). We reason by induction
on the structure of C. If C 2 C the thesis is trivial. If C  D ! E, then
C  , hence C\D ! E. If C  D\E and   C then the thesis is immediate.
Otherwise we cannot have both   D and   E. Let us suppose  6 D. Then,
by induction, it follows D \
I and A
Now, if   E, we get C \ D \  and we are done by above. If  6 E, then,
by induction, it follows E \
Therefore C \ (
T(C), we easily get:
Corollary 5.21. Let
To discuss F-semantics it is useful to characterize the subset of types which are
functional.
Denition 5.22. We dene the predicate fun on T(C) by induction on the structure
of types:
The following proposition gives an alternative characterization of functional types
for F-preorders.
proposition 5.23. If is an F-preorder then
or A
Proof. (() is trivial.
We reason by induction on the structure of A. If A 2 C, or A
or A, the thesis follows by denition of fun(A). Otherwise we have A  B \ C
A Complete Characterization of Complete Intersection-Type Preorders  21
and either fun(B) or fun(C). We assume fun(B), the case fun(C) being similar. By
induction either B or B
I and A In the
rst case
- either   C and AC \ ,
- or AC \
In the second case it follows AC \ T
choosing an arbitrary i 2 I
we get
for some J and A 0
by Corollary 5.21. So we conclude
To prove adequacy we will again use the lter structure hF  ; F  ; G  i for dening,
as in the previous cases, the type interpretation domain hF
F
i. The de-
nition below diers from Denition 5.14 in that we choose a dierent functionality
set.
Denition 5.24. Let be an F-preorder. Let:
(1)
F be the functionality set dened by
for some x; M;
(2) I
F be the type interpretation domain hF
F
be the type environment dened by
be the mapping
F
F
When restricting to F-preorders, all lters which contain a functional type belong
to the functionality set.
Lemma 5.25. Let be an F-preorder and X 2 F  . Then A 2 X and
imply
F .
Proof. We show that under the given conditions
Proof of X
. Take an arbitrary B 2 X . Notice that if  2 C then
implies A   by proposition 5.23. Moreover fun(A) implies
by Denition 5.22. Then either A \ B or A \ B
i2I
again by proposition 5.23. In the rst case we get   B and
then '
rule (). In the second case we can derive
using axiom (Ax) and rules (),
(! E), (! I), and (\I). This implies fx:A \ Bg '  y:xy : B by rules () and
( L). In both cases we conclude B 2
0 by Theorem 4.6, since ;
(case A \ B) and fx:A \ Bg
Proof of
By Theorem 4.6,
22  M. Dezani et al.
If
since A   by proposition 5.23. Otherwise we get fx:C; y:D i
some I ; D
Theorem 2.13(4). This
implies
Theorem 2.13(3). Using Theorem 2.13(1) we have C  F
so we get C  D rule (), and we can conclude C  B, i.e.
Lemma 5.26. Let be a F-preorder then
Proof. The proof by induction on A is similar to that of Lemma 5.15. All cases
are trivial but for  and arrow types.
If A   let X be any lter in
F , that is
for some x; M; . Then,
by Theorem 4.6,
we have  2 X . Vice versa, if  2 X , then by Denition 5.22 fun(), and so by
F . We have proved, when  2 C, that
Hence
Xg.
If A
as in the proof of Lemma 5.15
proposition 4.4 since,
when
2 C, Theorem 4.6
imply
Lemma 5.27. Let be an F-preorder. Then I
F are F-good and
they agree with .
Proof. We can mimic the proof of Lemma 5.16, using Lemma 5.26 instead of
Lemma 5.15, for all points of Denition 5.5 but for (2). So we are left to prove
that this last condition holds. The key observation is that by Lemma 5.26 and
Theorem 4.6
some basis such that
Let
F \
F . Then
0 for some z; M;  0 . By () there
exists a basis 0 such that 0 A. By Theorem 2.13(4) there
are I ; A
Hence by () [[z:M
F . Since
0 by () there
exists a basis j= , such that '  x :
applying
rules (), (!E), (!I) and (\I), we get '  y:xy :
have by ()
F . Since I
F agree with , we get
F
F , so we conclude
F .
Theorem 5.28. (Adequacy for the F-semantics)
A i  is an F-preorder.
A Complete Characterization of Complete Intersection-Type Preorders  23
Proof. First we check that the given conditions are necessary.
Let which are F-good,
agree with , and some good . Then
Denition 5.5(2) it follows
By a similar argument we can obtain
x: \
when  2 C. Therefore we have F-adequacy of \  only if we can prove
for some I ; A
by Theorem 2.13(4)
and x: \
for some C i 2 T(C)
by Theorem 2.13(3)
and A i  C i by Theorem 2.13(1)
by rule ().
This last judgment along with (y) implies \
Similarly from x: \
we can show that either   or
For the vice versa, we consider the F-interpretation domain I
F and the type environment
F of Denition 5.24. They are F-good and agree with  by Lemma
5.27. By Lemma 5.26
Xg. So we have that
implies mimicking the proof of Theorem 5.17.
The preorders  Ba ,  EHR , and  AO , as well as the type preorders of [Honsell
and Lenisa 1999; Scott 1972; Park 1976; Coppo et al. 1987; Honsell and Ronchi della
Rocca 1992] are adequate for the F-semantics. Moreover for the last ve the simple
semantics coincides with the F-semantics. The preorder  BCD is an example of
a preorder which is not adequate with respect to the F-semantics. The remark
concerning -models and restricted -models made for the inference and the simple
semantics, applies also to the F-semantics.
6. RELATED WORK AND FINAL REMARKS
In the literature there are essentially ve ways of interpreting Curry's types in
a model of the untyped -calculus. They dier in the interpretation of the arrow
type constructor. In what follows we shall mainly follow the terminology of [Hindley
1983a].
M. Dezani et al.
The simple and the F-semantics are dened as expected.
Following [Scott 1980a], the quotient set semantics takes into account that we
want to consider equivalent two functions i they give equivalent results when
applied to equivalent arguments. So types are interpreted as partial equivalence
relations of the domain rather than simply as subsets. The arrow constructor is
dened as for logical relations: d A!B d 0 i for all c; c 0 such that c A c 0 it holds
The F-quotient set semantics [Scott 1976], modies the quotient set semantics, in
the same way as the F-semantics modies the simple semantics. Namely it requires
that all elements of the domain which are equivalent with respect to an arrow must
be canonical representatives of functions.
Finally, Mitchell in [Mitchell 1988] introduces another semantics, which he calls
inference semantics, in which the interpretation of the arrow must at least contain
the canonical representatives of functions which behave correctly with respect to
the application.
All the above semantics easily extend to intersection-types [Dezani-Ciancaglini
and Margaria 1986] and to polymorphic types [Mitchell 1988].
The crucial question in the semantics of types is the completeness of type assignment
systems. Hindley proved in [Hindley 1983a] that Curry's type assignment
system is complete for all the mentioned semantics. More specically [Hindley
1983a] and [Hindley 1983b] show the completeness for the simple semantics and
moreover that:
if and only if
when A is a Curry type;
(2) the simple semantics is a particular case of the quotient set semantics;
(3) the F-semantics is a particular case of the F-quotient set semantics.
The argument showing points (2) and (3) easily extends to intersection and polymorphic
types, so for these type disciplines it is enough to discuss only completeness
for the simple and the F-semantics to get completeness results for the quotiented
versions. One could dene also a quotient version of the inference semantics, but
this would be treated similarly.
The completeness with respect to the simple semantics, of various intersection-
type assignment systems, over -models, has been proved in [Barendregt et al. 1983;
Hindley 1982; Coppo et al. 1984; Coppo et al. 1987; van Bakel 1992].
As far as the completeness with respect to the F-semantics of intersection-type
assignment systems over -models, we can cite [Dezani-Ciancaglini and Margaria
1986], [Yokouchi 1994], [Abramsky and Ong 1993]. In [Dezani-Ciancaglini and
Margaria 1986] the type preorders which give -models where some lters are never
interpretations of -abstractions and which are complete for the F-semantics are
characterized. More specically it is shown that a type preorder  satises the
previous conditions if and only
if
6
types are invariant under -equality
of subjects, and moreover the following rule (due to R.Hindley):
(Hindley rule)
for all 2 C, is a derived rule.
A Complete Characterization of Complete Intersection-Type Preorders  25
Yokouchi in [Yokouchi 1994] shows that if we add two suitable rules (quite similar
to Hindley rule) to the intersection-type assignment system of [Coppo et al. 1981]
we obtain completeness for the F-semantics.
Abramsky and Ong, in [Abramsky and Ong 1993], prove the completeness of the
preorder  AO , with respect to the F-semantics, over applicative structures with
convergence.
We conclude the paper with three nal remarks.
If  is a natural type preorder which is adequate for the F-semantics, then Hind-
ley's rule is admissible in \
. This follows from the observation that under the
given conditions for all n  0 and for all 2 C we can nd I ; A (1)
such that

i2I
We could have used the syntactic approach based on term models introduced in
[Hindley 1982] for showing all our adequacy results concerning the simple semantics,
but not as far as the inference or the F-semantics. To this end, notice that if
reduces to an abstraction then a fortiori M1 reduces to an
abstraction, where I  x:x and 1  xy:xy. Therefore  is the representative
of a function whenever  is the representative of a function. Now consider the
F-preorder
Ciancaglini and Margaria 1986].
We have
DM
xI
which implies, by soundness,
F xI
By the above we get
F x1
but it is easy to check, using the Generation Lemma, that we cannot deduce x1 :
from
As a matter of fact, the proof of completeness
for the F-semantics in [Yokouchi 1994] uses a clever variant of the term model for
a -calculus with constants. It is not clear to us if this could be adapted to the
general case treated here.
It would be nice to investigate independent set-theoretic conditions which imply
that a type interpretation and a type environment agree with a type preorder. The
canonical example in this sense is the one given by partial applicative structures
and the preorder  EHR .
[Dezani-Ciancaglini et al. 2000] is an extended abstract of the present paper.

ACKNOWLEDGMENT

The authors are grateful to Wil Dekkers, Yoko Motohama, and to the referees
of ITRS submission and of the present submission for their useful comments and
suggestions. In particular the present general denition of type preorder which
26  M. Dezani et al.
allows to represent all graph models was worked out under the crucial guide of a
referee of TOCL submission.



--R

Domain theory in logical form.
Full abstraction in the lazy lambda calculus.
The Lambda Calculus: its Syntax and Semantics


From computation to foundations via functions and application: The
An extension of the basic functionality theory for the
Extended type structures and
Functional characters of solvable terms.
Type theories
A complete characterization of the complete intersection-type theories

A characterization of F

Algebras and combinators.
Introduction to Combinators and
The simple semantics for Coppo-Dezani-Salle types
The completeness theorem for typing
Curry's type-rules are complete with respect to F-semantics too

Semantical analysis of perpetual strategies in


type inference and containment.




A type assignment for the strongly normalizable

Continuous lattices.
Open problem.
Data types as lattices.
Lambda calculus: Some models
Letter to Albert Meyer.
Complete restrictions of the intersection type discipline.
Topology via logic.

--TR
Introduction to combinators and MYAMPERSANDlgr;-calculus
A characterization of <italic>F</>-complete assignments
Type theories, normal forms, and <italic>D</><subscrpt><inline-equation><f>MYAMPERSANDinfin;</f></inline-equation>0E-lambda-models
type inference and containment
Topology via logic
Complete restrictions of the intersection type discipline
Operational, denotational and logical descriptions
Set-theoretical and other elementary models of the MYAMPERSANDlgr;-calculus
An approximation theorem for topological lambda models and the topological incompleteness of lambda calculus
Full abstraction in the lazy lambda calculus
F-semantics for type assignment systems
Semantical analysis of perpetual strategies in MYAMPERSANDlgr;-calculus
From computation to foundations via functions and application
The simple semantics for Coppe-Dezani-SallMYAMPERSANDeacute; types
The Y-combinator in Scott''''s Lambda-calculus Models

--CTR
M. Dezani-Ciancaglini , F. Honsell , Y. Motohama, Compositional characterisations of -terms using intersection types, Theoretical Computer Science, v.340 n.3, p.459-495, 31 August 2005
Fabio Alessi , Franco Barbanera , Mariangiola Dezani-Ciancaglini, Intersection types and lambda models, Theoretical Computer Science, v.355 n.2, p.108-126, 11 April 2006
lambda models;lambda calculus;completeness;intersection types