18.12 A More Efficient Implementation

< Free Open Study >

The tests above demonstrate that our implementation of classes matches the "open recursion" behavior of method calls through self in languages like Smalltalk, C++, and Java. However, we should note that the implementation is not entirely satisfactory from the point of view of efficiency. All the thunks we have inserted to make the fix calculation converge have the effect of postponing the calculation of the method tables of classes. In particular, note that all the calls to self inside method bodies have become (self unit)—that is, the methods of self are being recalculated on the fly every time we make a recursive call to one of them!

We can avoid all this recalculation by using reference cells instead of fixed points to "tie the knot" in the class hierarchy when we build objects.^[4] Instead of abstracting classes on a record of methods called self that will be constructed later using fix, we abstract on a reference to a record of methods, and allocate this record first. That is, we instantiate a class by first allocating a heap cell for its methods (initialized with a dummy value), then constructing the real methods (passing them a pointer to this heap cell, which they can use to make recursive calls), and finally back-patching the cell to contain the real methods. For example, here is setCounterClass again.

   setCounterClass =     λr:CounterRep. λself: Ref SetCounter.       {get = λ_:Unit. !(r.x),        set = λi:Nat. r.x:=i,        inc = λ_:Unit. (!self).set (succ ((!self).get unit))}; ▸ setCounterClass : CounterRep → (Ref SetCounter) → SetCounter

The self parameter is a pointer to the cell that contains the methods of the current object. When setCounterClass is called, this cell is initialized with a dummy value:

   dummySetCounter =     {get = λ_:Unit. 0,      set = λi:Nat.  unit,      inc = λ_:Unit. unit}; ▸ dummySetCounter : SetCounter   newSetCounter =     λ_:Unit.       let r = {x=ref 1} in       let cAux = ref dummySetCounter in       (cAux := (setCounterClass r cAux); !cAux); ▸ newSetCounter : Unit → SetCounter

However, since all of the dereference operations (!self) are protected by lambda-abstractions, the cell will not actually be dereferenced until after it has been back-patched by newSetCounter.

To support building subclasses of setCounterClass, we need to make one further refinement in its type. Each class expects its self parameter to have the same type as the record of methods that it constructs. That is, if we define a subclass of instrumented counters, then the self parameter of this class will be a pointer to a record of instrumented counter methods. But, as we saw in §15.5, the types Ref SetCounter and Ref InstrCounter are incompatible—it is unsound to promote the latter to the former. This will lead to trouble (i.e., a parameter type mismatch) when we try to create super in the definition of instrCounterClass.

   instrCounterClass =     λr:InstrCounterRep. λself: Ref InstrCounter.     let super = setCounterClass r self in     {get = super.get,      set = λi:Nat. (r.a:=succ(!(r.a)); super.set i),      inc = super.inc,      accesses = λ_:Unit. !(r.a)}; ▸ Error: parameter type mismatch

The way out of this difficulty is to replace the Ref constructor in the type of self by Source—i.e., to pass to the class just the capability to read from the method pointer, not the capability to write to it (which it does not need anyway). As we saw in §15.5, Source permits covariant subtyping—i.e., we have Ref InstrCounter <: Ref SetCounter—so the creation of super in instrCounterClass becomes well typed.

   setCounterClass =     λr:CounterRep. λself: Source SetCounter.       {get = λ_:Unit. !(r.x),        set = λi:Nat. r.x:=i,        inc = λ_:Unit. (!self).set (succ ((!self).get unit))}; ▸ setCounterClass : CounterRep → (Source SetCounter) → SetCounter   instrCounterClass =     λr:InstrCounterRep. λself: Source InstrCounter.     let super = setCounterClass r self in     {get = super.get,      set = λi:Nat. (r.a:=succ(!(r.a)); super.set i),      inc = super.inc,      accesses = λ_:Unit. !(r.a)}; ▸ instrCounterClass : InstrCounterRep →                       (Source InstrCounter) → InstrCounter

To build an instrumented counter object, we first define a dummy collection of instrumented counter methods, as before, to serve as the initial value of the self pointer.

   dummyInstrCounter =     {get = λ_:Unit. 0,      set = λi:Nat.  unit,      inc = λ_:Unit. unit,      accesses = λ_:Unit. 0}; ▸ dummyInstrCounter : InstrCounter

We then create an object by allocating heap space for the instance variables and methods, calling instrCounterClass to construct the actual methods, and back-patching the reference cell.

   newInstrCounter =     λ_:Unit.       let r = {x=ref 1, a=ref 0} in       let cAux = ref dummyInstrCounter in       (cAux := (instrCounterClass r cAux); !cAux); ▸ newInstrCounter : Unit → InstrCounter

The code for constructing the method table (in instrCounterClass and counterClass) is now called once per object creation, rather than once per method invocation. This achieves what we set out to do, but it is still not quite as efficient as we might wish: after all the method table that we construct for each instrumented counter object is always exactly the same, so it would seem we should be able to compute this method table just once, when the class is defined, and never again. We will see in Chapter 27 how this can be accomplished using the bounded quantification introduced in Chapter 26.

^[4]This is essentially the same idea as we used in the solution to Exercise 13.5.8. I am grateful to James Riely for the insight that it can be applied to class construction by exploiting the covariance of Source types.

< Free Open Study >