Chapter 5
Object-Oriented Language Features

Object-oriented programming can today be declared a success. Introductory programming courses are often taught using object-oriented languages such as C++ and Java. Most new commercial projects choose an object-oriented language. Yet, object-oriented features do not fundamentally add much to a language. They certainly do not lead to shorter programs. The success of object-oriented programming is due mainly to the fact that it is a style that is appropriate for the human psychology. Humans, as part of their basic function, are highly adept at recognizing and interacting with everyday objects. And, objects in programming are enough like objects in the everyday world that our rich intuitions can apply to them.

Before we discuss the properties of objects in object-oriented programming, let us briefly review some of the more important properties of everyday objects that would make them useful for programming.

• Everyday objects are active, that is, they are not fully controlled by us. Objects have internal and evolving state. For instance, a running car is an active object, and has a complex internal state including the amount of gas remaining, the engine coolant and transmission fluid levels, the amount of battery power, the oil level, the temperature, the degree of wear and tear on the engine components, etc.
• Everyday objects are communicative. We can send messages to them, and we can get feedback from objects as a result of sending them messages. For example, starting a car and checking the gas gauge can both be viewed as sending messages to the car.¹
• Everyday objects are encapsulated. They have internal properties that we can not see, although we can learn some of them by sending messages. To continue the car example, checking the gas gauge tells us how much gas is remaining, even though we can’t see into the gas tank directly, and we don’t know if it contains regular or premium gas.
• Everyday objects may be nested, that is, objects may be made up of several smaller object components, and those components may themselves have smaller components. Once again, a car is a perfect example of a nested object, being made of of smaller objects including the engine and the transmission. The transmission is also a nested object, including an input shaft, an output shaft, a torque converter, and a set of gears.
• Everyday objects are, for the most part, uniquely named. Cars are uniquely named by license places or vehicle registration numbers.
• Everyday objects may be self-aware, in the sense that they may intentionally interact with themselves, for instance a dog licking his paw.
• Everyday object interactions may be polymorphic in that a diverse set of objects may share a common messaging protocol, for example the accelerator/brake/steering wheel messaging system common to all models of cars and trucks.

The objects in object-oriented programming also have these properties. For this reason, object-oriented programming has a natural and familiar feel to most people. Let us now consider objects of the programming variety.

• Objects have an internal state in the form of instance variables or fields. Objects are generally active, and their state is not fully controlled by their callers.
• Objects support messages, which are named pieces of code that are tied to a particular object. In this way objects are communicative, and groups of objects accomplish tasks by sending messages to each other.
• Objects consist of encapsulated code (methods or operations) along with a mutable state (instance variables or fields). Right away it should be clear that objects are inherently non-functional. This mirrors the statefulness of everyday objects.
• Objects are typically organized in a nested fashion. For example, consider an object that represents a graphical web browser. The object itself is frame, but that frame consists of a toolbar and a viewing area. The toolbar is made up of buttons, a location bar, and a menu, while the viewing area is made up of a rendered panel and a scroll bar. This concept is illustrated in Figure 5.1. Object nesting is generally accomplished by the outer object storing its inner objects as fields or instance variables.
• Objects have unique names, or object references, to refer to them. This is analogous to the naming of real-world objects, with the advantage that object references are always unique whereas real-world object names may be ambiguous.
• Objects are self aware, that is, objects contain references to themselves. this in Java and self in Smalltalk are self-references.
• Objects are polymorphic, meaning that a “fatter” object can always be passed to a method that takes a “thinner” one, that is, one with fewer methods and public fields.

There are several additional features objects commonly have. Classes are nearly always present in languages with objects. Classes are not required: it is perfectly valid to have objects without classes. The language Self [19, 20, 1] has no classes, instead it has prototype objects which are copied that do the duty of classes. Important concepts of classes include creation, inheritance, method overriding, superclass access, and dynamic dispatch. We will address these concepts later.

Information hiding for fields and methods is another feature that most object-oriented languages have, generally in the form of public, private, and protected keywords.

