A Comparison of NOOP to Structural
Domain-Theoretic Models of OOP

arXiv:1603.08648v3 [] 29 Dec 2017

Moez A. AbdelGawad
moez@cs.rice.edu
College of Mathematics and Econometrics, Hunan University
Changsha 410082, Hunan, P.R. China
Informatics Research Institute, SRTA-City
New Borg ElArab, Alexandria, Egypt

Abstract. Mainstream object-oriented programming languages such as
Java, C#, C++ and Scala are all almost entirely nominally-typed. NOOP
is a recently developed domain-theoretic model of OOP that was designed
to include full nominal information found in nominally-typed OOP. This
paper compares NOOP to the most widely known domain-theoretic
models of OOP, namely, the models developed by Cardelli and Cook,
which were structurally-typed models. Leveraging the development of
NOOP, the comparison presented in this paper provides a clear and
precise mathematical account for the relation between nominal and structural OO type systems.

1

Introduction

The first mathematical models of object-oriented programming (OOP) to gain
wide-spread recognition were structural models. Being structural, objects were
viewed in these models as being mere records. Object types, in accordance, were
viewed as record types, where the type of an object specifies the structure of the
object, meaning that object types carry information on the names of the members
of objects (i.e., fields and methods), and, inductively, on the (structural) types of
these members. The model of OOP developed by Cardelli in the eighties of last
century, and later enhanced by Cook and others, is an example of a structural
model of OOP. Examples of structurally-typed OO languages include lesserknown languages such as O’Caml [41], Modula-3 [24], Moby [34], PolyTOIL [17],
and Strongtalk [15].
Despite the popularity of the structural view of OOP among programming
languages researchers, many industrial-strength mainstream OO programming
languages are nominally-typed. Examples of nominally-typed OO languages include well-known languages such as Java [38], C# [3], C++ [2], and Scala [50].
In nominally-typed OO languages, objects and their types are nominal, meaning
that objects and their types carry class names information (also called nominal
information) as part of the meaning of objects and of their types, respectively.
In pure structurally-typed OO languages, nominal information is not used as
part of the identity of objects and of their types during static type checking nor

is nominal information available at runtime1 . Accordingly, nominal information
is missing in all structurally-typed models of OOP.
OOP was in its early days at the time the first mathematical models of OOP
were developed, in the eighties of last century. Functional programming was the
dominant programming paradigm among programming languages researchers at
that time—and largely still is today. As such, the role of nominality of objects
and of their types (i.e., the inclusion of nominal information in their identities)
in the semantics of mainstream OOP was not widely appreciated, and nominal
OO type systems remain under-researched. NOOP [6,8] is a recently developed
domain-theoretic model of OOP that addresses this shortcoming. To the best
of our knowledge, NOOP is so far the only domain-theoretic model of OOP to
include full class names information as found in mainstream nominally-typed
OO programming languages. In this paper, we compare NOOP to other wellknown structural domain-theoretic models of OOP.
This paper is structured as follows. First, we discuss related work—including
the history of modeling OOP—in Section 2. As an appetizer for the following
comparison, a fundamental technical difference between pure nominally-typed
OO languages and pure structurally-typed OO languages is discussed in Section 3. In Section 4 we then compare the nominal mathematical view of OOP to
the structural mathematical view of OOP by presenting a comparison between
NOOP and the structural models of OOP constructed by Cardelli and enhanced
by Cook and others. We conclude in Section 5 by summarizing our findings, making some final remarks, and discussing some possible future research.

2

Related Work

Even though object-oriented programming emerged in the 1960s, and got mature
and well-established in mainstream software development in the late 1980s, the
differences between nominally-typed and structurally-typed OO programming
languages started getting discussed by programming languages (PL) researchers
only in the 1990s [44,54,59]. In spite of these early research efforts, the value of
nominal typing and nominal subtyping to mainstream OO developers did not
get the full attention of the PL research community until around the turn of the
century.
In the eighties, while OOP was in its infancy, Cardelli built the first denotational model of OOP [21,22]. Cardelli’s work was pioneering, and naturally,
given the research on modeling functional programming extant at that time, the
model Cardelli constructed was a structural denotational model of OOP.2 In the
1

2

Given that most industrial-strength OO languages are statically-typed, in this work
we focus on nominal and structural statically-typed OO languages. A discussion
of statically-typed versus dynamically-typed OO languages (including the non-welldefined so-called “duck-typing”), and the merits and demerits of each, is beyond the
scope of this work. The interested reader should check [47].
Quite significantly, Cardelli in fact also hinted at looking for investigating nominal
typing [23, p.2]. Sadly, Cardelli’s hint went largely ignored for years, and structural

