18 Objects
When a language admits functions as values, it provides developers the
most natural way to represent a unit of computation. Suppose a
developer wants to parameterize some function f. Any language
lets f be parameterized by passive data, such as numbers
and strings. But it is often attractive to parameterize it over
active data: a datum that can compute an answer, perhaps
in response to some information. Furthermore, the function passed to
f can—
While a function is a splendid thing, it suffers from excessive
terseness. Sometimes we might want multiple functions to all close
over to the same shared data; the sharing especially matters if
some of the functions mutate it and expect the others to see the
result of those mutations. In such cases, it becomes unwieldly to
send just a single function as a parameter; it is more useful to send
a group of functions. The recipient then needs a way to choose
between the different functions in the group. This grouping of
functions, and the means to select one from the group, is the essence
of an object. We are therefore perfectly placed to study
objects having covered functions (Functions Anywhere)
and mutation (Mutation: Structures and Variables)—
I cannot hope to do justice to the enormous space of object systems. Please read Object-Oriented Programming Languages: Application and Interpretation by Éric Tanter, which goes into more detail and covers topics ignored here. Let’s add this notion of objects to our language. Then we’ll flesh it out and grow it, and explore the many dimensions in the design space of objects. We’ll first show how to add objects to the core language, but because we’ll want to prototype many different ideas quickly, we’ll soon shift to a desguaring-based strategy. Which one you use depends on whether you think understanding them is critical to understanding the essence of your language. One way to measure this is how complex your desguaring strategy becomes, and whether by adding some key core language enhancements, you can greatly reduce the complexity of desugaring.
18.1 Interpreting Objects
a value, that
maps names to
stuff: either other values or “methods”.
data Value:
| numV (n :: Number)
| closV (f :: ExprC, e :: List<Binding>)
| objV (ns :: List<String>, vs :: List<Value>)
end
| objC (ns :: List<String>, vs :: List<ExprC>)
| objC(ns, vs) =>
obj-vs = eval-obj-vs(vs, nv, st)
ret(objV(ns, obj-vs.exprs), obj-vs.final-store)
Write eval-obj-vs, which evaluates each expression in vs while threading the store. Assume it returns an object with two fields: exprs is the list of evaluated expressions, while final-store is the final store ensuing from these evaluations.
| msgC (o :: ExprC, n :: String) |
| msgC(o, n) =>
o-val = interp(o, nv, st)
msg = lookup-msg(n, o-val.v)
ret(msg, o-val.st)
Implement lookup-msg.
In principle, msgC can be used to obtain any kind of
member but for simplicity, we need only assume that we have
functions. To use them, we must apply them to values. This is
cumbersome to write directly, so let’s assume desugaring
has taken care of it for us: that is, the user can write
(msg o m v)—
(let o (obj (add1 (lambda x (+ x 1))) |
(sub1 (lambda x (+ x -1)))) |
(msg o sub1 2)) |
18.2 Objects by Desugaring
While defining objects in the core language is good to really understand their essence, it’s an unwieldy way to go about studying them. Instead, we’ll use Pyret to represent objects, sticking to the parts of the language we already know how to implement in our interpreter. That is, we’ll assume that we are looking at the output of desugaring. (For this reason, we’ll also stick to stylized code, potentially writing unnecessary expressions on the grounds that this is what a simple program generator would produce.)
The code that follows largely drops type annotations. Go back in and add these annotations wherever possible; where you can’t, explain what problems you encounter.
18.2.1 Objects as Named Collections
o-1 = |
fun(m): |
if m == "add1": |
fun(x): x + 1; |
else if m == "sub1": |
fun(x): x - 1; |
else: |
raise("message not found: " + m) |
end |
end |
check: o-1("add1")(5) is 6;
fun msg(o, m, a): o(m)(a);
check: msg(o-1, "add1", 5) is 6;
Something very important changed when we switched to the desguaring strategy. Do you see what it is?
check: msg(o-1, "add" + "1", 5) is 6;
This is a general problem with desugaring: the target language may allow computations that have no counterpart in the source, and hence cannot be mapped back to it. Fortunately we don’t often need to perform this inverse mapping, though it does arise in some debugging and program comprehension tools. More subtly, however, we must ensure that the target language does not produce values that have no corresponding equivalent in the source.
o-1-1 = mk-object(
[ mtd("add1", fun(x): x + 1;),
mtd("sub1", fun(x): x - 1;) ] )
data Mtd:
| mtd (name :: String, value)
end
fun mk-object(n-vs):
fun(m):
fun lookup(locals):
cases (List) locals:
| empty => raise("message not found: " + m)
| link(f, r) =>
if f.name == m: f.value else: lookup(r);
end
end
lookup(n-vs)
end
end
With this much simpler notation—
18.2.2 Constructors
o-constr-1 =
fun(x):
mk-object( [ mtd("addX", fun(y): x + y;) ])
end
check:
msg(o-constr-1(5), "addX", 3) is 8
msg(o-constr-1(2), "addX", 3) is 5
end
18.2.3 State
o-state-1 =
fun(count):
var mut-count = count
mk-object(
[ mtd("inc", fun(n): mut-count := mut-count + n;),
mtd("dec", fun(n): mut-count := mut-count - n;),
mtd("get", fun(_): mut-count;) ] )
end
check:
o = o-state-1(5)
msg(o, "inc", 1)
msg(o, "dec", 1)
msg(o, "get", "dummy") is 5
end
check:
o1 = o-state-1(5)
o2 = o-state-1(5)
msg(o1, "inc", 1)
msg(o1, "inc", 1)
msg(o1, "get", "dummy") is 7
msg(o2, "get", "dummy") is 5
end
18.2.4 Private Members
Another common object language feature is private members: ones that are visible only inside the object, not outside it.Except that, in Java, instances of other classes of the same type are privy to “private” members. Otherwise, you would simply never be able to implement an Abstract Data Type. These may seem like an additional feature we need to implement, but we already have the necessary mechanism in the form of locally-scoped, lexically-bound variables, such as mut-count above: there is no way for surrounding code to access mut-count directly, because lexical scoping ensures that it remains hidden to the world.
18.2.5 Static Members
mk-bank-account =
block:
var counter = 0
fun (amount):
var balance = amount
counter := counter + 1
mk-object(
[ mtd("deposit", fun(m): balance := balance + m;),
mtd("withdraw", fun(m): balance := balance - m;),
mtd("balance", fun(_): balance;),
mtd("how-many-accounts", fun(_): counter;) ])
end
end
check:
acc-1 = mk-bank-account(0)
msg(acc-1, "how-many-accounts", "dummy") is 1
acc-2 = mk-bank-account(100)
msg(acc-1, "how-many-accounts", "dummy") is 2
msg(acc-2, "how-many-accounts", "dummy") is 2
msg(acc-1, "deposit", 100)
msg(acc-1, "withdraw", 50)
msg(acc-2, "deposit", 10)
msg(acc-1, "balance", "dummy") is 50
msg(acc-2, "balance", "dummy") is 110
msg(acc-1, "how-many-accounts", "dummy") is 2
msg(acc-2, "how-many-accounts", "dummy") is 2
end
18.2.6 Objects with Self-Reference
Until now, our objects have simply been packages of named functions
grouped together and hence given different, named entry-points. We’ve
seen that many of the features considered important in object systems
are actually simple patterns over functions and scope, and have indeed
been used—
One characteristic that actually distinguishes object systems is that each object is automatically equipped with a reference to the same object, often called self or this.I prefer this slightly dry way of putting it to the anthropomorphic “knows about itself” terminology often adopted by object advocates. Indeed, note that we have gotten this far into object system properties without ever needing to resort to anthropomorphism. Can we implement this easily?
18.2.6.1 Self-Reference Using Mutation
o-self =
block:
var self = "dummy"
self :=
mk-object(
[ mtd("first",
fun(v): msg(self, "second", v + 1);),
mtd("second",
fun(v): v + 1; )])
self
end
check: msg(o-self, "first", 5) is 7;
18.2.6.2 Self-Reference Without Mutation
o-self-no-state =
mk-object(
[ mtd("first",
fun(self, v): smsg(self, "second", v + 1);),
mtd("second",
fun(self, v): v + 1; )])
fun smsg(o, m, a): o(m)(o, a);
check: smsg(o-self-no-state, "first", 5) is 7;
18.2.7 Dynamic Dispatch
Finally, we should make sure our objects can handle a characteristic
attribute of object systems, which is the ability to invoke a method
without the caller having to know or decide which object will handle
the invocation. Suppose we have a binary tree data structure, where a
tree consists of either empty nodes or leaves that hold a value. In
traditional functions, we are forced to implement the equivalent some
form of conditional that exhaustively lists and selects between the
different kinds of trees. If the definition of a tree grows to
include new kinds of trees, each of these code fragments must be
modified. Dynamic dispatch solves this problem by making that
conditional branch disappear from the user’s program and instead be
handled by the method selection code built into the language.
The key feature that this provides is an extensible conditional.
This is one dimension of the extensibility that objects
provide.This property—
mt =
fun():
mk-object(
[ mtd("add",
fun(self, _): 0;) ])
end
node =
fun(v, l, r):
mk-object(
[ mtd("add",
fun(self, _):
v
+ smsg(l, "add", "dummy")
+ smsg(r, "add", "dummy");) ] )
end
a-tree =
node(10,
node(5, mt(), mt()),
node(15, node(6, mt(), mt()), mt()))
check: smsg(a-tree, "add", "dummy") is (10 + 5 + 15 + 6);
18.3 Member Access Design Space
Name is Static | Name is Computed | |
Fixed Set of Members | As in base Java. | As in Java with reflection to compute the name. |
Variable Set of Members | Difficult to envision (what use would it be?). | Most scripting languages. |
The lower-right quadrant corresponds closely with languages that use hash-tables to represent objects. Then the name is simply the index into the hash-table. Some languages carry this to an extreme and use the same representation even for numeric indices, thereby (for instance) conflating objects with dictionaries and even arrays. Even when the object only handles “member names”, this style of object creates significant difficulty for type-checking [REF] and is hence not automatically desirable.
Therefore, in the rest of this section, we will stick with “traditional” objects that have a fixed set of names and even static member name references (the top-left quadrant). Even then, we will find there is much, much more to study.
18.4 What (Goes In) Else?
So far, the “else clause” of method lookup (which is currently
implemented by mk-object)—
Let’s return to our model of desugared objects above. To implement inheritance, the object must be given “something” to which it can delegate method invocations that it does not recognize. A great deal will depend on what that “something” is.
| empty => raise("message not found: " + m)
Observe that the application parent-object(m) is like “half a msg”, just like an l-value was “half” a variable’s evaluation (Interpreting Variables). Is there any connection?
Let’s try this by extending our trees to implement another method, "size". We’ll write an “extension” (you may be tempted to say “sub-class”, but hold off for now!) for each node and mt to implement the size method. We intend these to extend the existing definitions of node and mt, so we’ll use the extension pattern described above.We’re not editing the existing definitions because that is supposed to be the whole point of object inheritance: to reuse code in a black-box fashion. This also means different parties, who do not know one another, can each extend the same base code. If they had to edit the base, first they have to find out about each other, and in addition, one might dislike the edits of the other. Inheritance is meant to sidestep these issues entirely.
18.4.1 Classes
node-size-ext =
fun(parent-object, v, l, r):
...
node-size-ext =
fun(parent-maker, v, l, r):
parent-object = parent-maker(v, l, r)
mk-ext-object(parent-object,
[ mtd("size",
fun(self, _):
1
+ smsg(l, "size", "dummy")
+ smsg(r, "size", "dummy");) ] )
end
fun node-size(v, l, r): node-size-ext(node, v, l, r);
Did you notice that instead of mk-object we’ve used mk-ext-object above? Do you see that it takes one extra parameter? Try to define it for yourself.
fun mk-ext-object(parent, n-vs):
fun(m):
fun lookup(locals):
cases (List) locals:
| empty => parent(m)
| link(f, r) =>
if f.name == m: f.value else: lookup(r);
end
end
lookup(n-vs)
end
end
mt-size-ext =
fun(parent-maker):
parent-object = parent-maker()
mk-ext-object(parent-object,
[ mtd("size",
fun(self, _): 0;) ])
end
fun mt-size(): mt-size-ext(mt);
a-tree-size =
node-size(10,
node-size(5, mt-size(), mt-size()),
node-size(15, node-size(6, mt-size(), mt-size()), mt-size()))
check:
smsg(a-tree-size, "add", "dummy") is (10 + 5 + 15 + 6)
smsg(a-tree-size, "size", "dummy") is 4
end
Earlier, we commented that chaining method-lookup to parents presumably bottoms out at some sort of “empty object”, which might look like this:
fun empty-object(m):
raise("message not found: " + m)
end
However, we haven’t needed to define or use this despite the use of mk-ext-object. Why is that, and how would you fix that?
class NodeSize extends Node { ... }
So why are we going out of the way to not call it a “class”?
When a developer invokes a Java class’s constructor, it in effect
constructs objects all the way up the inheritance chain (in practice,
a compiler might optimize this to require only one constructor
invocation and one object allocation). These are private copies of
the objects corresponding to the parent classes (private, that is,
up to the presence of static members). There is, however, a question
of how much of these objects is visible. Java chooses that—
In the implementation above, we have relied on the self-application semantics for recursive access to an object, rather than using state. The reason is because the behavior of inheritance would be subtly wrong if we used state naively, as we have shown above. Can you construct an example that illustrates this?
By examining values carefully, you will notice that the self reference is to the most refined object at all times. This demonstrates the other form of extensibility we get from traditional objects: extensible recursion. The extensible conditional can be viewed as free extension across “space”, namely, the different variants of data, whereas extensible recursion can be viewed as free extension across “time”, namely, the different extensions to the code. Nevertheless, as this paper points out, there’s no free lunch.
18.4.2 Prototypes
In our description above, we’ve supplied each class with a description of its parent class. Object construction then makes instances of each as it goes up the inheritance chain. There is another way to think of the parent: not as a class to be instantiated but, instead, directly as an object itself. Then all children with the same parent would observe the very same object, which means changes to it from one child object would be visible to another child. The shared parent object is known as a prototype.
The archetypal prototype-based language is
Self.
Though you may have read that languages like JavaScript are “based
on” Self, there is value to studying the idea from its source,
especially because Self presents these ideas in their purest form.
Some language designers have argued that prototypes are more primitive
than classes in that, with other basic mechanisms such as functions,
one can recover classes from prototypes—
Modify the inheritance pattern above to implement a Self-like, prototype-based language, instead of a class-based language. Because classes provide each object with distinct copies of their parent objects, a prototype-language might provide a clone operation to simplify creation of the operation that simulates classes atop prototypes.
18.4.3 Multiple Inheritance
Now you might ask, why is there only one fall-through option?
It’s easy to generalize this to there being many, which leads naturally
to multiple inheritance. In effect, we have multiple objects to
which we can chain the lookup, which of course raises the question of
what order in which we should do so. It would be bad enough if the
ascendants were arranged in a tree, because even a tree does not have
a canonical order of traversal: take just breadth-first and
depth-first traversal, for instance (each of which has compelling
uses). Worse, suppose a blob A extends B and C;
but now suppose B and C each extend
D.This infamous situation is called
diamond inheritance. If you choose to include multiple
inheritance in your language you can lose yourself for days in design
decisions on this. Because it is highly unlikely you will find a
canonical answer, your pain will have only begun. Now we have to
confront this question: will there be one or two D objects in
the instance of A? Having only one saves space and might
interact better with our expectations, but then, will we visit this
object once or twice? Visiting it twice should not make any
difference, so it seems unnecessary. But visiting it once means the
behavior of one of B or C might change. And so on. As
a result, virtually every multiple-inheritance language is accompanied
by a subtle algorithm merely to define the lookup order—
Multiple inheritance is only attractive until you’ve thought it through.
18.4.4 Super-Duper!
Many languages have a notion of super-invocations, i.e., the ability to invoke a method or access a field higher up in the inheritance chain.Note that I say “the” and “chain”. When we switch to multiple inheritance, these concepts are replaced with something much more complex. This includes doing so at the point of object construction, where there is often a requirement that all constructors be invoked, to make sure the object is properly defined.
We have become so accustomed to thinking of these calls as going “up” the chain that we may have forgotten to ask whether this is the most natural direction. Keep in mind that constructors and methods are expected to enforce invariants. Whom should we trust more: the super-class or the sub-class? One argument would say that the sub-class is most refined, so it has the most global view of the object. Conversely, each super-class has a vested interest in protecting its invariants against violation by ignorant sub-classes.
These are two fundamentally opposed views of what inheritance means. Going up the chain means we view the extension as replacing the parent. Going down the chain means we view the extension as refining the parent. Because we normally associate sub-classing with refinement, why do our languages choose the “wrong” order of calling? Some languages have, therefore, explored invocation in the downward direction by default.gbeta is a modern programming language that supports inner, as well as many other interesting features. It is also interesting to consider combining both directions.
18.4.5 Mixins and Traits
Let’s return to our “blobs”.
When we write a class in Java, what are we really defining between the opening and closing braces? It is not the entire class: that depends on the parent that it extends, and so on recursively. Rather, what we define inside the braces is a class extension. It only becomes a full-blown class because we also identify the parent class in the same place.
class C extends B { ... } |
classext E { ... } |
class C = E(B); |
class C1 = E(B1); |
class C2 = E(B2); |
Mixins make class definition more compositional. They provide many of the benefits of multiple-inheritance (reusing multiple fragments of functionality) but within the aegis of a single-inheritance language (i.e., no complicated rules about lookup order). Observe that when desugaring, it’s actually quite easy to add mixins to the language. A mixin is primarily a “function over classes’; because we have already determined how to desugar classes, and our target language for desugaring also has functions, and classes desugar to expressions that can be nested inside functions, it becomes almost trivial to implement a simple model of mixins.This is a case where the greater generality of the target language of desugaring can lead us to a better construct, if we reflect it back into the source language.
In a typed language, a good design for mixins can actually improve
object-oriented programming practice. Suppose we’re defining a
mixin-based version of Java. If a mixin is effectively a
class-to-class function, what is the “type” of this “function”?
Clearly, a mixin ought to use interfaces to describe what it
expects and provides. Java already enables (but does not require) the
latter, but it does not enable the former: a class (extension) extends
another class—
mixin M extends I { ... } |
A good design for mixins can go even further. A class can only be used once in an inheritance chain, by definition (if a class eventually referred back to itself, there would be a cycle in the inheritance chain, causing potential infinite loops). In contrast, when we compose functions, we have no qualms about using the same function twice (e.g.: (map ... (filter ... (map ...)))). Is there value to using a mixin twice?There certainly is! See sections 3 and 4 of Classes and Mixins.
Mixins solve an important problem that arises in the design of libraries. Suppose we have a dozen features that can be combined in different ways. How many classes should we provide? Furthermore, not all of these can be combined with each other. It is obviously impractical to generate the entire combinatorial explosion of classes. It would be better if the devleoper could pick and choose the features they care about, with some mechanism to prevent unreasonable combinations. This is precisely the problem that mixins solve: they provide the class extensions, which the developers can combine, in an interface-preserving way, to create just the classes they need.Mixins are used extensively in the Racket GUI library. For instance, color:text-mixin consumes basic text editor interfaces and implements the colored text editor interface. The latter is iself a basic text editor interface, so additional basic text mixins can be applied to the result.
How does your favorite object-oriented library solve this problem?
Mixins do have one limitation: they enforce a linearity of composition. This strictness is sometimes misplaced, because it puts a burden on programmers that may not be necessary. A generalization of mixins called traits says that instead of extending a single mixin, we can extend a set of them. Of course, the moment we extend more than one, we must again contend with potential name-clashes. Thus traits must be equipped with mechanisms for resolving name clashes, often in the form of some name-combination algebra. Traits thus offer a nice complement to mixins, enabling programmers to choose the mechanism that best fits their needs. A handful of languages, such as Racket, therefore provide both traits and mixins.