Other aspects of objects include object types and modules. Types are discussed briefly, but modules are beyond the scope of this book. We also ignore method overloading, as it is simply syntactic sugar and adds only to readability, not functionality. Recall that overloading a method means there are two methods with the same name, but different type signatures. Overriding means redefining the behavior of a superclass’s method in a subclass. Overriding is discussed in Section 5.1.5.

5.1 Encoding Objects in DSR

One of the most important aspects of objects is how close they are to existing concepts that we have already discussed. In this section we demonstrate how objects may be encoded in DSR. We will model objects as records of functions and references. Record labels and values can be thought of as slots for either methods or fields. A slot with a function is a method, and a slot with a reference is a field.

5.1.1 Simple Objects

Consider the object in Figure 5.2² that represents a point in two-dimensional space. The object has fields x and y, along with two methods: magnitude and iszero, with obvious functionality. To encode this object as a record, we are going to need a record that has the following structure.

We can’t write the magnitude method yet, because we need to define it in terms of x and y, but there is no way to refer to them in the function body. The solution we will use is the same one that C++ uses behind the scenes: we pass the object itself as an argument to the function. Let’s revise our first encoding to the following one (assuming we’ve defined a sqrt function).

There are a few points of interest about the above example. First of all, the object itself needs to be explicitly passed as an argument when we send a message. For example, to send the magnitude message to point, we would write

point.magnitude point {}.

For convenience, we can use the abbreviation obj <- method to represent the message (obj.method obj).

Even inside the object’s methods, we need to pass this along when we call another method. iszero illustrates this point in the way it calls magnitude. This encoding of self-reference is called the self-application encoding. There are a number of other encodings, and we will treat some of them below.

There is a problem with this encoding, though; our object is still immutable. An object with immutable fields can be a good thing in many cases. For example, windows that can’t be resized and sets with fixed members can be implemented with immutable fields. In general, though, we need our objects to support mutable fields. Luckily this problem has an easy solution. Consider the following revision of our point encoding, which uses Refs to represent fields.

To set x to 12, we can write either point <- setx 12, or we can directly change the field with (point.x) := 12. To access the field, we now write !(point.x), or we could define a getx method to abstract the dereferencing. This strategy gives us a faithful encoding of simple objects. In the next few sections, we will discuss how to encode some of the more advanced features of objects.

5.1.2 Object Polymorphism

Suppose we define the following function.

If we were to define person objects that supported the height message, we could pass them as arguments to this function. However, we could also create specialized person objects, such as mother, father, and child. As long as these objects still support the height message, they are all valid candidates for the tallerThan function. Even objects like dinosaurs and buildings can be arguments. The only requirement is that any objects passed to tallerThan support the message height. This is known as object polymorphism.

We already encountered a similar concept when we discussed record polymorphism. Recall that a function

Let getheight = Function r -> r.height ...

can take any record with a height field:

... In getheight {radius = 4; height = 4; weight = 44}

Object polymorphism is really the same as record polymorphism, evidenced by how we view objects as records. So simply by using the record encoding of objects, we can easily get object polymorphism.

The object passed to equal needs only to define x and y. Object polymorphism in our embedded language is thus more powerful than in C++ or Java: C++ and Java look at the type of the arguments when deciding what is allowed to be passed to a method. Subclasses can always be passed to methods that take the superclass, but nothing else is allowed. In our encoding, which is closer to Smalltalk, any object is allowed to be passed to a function or method as long as it supports the messages needed by the function.

One potential difficulty with object polymorphism is that of dispatch: since we don’t know the form of the object until runtime, we do not know exactly where the correct methods will be laid out in memory. Thus hashing may be required to look up methods in a compiled object-oriented language. This is exactly the same problem that arises when writing the record-handling code in our DSR compiler (see Chapter 7), again illustrating the similarities between objects and records.

5.1.3 Information Hiding

Most object-oriented languages allow information hiding which is used to protect methods and instances variables from direct outside use. Information hiding is one of the key tools for the encapsulation of object data. In C++ and Java, the public, private, and protected qualifiers are used to control the degree of information hiding for both fields and methods.

