Recursive Records and Instance Variable Initialization

In Subtleties of Instance Variable Initialization we looked at the curious difficulty in initializing instance variables defined in terms of each other. If in reading that you felt some flicker of recognition when we talked about call-by-value versus call-by-name, you may be on the right track to connecting this all together. In this post we'll trace this difficulty all the way down to the divergence of the fixed point operator in non-function fields of recursive records in call-by-value languages. Are you up for it? Then you're the CS equivalent of a hard-core spelunker. Let's go, you're responsible for your own safety.

Review of the Problem

The problem is how a language implementer provides instance variable initialization, giving an initialization expression when a field is declared, when the expressions can refer to other instance variables of the same object. How do you sort out the "bootstrap" dependence graph, or do you? If not, what's your algorithm for the constructor? It turns out this is more or less the same question as how to encode the fixed point operator on records.

This Javascript program illustrates the use case:

// Construct an object with two different orderings depending on its argument
function DynamicDependence(state)
{
 return {
   x : (state? 1 : this.y-1),
   y : (state? this.x+1 : 2)
 }
}
var dd = new DynamicDependence(true)
document.write('x='+dd.x+' y='+dd.y+'<br/>')
var dd2 = new DynamicDependence(false)
document.write('x='+dd2.x+' y='+dd2.y+'<br/>')

You'll get this output:

x=1 y=NaN
x=NaN y=2

A note about terminology. The {x : expr, ...} is Javascript syntax for an "associative array", but that is basically identical to the notion of a "record" in a lot of the academic literature on programming languages. When we say record here, we mean something close to the Javascript meaning, which generalizes to the way objects can be viewed in every object-oriented language I've seen. Whether the fields are ordered are not, syntactic details about how to access fields, and some other aspects, are unimportant to this discussion.

Possible Solutions

Of course with the Javascript example, or in Ruby or most languages, the programmer could control the ordering by writing the constructor with explicit assignments (this.x=1; this.y=this.x+1), but that goes outside the problem being addressed. If we allow instance variable initialization at all, what happens with references to other instance variables? How are they treated? As an example solution, in Javascript, the algorithm appears to be as follows:

1. Allocate (associative array) object, call it "this".
2. Evaluate initialization expressions, store them aside.
   References to fields in this are undefined.
3. Bind the evaluated expressions to the "this."
   After this point, references to instance variables work with the given initial values.

The Java constructor algorithm appears to be something more like this:

1. Allocate object, call it "this".
2. Initialize each field to its native type
   (Object initialized to null, int to 0, boolean to false, etc.).
3. For each declared field, in order they're declared:
   Evaluate the initializer expression and assign it

As we saw with the BreakJava example in the previous post, forward references are prevented by the compiler, so typical programs that compiled won't have forward references, but it's possible there still are some via method calls, and in that case the reference will get the value from step 2, the default value for its core Java type.

These are some ways to deal with the problem, but let's dig a little deeper and see where the problem comes from in the first place.

This is the Crux of the Problem

In all these examples, notice the problem comes about because of dependences between instance variables. Did you ever wonder how you can even express that dependence?

It all has to do with the magical this variable (also known as self in Smalltalk et. al). And this is none other than the implicit argument to the function you pass to the fixed point operator (known in connection with its most famous embodiment, the Y Combinator).

Yep - every class definition in every object language out there is implicitly wrapped in an expression, something like:
fix (λ this . { ERROR=1, WARN=2, DEBUG=3, level=this.DEBUG })

"What the...?" You're thinking. "I thought the fixed point operator was only for functions." The snarky answer to that is "everything is a function" (see Church encoding). But really, from the fixed point on functions to records is not a far leap.

How to Think About Recursive Records

The way to think about the fixed point operator on a record (object)
is similar to how we think about it for functions.

The way we think about it for functions,
is that you start with a recursive function:

function fact(n) {
 return (n<2)? 1 : fact(n-1)
}

but you
1. make it anonymous
2. wrap it in another function, and
3. replace the recursive call with the name of the outer function's argument:

function(self) {
 function(n) { return (n<2)? 1 : self(n-1) }
}

(I've used self instead of this since I'm giving Javascript code and want to avoid confusion.)

The fix operator will take your function and return a function that has the effect of the original recursive definition.

The way to think about the fixed point operator on a record (object)
is that we write a recursive record
(referring to the record itself as this or self)
but we
1. make it anonymous,
2. wrap it in another function, and
3. replace the "recursive" reference
with the name of the outer function's argument:

newobj = function(self) { return { DEBUG : 3, level : self.DEBUG } }

We pass it to fix, and it returns the a record having the same effect as the desired recursive definition:

{ DEBUG : 3, level : this.DEBUG }

The funny thing about this: what stops the recursion?

The Problem with Recursive Records

As alluded to last time, we run into problems initializing instance variables for two reasons: (1) when there are dependent expressions ({x=1, y=this.x+1}) and (2) when the language uses the near-universal call-by-value evaluation strategy. Now we can clearly see that the dependence comes from the recursive reference, i.e. the reference to this.

When you think about recursive functions, you typically don't write them with direct recursion:

function killit() {
 return killit()
}

That would typically be stupid. (There are cases where you want infinite recursion, as with server loops, but those generally call an operating system function that effectively does the busy waiting in hardware.) Instead, the recursive call is nearly always inside an if statement:

function loop(n) {
 if (n<1)
   return true
 else
   return loop(n-1)
}

And guess what -- in order to be effective, if statements in every call-by-value language are in effect special functions that use call-by-name evaluation. In other words, the if "function" doesn't evaluate both the if case and the else case (every normal function evaluates all its arguments before executing the function body), but only the one that it "needs" to evaluate, based on the test expression.

But with recursive records, I think what we're effectively asking with cases like
{ x : 1, y : this.x } is to eagerly evaluate the value of this in the act of computing what this is supposed to be, just the same as killit above wants the value of killit. We say the derivation of these fixed points diverges, or fails to converge to the fixed point.

Fixed Point for Records

In Ila, I had to actually implement the fix operator for records to support the mutual recursion between record fields at all: the typical case where methods can call each other. And as with Javascript, Java, Ruby and others, initializing instance variables is done at your own risk, and happens to work if the fix operator evaluates fields in the proper order. The approach taken there was this:

public static Object fix__rec =
 // fix : (T->T) -> T
 new Ila_Lambda_OO()
 {
   public Object applyOO(Object f)
   {
     return new FixedRecord((Ila_Lambda_OO)f);
   }
 };

where the FixedRecord constructor was like this:

public FixedRecord(LAO__OZ f)
{
 super();
 m_creationFn = f;
 Ila_Record temp = (Ila_Record)f.applyOO(this);
 this.copyFields(temp);
}

The two key lines are the f.applyOO(this) and the this.copyFields(temp). We evaluate the given function, passing it the Java object reference for the new object which will be recursive by the time we get done with it. The given function returns a record, where recursive definitions have been bound to the recursive record we will return. The problem is that this record returned from the function is not itself the recursive record. We then simply copy each field in the record back to the recursive record:

public Ila_Record copyFields(Ila_Record src)
{
 Enumeration en = src.keys();
 while(en.hasMoreElements())
 {
   Object key = en.nextElement();
   this.put(key,src.get(key));
 }
 return this;
}

---

While I've seen this area discussed in academic circles (e.g. in connection with Didier Rémy and OCAML), for some reason I've never seen this topic addressed in more mainstream programming language forums.