late 1980s/early 1990s, Cook and his colleagues worked to improve on Cardelli’s
model, leading them to break the identification of the notions of inheritance
and subtyping [28,31,30]. Unlike Cardelli, Cook emphasized in his work—as we
discuss in more detail in Section 4.2—the importance of self-references in OOP,
at the value level (i.e., self variables, such as this) and at the type level (i.e.,
self-type variables).
In 1994, Bruce et al. presented a discussion of the problem of binary methods in OOP [18]. Later, Bruce, and Simons, also promoted the structural view
of OOP in a number of publications (e.g., [19] and [58]) and they promoted
conclusions based on this view. However, the deep disagreement between these
conclusions (such as breaking the correspondence between inheritance and subtyping) and the fundamental intuitions of a significant portion of mainstream
OO developers persisted [25,10].
Under the pressure of this disagreement, some PL researchers then started
in the late 1990s/early 2000s stressing the significance of the differences between
nominally-typed OOP and structurally-typed OOP, and they started acknowledging the practical value of nominal typing and nominal subtyping (see [10,7]
for more details) and asserted the need for more research on studying nominal
OO type systems [52]. Accordingly, some attempts were made to develop OO
languages that are both nominally- and structurally-typed [33,51,37,45,46,50].3
However, at least in the eyes of mainstream OO developers, these hybrid languages have far more complex type systems than those of OO languages that
are either purely nominally-typed or purely structurally-typed (see discussion in
Section 4.1).
As to operational mathematical models of OOP, Abadi and Cardelli were the
first to present such a model [4,5]. Their model also had a structural view of OOP.
However, operational models of nominally-typed OOP got later developed. In
their seminal work, Igarashi, Pierce, and Wadler presented Featherweight Java
(FJ) [40] as an operational model of a nominally-typed OO language. Even
though FJ is not the first operational model of nominally-typed OOP (for example, see [32], [49] and [35,36]), yet FJ is the most widely known operational
model of (a tiny core subset of) a nominally-typed mainstream OO language,
namely Java. The development of FJ and other operational models of nominallytyped OOP marked a strong focus on studying nominal-typing in OO languages,
thereby departing from earlier disregard of it.
These developments later motivated the construction of NOOP. Featherweight Java (FJ) in fact offers the closest research to NOOP since it offers a
very clear operational semantics for a tiny nominally-typed OO language. It is
worth mentioning that NOOP, as a more foundational domain-theoretic model
of nominally-typed OO languages (i.e., that has fewer assumptions than FJ),
provides a denotational justification for the inclusion of nominal information in

3

typing was rather assumed superior to nominal typing instead, particularly after the
publication of Cook et al.’s and Bruce et al.’s work.
Multiple dispatch (see [26,14,27]), also, was discussed (e.g., in [18]) as a possible
solution to the problem of binary methods.

FJ. The inclusion of nominal information in NOOP is crucial for proving the
identification of inheritance and subtyping in nominally-typed OOP. In FJ [40],
rather than being proven as a consequence of nominality, the identification of
inheritance and subtyping was taken as an assumption. NOOP also allows discussing issues of OOP such as type names, ‘self-types’ and binary methods on a
more foundational level than provided by operational models of OOP. The more
abstract description of denotational models results in a conceptually clearer understanding of the programming notions described, as well as of the relations
between them.4
Finally, related to our work is also the dissatisfaction some researchers expressed about possible misunderstandings extant in the PL research community,
and about the (mal)practices based on these misunderstandings when PL researchers study object-oriented programming languages in particular. Given the
different basis for deriving data structuring in functional programming (based on
standard branches of mathematics) and in object-oriented programming (based
on biology and taxonomy) [21,22], some PL researchers have expressed dissatisfaction with assuming that the views of programming based on researching functional programming (including a view that assumes structural typing) may apply
without qualifications to object-oriented programming. In addition to pointing
out the importance of distinguishing between nominal typing and structural typing, MacQueen [42], for example, has noted many mismatches between Standard
ML [48] (a popular functional programming language) and class-based OO languages such as Java and C++. Later, Cook [29] also pointed out differences
between objects of OOP and abstract data types (ADTs), which are commonly
used in functional programming.5,6
4

5

6

It is worthy to also mention that NOOP was developed, partially, in response to the
technical challenge Pierce (an author of FJ) presented in his LICS’03 lecture [53] in
which Pierce looked for precising the relation between structural and nominal OO
type systems (notably, after the development of FJ was concluded).
We consider these research results as running in a similar vein as ours, since they
somewhat also point to some mismatches between the theory and practice of programming languages—theory being mathematics-based, functional, and structurallytyped, and practice being biology/taxonomy-based, object-oriented, and nominallytyped.
Yet another research that is also somewhat similar to the one we present here,
but that had different research interests and goals, is that of Reus and Streicher [55,57,56]. In [56], an untyped denotational model of class-based OOP is developed. Type information is largely ignored in Reus and Streicher’s work (in particular,
members of objects have no type signatures) and some minimal amount of nominal
information is included with objects only to support analyzing OO dynamic dispatch.
This model was developed to analyze mutation and imperative features of OO languages and for developing specifications of OO software and the verification of its
properties [56]. Analyzing the differences between structurally-typed and nominallytyped OO type systems was not a goal of Reus and Streicher’s research. Despite the
similarity of NOOP and the model of Reus and Streicher, we thus make no further
mention of Reus and Streicher’s model in this paper due to its different interests and
goals, and due to the fundamentally different nature of NOOP compared to their

3

Type Names, Type Contracts, Recursive Types and
Binary Methods

From the point of view of OO developers and OO language designers, there are
many technical differences between nominally-typed OO languages and structurallytyped OO languages. We discuss these in brief in this section. (A more detailed
discussion is presented in [10] and [7].)
Type Names and Behavioral Type Contracts A fundamental technical difference between nominally-typed OO type systems and structurally-typed OO
type systems is how the two approaches view type names. In structurally-typed
OO languages, type names are viewed as being names for type variables that
abbreviate type expressions (i.e., are “shortcuts”). As such, the use of type names
in structurally-typed OO languages is not always necessary, but type names are
useful as abbreviations and they are even necessary for defining recursive type
expressions. As variable names, however, recursive type names in structurallytyped OO languages (such as the name of a class when used inside the definition
of the class—which gets interpreted as “self-type”) get rebound to different types
upon type inheritance, and they get rebound to types that, if they were subtypes,
could break the contravariant subtyping rule of method parameter types (and,
thus, break the type safety of structurally-typed OO languages). Structurallytyped OO languages resolve this situation by breaking the correspondence between type inheritance and subtyping.
In nominally-typed OO languages, on the other hand, the nominality of types
means type names are viewed as part of the identity and meaning of type expressions, since type names in these languages are associated with public formal or
informal behavioral contracts.7 Being names for public, and thus fixed, contracts
means that, in nominally-typed OO languages, type names cannot be treated as
variable names. In nominally-typed OO languages, thus, type names have fixed
meanings that do not change upon inheritance. Further, in these languages the
fixed type a type name is bound to does not break the contravariant subtyping
of method parameters when the method and its type get inherited by subtypes
(types corresponding to subclasses/subinterfaces). As such, in nominally-typed