For now we will simply encode hiding in DSR. Note that only public and private data makes sense in DSR (protected data only makes sense in the context of classes and inheritance, which we have not defined yet). In our encoding, we accomplish hiding by simply making data inaccessible. In real, typed languages, it it the type system itself (and the bytecode verifier in the case of Java) that enforces the privacy of data.

Let’s begin with a partial encoding of information hiding.

In this encoding, each method is “preapplied” to pointImpl, the full point object, while pointInterface contains only public methods and instances. Methods are now invoked simply as

pointInterface.setx 5

This solution has a flaw, though. Methods that return this re-expose the hidden fields and methods of the full object. Consider the following example.

The sneaky method returns the full pointImpl object instead of the pointInterface version. To remedy this problem, we need to change the encoding so that we don’t have to pass this every time we invoke a method. Instead, we will give the object a pointer to itself from the start.

Now message send is just

point.magnitude {}

The method getThis still returns this, but this contains the public parts only. Note that for this encoding to work, privateThis can be used only as a target for messages, and can not be returned.

The disadvantage of this encoding is that this will need to be applied to itself every time it’s used inside the object body. For example, instead of writing

(point.getThis {}).magnitude {}

we would, instead, have to write

((point.getThis {}) (point.getThis {})).magnitude {}

These encodings are relatively simple. Classes and inheritance are more difficult to encode, and are discussed below. Object typing is also particularly difficult, and is covered in Chapter 6.

5.1.4 Classes

Classes are foremost templates for creating objects. A class is, in essence, an object factory. Each object that is created from a class must have its own unique set of instance variables (with the exception of static fields, which we will treat later).

It is relatively easy to produce a simple encoding of classes. Simply freeze the code that creates the object, and thaw to create new object. Ignoring information hiding, the encoding looks as follows.

We can define new pointClass to be pointClass {}. Some typical code which creates and uses instances might look as follows.

point1 and point2 will have their own x and y values, since Ref creates new store cells each time it is thawed. The same freeze and thaw trick can be applied to our encoding of information hiding to get hiding in classes. The difficult part of encoding classes is encoding inheritance, which we discuss in the next section.

5.1.5 Inheritance

As a rule, about 80 percent of the utility of objects is realized in the concepts we have talked about above, namely

• Objects that encapsulate data and code under a single name to achieve certain functionality.
• Polymorphic objects.
• Templates for generating objects (the main function of classes)

The other 20 percent of the utility comes from from inheritance. Inheritance allows related objects to be defined that share some common code. Inheritance can be encoded in DSR by using the following scheme. In the subclass, we create an instance of the superclass object, and keep the instance around as a “slave.” We use the slave to access methods and fields of the superclass object. Thus, the subclass object only contains new and overridden methods. Real object oriented languages tend not to implement inheritance this way for reasons of efficiency (imagine a long inheritance chain in which a method call has to be delegated all the way back to the top of the hierarchy before it can be invoked). Still, the encoding is good enough to illustrate the main points of inheritance. For example, consider the following encoding of ColorPoint, a subclass of Point, illustrated in Figure 5.3.

There are several points of interest in this encoding. First of all, notice that to inherit methods and fields from the superclass, we explicitly link them together (i.e. x, y, setx, and sety). To override a method in the superclass, we simply redefine it in the subclass instead of linking to the superclass; magnitude is an example of this. Also notice that we can still invoke superclass methods from the subclass. For instance, magnitude invokes super.magnitude in its body. Notice how super.magnitude is passed this instead of super as its argument. This has to do with dynamic dispatch, which we will address now.

5.1.6 Dynamic Dispatch

We say that a method is dynamically dispatched if, looking at a message send v<-m, we are not sure precisely what method m will be executed at runtime. Dynamic dispatch is related to object polymorphism: a variable v could contain many different kinds of objects, so v<-m could be sending m to any one of those different kinds of objects. Unless we know what kind of objects v is at runtime, we cannot know which method m will be invoked.

