Let's do the twist

This post is about amateur physics. No computer science is involved, but it was pretty cool.

In 1798 Henry Cavendish did an experiment to weigh the world. Although Cavendish didn't bother deriving the gravitational constant, his experiment was the first that could produce a direct measurement of it.

In the summer of 1985 I was at home convalescing and being bored. It occurred to me one day that if Cavendish could determine the gravitational constant back in 1798, I ought to be able to do something similar, especially because I had access to a few things that were a little hard to obtain in 1798.
The Cavendish experiment involves a torsion balance, which is like a dumbbell which is suspended in the middle by a thin fiber. After letting the thing settle down for a long time, it will be very sensitive to forces that cause it to rotate in the horizontal plane. But any rotation will be opposed (very slightly) by the torsion on the fiber. By placing a pair of large masses near the weights on the end of the dumbbell, the gravitational attraction between the masses will cause the dumbell to rotate until the force of gravity matches the opposing force of the torsion. If we can measure the angle of rotation and determine the torsion of the fiber, we can derive the gravitational attraction between the masses.

Cavendish cast a pair of 1.61 pound lead weights. I found a couple of 2-pound lead cylinders my dad had lying around. I used duct tape to attach them to a 3-foot wooden dowel. Cavendish used a wire to suspend the balance, I used nylon monofilament. To determine the torsion of the fiber, you wait until the balance stops moving (a day or two) and then you slightly perturb it. The balance will slowly oscillate back and forth. The restoring force is calculated from the period of oscillation. Cavendish had a 7-minute period. My balance had a 40 minute period (nylon is nowhere near as stiff as wire).

Cavendish used a pair of 350 pound lead balls to attract the ends of the balance from about 9 inches away. I put a couple of 8 pound jugs of water about an inch away. The next trick was to measure the rotation of the balance. Cavendish had a small telescope to read the Vernier scale on the balance. I used some modern technology. I borrowed a laser from Tom Knight (Thanks again!), and bounced it off a mirror that I mounted on the middle of the balance. This made a small red dot on the wall about 20 feet away. (I was hoping this would be enough to measure the displacement, but I was considering an interferometer if necessary.)

To my surprise, it all worked. After carefully putting the jugs of water in place, the dot on the wall started to visibly move. Within a few minutes, it had moved an inch or two. I carefully removed the jugs of water and sure enough, the dot on the wall drifted back to its starting position.

This was really cool. Newton's theory of gravity was the first ‘unified theory’ of physics. It took several disparate phenomena — the orbits of the planets, the orbits of moons, tides, and the kinematics of falling objects — and proposed a single theory that explained them all mathematically. But Newton's theory supposed that every object has a slight gravitational attraction to every other. This is a strange phenomenon that hadn't been observed (prior to Cavendish). It's not something you usually see because the force is extraordinarily small.

My dad was astounded. Of course he knew about gravity from high school, and knew it kept the planets in orbit and stuff stuck on the ground, but he hadn't remembered (or perhaps wasn't taught) that there was a very small gravitational force between everything, including the lump of lead on the end of my stick and the jug of water a few inches away.

Even though I knew there was a force I could measure, it was still pretty amazing to watch it happen. Sure, you believe Newton's laws, but after seeing this in action, there is still a `wow' factor.

Now as for the value of G. I think I gave enough information here for someone to derive it. I think I calculated it to be somewhere around 10^^-11 plus or minus an order of magnitude. One day I might try to really calculate it.

I have to recommend trying this experiment if you have the room to set it up. It's something to see.

Some Lisp Machine minutia

Bit 59 in the Lisp Machine microcode is the halt bit. If the microcode instruction register ever has bit 59 turned on, the clocks stop and the entire processor freezes. Sprinkled throughout the microcode are sanity checks that call the ILLOP subroutine if they fail. The ILLOP subroutine tries to write a ‘crash record’ in a pre-defined location and then halts the processor. If things are running correctly, this should never happen. Well, hardly ever.

The System Diagnostic Unit (SDU) has a watchdog timer. Every now and then, the processor resets the watchdog timer in the SDU. If the watchdog timer ever times out, the SDU assumes that the Lisp processor has stopped. The SDU will blink the screen to let you know the machine crashed. If you wish, you can tell the SDU to turn the clocks back on. Since ILLOP is a microcode subroutine, it will return back to the instruction immediately following the failed sanity check. This allows you to put debugging ILLOPs in the code to act as very primitive breakpoints.

