You knew I'd say something, Part III

Earlier I said that tail recursion allows a program access to a more powerful computation model. I'm referring to Hewitt's Actor model. At its core, the Actor model is extremely simple. Computation agents called ‘Actors’ interact only through message-passing. The full Actor model allows for multiple asynchronous agents, each acting independently. On a single processor computer, it can be much more convenient to use a synchronous, serial Actor model in which only one Actor at a time is running and control of the processing is passed along with the messages.

One important feature of the Actor model is that messages are unidirectional. When an actor sends a message it does not require a reply as part of the protocol. If the actor needs a reply or wishes to handle a reply, it sets up a callback. The callback can have a well-known name that any actor can use in a message, or it can be an unnamed piece of code (a lambda expression) that shares the context of the sender.

Since messages are unidirectional, they don't require a ‘return address’. The message may have a return address as part of a callback, but that's a protocol decision, it isn't built-in to the message itself. The recipient of the message might simply ignore the callback (it is allowed to).

The recipient of a message can pretty much do anything it wants. Of course we expect the program to be written such that something useful happens, but the recipient of a message is allowed to do things like

• compute something
• change its state
• send a message
• create new actors

Or any combination of the above. For example, upon receiving a message, an actor could compute something based on the message contents, create a new actor, and resend the message (with the newly computed value) on to the newly created actor. This kind of arbitrary delegation is a key feature of the actor model. Once a message is sent, the sender is completely out of the picture (although he could put his return address in a callback). The message recipient is allowed to delegate all or any part of its action to other actors. Control structure emerges from the patterns of message passing.

Function calling = message passing (almost)

A procedure is like an actor. Nothing happens until you invoke it (send it a message), it can compute something, change its state (if it is a closure or has access to something mutable), and call other procedures (create new actors and send them messages). But a procedure will be a limited form of actor if it cannot fully delegate its computation to another procedure.

In virtually every computer language, a procedure call has an implicit continuation (informally, the caller). ‘Returning a value’ is ‘invoking the continuation’. Whether a procedure can fully delegate to another depends on how the language manages the implicit continuation. If the language supports proper tail recursion, then when a procedure tail calls another, the implicit continuation is passed directly along to the callee. If the language does not support proper tail recursion, then the implicit continuation is not passed to the callee. Instead, a new implicit continuation is allocated that contains (wraps around) the old one. The wrapper doesn't actually do anything in the tail call situation, it just takes up space and possibly retains pointers to reclaimable storage, but you can't get rid of it because it is built in to the language.

If you cannot pass the implicit continuation on to the callee, then you cannot fully delegate the computation. If you cannot fully delegate, then you cannot fully model message passing with function calls. On the other hand, if you can fully delegate, then a function call is exactly the same passing a message (in our synchronous, serial actor model).

Tail recursion unifies message passing and function calling. This is the reason tail recursion is cool. The fact that this allows you to write a loop as a tail call is sort of a side benefit. (It directly follows because all control structure can be modeled as message passing, but as I mentioned repeatedly, I have nothing against looping constructs per se.)

With tail recursion, you have message passing embedded in your language. By embedded I mean that you don't have to directly manipulate message objects and inject and extract values from them. That happens automatically as part of the function call syntax.

Without tail recursion, you have to implement message passing as a separate, ‘bolted on’, feature. You will have explicit message objects to allocate, initialize, enqueue, poll for, destructure, and deallocate. The control structure that emerges from the message passing patterns will interfere with the control structure in your code (you'll have to structure all your code around the ‘driver loop’).

Interlude

Part III is coming, but I wanted to make an observation. As I've been writing stuff, I've been poring over a lot of code looking for examples and counter-examples of ideas I want to talk about. Since I've been talking about tail recursion, I've been looking in particular at procedures that return answers that are computed by other procedures. It's fairly easy to find these things — you just look for a return statement immediately followed by a function call: return<whitespace+><identifier><whitespace*> (. This doesn't match perfectly, but it gets more than enough results to look at. In looking at several examples of code I've noticed a common pattern like this:

    ...
    Type foo = computeFoo (a, b);
    return foo;
}