7

model (i.e., NOOP including all essential class names information inside objects
versus Reus and Streicher’s model lacking most of this information.)
In well-designed OO programs, each class (and interface and trait, in languages that
support these notions) has associated contracts describing the behavior of objects
of the class (its instances). The contracts include an invariant (a predicate) for the
values of class fields, and a contract for each method stipulating what conditions
the inputs should satisfy and what output condition should hold over the value
returned by the method, as well as side effects that have been performed on this and
perhaps other objects passed as arguments to the method. (The output predicate
may mention the values of arguments and in such case is often called an input-output
predicate.) In practice, class contracts are typically informal, may be incomplete, and
are usually expressed only in code documentation. (See [10] for a longer, detailed
and deeper discussion of the association of type names with contracts, and of the
import of this association to mainstream OO developers.)

OOP it is not necessary to break the identification of type inheritance with
subtyping.
Recursive Types Further, in class-based OOP, a class (or interface or trait, in
languages that support these notions) can directly refer to itself (using class/interface/trait names) in the signature of a field, or the signature of a method parameter or return value, where the class name is used also as a type name. This
kind of reference is called a type self-reference, recursive reference, or, sometimes, circular reference. Also, mutually-dependent classes, where a class refers
to itself indirectly (i.e., via other classes), are allowed in class-based OOP. As
Pierce noted [52], nominally-typed OO languages allow readily expression of
mutually-dependent class definitions. Since objects are characterized as being
self-referential values (according to Cook [29], objects are ‘autognostic’), and
since self-referential values can be typed using recursive types [43], there is wide
need for recursive type definitions in mainstream OOP. As such, direct and indirect circular type references are quite common in mainstream OOP [29]. The ease
by which recursive typing can be expressed in nominally-typed OO languages is
one of the main advantages of nominally-typed OOP.8
In the comparison of nominal and structural mathematical models of OOP
in Section 4 we will see that, in accordance with their different views of type
names, self-referential class references are viewed differently by nominally-typed
models of OOP than by structurally-typed models of OOP. The different views
of circular class references are behind nominal models of OOP leading to a
different conclusion about the relation between inheritance and subtyping than
the conclusion reached based on structural models.
Binary Methods From the point of view of OO developers, the difference between the nominal and the structural views of type names in OOP demonstrates
itself, most prominently, in the different support and the different treatment provided by OO languages to what are usually called “binary methods”. In OOP,
a ‘binary method’ is defined as a method that takes a parameter (or more)
of the same type as the class the method is declared in [18]. “The problem of
binary methods” and requiring them to be supported in OO languages was a
main motivation behind structural models of OOP leading to inheritance and
subtyping not being identified (i.e., as not being in a one-to-one correspondence) [30]. As explained above, given their view of type names as type variable
names, structurally-typed OO languages require the self-type of the argument
of a method—where the method is identified as a binary method, and upon inheritance of the method by a subclass of the class the method is first declared
in—to be that of the type corresponding to the subclass.
Nominally-typed OO languages, on the other hand, with their fixed interpretation of type names, treat a method taking in an argument of the same class
as that in which the method is declared like any other method, i.e., needing no
special treatment. As such, nominally-typed OO languages guarantee that the
8

According to Pierce [52, p.253], “The fact that recursive types come essentially for
free in nominal systems is a decided benefit [of nominally-typed OO languages].”

type of the input parameter of a method that approximates a binary method is
a supertype of its type if it were a true binary method.
Nominally-typed OO languages, thus, offer a somewhat middle-ground solution between totally avoiding binary methods and overly embracing them (as
pure structurally-typed OO languages do). Given that the meaning of types
names in nominally-typed OO languages does not change upon inheritance,
these languages provide methods whose type, upon inheritance, only approximates the type of true binary methods. Nominally-typed OO languages do not
quite support binary methods, but, for good reasons (i.e., so as to not break
the identification of inheritance of contracts and subtyping, nor lose other advantages of nominal typing [10]), offer only a good approximation to binary
methods. Given that the type of the parameter does not change in subclasses,
the degree of approximation (if the method was indeed a true binary method)
gets lesser the deeper in the inheritance hierarchy the method gets inherited.9

4

Nominally-Typed versus Structurally-Typed Models of
OOP

To see how nominality and nominal typing affects mathematical views of OOP,
we compare NOOP, as a nominally-typed denotational model of OOP, to the
most widely known structural model of OOP—the one constructed and presented
by Cardelli [21,22], and extended, analyzed and promoted by others such as
Cook [28,31,30], Bruce [19] and Simons [58].
Even though unnamed by their authors, for ease of reference in this paper we
call Cardelli’s model SOOP, for Structural OOP, while calling the extension of
SOOP by Cook et al. µSOOP (due to its inclusion of recursive types). As we
discussed earlier, NOOP is the first domain-theoretic model of OOP to include
full nominal type information found in nominally-typed OOP. The construction
of NOOP is presented in [6], and is summarized in [8]. In the following sections
we first compare NOOP to SOOP then compare it to µSOOP.
9

