Lecture 18: Supporting Object-Oriented Programming🔗

1 Supporting Object-Oriented Programming🔗

So far our language is mostly-pure, functional and expression-based. There are obviously many other styles of languages and many other language features to consider supporting; one of the most salient is object-oriented programming.

Do Now!

What language features would you consider to be essential for supporting object-oriented programming? Why?

The primary feature of an object-oriented language is the eponymous object: a new kind of value that contains both local state and local computation. To support objects, we potentially need a bunch of related features:

• this

• Methods

• Fields

• Dynamic dispatch

• Inheritance

• Overriding

• Overloading

• instanceof

• Classes and constructors

Do Now!

Which of these features are intrinsically statically-typed, and which ones might apply in a dynamically-typed language also?

Looking just at dynamically-typed languages: JavaScript gets by without classes or overloading, while Python has classes but no overloading. Both languages have a notion of instanceof and inheritance, whether or not they have classes. Both languages fields, this, methods, dynamic dispatch and overriding. Evidently, these features aren’t a all-or-nothing design choice.

Classes, in particular, have two roles: they dynamically provide a way to construct new objects and determine instanceof relationships and method implementations, and they statically can define inheritance relationships and static type system choices.

2 Static type system issues🔗

Let’s just consider constructing objects for now; field accesses and method accesses add even more static complexity. To a crude first approximation, every class definition creates a new type, distinct from all other types. The constructor for a class is simply a function that returns an instance of that type. Ignoring syntactic details, we might model this as saying, class Foo { Foo(int x) { ... } ... } defines a function new-Foo of type Int -> Foo. Since Foo is a brand-new type, and new-Foo is the only function that creates such a type, we are guaranteed that this constructor function is the only way to construct an instance of Foo.

Or is it? Consider two classes in a Java-like language:

class Base {
  ...
}
class Derived extends Base {
  ...
}

// Elsewhere in the program
Base b = new Derived(); // Why is this legal?

The intent behind subclassing is two-fold: to assert that every instance of the derived class is also an instance of the base class, and for every instance of the derived class to inherit all the behaviors and state of the base class. To handle this scenario, we need a new subtyping relation as part of our type system, to model when values of one type can safely be considered values of another type. For example, we might define the rule

\begin{equation*}\dfrac{\texttt{class D extends B}}{D <: B}\end{equation*}

Read this rule as, “D is a subtype of B when we have a declaration class D extends B.” We use the symbol \(<:\) as a visual contraction of both “less-than” and “has-type”.

(Note that this is different from saying that one particular type might be an instantiation of some other polymorphic type scheme. Instantiating a type scheme allows us to say, “there exists a way for me to make these two types equal.” Subtyping, on the other hand, lets us say “this type is less-than-or-equal, or more-specific-than, this other type.” It is a qualitatively different kind of relationship.) Adding a subtyping relation fits in neatly to type systems, at least in terms of judgement rules:

\begin{equation*}\dfrac{e : \mathsf{\tau_1} \quad \tau_1 <: \tau_2}{e : \mathsf{\tau_2}}\end{equation*}

The challenge is when and how to apply this subtyping rule: we don’t know what \(\tau_1\) is! Worse, subtyping obeys a transitivity rule, analogous to transitivity for less-than, that says

\begin{equation*}\dfrac{\tau_1 <: \tau2 \quad \tau_2 <: \tau_3}{\tau_1 <: \tau_3}\end{equation*}

In words, if one type is a subtype of a second, and that second is a subtype of a third type, then the first type is a subtype of the third. Once again, this rule is difficult to use well, because we have to guess the middle type (or types, if we use the rule repeatedly!).

These difficulties make both type checking and type inference difficult: unless the input programs are sufficiently annotated, we can’t guess what type derivations are needed. Since designing a sufficiently powerful type system is not our goal right now, we’ll abandon the static typing implications of classes, and focus on the dynamic implications.

3 Representing objects in memory🔗

Do Now!

What well-formedness errors might we want to enforce on class definitions, to ensure that any field declarations make sense? How might that change (or be refined) in the presence of inheritance?

3.1 Simple objects🔗

Reasoning by similarity, a class is “like a tuple, but with named fields”. Accordingly we might choose a representation similar to tuples for our objects: some header information (perhaps indicating the size of the object), followed by a bunch of words, one per field. Of course, we’d need to tag our values as objects, and we’ve run out of tags... We have a few options:

• We could remove tuples from our language, and reuse that tag for objects.

• We could force a 16-byte alignment policy, and gain one more tag bit.

• We could change our tagging strategy entirely, such that a tag indicates Boolean, Int, or On-the-heap, and the first word of every heap-allocated value contains another tag indicating which sort of value it is.

This last strategy seems the most invasive (and it substantially complicates our tag-checking code), but is likely the most flexible. For now though, we’ll assume the first strategy, and just focus on objects while excluding tuples.

Do Now!

Brainstorm the upcoming challenges here: how do we lay out fields within the object? What other OO features complicate matters?

To determine which field offset corresponds to which named field, our compiler can build a table mapping class names and field names to indices — preserving the declaration order of the fields in a class. For example, given

class Point2d:
  fields x, y
  ...
end
class Foo:
  fields a, b, x
  ...
end

3.2 Inheritance of fields🔗

Suppose we declared a class

class Point3d extends Point2d:
  fields z
  ...
end

How many fields should we have in each Point3d object, and at what offsets? Because we know at compile time which classes extend which others, we can compute that Point3d contains three fields. Moreover, we want every Point3d instance to “look like” a Point2d instance:

def xyDist(p : Point2d):
  p.y - p.x

xyDist(new Point3d(3, 4, 5)) # should produce 1, rather than crash

Therefore, we must lay out all the base class’s fields in order, followed by any new fields from the derived class. This proceeds recursively up the class hierarchy: if we have a class C3 that extends another class C2 that itself extends a base class C1, we would lay out C1’s fields first (in order), followed by C2’s fields, followed finally by C3’s fields. This way, even in functions like xyDist, which expect a base-class object, the field accesses will use the correct offsets in derived-class objects, because the two classes agree on locations for fields they share in common.

Do Now!

Given this layout description, explain why multiple inheritance is remarkably difficult to do well.

4 Compilation of methods🔗

Do Now!

What new well-formedness errors might we want to enforce on class definitions, now that they have both fields and methods?

4.1 Simple methods and this🔗

The crucial distinction between methods and mere functions is the presence of this: the ability for each method to know what object it was invoked on, so that it can access the object’s fields. However we compile method invocations, we must somehow supply this extra parameter.

Consider the expression o.m(a). Assuming that we ensure that field names and method names are mutually unique (such that we prohibit having a field and a method of the same name), then we can always tell whether m is a method, or a field that happens to contain a function.

Do Now!

Is this assumption easy to enforce? Consider the cases where o is declared to have a type that is any class, a base class, or a derived class, and whether m is declared in that class, a base class, or a derived class. Are there any cases where we cannot know what m is? Could such cases be compile-time errors?

4.2 Inheritance of methods🔗

5 Supporting instanceof🔗

1Contrast this with languages like JavaScript, where field names can be dynamically constructed, and objects are nothing more than dictionaries.