This isn't a tail recursive call, but it is trivially transformed into one. Then I was thinking that I wouldn't write code like that. (At least I don't think I would.) It's like writing this in Scheme:

    (let ((foo (compute-foo a b)))
       foo)

Which is simply syntactic sugar for this:

    ((lambda (foo) foo) (compute-foo a b))

Which trivially beta-reduces. That first term is better known as the identity function, so I could have just written:

    (id (compute-foo a b))

instead of the let expression, but why would I even bother? So this code:

    ...
    Type foo = computeFoo (a, b);
    return foo;
}

is really a verbose way of writing this:

    ...
    return Identity<Type> (computeFoo (a, b));
}

which no sane person would prefer to

    ...
    return computeFoo (a, b);
}

Yet there are apparently reasonably sane people who seem to prefer the first version. (caveat here: I'm assuming that the Identity function is being called for value and that this is not an obscure means of forcing a type coercion. In all the code I've looked at, I haven't seen anything that nasty, but it wouldn't surprise me. I'm not talking about obscure compiler tricks.)

You knew I'd say something (Part II)

Part II
van Rossum writes:

Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)

If this were true, I'd be far, far less concerned about the issue. Sure, a lot of tail recursion really is just looping, and it isn't such a big deal to use a loop. In fact, a loop may be a better construct in many situations. This particular use of tail recursion is not the interesting case.

It is difficult to find a compelling example of code that demonstrates why interprocedural tail recursion is useful. You won't find many examples taken from languages that don't support tail recursion; they are either too small to cause a problem, or the author used some sort of workaround to avoid the space issues. Examples taken from languages that do support tail recursion will inevitably be dismissed as unrealistic and artificial, or particular to Scheme, or simply irrational (‘No real program would ever be written that way. Maybe a Scheme programmer would think in such a way, but...’)

The difficulty is in finding a program that is big enough to illustrate the problem, small enough to post in a blog, easy enough to understand, but complex enough to suggest what problems would occur in the real world.

Continuation passing style needs proper tail recursion to be useful on anything but small problems, but it is a very complex technique which makes it hard to illustrate succinctly. Several people have suggested implementing a state machine through tail calls. I like this technique, but there are so many ways of implementing state machines that someone is bound to claim that the problem is artificial.

Here's an example that I think will be persuasive.

Consider the Visitor Pattern. This is a technique that allows you to abstract away the details of a data structure and the method of traversing it from the algorithm that operates on the data. It is commonly found in object-oriented languages like Java.

In this Python code we implement a binary tree and we provide a means to traverse it with the Visitor Pattern. To make things a bit more interesting, we also implement a DelegateNode class that acts like a Node by delegating the method calls. In this example we pass an accumulator variable with the visitor. We can use the accumulator to collect information about the tree.

import math, random, sys, traceback

class Node:
  def __init__(self, left, right):
      self.left = left
      self.right = right

  def accept(self, visitor, accum):
    return visitor.visitNode (self.left, self.right, accum)


class Leaf:
  def __init__(self, value):
    self.value = value

  def accept(self, visitor, accum):
    return visitor.visitLeaf(self.value, accum)


class DelegateNode(Node):
  def __init__(self, originalNode):
    self.originalNode = originalNode

  def accept(self, visitor, accum):
    return self.originalNode.accept(visitor, accum)

# Generate a tree for us to visit.
def GenerateTree(n):
  if n <= 0:
    return Leaf (1)
  else:
    return DelegateNode (Node(GenerateTree(int(math.sqrt(float(n))) - 1),
                              GenerateTree(n - 1)))

Now remember that this is a toy example. A real example would have several kinds of nodes and the nodes would have some interesting functionality and we'd do something more than just traverse them. The important point is this is a simplified version of some code we might actually encounter in a real-world problem.

So let's traverse the tree and count the different kinds of nodes. First we need a Visitor that can do that:

class TreeCountingVisitor:
  def visitNode (self, left, right, accum):
    return right.accept (self, left.accept (self, [accum[0] + 1, accum[1]]))

  def visitLeaf (self, value, accum):
    return [accum[0], accum[1] + 1]