With the introduction of generics [38,3,50,13,11,16,40], and ‘F-bounded generics’
(the nominal counterpart of F-bounded polymorphism [20,12,39]) in particular,
nominally-typed OO languages provided better support for true binary methods
while keeping the identification of type inheritance with subtyping and other benefits of nominal typing. It should be noted that the lesser-recognized problem of
‘spurious binary methods’ in structurally-typed OOP (see [10, Section 3.3.1]) provides further justification for nominally-typed OO languages being cautious about
fully embracing binary methods by treating a method that “looks like” a binary
method as indeed being one. In light of the spurious binary methods problem, and
precluding the use of F-bounded generics, in our opinion a better approach towards
supporting true binary methods in mainstream OO languages might be by allowing
developers to explicitly mark or flag true binary methods as being such, or, even
more precisely, to allow developers to mark specific arguments of methods as being
arguments that ‘need to be treated as those of true binary methods.’

4.1

NOOP Compared to SOOP

The model of OOP developed by Cardelli in the 1980s [21,22] was the first
denotational model of OOP to gain widespread recognition. In his pioneering
and seminal work Cardelli, according to him himself, had a goal of ‘unifying
functional programming and object-oriented programming’ [22, p.2]. A domain
equation that describes the main features of SOOP (distilled to exclude variants.
See [22, pp.15, 16] for the actual domain equations used by Cardelli) is
V = B + (V → V) + (L → V)
where V is the main domain of values, B is a domain of base values, L is the
flat domain of labels, → is the standard continuous functions domain constructor, and + is the disjoint summation domain constructor. The distilled SOOP
domain equation expresses the view that values are either base values, unary
functions over values, or records (“objects”) modeled as (infinite) functions from
labels to values.
The domain equation describing NOOP is
O = S × (L ⊸ O) × (L ⊸ (O∗ ⊸→ O))
where the main domain defined by the equation, namely domain O, is the domain
of (raw) objects, × is the strict product domain constructor, and ⊸ is the records
domain constructor (See [8] or [6, Chapter 6] for more details on the NOOP
domain equation). The NOOP domain equation expresses the view that every
object is a triple of: (1) a class signature closure (i.e., a member of domain S),
(2) a fields record (i.e., a member of L ⊸ O), and (3) a methods record (i.e.,
a member of L ⊸ (O∗ ⊸→ O), where ⊸→ is the strict continuous functions
domain constructor, and ∗ is the finite-sequences domain constructor).
Class signatures and other related constructs are syntactic constructs that
capture all nominal (i.e., class/interface/trait names) information found in objects of mainstream nominally-typed OO software [8,6]. Class signatures formalize the informal notion of ‘object interfaces’ [10,7,6]. Embedding class signature
constructs in objects of NOOP makes them nominal objects. It should be noted
that consistency conditions for signature constructs in NOOP [8, Section 4] [6,
Section 5.1] do not preclude a signature from directly or indirectly referring to
itself in the signature of a field or of a method parameter or method return value,
so as to allow for self-referential types (see Section 3.)
A comparison of NOOP to SOOP reveals the following fundamental difference between the two models:
– SOOP is a structural model of OOP, that, as explained by its domain equation, does not include nominal information into its objects. As such, SOOP
views objects as being essentially records (of functions) [22, p.3]. Due to
the lack of nominal information, the definitions of types of objects and of
subtyping, based on SOOP, are also structural definitions, i.e., ones that
can only respect object structures but that cannot respect the behavioral
contracts maintained by objects that are associated with their type names.

– NOOP is a nominal model of OOP, that, via the S component (for signatures) of its domain equation, includes full nominal information into its
objects . As such, NOOP views objects as records (of fields and methods)
accompanied by nominal information referencing the behavioral contracts
maintained by the fields and methods of the objects. The definition of types
of objects and of subtyping, based on NOOP, can thus be nominal ones,
i.e., ones which can respect behavioral contracts associated with type names
in addition to respecting object structures.
In the comparison of NOOP to SOOP it should also be noted that the ‘Inheritance ⇔ Subtyping’ (‘inheritance is subtyping’) theorem of NOOP ([8, Sectionï¿œ5.3]), stating the identification of type inheritance with subtyping in
nominally-typed OOP, is very similar to Cardelli’s ‘Semantic Subtyping’ theorem ([22, Sectionï¿œ11]). Cardelli did not model recursive types, and thus did
not handle recursive type expressions (which are the structural counterpart of
self-referential class signatures). As such, despite the model of Cardelli being a
structural model of OOP, the omission of recursive types enabled Cardelli to
easily identify an inaccurate “structural” notion of inheritance with a structural
definition of subtyping and prove their one-to-one correspondence10.
Other tangential differences that are noted in the comparison between NOOP
and SOOP include:
1. SOOP models records as infinite functions, with only an informal restriction on the functions that requires the functions to map a cofinite set of
input labels—i.e., all but a finite number of labels—to the value wrong.
NOOP, on the other hand, models the record component of objects using
the ⊸ (‘rec’) domain constructor which constructs records as tagged finite
functions. Domain constructor ⊸, even though having similarity to some
other earlier-developed domain constructors, was particularly developed to
let NOOP model mainstream OOP more accurately. Because of using ⊸,
the NOOP domain of objects formally includes no “junk” (i.e., unnecessary)
infinite records as those found in the formal definition of SOOP.
2. Given its attempt to unify FP and OOP, SOOP allows functions as firstclass values in its main domain of values. As such, SOOP is not a pure-OO
model of OOP. NOOP, on the other hand, is a pure-OO model of OOP.
Every value in the main domain of NOOP is an object. To model methods
and records, NOOP uses functional domains, but they are used only as
auxiliary domains.
3. Functions (used to model methods) in SOOP are unary functions that take
exactly one argument—an element of domain V. SOOP thus requires ‘currying’ to model multi-ary functions and methods. In NOOP, on the other
10