Down at the bottom of the Lisp Machine screen, there is a status bar called the ‘wholine’. Under the wholine there are three little lines that are 1 pixel high and 16 pixels long. These are the ‘run lights’. The rightmost one is on unless the processor is in an input wait state, the middle one comes on when the processor is waiting for the disk, and the leftmost one comes on when garbage collection is occurring. The GC runlight has two parts, one indicates scavenging, the other indicates transporting.

When the machine is working, the runlights flicker on and off. When it crashes, everything freezes for a second or two. There is a tense pause while you wait for some sign of life from the runlights or for the SDU to blink the screen.

---

In my previous post I had decided to turn on the garbage collector so I wouldn't run out of memory when trying to trace the microcode. Once I had the GC turned on, I tried to run my code. The machine froze and the screen blinked.

I got very, very familiar with this.

An LMI Lambda 2x2 had two Lisp Machine processor on a single NuBus. If a processor halted, it was possible to read the processor state from other devices on the bus. When you were debugging the microcode, the best way was to have a 2x2 so you could decode the frozen processor state from the other processor and match up machine addresses with symbols, etc.

The Lisp Machine had a hardware ring buffer that recorded the value of the microcode program address register on every cycle. You could get a backtrace of the last thousand instructions that lead to the crash. This is an incredibly cool and useful feature.

When I ran my microcode tracer and crashed the machine, the microcode trace revealed that we had encountered an illegal stack environment while attempting to transport a lexical environment from within the garbage collector loop. RG sent me to talk to Ken Sinclair. The Symbolics 3600 had come out a couple of years before and had the first commercial generational garbage collectors. LMI was trying to play catch-up and Ken Sinclair was in the process of writing a generational GC for the LMI Lambda. Ken had actually completed the garbage collector, but the rest of the company was slow in adopting it.

There was an unforseen consequence of the practice of running the machine with the garbage collector turned off. The microcode had gotten sloppy and people were playing a bit fast and loose with the memory model. Untagged addresses would be squirreled away and dereferenced later with no thought given to whether the GC might move the object referred to. Bogus objects — properly tagged words with invalid addresses that pointed at uninitialized memory or into the middle of object of a different type — which would cause the GC to corrupt memory would be left in registers or on the stack. These sort of problems were everywhere in the microcode. Of course it was the garbage collector that discovered these, and following the ancient tradition, the messenger was blamed for the message.

The stack allocated lexical closure microcode was written in haste by RMS, and repented in liesure by yours truly. With Ken Sinclair's help from the GC side, and a lot of poring over microcode, I managed to fix the stack closure bug.

I don't imagine you really want the gory details, but I'll give them anyway. Here are the comments at the beginning of uc-stack-closure.lisp.

Here is how lexical closures work 
A lexical closure consists of a piece of code and an environment to 
resolve free variables in.  The code is implemented by a FEF and the 
environment is implemented as a list of vectors.  Each car in the 
environment is a lexical environment frame which is a vector of 
variable bindings. As there is no way to extend the number of variables 
in a lexical environment, a vector saves space, but more 
importantly, since the lexically visible variables can be known at 
compile time, the compiler can generate code that simply "arefs" a 
given frame and finds the correct value of a lexical variable.  A 
lexical environment is a list of these vectors.  

A closure (any kind, stack or regular) is implemented like this: 
  (dtp-{stack-}closure         ) 
                             | 
                /------------/ pointer to closure 
               V 
  (cdr-next dtp-fef-pointer  --)---> points to a fef containing the code 
  (cdr-nil  dtp-list           ) 
                             | 
                /------------/ pointer to lexical environment 
               V 
  (cdr-normal dtp-list       --)---> points to lexical frame 
  (cdr-error  dtp-list       --)---> points to next environment  

This would be too easy if it weren't for efficiency hacks.  The 
following things are noted: 

1) Some closures are only used in downward funargs and will never be 
   needed after this dynamic frame is exited.  The extent of these 
   closures is dynamic and follows stack discipline, so they can be 
   consed on the stack giving the garbage collector a break. 
   (Actually, this was done so that you wouldn't have to use a 
   losing garbage collector.)  It is not possible to tell if a 
   funarg is to be used in a downward only direction if it is passed 
   to a procedure external to the one currently running. 

2) The uppermost lexical frame of the closure when it is created is 
   the current dynamic frame.  The args and locals of the frame are 
   the ones that are seen by the code.  They cannot be copied out of 
   the frame. 

3) Not all the args and locals of a dynamic frame need appear in a 
   lexical frame.  Which args and locals are needed can be 
   determined at compile time.  This will save space and allow the 
   garbage collector to reclaim inaccessable objects that would be 
   otherwise saved if we kept the whole dynamic environment. 