The accumulator is a two-tuple. The first element is the number of nodes, the second element is the number of leaves. When we visit a leaf, we return a new tuple with the leaf count bumped by 1. When we visit a node, we bump the node count by 1 before traversing the left branch. Since the visitor returns an updated accumulator, we pass that in when we traverse the right branch.

And our main function to try this out. We'll start with a small tree and see how it scales.

if __name__=="__main__":

  for i in range(25,1000,25):
    print "Generating tree " + str(i)
    testTree = GenerateTree(i)
    print "Testing"
    total = testTree.accept(TreeCountingVisitor(), [0,0])
    print "Total is " + str(total)

On my machine, this runs out of stack at about 350.

Can the tail recursion in this be easily replaced by a loop? It depends on what you mean by easy. Certainly we could write a looping program that traverses the tree without using the Visitor pattern, and it wouldn't take long at all. But in a real-world situation, this may not be so easy. If the Visitor pattern is the ‘advertised’ API, we'd be deliberately bypassing an important abstraction. Another developer could change a node or add a new node type and provide the appropriate Visitor API, but if we weren't using the Visitor pattern, we'd be out of luck.

Assuming we want to organize our code around the Visitor pattern, it becomes much harder to replace the recursion with a loop.

Part III in a day or two...

You knew I'd say something.

In a recent blog post, Guido van Rossum gave his rationale for not wanting tail recursion in Python. From the nature of his arguments, it seems he has several misconceptions about tail recursion. I have to admit spending a bit of time thinking up snarky remarks, but I found that some friends of mine — programmers that I respect a great deal — shared some of these misconceptions. I already know I'm not going to change van Rossum's mind, and I'm preaching to the choir for most of the people who read this, but maybe I can clear up these misconceptions for one or two people.

Will Clinger's paper Proper tail recursion and space efficiency in the Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, June 1998, pages 174-185, is the best reference I've found on the topic.

First of all, let's be clear about what ‘proper tail recursion’ is. Clinger defines it this way:

The essence of proper tail recursion is that a procedure can return by performing a tail call to any procedure, incuding itself.

It is important to recognize that we're not just talking about loops written in tail-recursive style, but any procedure that (tail) calls another in order to compute the return value.

It is a common misconception that tail recursion is primarily a syntactic sleight-of-hand that allows a programmer to use a function call rather than a traditional iteration construct. A Scheme programmer might write this:

(define (factorial x)
  (define (fact-iter n answer)
    (if (> n x)
        answer
        (fact-iter (+ n 1) (* answer n))))
  (fact-iter 1 1))

Where a more traditional formulation is this:

int factorial (int x)
{
    int answer = 1;
    for (int n = 1; n <= x; n++)
      answer *= n;
    return answer;
}

The Scheme programmer relies on the compiler to recognize that the recursive call to fact-iter is intended to be a loop. He expects that the code will compile to something very close to the traditional formulation. The MIT-Scheme compiler generates this code:

;; Note: some instructions have been omitted for clarity
;; (tagging, interrupt polling, etc.)
fact-iter-3:
        ;; (assign (register #x10) (offset (register 4) (machine-constant 0)))
        (mov w (r 0) (@r 4))
        ;; (assign (register #x12) (offset (register 4) (machine-constant 2)))
        (mov w (r 1) (@ro b 4 8))
        ;; (fixnum-pred-2-args greater-than-fixnum? (register #x11) (register #x13))
        (cmp w (r 0) (r 1))
        (jg (@pcr label-6))

        ;; (assign (register #x15) (offset (register 4) (machine-constant 1)))
        (mov w (r 1) (@ro b 4 4))

        ;; (assign (register #x19) (fixnum-2-args multiply-fixnum (register #x16) (register #x11) #f))
        (imul w (r 1) (r 0))

        ;; (assign (offset (register 4) (machine-constant 1)) (register #x14))
        (mov w (@ro b 4 4) (r 1))
        ;; (assign (register #x1d) (fixnum-1-arg one-plus-fixnum (register #x11) #f))
        (add w (r 0) (& #x5a))

        ;; (assign (offset (register 4) (machine-constant 0)) (register #x1a))
        (mov w (@r 4) (r 0))
        ;; (invocation:jump 2 #f fact-iter-3)
        (jmp (@pcr fact-iter-3))

As you can see, the compiler dutifully turned it into a loop.

Not everyone is aware that this works across procedure boundaries.

(define (even? x)
  (if (= x 0)
      #t
      (odd? (- x 1))))

(define (odd? x)
  (even? (- x 1)))
Yeah, I blew it here by forgetting to test for
a base case.  But the conditional wasn't the interesting part anyway.

;; Note: some instructions have been omitted for clarity
;;
even?-2:
        ;; (assign (register #x10) (offset (register 4) (machine-constant 0)))
        (mov w (r 0) (@r 4))
        ;; (eq-test (register #x10) (constant 0))
        (cmp w (r 0) (&u #x68000000))
        (je (@pcr label-4))
        ;; (lap-opt fixnum-add-const-in-place)
        ;; (assign (register #x14) (object->fixnum (register #x10)))
        ;; (assign (register #x15) (fixnum-1-arg minus-one-plus-fixnum (register #x14) #f))
        ;; (assign (register #x12) (fixnum->object (register #x15)))
        (add w (r 0) (& #x3ffffff))
        (and w (r 0) (& #x6bffffff))
        ;; (assign (offset (register 4) (machine-constant 0)) (register #x12))
        (mov w (@r 4) (r 0))
        ;; (invocation:uuo-link 2 #f odd?)
        (jmp odd?-1)
label-4:
        ;; (assign (offset (register 6) (machine-constant 2)) (constant #t))
        (mov w (@ro b 6 8) (&u #x20000000))
        ;; (pop-return)
        (return)

odd?-1:
        ;; (assign (register #x11) (offset (register 4) (machine-constant 0)))
        (mov w (r 0) (@r 4))
        ;; (lap-opt fixnum-add-const-in-place)
        ;; (assign (register #x12) (object->fixnum (register #x11)))
        ;; (assign (register #x13) (fixnum-1-arg minus-one-plus-fixnum (register #x12) #f))
        ;; (assign (register #x10) (fixnum->object (register #x13)))
        (add w (r 0) (& #x3ffffff))
        (and w (r 0) (& #x6bffffff))
        ;; (assign (offset (register 4) (machine-constant 0)) (register #x10))
        (mov w (@r 4) (r 0))
        ;; (invocation:uuo-link 2 #f even?)
        (jmp even?-2)

And people have pointed out that this may be surprising and baffling to someone who expects to see the history of the computation laid out on the stack.

Scheme programmers make a big deal out of this. They point out that with proper tail recursion, Scheme doesn't need looping constructs like while or for or do because the user can write them himself. But Scheme hackers are a fringe group of the archetypical fringe group: Lisp hackers. They enjoy removing features from the language that they consider ‘unnecessary’. Then they write papers that somehow ‘prove’ that this is better. Of course these academic papers contain an awful lot of math and not very many actual programs.

In fact, Scheme programmers will try to sneak tail recusion into other programming languages. There's hardly a point to doing so because other languages have loops already. But now you get programs written by wet-behind-the-ears neophytes that use tail recursion rather than something more obvious. Furthemore, you cannot debug this code because the tail recursion has erased the backtrace.

And what does this buy you? In theory, when you exit a procedure with a tail-recursive call, you can replace the call/return instruction pair with a jump. In theory, that's not much of an improvement. In practice, however, it isn't quite that simple. The stack usually has to be adjusted one way or the other and this completely wipes out any benefit to be seen from avoiding the push and pop of the return address.

To summarize, this point of view about tail recursion is based on these ideas:

• Its purpose is to avoid writing looping constructs, which are somehow considered ‘bad’ by ‘purists’. These weirdos ‘think’ in loops, then transform the code to be ‘recursive with tail calls’ when they write it, and then expect the compiler transform it back. This is academic mental gymnastics with no practical purpose.
• People who like tail recursion are purposefully burdening their code in the name of ‘mathematical’ or ‘theoretical’ purity, but they expect the language implementor to bear the weight.
• Any code that depends on tail recursion can easily be rewritten to use a looping construct instead. Such a rewrite is a trivial local transformation.
• Inter-procedural tail recursion may have some performance benefit, but such benefit is very small at best, and the tradeoff is the loss of valuable debugging information.

van Rossum's blog post almost screams each of these points.

If these were in fact the key issues to be argued, then there would be little more to say beyond de gustibus non est disputandum. But these arguments are a sideshow. The true argument about tail recursion is that it reduces the space complexity class of a program and allows a program access to a more powerful computation model. This argument is subtle.

Let me digress for a moment. Remember the Bubble Sort algorithm? If I were to write some code that used Bubble Sort to maintain the order of elements in a set, I would be lucky if I only got laughed at. The Hacker's Jargon file calls Bubble Sort `the generic bad algorithm'.

What makes Bubble Sort so bad? It is extremely inefficient. On the average, Bubble Sort performs O(n^2) operations to sort a set of n elements. The Big-O notation is the asymptotic time complexity of the algorithm. O(n^2) means that when the value of n is large enough, the number of operations grows proportional to the square of the number of elements. So if we were to Bubble Sort a set of one thousand objects, we might expect the number of operations to be in the millions. If our set grew to ten thousand objects, the amount of time to sort it would grow by a hundredfold.

Let's compare this to mergesort. Mergesort has an asymptotic time complexity of O(n log n). A mergesort of one thousand objects would take something like 1000 * 4 operations. This is much less than the millions required for a Bubble Sort of the same set. If we grew the set to ten thousand items, the amount of time to sort it would only grow by a factor of a little more than ten. Certainly far less than the hundredfold growth we see in Bubble Sort.

Bubble Sort is bad because it wastes a valuable resource: time. And when you let the problem grow larger, it wastes a disproportionately larger amount of time compared to other, more efficient algorithms.

When you determine a strategy to solve a problem, you take a close look at the complexity classes of your algorithms. You'd like a solution within a reasonable amount of time, and you'd like to avoid using an unreasonable amount of space (whether memory or disk). Picking an inefficient algorithm for some minor part of your program can have a major impact on the resource usage of your program. Even the small change from O(n^2) to O(n log n) makes a huge difference.

Asymptotic time complexity is not the only measure of an algorithms efficiency. Space (memory usage) can be as much of a limiting factor as time, so asymptotic space complexity should be considered. Consider the diff program that compares two files. The naive implementation of diff using dynamic programming requires a rectangular tableau with a size that is the product of the length of the two files being compared. Diffing a pair of fairly large files in this way will exhaust memory. A tradeoff can be made where multiple passes are needed to complete the diff, but the space complexity, rather than being O(n*m) is O(n + m). It takes longer, but now truly enormous files can be diffed without running out of memory.

So what does this have to do with tail recursion?

A program describes a process. An implementation takes a program and performs the process the program describes. The process that emerges has a space and time complexity that is characteristic of both the implementation and the program.

Programmers usually expect to be able to ignore the implementation's contribution to the time and space complexity of a problem. A programmer would be surprised if he had coded up a mergesort with the expected O(n log n) asymptotic time complexity but found that the actual asymptotic time complexity on his computer was O(n^2). He would be understandably upset if an obviously linear text search required O(n^2) asymptotic space complexity in the size of the corpus.

To quote Clinger:

Proper tail recursion yields a well-defined asymptotic space complexity that can be relied upon by portable programs.

and

Among these [space consumption] properties of an implementation, proper tail recursion is especially important because it is easy to construct programs that should run in small constant space, but are likely to require at least linear space in implementations that are not properly tail recursive.

That is to say, if your implementation is not properly tail recursive, you will often find that a program that ought to run in O(1) space is actually taking O(n) space or even worse.

How could this be?

Consider this very simple program:

(define (foo x)
  (baz (bar x)))

In a non tail recursive implementation, the call to baz would return back to foo, which would then return to foo's caller. In a tail recursive implementation, foo would directly jump to baz and baz would return directly to foo's caller. The difference is that foo releases its resources before transferring to baz in the tail recursive case, and after baz's computation in the non tail recursive case. There are two resources of interest. The obvious one is the stack frame itself. The less obvious one is the reference to the value of X.

This is a very important. Code like the above is typical where one is performing a computation that involves part of a data structure. The call to bar traverses X to find the relevant sub-structure to operate upon. Once this substructure is located, it is no longer necessary to retain the enclosing structure X. The tail recursive implementation immediately discards the reference to X and allows the garbage collector to reclaim the resources. The non tail recursive implementation unnecessarily retains X during the computation of baz. This is not simply an inconvenience. If X holds substantial resources, we may run out during baz. If baz somehow depends on a recursive call to foo, we'll find our space complexity is not a function of the relevant information sitting in the bar portion of X, but a function of X itself, the container of our information. If we write a program that processes text sentence by sentence, we'd be surprised to find that the implementation uses space proportional to the entire document!

If one objects to Bubble Sort on the grounds of its poor asymptotic time complexity compared to better algorithms, then one clearly should object to a lack of tail recursion. It has even worse asymptotic space complexity, and it acts upon the entire program. (At least Bubble Sort doesn't slow down your program if you don't sort anything.)

Part II on its way....

(By the way, if you have questions or need some clarification on what I've said so far, please comment or email me.)

The TI Explorer was a clone of the LMI Lambda. At some point when LMI needed financing, TI and LMI did a technology swap where TI ended up with the Lambda architecture and LMI ended up with some cash and the NuBus. The Explorer was a close enough clone of the Lambda that it could run the same microcode.

Ever run into one of those bugs where you begin to doubt your basic assumptions? I hit one of those on the Explorer. The symptom was simply this: about 15 minutes after booting, the Explorer would crash. The proximate cause of the crash was a bad entry in the page tables. The Lisp machine really had an operating system hiding within it, and there's a virtual memory system with demand paging. There was a table that kept track of what the physical memory was being used for. If physical memory was needed and wasn't available, an existing physical page would be written back to the hard disk. This was when the bug was detected. A check on the page status showed it to be in an undefined state, so the machine halted.

In theory, there was no way for a page to transition to an undefined state, so something really bad must have happened. Fortunately, it was always the same page, so it was clearly a programming logic bug. It was also fortunate that it was in the page fault handler. The Lambda and Explorer microcode is completely single threaded, and interrupts are polled for in known locations. Since the page fault handler would play with the memory mapping hardware, it only polled for interrupts at the very few places that the hardware was in a known, good state. I could pretty much ignore the interrupts for debugging this one.

I put in a couple of quick checks to halt the machine when it wrote the page table entry and rebooted the machine. The machine ran for a while and then halted at my debug break. I single stepped the microcode (from the other processor), and watched it write the page table entry. It read the bits, modified the correct subfield and wrote the bits back correctly. Hmmm. Must be a different write. I let the machine run, but it didn't touch that entry again. The machine halted at the sanity check.

This was weird. The machine correctly modified only the field it was supposed to, yet it crashed. Perhaps the word was smashed after the modification. I added some code to check the value of the word at crash time. When I ran it again, I found that the word contained exactly what was written at my breakpoint.

I had to re-evaluate my assumption that the field being modified had something to do with the crash. Since that page had not previously been in use at all, I assumed it was zeroed out. I added a sanity check to ensure this. My sanity check failed. The pristine page table entry was not zeroed out. This made sense. The code had taken an entry that was not correctly initialized, correctly filled in the right field, but the other bits were wrong and that caused the crash. Clearly there was a bug in the initialization code.

This was sounding like a fencepost error. A fencepost error when initializing a table might leave one entry at the end uninitialized, or it might overwrite an entry in the next table. I didn't see anything obvious in the page table initialization code, though. I put a debug halt in just after the page table was initialized. When the machine halted, I looked at the table. It was fine. Everything was zeroed out correctly, and the next table in memory had no problems, either.

Obviously someone had done something with the entry between the time it was initialized and the time it was first used. I put in some more debug code to halt whenever that particular page table entry was accessed. This was possible because the page table manipulation code was in a single subroutine. I restarted the machine. It first halted when it initialized the page. As expected. It halted a second time when it read the page entry. That wasn't expected. Whoever modified the page table entry didn't go through the normal channels. That would cause a bug, but it was wasn't going to be easy to find.

I wrote a debugging subroutine that would simply validate the contents of that one special address and put a call to that subroutine in the middle of the boot sequence. The machine halted at my new test. I put it one quarter of the way into the boot sequence. It didn't halt. I put it three eights of the way through. Over a period of a couple of hours, I had determined where in the boot sequence the memory location was being overwritten. It was some subroutine that really had nothing to do with the memory system. In fact, it barely used the memory system. I pored over the code, but there seemed to be nothing at all out of the ordinary.

I was baffled. I was beginning to wonder if the memory maps had been corrupted. It is almost inconceivable that the machine would be able to run for more than a few milliseconds with corrupt memory maps, but it was the only thing I could think of that would allow you to make an undetected stray memory write. I wrote some more code to validate the memory maps. They were fine.

Ok, if that memory location started as zero, then later became non-zero, then a memory write cycle must have occurred. There are no two ways about it. I wrote some more microcode that checked the contents of that location and verified that it contained the correct value. I modified the microassembler to insert a microcode subroutine call to my validation code after every memory cycle. I rebooted the machine. It was incredibly slow. Every single memory reference involved an out-of-line microcode call to validate the page map. Nonetheless, the validation code finally caused the machine to halt.

It was in a weird location. Well, weird only in the fact that absolutely nothing interesting was going on. By using the backtrace buffer and looking at the microcode I could see which write instruction must have failed. But there was no reason it should have failed because the nearby writes to the same page worked just fine. I looked at the contents of the virtual address register and the memory data register. Surprisingly, they were the expected values. In fact, the memory data register did not contain the bogus value that was written to the page table. This is, in a word, impossible.

So what were the implicit assumptions I was making? One of them was wrong. Bad memory board? The memory test passed. I swapped the memory cards on the machine, but it still crashed in the same place. It was too deterministic and predictable to be flaky hardware. But the Lisp processor wasn't writing to that location.

On the other hand, the Lisp processor wasn't the only device on the bus. The corrupted memory location contained a byte full of 1s. I asked our hardware people: Is there any reason a device would write a byte full of 1s to another card on the bus?

As a matter of fact, there was. The NuBus doesn't have separate interrupt or I/O channels. It signals an interrupt by doing a memory cycle and plopping a byte full of 1s into another card's address space. For some reason, a device in the Explorer was trying to post an interrupt and ended up dropping a turd right where the Explorer put its physical page tables. This happened fairly early on, but after the page table were initialized. Then, some 15 minutes later, when the Explorer finally got around to using that page, it bombed on the corrupted entry.

I found the resident Explorer experts and mentioned that something was trying to post an interrupt. They looked at the initialization sequence and discovered that the code to initialize one of the devices had a bug and didn't correctly turn off the interrupt. The device would post an interrupt every few seconds. It was a couple of lines to fix it, but it took me several days of intense debugging to find it.

Taking a header

It took a while to iron out the contract between the stack closure implementation and the garbage collector. Timing was a critical factor, and memory integrity bugs have a special ability to survive one iteration of garbage collection. The bug confuses the garbage collector on the first iteration and causes it to corrupt memory as it is collecting, but the collector doesn't notice it at this point. On the next garbage collection it encounters the memory corruption and craps out. The problem is that the source of the corruption is long, long gone.

When Ken Sinclair left LMI to go to Symbolics, I inherited the garbage collector. As I mentioned in an earlier post, the garbage collector tended to get blamed because it discovered memory corruption caused by other modules. It was simply the case that if you ran the collector often enough, you'd eventually trigger a collection when someone wasn't expecting it and cause a crash. My microcode tracer cause the GC to run a lot, so I saw most of the errors.

Here's a good example. In uc-lambda-array.lisp you'll find this microcode:

store-array-registers-in-accumulators
((m-a) m-array-pointer)
((m-b) q-pointer m-array-header) ;Don't put headers in accumulators!
((m-d) m-array-rank)
(popj-after-next
(m-e) m-array-origin)
((m-s) m-array-length)

This subroutine copies the pointer, header, rank, origin, and length of an array to the m-a, m-b, m-d, m-e, and m-s registers. (The popj-after-next is the microcode subroutine return. You always put it one instruction ahead of when the return actually happens because of pipelining.) The point of this copying is to cache the information needed by the most recent array operation. If the next array operation uses the same array, it runs much faster because it doesn't have to go to main memory.

Note that second line with the comment. An array header is the marker that appears before the array contents. It is used for various things, but one of the most important is that it contains a count of contiguous words of memory that follow. When the garbage collector is scavenging memory to relocate pointers, it checks the array header to see if the array contains ‘boxed’ pointers, or ‘unboxed’ immediate values. If the array is unboxed, the scavenger skips the block of memory containing the array contents.

Enter the law of unintended consequences.

If you browse the microcode, you'll see comments about ‘sequence breaks’. A sequence break is point where the microcode is allowed to transfer control to a different stack-group. The Lisp machine simulated multitasking through time-division multiplexing. When a sequence break occurred, the current state of the micro-machine was saved in a main memory data structure. The accumulators (the m registers with single letter names) are stored in the data structure. If you were very unlucky, you could take a sequence break right after performing an array operation on an unboxed array. The array header would then be stored in the data structure. This wasn't very likely to happen because the m-b accumulator is one of the most frequently used registers and the array header would usually be overwritten within microseconds.

If you didn't turn on the garbage collector, this rare occurrence would be irrelevant. If you did turn on the garbage collector, it would be mostly irrelevant unless you happened to be very unlucky indeed. If you had a sequence break immediately after performing an array operation on an unboxed array, and the garbage collector decided at that point to scavenge the page that contained the saved m-b accumulator, then it would skip over some of the following pointers.

You might be surprised to learn that even that doesn't usually lead to memory corruption. You had to be really, really unlucky. If control is transferred back to this stack-group, the registers are re-loaded from memory. The memory system enforced a read barrier to support incremental garbage collection, so the pointers in the registers would have been adjusted at that point. The problem only occurs when you

1. Perform an array operation on an unboxed array.
2. Immediately swap out the stack.
3. While the stack is swapped out, start and complete a garbage collection. Some registers (the ones stored in memory locations after where m-b is store) may contain bad pointers at this point.
4. Start another garbage collection before re-assigning the registers.

This long chain of events is typical of the bugs I encountered. They were quite hard to reproduce. This bug had an easy fix. When we strip the data type off the array-header, the garbage collector no longer recognizes the object as a special case and simply steps over it to the next word in memory.

There were at most a couple dozen of these sort of bugs in the microcode. They were a real bear to find, but over the course of several months I eliminated a lot of them. Within the year you could expect to run the garbage collector without crashing the machine.

A short followup

I got some great feedback on the Cavendish experiment. fuf2 said:

how can you be sure electrical attraction is not interfering? I understand those forces are much stronger and might have contributed to the balance moving.

Short answer: I can't. I'd be sure it was electrical if the masses repelled. I did the experiment in a humid basement during the summer rather than in a carpeted room during a crisp, dry winter, but it's hard to discount electrical attraction.

Lincoln Quirk did the math and came up with a value of G = 1.32 * 10^^-10. That's good enough for me (and sounds near what I came up with, but my memory might be fooling me).

I remember the most difficult part of figuring out G was determining the angular momentum of the torsion balance and deriving the restoring force from the period. I had my physics and calculus textbooks, but they didn't give the formula. In fact, the textbooks had this particular configuration as one of the student exercises. I eventually set the problem up as an integral and solved it, but it was a bit painful. (It's not a hard integral, and it's not a hard problem, but when was the last time you did it?) Our local library didn't have very many of the kind of reference books you'd need for this. Inter-library loan works great if you know the title you want, but it isn't as convenient for browsing. The monks at the monastery down the road were in the middle of illuminating Strunk and White and were expecting to take a while before getting to anything scientific.

Thanks to everyone that wrote in!