In his work, Cardelli, informally and somewhat implicitly, defined inheritance as
structural subtyping between (record) type expressions. Demonstrating the strong
influence of functional programming on Cardelli’s model, Cardelli even argued for expanding the definition of inheritance to include some notion of “inheritance” between
function types (by which it seems Cardelli really meant subtyping, since Cardelli did
not suggest any code sharing).

hand, sequences of objects are used as method arguments to model multiary methods more precisely (i.e., without the need for currying, which is
not commonly familiar to mainstream OOP developers as it is to FP developers, and thus, inline with the previous point, also without the need for
functions/methods to be first-class values).
4. SOOP uses the same namespace for fields and methods of records, disallowing a field in a record to have the same name as a method in the record.
NOOP, on the other hand, aims to mimic mainstream OO languages more
closely, and thus it uses two records as separate components inside objects
to give fields and methods separate namespaces. A field and a method in a
NOOP object can thus have the same name without conflict (method overloading, however, where two methods inside an object can have the same
name, is supported neither by SOOP nor by NOOP).11
Nominal vs. Structural vs. Hybrid Typed OO Languages It is worthy
to mention here that the fundamental ‘structural versus nominal’ difference between SOOP and NOOP has profound implications on comparing nominallytyped OO languages to structurally-typed OO languages, and to hybrid OO
languages that try or claim to support both nominal and structural typing.
First, it is clear that supporting nominal typing in an OO language with a
structural view of objects is impossible, since the nominal information stripped
by the structural view of objects is irrecoverable from the structure of the objects.
Second, due to the association of type names to behavioral contracts, it is clear
nominal typing is closer to semantic/behavioral typing than structural typing is
(More discussion of contracts and semantic typing is presented in [10]).
Thirdly, from the definition of NOOP it is clear also that, if needed, it is
easy to define structural types on a domain of nominal objects. The definition
of these types can be done in NOOP by ignoring nominal information, as is
done in “hybrid” OO languages such as Scala, SmallTalk, Whiteoak and Unity.
The definition of these structural types in this case is not the same as for an OO
language based on a structural view of objects and modeled by SOOP, since
objects of the defined structural types will still carry nominal information at
run-time (ready to be used during software run-time, such as in type casting
operations and instanceof type tests). Structural OO languages that support
a structural view of objects are fundamentally different than nominal languages
because objects in such languages, as modeled by SOOP, are plain records (and
thus without any reference to behavioral class contracts), which is not true in
OO languages that try to support both nominal and structural types.12
11

12

To put research on structural OOP on a more rigorous footing, and as a step towards
the construction of NOOP, we constructed COOP—[6, Ch. 4] and [9, Sec. 4]—as
a simple structural domain-theoretic model of OOP that dealt with the first three
of the four tangential differences between NOOP and SOOP.
A further reason we do not believe hybrid languages, such as Scala [50], SmallTalk [1],
Whiteoak [37] and Unity [45], indeed provide true or full support for structural typing
is that these languages do not quite support recursive structural types (varying

4.2

NOOP Compared to µSOOP

Cook built on Cardelli’s work by first developing a model of untyped inheritance [28,31] and, with others, then built a model of typed inheritance [30]. In
his work, Cook took self-referential classes, and thus recursive types, in consideration, but, following the footsteps of Cardelli, Cook kept a structural view of
OO typing. Thus Cook et al. concluded that ‘inheritance is not subtyping’ [30].
Building on the work of Cook et al. and based on its conclusions, Bruce, in his
book on the foundations of OO languages [19], and Simons, in a series of articles
on the theory of classification [58], enforced in the PL research community the
conclusion reached by Cook and his colleagues regarding breaking the relation
between inheritance and subtyping (implying the superiority of a structural view
of OOP in the process), even when the conclusion opposed and contradicted the
intuition (and even the “conventional wisdom” [30, p.125]) of a large section
of OO developers and OO language designers. To explain the discrepancy, it
was then thought that mainstream OO languages are technically deficient or
flawed because, according to Cook [30], these languages ‘place restrictions on
inheritance’.
Given that µSOOP (i.e., Cook et al’s work) is based on that of Cardelli, the
differences between NOOP and SOOP we discussed in Section 4.1 get inherited
by a comparison between NOOP and µSOOP.
The main technical similarity between NOOP and µSOOP is that both
models of OOP take self-referential classes, and thus recursive types, in consideration. This is also where the two models strongly disagree, since NOOP leads to
a different conclusion about the relation between inheritance and subtyping than
µSOOP does. This different conclusion is due to the differences in the nominal
view of objects versus the structural view of th em and to the inclusion/exclusion
of contracts in object typing and object subtyping, and accordingly due to the
role of inheritance (and thus contracts) in deciding subtyping.
As such, in addition to the main difference with SOOP, comparing NOOP
to µSOOP highlights the following four differences, which we first mention then
discuss afterwards in some detail.
1. NOOP and µSOOP have different views of type names.
2. NOOP and µSOOP have different definitions of type inheritance.
3. NOOP and µSOOP are different as to the uniformity of their inheritance
models at the object level and at the type level.
4. NOOP and µSOOP are different as to the simplicity of the mental model
they present to developers during the OO software design process.
between having reluctant/weak support to having no support for them at all). As
discussed in Section 3, recursive types are essential for serious OO programming. As
demonstrated by Cook’s work (which we discuss in more detail in the next section),
supporting recursive structural types (and thus fully supporting structural typing in
these so-called hybrid languages) leads to undesirable consequences. The interested
reader is again advised to see [10] for more details.