4) Nested lexical contexts can be "flattened" if the code that 
   creates them is only run once.  See page 87 - 89 (base 10) of the 
   common lisp book for examples of flattenable and unflattenable 
   contexts.  A corollary to this is the fact that a binding which 
   is lexically visible to different closures and which should be 
   distinct in each closure can be shared among them if the code 
   never mutates the variable. 

The above is taken advantage of by the below. 
Efficiency hacks: 
1) We take an optimistic approach and assume all funargs are 
   downward.  Lexical frames and closures are initially allocated on 
   the stack.  All pointers made to the closure are labeled 
   dtp-stack-closure.  If a dtp-stack-closure is ever moved anywhere 
   but to a frame closer to the top of the stack, it becomes 
   necessary to copy the closure and the lexical frame 
   out of the stack and into the heap.  All closures that 
   are in the heap are labeled dtp-closure. 

2) The lexical frame when it is created contains 
   external-value-cell-pointers (EVCP's) to the actual locations in 
   the stack of the args and locals.  This makes it possible to 
   smash the args and locals from downward funargs. 

3) The lexical frame is created only with those bindings needed by 
   the closure.  This is determined by looking at the FEF of the 
   current procedure (not the one you are closing!).  Two slots 
   before the unboxed instructions is a list which is a template for 
   making lexical frames.  It is a list of fixnums in which the low 
   twelve bits specifies which argument or local appears and the 
   sign bit indicates whether it is an arg or local.  This list is 
   arranged in "reverse" order, i.e. the first argument is the last 
   on the list and the last local is the first element of the list. 
   The list is stored in reverse order because the microcode just 
   happens to make a pointer to the box just after the lexical 
   frame.  It then constructs the lexical frame by decrementing the 
   pointer and cdring down the map in the FEF. 

4) The contexts are in fact flattened by the compiler.  The compiler 
   makes sure variable references go to the right slot, so there are 
   no name conflicts.  In order to take advantage of sharing, we 
   assume that all lexical frames closed in the current dynamic 
   frame can be shared and only cons up one initially.  The compiler 
   issues commands STACK-CLOSURE-DISCONNECT to force a 
   splitting of shared frames.  This copies the current frame into 
   the heap.  Two frames which were EQ are now EQUAL (i.e. identical 
   copies instead of being identical).  Then, the compiler does a 
   STACK-CLOSURE-UNSHARE giving it an argument which specifies which 
   lexical slot to unshare.  Remember that the lexical frame 
   initially contains EVCP's to the args and locals. 
   STACK-CLOSURE-UNSHARE "snaps" the invisible pointer and copies 
   the arg into the lexical frame.  The frame will still share the 
   other args and locals by virtue of the remaining EVCP'S 

   When it finally comes time to exit the stack frame, if there are 
   any outstanding closures in the heap pointing to a lexical frame 
   which is stack consed in the current stack frame, we copy the 
   stack frame to the heap and snap all the EVCP's in it.  We then 
   go to each closure pointing sharing any of the args or locals and 
   make their EVCP's point to the copy we just constructed.  Now we 
   can exit the frame.  Note that in order to find each closure in 
   the heap, we keep around a list of all closures disconnected from 
   this frame.  

How a frame with closures is set up in the first place:  

Frame begins here  (dtp-fix) ;bits controlling return 
                  (dtp-fix) 
                (DTP-FEF-POINTER  --)---> to code for the frame. 
Arguments        (cdr-next ......) 
 cdr codes are   (cdr-next ......) 
 set right               : <more args> 
                         : 
 last arg        (cdr-nil  ......) 
Locals           (...............) <--- A-LOCALP if this is the current function 
 random boxed    (...............) 
 objects                 : <more locals> 
                         : 
   Stack closures are allocated in the area for locals and take up 
   four local slots.  They are not really locals, they just live here. 
   The <pointer to next cell> is the pointer to the lexical 
   environment chain which just happens to be in the next cell. 
stack closure   (cdr-next   dtp-fef-pointer --)---> points to closure code 
                (cdr-nil    dtp-list  <points to next cell>) 
                (cdr-normal dtp-list  <points to lexical frame>) 
                (cdr-error  dtp-list  <points to next higher context>) 
                        :  <more stack closures> 
                        : 
   The lexical frame also takes up locals.  It is constructed from the 
   map found two slots before the instructions in the FEF.  We work 
   here on the assumption that we will not need more than one lexical 
   frame (in the case where all variables are or can be shared). 
                (dtp-list <pointer to beginning of frame>) 
