Overview of Objects We don't have time to go into too many details regarding the design, implementation, and tradeoffs of OO languages, so we'll only hit the high-level details: To a first approximation, an object is a record consisting of some local state (the instance variables) and some methods that operate on that state. For example, we might define a point object as: let val x = ref 1.24 val y = ref 3.21 fun move_x (i:real) = x := (!x) + i fun move_y (i:real) = y := (!y) + i in { x = x, y = y, move_x = move_x, move_y = move_y } end The resulting value will have type: { x:real ref, y:real ref, move_x:real->unit, move_y:real->unit } Often, we want to hide some portions of the object's state or leave some methods as internal. In languages such as Java, this is accomplished by making the variables or methods private. For our encoding above, we would just omit them from the record. For example: let val x = ref 1.24 val y = ref 3.21 fun move_x (i:real) = x := (!x) + i fun move_y (i:real) = y := (!y) + i in { move_x, move_y } end Now the only way to get to the x and y components is via the methods. The primary advantage of hiding these components and only exporting methods is that we retain control over the state (and the invariants) associated with an object. This sort of encapsulation is the key to OO programming. For instnce, if I changed to a polar representation, you couldn't tell, and indeed, I can easily mix and match polar and cartesian points (e.g., have a list of points, some of which are cartesian and some of which are polar.) Note that the environments for move_x and move_y contain pointers to the x and y reference cells. They are *encapsulated* within the closures of the functions. So, as a pointer graph, we get something that looks like this: +-----------------------------------+ ---->| move_x closure | move_y closure | +---------|----------------|--------+ | | V V +---------------------+ +-------------------+ | move_x code | env | | env | move_y code | +-----------------\---+ +--/----------------+ \ / \ / +------------------+ | x | y | +------------------+ In Java (or C#) you get a slightly different organization that looks more like this: +------------------------------------+ ---->| vtable | x | y | +----|-------------------------------+ | V +-----------------------------------+ | code for move_x | code for move_y | +-----------------------------------+ Furthermore, the move_x and move_y methods are passed a "self" reference as an implicit extra argument. (Note that the move_x and move_y closures above are passed the environment as an extra argument. So they're quite similar.) Notice that so far, I haven't said anything about classes. That's because classes are completely separable from objects and indeed, some OO languages (e.g., Cecil and Self) are not class based. Suppose we wanted to write a function to create new point objects. We might write: fun new_point(x:real, y:real) = let val x = ref x val y = ref y fun move_x (i:real) = x := (!x) + i fun move_y (i:real) = y := (!y) + i in { move_x = move_x, move_y = move_y } end Here, new_point is a constructor -- something that builds an object. As an alternative, we might provide a primitive to copy a given object (e.g., clone). Prototype-based languages are usually based on this latter concept -- create one prototype for objects, clone it as needed, and then update the copy to get a "new" object. When you clone, there is an issue as to whether you should do a deep clone or not. Another hallmark of most OO languages (at least the statically typed ones) is subtyping. As we discussed earlier, it's sensible to treat a record with more components as a subtype of a record with fewer components. So, if we have: fun new_3dpoint(x:real,y:real,z:real) = let val x = ref x val y = ref y val z = ref z fun move_x (i:real) = x := (!x) + i fun move_y (i:real) = y := (!y) + i fun move_z (i:real) = z := (!z) + i in { move_x = move_x, move_y = move_y, move_z = move_z } end we could hope to use a 3dpoint whereever we were expecting a 2d-point. That's because if we only expect a 2dpoint, then we can only call the move_x or move_y methods, both of which are provided by 3dpoint. Note that, once again, we haven't said anything about classes yet. Key point: subtyping and subclassing are different concepts that happen to get confused in most languages (e.g., Java, C++, C#.) Now, often it's the case that we want to share the code for different groups of objects. This is where classes come in. They're a way to factor out common definitions among object constructors. For example, we might define: fun new_point(x:real, y:real) = let val x = ref x val y = ref y fun move_x (i:real) = x := (!x) + i fun move_y (i:real) = y := (!y) + i in { move_x = move_x, move_y = move_y } end fun new_3dpoint(x:real, y:real, z:real) = let val {move_x = mx, move_y = my} = new_point(x,y) val z = ref z fun move_z(i:real) = z := (!z) + i in {move_x, move_y, move_z} end What we really want is a way to conveniently build new constructors for objects out of old ones. In particular, we would like to be able to extend a constructor so that it adds new instance variables and new operations as in the example above. This is part of what classes do. For example: class Point { double x; double y; void move_x(i:double) { x = x + i; } void move_y(i:double) { y = y + i; } void Point(x:double, y:double) { this.x = x; this.y = y; } } class Point3D extends Point { double z; void move_z(i:double) { z = z + i; } void Point3D(x:double, y:double, z:double) { this.x = x; this.y = y; this.z = z; } } When we write class C1 extends C2, we really mean (almost) to cut and paste the definitions of the instance variables and methods for C1 into C2. So the Point3D is essentially the same as: class Point3D { double x; double y; double z; void move_x(i:double) { x = x + i; } void move_y(i:double) { y = y + i; } void move_z(i:double) { z = z + i; } void Point3D(x:double, y:double, z:double) { this.x = x; this.y = y; this.z = z; } } Now, if all you ever did was extend a class, then you'd be ensured that the objects generated by a sub-class would have types that are sub-types of the type of the objects generated by the super-class. This leads to a lot of code-reuse, and makes it genuinely easy to extend a system with new kinds of data. Sadly, the situation is a little more subtle than this for three or more reasons. First, remember that every method takes an implicit extra argument (self) of the class's type. So, the move_x in Point3D takes a Point3D as an argument, whereas the move_x in Point takes a Point2D as an argument. What's the rule for sub-typing on functions? Uh oh. Second, there's the issue of multiple inheritance. With the description above, it seems perfectly sensible to inherit from two different classes -- just cut and paste their definitions. But two problems arise with this. One is an implementation problem: How do you lay out the vtable and instance variables? Each of the super-classes expects that *its* stuff comes first and any extensions are at the end. The other problem is that both super-classes may define the same instance variable or method. Which one do you use? And what if the other methods call that method? It's a mess (which is part of the reason C++ is a mess.) So, the usual answer is to rule out multiple-inheritance as being too complicated. Of course, this really forces you to design things in a strict hierarchical fashion which fits some things, but not others. Note that if you follow the "objects are just records" and use record subtyping, you naturally get multiple super-types. So, that solves half the problem. You can use the object anywhere any of the super types are expected. And that's what Java and C# accomplish with interfaces. If you really want to get reusable code in Java, you should ignore classes and focus on interfaces. The problem is that interfaces are slightly more expensive to use (for the same reason that providing general subtyping on records is hard). Oh well. The third problem is that you can do more than just *extend* with a sub-class. You can also override a definition. In languages such as Java, you can only override a method (not an instance variable). For instance, we could define: class C { void m1() { putline("hello!"); } void m2() { m1(); putline("goodbye!"); } } class D extends C { void m1() { putline("ciao!"); } } Now if we create a D object and call its m2, we get "ciao!\ngoodbye!\n" instead of "hello!\ngoodbye!\n". Again, we can think of declaring a sub-class as copying the super-classes definition, but throwing away those methods that are re-defined (overridden) in the second class. Overriding is a mixed blessing. You can do some wonderful things with it, but it leads to real speghetti code in terms of control transfers. You really have to think about how code bounces around, going back and forth between super and sub-class definitions. Now, the rules for overriding in Java prevent you from changing the types of the method, even though it's possible to do so (contra/covariant, remember?) And, Java doesn't really allow you to override instance variables (though you can shadow them.) It's all very confusing, but you can get used to it. There are other issues that arise in class-based languages, such as the "fragile base class" phenomenon. The problem is that you might want to add an instance variable/method to a base class, but it may conflict with an already defined by sub-classes. In general, classes are not all that compositional in the sense that minor perturbations cause lots of headaches. Furthermore, we'd all be better off if classes could be divorced from types. Some more recent languages (e.g., Moby) attempt to do this. But programmers today seem brainwashed into thinking class == type and so sub-class == sub-type. One way to think about a class is that it's a set of open definitions where "self" has not yet been resolved. For instance, we can think of the Point class as having components with types: val x : real ref val y : real ref val move_x : (self: ?) -> (i:real) -> unit val move_y : (self: ?) -> (i:real) -> unit Let us write this as a parameterized type definition: type 'self PointClass = { x : real ref, y : real ref, move_x : 'self -> real -> unit, move_y : 'self -> real -> unit } Then Point3D would look similar: type 'self Point3DClass = { x : real ref, y : real ref, y : real ref, move_x : 'self -> real -> unit, move_y : 'self -> real -> unit, move_z : 'self -> real -> unit } and we could build a Point3DClass out of a PointClass. Now when we create a Point object using the PointClass definition, we tie off the free type variable 'self using a recursive type: type point = point PointClass type point3d = point3d PointClass So, classes are underdetermined until you instantiate them to get an object out. At that point, we tie the knot using a fixed point operator. This knot-tying has to be delayed because of the semantics of "self". So, the semantics of class-based languages is far from easy. Some of these issues are compounded when you start to add parameterized (aka generic or polymorphic) classes and methods to a language like Java or C#. For instance, we might like LinkedList to be a sub-type of DoublyLinkedList but this is not valid since the components of the list are mutable. Many of the design tradeoffs incorporated in generic additions for Java and C# can only be understood by compiling them down to a lambda-calculus-based framework where the typing rules are relatively simple, and establishing soundness is relatively straightforward. But it leads to a lot of incomprehensible restrictions at the source level...