Views of type names As we discussed, in detail, in Section 3, a main difference
between nominal typing and structural typing that is illustrated by comparing
NOOP to µSOOP is how type names are viewed in nominal versus structural
OO type systems, them having fixed meanings in the first, while allowing their
meanings to get rebound (upon inheritance) in the latter.
Definitions of inheritance It is worthy to note that the different conclusion
reached by NOOP than that by µSOOP on the relation between inheritance
and subtyping is based, in particular, on how the two models differently define
inheritance. Cook defines inheritance as ‘a mechanism for the definition of new
program units by modifying existing ones in the presence of self-reference’ [28].
Cook also intentionally targets modeling the multiple levels of inheritance that
take place in OOP uniformly (as we discuss below), having a single model of
inheritance that models type-level inheritance and object-level inheritance. Applied to types, Cook’s definition of inheritance based on a structural view of
types makes type inheritance ‘a mechanism for the definition of new record type
expressions by modifying existing ones, in the presence of ‘self-type’ ’. On the
other hand, for the purpose of modeling nominally-typed mainstream OOP with
a nominal view of types (as in NOOP), Cook’s definition of type inheritance
has to be changed to ‘a mechanism for the definition of new class signatures by
adding member (i.e., field and method) signatures to an explicitly-specified set
of existing class signatures.’
In contrast to Cook’s structural definition of type inheritance, the nominal
definition of type inheritance, first, disregards self-types as having relevance in
the definition, in agreement with the intuitions of mainstream OO developers
about the inheritance of class signatures (where it is implied that nominal typing,
with its fixed bindings of type names, only presents an approximation to selftypes). Secondly, also in agreement with intuitions of mainstream OO developers,
the nominal definition of type inheritance stresses explicitness in specifying inheritance, making inheritance an intended relation that is based on behavioral
contracts and structure, not an accidental relation based only on structure.
Uniformity of inheritance models Structurally-typed OOP, as modeled by µSOOP,
uniformly applies the same model of inheritance (i.e., Cook’s model [28]) at the
level of values (i.e., objects) and at the level of types. Using the same model at
both levels requires rebinding the self-variable, at the value level, and rebinding
of the self-type-variable, at the type level, upon inheritance. Nominally-typed
OOP, and thereby NOOP, on the other hand, uses two different models of inheritance, one at the level of values (i.e., objects) and another at the level of
types. The model of inheritance at the level of values used in nominally-typed
OOP (the model of [28] applies well) allows for rebinding the self-variable upon
inheritance. At the level of types, however, a different model where type names
do not get rebound is used by nominally-typed OOP, since there is no exact
notion of a self-type-variable in nominally-typed OO languages (but only an
approximation to it, using a superclass name, is available, as we explain in Section 3).

As such, while the model of inheritance used in µSOOP uniformly applies to
object-level inheritance and type-level inheritance, we can see that the models of
inheritance used in NOOP reflect the non-uniformity of inheritance models in
mainstream nominally-typed OOP, where a different model (and thus a different
definition of inheritance) is used at the object level than that at the type level.
Economy of OO software design conceptual model Agreeing with the intuitions
and conventional wisdom of mainstreaom OOP software developers and OOP
language designers, NOOP proves that ‘inheritance is subtyping’ [6,8,25], i.e.,
that there is a one-to-one correspondence between OO type inheritance and
OO subtyping, while µSOOP breaks the correspondence and proves that ‘inheritance is not subtyping’ [30,19,58]. Splitting inheritance from subtyping, as
µSOOP necessitates, requires a structurally-typed OOP developer to keep two
hierarchies in mind when developing his software, namely, the inheritance hierarchy and the subtyping hierarchy13.
This complexity, and the disregard of class contracts in deciding subtyping, creates significant problems from the perspective of OO program design
(See [10]). Respecting semantic class contracts in subtyping (thereby maintaining the identification of inheritance with subtyping) allows nominally-typed OOP
developers on the other hand to reason about their software more readily and
to keep only one hierarchy in mind while developing their software, leading to a
simpler more economic software design conceptual model.
Table 1 on the following page summarizes the similarities and differences
between NOOP, SOOP and µSOOP.

5

Concluding Remarks and Future Work

The identification of types with behavioral contracts, and of subtyping with the
inheritance and possible narrowing of contracts, makes nominal typing and nominal subtyping in nominally-typed OOP closer to semantic typing and semantic
subtyping. Based on noting that, in this paper we compared a nominally-typed
domain-theoretic model of OOP to the most well-known structurally-typed models. Our comparison has shown that nominally-typed models and structurallytyped models of OOP lead to different views of fundamental notions of object13

Bruce, in an attempt to address this issue, suggested that OO languages replace subtyping with ‘match-bounded polymorphism’ (which is a simplification of F-bounded
polymorphism [20,12]) then identify type inheritance with matching. Matching [18],
upon which match-bounded polymorphism depends, however, uses subtyping in its
definition. As such, match-bounded polymorphism is not truly a full replacement
of subtyping, since developers still need to understand subtyping to be able to understand matching. Having a non-simple mental model of OOP, due to insisting on
maintaining the split between subtyping and inheritance, creates significant conceptual problems when designing OO software. We speculate that this led Bruce’s
suggested language extensions on matching to not gain traction or support in mainstream OO languages.

SOOP
µSOOP
NOOP
(Cardelli; 1980s)
(Cook et al; 1990s) (AbdelGawad; 2010s)
Structural model;
Structural model;
Nominal model;
Nominal Info.
Class names info.
Class names info.
Full class names info.
missing from objects missing from objects
included in objects
Structural (reflect
Structural (reflect Nominal (reflect struc.
Object Types
only object structure) only object structure) and assoc. contracts)
Recursive Types
Excluded
Included
Included
View of
Shortcuts. Self-ref.
Shortcuts. Self-ref. Associated with public
Type Names
not considered
gets rebound
contracts. No rebinding
Inheritance
Redefine inheritance
Same rebinding
Object level: ReModels
as non-recursive
model at object
binding. Type
structural subtyping level and type level
level: No rebinding
Type Inheritance
Structural
Structural
Nominal
Conceptual
Inher. = Subty.
Inher. 6= Subty.
Inher. = Subty.
Economy
Table 1. SOOP vs. µSOOP vs. NOOP