lexical frame   (cdr-next dtp-external-value-cell-pointer <pointer to local or arg>) 
                (cdr-next dtp-external-value-cell-pointer <pointer to local or arg>) 
                        : <more lexical slots> 
                        : 
next-to-last-local      (dtp-list <pointer to lexical frame>) 
last-local       Contains a list of all copies made of the lexical 
                 frame so we can set them up right when we exit this 
                 dynamic frame and deallocate storage for the 
                 variables. 

The top of the stack is here.  

Notes on the above diagram. 

1) The word just before the lexical frame is used by 
   COPY-STACK-ENVIRONMENT-INTO-HEAP to locate the beginning of the stack 
   frame. 

2) The lexical frame need not be there.  All the local slots 
   are set to point to nil when the frame is entered.  When it comes 
   time to make a stack closure, the next to last local slot is 
   checked to see if a lexical frame has been made.  If it has not, 
   (i.e. it is nil) the FEF is looked at to find a list of args and 
   locals to forward the slots in the lexical frame to.  If the list 
   in the FEF is nil, this means that the current frame is empty. 
   In this case, the next to last local is set to T indicating an 
   empty frame. 

3) In the comments above I used the words "lexical frame" to 
   indicate what it is that holds the bindings in an environment. 
   In the below code, it is called a "lexical frame"  I 
   apologize to those of you who tried to figure out what was going 
   on by examining my comments vs. the code before reading this. 
   "Lexical frame" is the use, "lexical frame" is the 
   implementation. 

4) A-LEXICAL-ENVIRONMENT will point to the context outside of this 
   frame so all closures created in this frame will contain a copy 
   of A-LEXICAL-ENVIRONMENT.   

When we copy a stack closure into the heap, we forward the copy on 
the stack.  We can't use HEADER-FORWARD because putting that in a 
structure will confuse other things.  What we do is put 
external-value-cell-forwards in the fef pointer and the environment 
pointer in the stack closure to point to the corresponding cells in 
the heap pointer.  This does not really forward the closure, but it 
will do the trick because the stack closure never moves until it is 
deallocated and anything that remains around after that sees only 
the heap allocated version.  The lexical frame (the stack closure 
vector) is not forwarded.  

The last word in the frame is a pointer to every copy of the lexical 
frame in the world.  If the stack frame is exited, we copy the 
lexical frame and go to each of the other copies and change their 
EVCP's to point to our new copy.  

This is the old comment. 
; Copy a DTP-STACK-CLOSURE when it is stored anywhere but 
; into the same stack it points at, and farther down than where it points. 
; There is no way to forward the stack closure to the copy, 
; because only header-forward works to forward a list's car and cdr, 
; and putting that inside a structure will confuse other things. 
; So we stick an external-value-cell-pointer into the stack closure 
; pointing at the copy.  This does not forward it as far as the 
; low levels of the system is concerned!  But as long as the 
; stack closure still exists, that's ok; the evcp forwards only the car 
; of the stack closure, but forwards it to the car of the copy, 
; which contains the correct value. 

Wow. I vaguely remember writing that.

An obvious solution

The reason the Lisp Machine doesn't have tail recursion is that there is too much random cruft on the stack. The reason there was so much cruft on the stack was because of the garbage collector. The connection there is probably not obvious.

The PDP-10 on which MACLISP ran had an address space of 2^¹⁸ words (a word was 36-bits and cold hold both the car and cdr of a cons cell). The CADR Lisp machine had an address space of 2^²⁴ words. The words were 32 bits, so the Lisp Machine could run an enormous 64 megabyte image. Of corse no one could afford anywhere near that much memory, so the CADR had something like 192K of RAM and the rest was paged to disk. (The LMI Lambda doubled the address space by snarfing a bit from the data tags.)

When the CADR needed to garbage collect, it would stop and copy. and copy... and copy .... and copy .... and copy .... The disk was slow and copying the image meant a lot of disk traffic. It was so slow that it was much faster to reboot the machine and restart your program. In fact, you didn't have to reserve a chunk of address space for GC if you didn't mind rebooting, and then you could run longer between reboots.

People got used to this mode of programming and added a lot of code to the machine to support it. You could allocate in discardable regions of memory, you could dynamically allocate on the stack, you could manage allocation pools and explicitly free objects. Some people became wizards at writing completely non-consing code.