The term dynamic dispatch refers to how the method invoked by a message send is not fixed at compile-time. If we had a method isNull declared in pointClass and inherited by colorPointClass with code

Function this -> Function _ -> (this.magnitude this {}) = 0,

the magnitude method here is not fixed at compile-time. If this is a point, it will use point’s magnitude method. If it’s a colorPoint, that colorPoint’s overridden magnitude method will be used.

To illustrate the difference between static and dynamic dispatch, let us consider a new example. Consider the following classes, rectClass and its subclass squareClass.

Notice that in the squareClass, getLength has been overridden to behave the same as getWidth. There are two ways to calculate the area in squareClass. areaStatic calls (super.area) super {}. This means that when rectClass’s area method is invoked, it is invoked with rectClass’s getLength and getWidth as well. The result is 1 × 10, which is 10.

On the contrary, the dynamically dispatched area method, areaDynamic is written (super.area) this {}. This time, rectClass’s area method is invoked, but this is an instance of squareClass, rather than rectClass, and squareClass’s overridden getLength and getWidth are used. The result is 1, the correct area for a square. The behavior of dynamic dispatch is almost always the behavior we want. The key to dynamic dispatch is that inherited methods get a revised notion of this when they are inherited. Our encoding promotes dynamic dispatch, because we explicitly pass this into our methods.

Java (and almost every other object-oriented language) uses dynamic dispatch to invoke methods by default. In C++, however, unless a method is declared as virtual, it will not be dynamically dispatched.

5.1.7 Static Fields and Methods

Static fields and methods are found in almost all object-oriented languages, and are simply fields and methods that are not tied to a particular instance of an object, but rather to the class itself.

We can trivially encode static fields and methods by simply making our class definitions records instead of functions. The creation of the object can itself be a static method of the class. This is, in fact, how Smalltalk implements constructors. Consider the following reimplementation of pointClass in which we make use of static fields.

Notice how the class method newWithXY is actually responsible for building the point object. new simply invokes newWithXY with some default values that are stored as class fields. This is a very clean way to encode multiple constructors.

Perhaps the most interesting thing the encoding is how classes with static fields start to look like our original encoding of simple objects. Look closely--notice that class methods take an argument class as their first parameter, for the exact same reason that regular methods take this as a parameter. So in fact, pointClass is really just another primitive object that happens to be able to create objects.

Viewing classes as objects is the dominant paradigm in Smalltalk. Java has some support for looking at classes as objects through the reflection API as well. Even in languages like C++ that don’t view classes as objects, design patterns such as the Factory patterns[11] capture this notion of objects creating objects.

This encoding is truly in the spirit of object-oriented programming, and it is a clean, and particularly satisfying way to think about classes and static members.

5.2 The DOB Language

Now that we have looked at encodings of objects in terms of the known syntax of DSR, we may now study how to add these features directly to a language. We will call this language DOB, D with objects. Our encodings of objects were operationally correct, but not adding syntactic support for objects makes them too difficult to work with in practice. The colorPoint encoding, for example, is quite difficult to read. This readability problem only gets worse when types are introduced into the language.

DOB includes the most of the features we discussed above: classes, message send, methods, fields, super, and this. We support information hiding in the same manner in which Smalltalk does: all instance variables are hidden (protected) and all methods are exposed (public).

DOB also supports primitive objects. Primitive objects are objects that are defined “inline,” that is, objects that are not created from a class. They are a more lightweight from of object, and are similar to Smalltalk’s blocks and Java’s anonymous classes. Primitive objects aren’t very common in practice, but we include them in DOB because it requires very little work. The value returned by the expression new aClass is an object, which means that an object is a first class expression. As long as our concrete syntax allows us to directly define primitive objects, no additional work is needed in the interpreter.

An interesting consequence of having primitive objects is that is that we could get rid of functions entirely (not methods). Functions could simply be encoded as methods of primitive objects. For this reason, object-oriented languages that support primitive objects have many of the advantages of higher-order functions.

5.2.1 Concrete Syntax