oriented programming, namely objects, type names, class types, subtyping and
the relation between subtyping and inheritance.
In particular, our comparison highlights that in nominally-typed OOP
1. An object should not be mathematically viewed as merely a records of its
members (i.e., its fields and methods) but rather as a record together
with nominal information that is associated with class contracts that
the object maintains—this information being carried along with the record,
behaviorally constraining its members,
2. A class type should not be viewed as a record type but rather as a record
type that additionally respects behavioral contracts associated with
nominal information embedded in elements of the type (i.e., its objects), and
3. Inheritance is correctly identified with nominal subtyping, i.e., that in pure
nominally-typed OOP inheritance is subtyping.
We believe the development of NOOP, and the mathematical comparison presented in this paper, are significant steps in providing a full account of the
relation between nominal and structural OO type systems.
Further, we hope that having a more accurate mathematical view of nominallytyped OO software presents programming languages researchers with better
chances for progressing mainstream OO programming languages. For example, generics ([38,3,50]) add to the expressiveness of type systems of nominallytyped OO programming languages ([13,11,16,40]). As hinted to earlier, we believe
that F-bounded generics offer better support for binary methods in nominallytyped OO languages while maintaining the benefits of nominal typing. Building
a domain-theoretic model of generic nominally-typed OOP, akin to NOOP,
and comparing it to domain-theoretic models of polymorphic structurally-typed
OOP, can as such offer better chances for having a deeper understanding of

features of generic mainstream OO languages such as generic binary methods,
variance annotations (such as Java wildcards), Java erasure, polymorphic methods, and generic type inference.

Acknowledgments
The author expresses his gratitude and appreciation to Professor Robert “Corky”
Cartwright for the discussions we had and the guidance he gave that helped in
developing and reaching some of the conclusions in this paper, and to Professor Benjamin Pierce for the feedback he offered on motivating and presenting
NOOP.

References
1.
2.
3.
4.
5.
6.
7.

8.

9.
10.
11.
12.
13.
14.
15.
16.

ANSI Smalltalk Standard. 1998.
ISO/IEC 14882:2011: Programming Languages: C++. 2011.
C# language specification, version 5.0. http://msdn.microsoft.com/vcsharp, 2015.
Martin Abadi and Luca Cardelli. A semantics of object types. In Proc. LICS’94,
1994.
Martin Abadi and Luca Cardelli. A Theory of Objects. Springer-Verlag, 1996.
Moez A. AbdelGawad. NOOP: A Mathematical Model of Object-Oriented Programming. PhD thesis, Rice University, 2012.
Moez A. AbdelGawad.
An overview of nominal-typing versus structuraltyping in object-oriented programming (with code examples). Technical report,
arXiv.org:1309.2348 [], 2013.
Moez A. AbdelGawad. A domain-theoretic model of nominally-typed objectoriented programming. Journal of Electronic Notes in Theoretical Computer Science (ENTCS), DOI: 10.1016/j.entcs.2014.01.002. Also presented at The 6th International Symposium on Domain Theory and Its Applications (ISDT’13), 301:3–19,
2014.
Moez A. AbdelGawad. Domain theory for modeling oop: A summary. Technical
report, arXiv.org:1406.7497 [], 2014.
Moez A. AbdelGawad. Why nominal-typing matters in OOP. In Submitted for
publication in Onward! Essays, 2016.
Ole Agesen, Stephen N Freund, and John C Mitchell. Adding type parameterization to the Java language, 1997.
Paolo Baldan, Giorgio Ghelli, and Alessandra Raffaeta. Basic theory of f-bounded
polymorphism. Information and Computation, 153(1):173–237, 1999.
Joseph A. Bank, Barbara Liskov, and Andrew C. Myers. Parameterized types and
Java. Technical report, 1996.
John Boyland and Giuseppe Castagna. Parasitic methods: An implementation of
multi-methods for Java. In OOPSLA, 1997.
G. Bracha and D. Griswold. Strongtalk: typechecking Smalltalk in a production
environment. In OOPSLA’93, pages 215–230, 1993.
Gilad Bracha, Martin Odersky, David Stoutamire, and Philip Wadler. Making
the future safe for the past: Adding genericity to the Java programming language.
In Craig Chambers, editor, ACM Symposium on Object-Oriented Programming:
Systems, Languages and Applications (OOPSLA), volume 33, pages 183–200, Vancouver, BC, October 1998. ACM, ACM SIGPLAN.

