The flow for this entry is a little odd. I started writing the next two paragraphs around 5:35PM but most of the remaining text was written early this morning.

Riding in on the bus this morning I got it into my head that I wanted to explain how subroutines are handled in machine code. It's not really that complicated and for some reason I thought someone might be interested in such an explanation. Subroutine calls are the programmer's equivalent of farming out some work to someone else where the someone else in this case is another block of code somewhere in memory. The hitch is that there's only one CPU to do anything so the CPU has to stop what it's doing in order to execute the other block of code. The tricky part involves not allowing the CPU to get so distracted that it can't return to what it was doing earlier.

This morning I had my laptop on the bus because I needed it in the office today. During the first part of ride I was just writing notes on a pad of paper, but then the bus got stuck in a traffic jam so I pulled out my laptop and started typing. When I got off the bus in downtown Providence I was so into writing about subroutines that I went into the first cafe I could find, ordered a coffee and ended up working on my laptop for another half hour or so. I was obviously finding it difficult to subroutine. Now its evening and I'm riding the bus back home reading over my notes from the morning and making a few changes. Here's what I wrote this morning.

I started writing the next few paragraphs around 7:45AM.

Try to anthropomophize the role of the CPU in dealing with a subroutine call in the midst of executing a block of machine instructions. Note that a subroutine is just another block of instructions, but one that get's called frequently from other blocks of instructions. Programmers create subroutines for tasks that are performed often. Procedures and functions serve a similar purpose but I use the the more generic and less baggage-laden term "subroutine" when talking about programming at the level of machine code (the "baggage" in this case is the terminology and expectations of high-level programming languages). So, imagine that you're the CPU and you're executing a block of code, merrily chunking along incrementing the program counter after completing each instruction and suddenly you encounter a JSR, (or jump to subroutine) instruction along with an address of the first instruction in the block of code corresponding to a subroutine. Here's what you might find written about the JSR instruction in an assembly language manual.

INSTRUCTION NAME
        JSR -- Jump to subroutine
CALL PATTERN
        JSR address
FUNCTION
        Pushes the long word address of the instruction immediately
        following the JSR instruction onto the stack. The PC contains
        the address of the instruction word plus one. Program execution
        continues at the location specified by the address.

Of course, you're in the midst of doing some other very important stuff and perhaps even have some registers full of operands that you have yet to perform computations on. You might even be in the midst of an earlier digression, executing a subroutine call that was called from some other block of code. Well, if there was important stuff in registers then the programmer writing this code had better have taken care of it because JSR doesn't save the contents of any registers accept the program counter. But the JSR instruction does take into account the fact that you'll want to return to finish whatever you were doing in the current block of code. And so here's what you'd do (playing the role of the CPU).

First, however, we have to explain the role of the stack and two instructions that are used to modify the stack. The stack is a part of memory where you put things so you won't forget them. The idea is that if you're planning to go off and do something other than what you're currently doing, then you place on the stack anything that you'll need to remember later when you resume whatever it was you were doing. The PUSH instruction puts the contents of a specified register on the top of the stack and the POP instruction removes the top item from the stack and loads it into a specified register. Think in terms of a stack of cards. Each time you POP something off the stack, the stack has one less item and each time you PUSH something on the stack the stack as more more item. The stack is like a Pez dispenser that you can press candies into or pop them out of. In the following, we'll refer to items on the stack as "words" corresponding to binary numbers of the same size as that which will fit into a register. Here's what a stack and the operations PUSH and POP look like implemented in Scheme.

> (define stack (list))
> (define (push word) (set! stack (cons word stack)))
> (define (pop) (let ((word (car stack))) (set! stack (cdr stack)) word))
> (push "A")
> (push "B")
> (pop)
"B"
> (pop)
"A"
> (push "C")
> (push "D")
> (pop)
"D"
> (push "E")
> (pop)
"E"
> (pop)
"C"

Indeed while the JSR instruction only saves the program counter, the programmer writing the code block you're currently in may have included instructions prior to the JSR instruction that PUSHed the contents of some other registers onto the stack, and, if so, then presumably there will be some instructions immediately after the JSR instruction that POP those items off the stack and into registers thereby restoring the registers to their state prior to executing the JSR instruction (and, incidently, prior to running the subroutine which the JSR instruction pointed to).

Here's a typical though somewhat simplified instruction sequence. I'm assuming that the programmer wants to save the contents of registers A and B so that he can make use of the data in these registers when the CPU returns from the subroutine call. Finally, assume that L is the address of the subroutine that we want to call.

PUSH A # push the contents of register A onto the stack
PUSH B # push the contents of register B onto the stack
JSR  L # jump to location L - this instruction will also cause 
       # the program counter + 1 to be pushed onto the stack
POP B  # pop the top word off the stack and load it into register B
POP A  # pop the top word off the stack and load it into register A

Following the code fragment, the registers are restored to their state just prior to the subroutine call. Note that as a programmer if you're not careful with your PUSHes and POPs, it might not be the case that the right things are on the stack when you need them. However, if you always make sure that you execute the same number of PUSHes before a JSR as POPs afterwards then at least you won't inadvertently leave stuff on the stack or remove more than you should. It's the pain of handling this sort of nitpicky bookkeeping that turns many programmers off of programming in machine language; modern programming languages and their associated compilers manage this busywork automatically.

Now it's 8:30PM and I'm just back from a bicycle ride to the beach and swim in the ocean. It's the first day the water has felt warm enough that it really seems like summer.

I'm tempted to just chuck this entry. I didn't do a very good job motivating the material and even if I had, a description of machine-code subroutine calls is pretty dry stuff. Of the billions of jump-to-subroutine instructions that exist in current programs, very few of them were written by human beings. JSRs are routinely generated by compilers in converting procedures written in high-level programming langauges into machine code to run on specific computers. Many programmers never even learn about JSRs and fewer still actually use them. Ah well, I still think they're interesting.

This was an odd day. In addition to spending a couple of hours writing about a topic that isn't likely to attract many readers, I retired one computer and acquired a new one. I've had a Sun Sparc Ultra running the Solaris operating system on my desk at the office for the last couple of years. The machine was called klee.cs.brown.edu on the net and I'd affectionately call it "klee" and sometimes even "paul" (Paul Klee, 1879-1940, is one of my favorite artists). Today they installed a new computer (PC) running Linux in my office. The "brand name" of the machine is "Maxbuilt" in honor of Max Salvas, a member of our department technical staff who custom builds computers for us out of stock motherboards, network cards and other components.

It's a nice machine but the hardware is not nearly as heavy duty as the equipment from Sun Microsystems and Solaris is a better operating system in my estimation. But more and more the machine in my office is just a conduit for me to make use of other machines and for the most part I don't care where my computing gets done. Still, I caught myself thinking maudlin thoughts when they shut klee down and wiped its disks. By the way, the new machine has inherited the older machine's IP (internet protocol) address and its DNS (domain name server) identity. I prefer to think of the machine swap as klee getting a brain transplant. For most of the things I do, I can't tell the difference and I expect I'll start calling the Linux box "paul" before the week is out.