But I always thought that the computer should handle the mundane tasks of memory management, and I wasn't going to contort my code to make up for a lame collector. Besides, I'd heard something about `ephemeral garbage collection' and I thought the machine was supposed to do that.

My microcode tracer tended to cons a lot of lexical closures. It would run out of memory for even moderately sized runs. I had three options for making progress:

1. Rewrite the code to avoid consing at all costs.
2. Figure out how to save and restore the intermediate state of the tracer so we could make progress across several reboots.
3. Turn on the garbage collector.

That's a no-brainer.

LMI Flashback

Once I fixed the compiler bug that was causing variable aliasing, I ran into the second (of many) problems. I discovered that there was a rather small limit on the stack frame size. The nested procedures that I used quickly exhausted the local variable space and caused the compiler to error out. Unfortunately, the Lisp Machine macro code (the microcode implemented a stack-oriented virtual machine) only had a small field for the displacement value of stack instructions, and there was no easy way to fix this. Given the choice between rewriting my code and rewriting the compiler, I chose to wimp out.

Next problem: stack overflow. It didn't occur to me that the Lisp Machine, the pinacle of AI Lab engineering, wouldn't optimize tail-recursion. It's a pretty trivial thing to implement. If you ever find the compiler emitting a call instruction followed immediately by a return instruction, you simply change that to a jump (what's tricky is if your calling sequence is such that the compiler never emits a call followed by an immediate return). It's easy to do dynamically in the microcode as well. When you do a function call, you peek at the following instruction. If it is a return instruction and the stack is empty, just omit pushing the return address.

I asked RG about this. He said that there was some microcode to handle tail recursion, but it was commented out because it didn't work. He said I was free to look into it, but he didn't expect that I'd have any luck. He was right.

Although the concept is easy, the devil is in the details. At function call time, the stack is never empty. Most of the cruft on the stack is not in use, so it could be deallocated, but there are things that might be in use. These are things like the dynamic binding level (for special variables), pending catches and unwind-protects, data structures with dynamic extent, and even more esoteric things (microcode state!) that happened to end up on the stack because it was convenient. The return instruction can simply deallocate the stack space because everything that stores stuff on the stack doesn't expect it to last beyond the next return. But for tail recursion, we want to deallocate stuff as soon as possible.

The code was a true mess. There is a status word at the beginning of the stack frame and many of the routines that store stuff on the stack set a flag in the status word to indicate they need the frame to last. But not every routine was this well behaved. In the particular case of lexical closures, the lexical environment was optimistically allocated on the stack and only moved to the heap if pointers to the closure still existed at the time of return. The code that implemented tail-recursion had to grovel around on the stack and try to determine if the stack frame was truly needed. It was easy enough to be conservative and punt, but the particular use case I had in mind (where I used some continuation-passing-style) was the hard case.

I eventually worked around the problem by allocating a particularly deep stack.

Over the time I was at LMI, I occasionally revisited this code to see if I could get it working again, but I never had any luck.

No More Boring Code!

I really wish I had thought of this. It is absolutely brilliant. Fortunately, John Clements is a friend and colleague of mine, so I'm glad he thought of it:

Reading and writing Java is, by and large, boring. Boring code is boring to write, and genuinely difficult to read without glossing over details. This is an observation made by Yaron Minsky at his Cam(e)l Trading talk at CMU. This resonated strongly for me, and got pretty close to the root of what I think functional languages are about: providing the abstraction tools to obviate the need for Boring Code.

Well, maybe Yaron Minsky thought of it. Alas it wasn't me. But John came up with a logo and I want to jump on the bandwagon.

Let's stamp out boring code!

Lisp Conference - Jerry Boetje

Jerry Boetje officially unveiled CLforJava at the conference. Jerry's goal is to ‘intertwine’ Common Lisp and Java so you can build programs out of components written in either or both languages and transparently move between the languages.

I think this is a great idea. I'd like to see something more formal about the semantics of doing this. What gets lost in the intertwining? What is intertwining? It isn't compilation or interpretation.

ObScheme: I'm doing some latency measurements and have adapted my old latency measuring code. It's a trivial SCSH script, but it produces the goods.

Lisp Conference - Mike Blair

I was surprised to see Mike Blair at the Lisp conference. Mike is an old friend of mine and we've worked on several projects together. He's very sharp and has some fantastic ideas about dynamic program optimization (examining the statistics of runtime values to guide JIT compilation).

Mike knows computing from the transistor on up through the meta-circular evaluator. (And even the meta-meta-circuluar. I recall that he once got the meta-circular evaluator to run itself. It took about forty minutes to get to the prompt.) I've seen him program a micro-coded Turing machine and I've worked with him on a spreadsheet program. He was at Transmeta for some time and has some interesting stories about debugging Microsoft Windows from below (finding bugs where Windows unintentionally relied on hardware behavior that was known to be probabilistic).