17. K. Bruce, A. Schuett, R. van Gent, and A. Fiech. PolyTOIL: A type-safe polymorphic object-oriented language. ACM Transactions on Programming Languages
and Systems, 25(2):225–290, 2003.
18. Kim Bruce, Luca Cardelli, Giuseppe Castagna, The Hopkins Objects Group, Gary
Leavens, and Benjamin C. Pierce. On binary methods. Theory and Practice of
Object Systems, 1994.
19. Kim B. Bruce. Foundations of Object-Oriented Languages: Types and Semantics.
MIT Press, 2002.
20. Peter S. Canning, William R. Cook, Walter L. Hill, J. Mitchell, and W. Olthoff.
F-bounded polymorphism for object-oriented programming. In Proc. of Conf. on
Functional Programming Languages and Computer Architecture, 1989.
21. Luca Cardelli. A semantics of multiple inheritance. In Proc. of the internat. symp.
on semantics of data types, volume 173, pages 51–67. Springer-Verlag, 1984.
22. Luca Cardelli. A semantics of multiple inheritance. Inform. and Comput., 76:138–
164, 1988.
23. Luca Cardelli. Structural subtyping and the notion of power type. In ACM Proceedings of POPL, 1988.
24. Luca Cardelli, James Donahue, Lucille Glassman, Mick Jordan, Bill Kalsow, and
Greg Nelson. Modula-3 Report (Revised), volume 52. Digital Systems Research
Center, 1989.
25. Robert Cartwright and Moez A. AbdelGawad. Inheritance Is subtyping (extended abstract). In The 25th Nordic Workshop on Programming Theory (NWPT),
Tallinn, Estonia, 2013.
26. C. Chambers. Object-oriented multi-methods in Cecil. In ECOOP, 1992.
27. C. Clifton, T. Millstein, G. Leavens, and C. Chambers. MultiJava: Design rationale,
compiler implementation and applications. ACM Transactions on Programming
Languages and Systems, 28(3):517–575, 2006.
28. William R. Cook. A Denotational Semantics of Inheritance. PhD thesis, Brown
Univ., 1989.
29. William R. Cook. On understanding data abstraction, revisited. volume 44, pages
557–572. ACM, 2009.
30. William R. Cook, Walter L. Hill, and Peter S. Canning. Inheritance is not subtyping. In POPL’90 Proceedings, 1990.
31. William R. Cook and Jens Palsberg. A denotational semantics of inheritance and
its correctness. In ACM Symposium on Object-Oriented Programming, Systems,
Languages and Applications (OOPSLA), pages 433–444, 1989.
32. Sophia Drossopoulou, Susan Eisenbach, and Sarfraz Khurshid. Is the java type
system sound? TAPOS, 5(1):3–24, 1999.
33. Robert Bruce Findler, Matthew Flatt, and Matthias Felleisen. Semantic casts:
Contracts and structural subtyping in a nominal world. In ECOOP 2004–ObjectOriented Programming, pages 365–389. Springer, 2004.
34. K. Fisher and J. Reppy. The design of a class mechanism for Moby. In PLDI,
1999.
35. Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen. Classes and mixins. In Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles
of programming languages, pages 171–183. ACM, 1998.
36. Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen. A programmer’s
reduction semantics for classes and mixins. In Formal syntax and semantics of
Java, pages 241–269. Springer, 1999.
37. J. Gil and I. Maman. Whiteoak: Introducing structural subtyping in Java. In
OOPSLA, 2008.

38. James Gosling, Bill Joy, Guy Steele, Gilad Bracha, and Alex Buckley. The Java
Language Specification. Addison-Wesley, 2014.
39. Ben Greenman, Fabian Muehlboeck, and Ross Tate. Getting f-bounded polymorphism into shape. In Proceedings of the 35th ACM SIGPLAN Conference on
Programming Language Design and Implementation, PLDI’14, 2014.
40. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. Featherweight Java:
A minimal core calculus for Java and GJ. ACM Transactions on Programming
Languages and Systems, 23(3):396–450, May 2001.
41. X. Leroy, D. Doligez, J. Garrigue, D. Rémy, and J. Vouillon. The Objective Caml
system. Available at http://caml.inria.fr/.
42. David B. MacQueen. Should ML be object-oriented? Formal Aspects of Computing,
13:214–232, 2002.
43. David B. MacQueen, Gordon D. Plotkin, and R. Sethi. An ideal model for recursive
polymorphic types. Information and Control, 71:95–130, 1986.
44. Boris Magnusson. Code reuse considered harmful, 1991.
45. Donna Malayeri and Jonathan Aldrich. Integrating nominal and structural subtyping. In ECOOP 2008–Object-Oriented Programming, pages 260–284. Springer,
2008.
46. Donna Malayeri and Jonathan Aldrich. Is structural subtyping useful? an empirical
study. In ESOP, 2009.
47. Erik Meijer and Peter Drayton. Static typing where possible, dynamic typing when
needed: The end of the cold war between programming languages. In OOPSLA,
2004.
48. R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard
ML (Revised). MIT Press, 1997.
49. Tobias Nipkow and David Von Oheimb. Javalight is type-safe–definitely. In Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 161–170. ACM, 1998.
50. Martin Odersky. The scala language specification, v. 2.9. http://www.scalalang.org, 2014.
51. Klaus Ostermann. Nominal and structural subtyping in component-based programming. Journal of Object Technology, 7(1):121–145, 2008.
52. Benjamin C. Pierce. Types and Programming Languages. MIT Press, 2002.
53. Benjamin C. Pierce. Types and programming languages: The next generation.
LICS’03, 2003.
54. Harry H Porter III. Separating the subtype hierarchy from the inheritance of
implementation. Journal of Object-Oriented Programming, 4(6):20–29, 1992.
55. Bernhard Reus. Class-based versus object-based: A denotational comparison. Algebraic Methodology And Software Technology, Lecture Notes in Computer Science,
2422:473–488, 2002.
56. Bernhard Reus. Modular semantics and logics of classes. In Computer Science
Logic, volume 2803, pages 456–469. Springer, 2003.
57. Bernhard Reus and Thomas Streicher. Semantics and logics of objects. Proceedings
of the 17th Symp. on Logic in Computer Science (LICS 2002), pages 113–122, 2002.
58. Anthony J. H. Simons. The theory of classification, part 1: Perspectives on type
compatibility. Journal of Object Technology, 1(1):55–61, May-June 2002.
59. Kresten Krab Thorup and Mads Torgersen. Unifying genericity. In ECOOP 99–
Object-Oriented Programming, pages 186–204. Springer, 1999.