Let’s introduce the DOB concrete syntax with an example. The following code is an implementation of the pointClass / colorPointClass hierarchy from before (Figure 5.3).

There is a lot going on with this syntax, so let’s take some time to point out some of the major elements. First of all, notice that This and Super are special “reserved variables.” In our D encodings, we had to write “Function this -> ” and pass this as an explicit parameter. Now, self-awareness happens implicitly, and is This is a reference to self.

Note the use of a primitive object to define the color field of the colorPointClass. The red, green, and blue values are implemented as methods, since fields are always “private.”

In our previous encodings we used one style when defining the base class, and another different style when defining the subclass. In DOB we use the same syntax for both by always specifying the superclass. To allow for base classes that do not inherit from any other class, we allow a class to extend EmptyClass, which is simply an special class that does not define anything.

DOB instance variables use the l/r-value form of state that was discussed in Section 4.1.3. There is no need to explicitly use the ! operator to get the value of an instance variable. DOB instance variables are therefore mutable, not following the Caml convention that all variables are immutable. Note that method arguments are still immutable. There are thus two varieties of variable: immutable method parameters, and mutable instances. Since it is clear which variables are instances and which are not, there is no great potential for confusion. It is the job of the parser to distinguish between instance variables and regular variables. An advantage of this approach is that it keeps instance variables from being directly manipulated by outsiders.

Method bodies are generally functions, but need not be; they can be any immutable, publicly available value. For example, immutable instances can be considered methods (see the color primitive object in the example above).

Note that we still have to explicitly inherit methods. This is not the cleanest syntax, but it simplifies the interpreter, and makes facilitates translation to DSR discussed in Section 5.2.3.

Also, there is no constructor function. new is used to create new instances, and, following Smalltalk, initialization is done explicitly by writing an initialize method.

For simplicity, DOB does not support static fields and methods, nor does it take the “classes as objects” view discussed in the previous section.

5.2.2 A Direct Interpreter

We first consider a direct interpreter for DOB. The abstract syntax can be expressed by the following Caml type.

Here is a rough sketch of the interpreter. This interpreter is not complete, but it gives a general idea of what one should look like.

This code sketch for the interpreter does a nice job of illustrating the roles of This and Super. We only substitute for this when we send a message. That’s because This is a dynamic construct, and we don’t know what it will be until runtime (see the discussion of dynamic dispatching in Section 5.1.6). On the other hand, Super is a static construct, and is known at the time we write the code, which allows us to substitute for Super as soon as the Class expression is evaluated.

5.2.3 Translating DOB to DSR

Another way to give meaning to DOB programs is by defining a translation mapping DOB programs into DSR programs. This is a complete characterization of how objects can be encoded in DSR, the topic of Section 5.1.

In Chapter 7 below, we devleop a compiler for DSR. To obtain a compiler for DOB, we can simply add a translation step that translates DOB to DSR, and then simply compile the DSR using this compiler. Thus, we will have a DOB compiler “for free” when we are all done. This section only discusses the DOB to DSR translation.

The translation is simply a formalization of the encodings given in Section 5.1. Although real object-oriented compilers are much more sophisticated, this section should at least provide an understandable view of what an object-oriented compiler does. The concrete syntax translation is inductively defined below in a piecewise manner.

The translation is fairly clean, except that messages to Super have to be handled a bit differently that other messages in order to properly implement dynamic dispatch. Notice again that instance variables are handled differently than function variables, because they are mutable. Empty function application, i.e. f (), may be written as empty record application: f {}. The “_” variable in Function _ -> e is any variable not occurring in e. The character “_” itself is a valid variable identifier in the DDK implementation of DSR, however (see Chapter A).

As an example of how this translation works, let us perform it on the DOB version of the point / colorPoint classes from Section 5.2.1. The result is the following:

After writing a Caml version of toDSR for the abstract syntax, a DOB compiler is trivially obtained by combining toDSR with the functions defined in Chapter 7:

Finally, there are several other ways to handle these kinds of encodings. More information about encoding objects can be found in [9].