Exploration Through Example

Example-driven development, Agile testing, context-driven testing, Agile programming, Ruby, and other things of interest to Brian Marick

191.8

⇒

167.2

⇒

186.2

183.6

184.0

183.2

184.6

Sun, 09 Jan 2005

Programming the PDP-1

A story, following up on my post about the virtues of knowing languages close to the machine. One of the things that always impressed me about the great Lisp hackers was the way they moved effortlessly between levels of abstraction. At one moment, they could be thinking extremely abstract ideas like call-with-current-continuation (often abbreviated call/cc). The next, they could be hacking PDP-10 assembler. But are the two levels so unconnected?

There was an OOPSLA workshop organized around reading PDP-1 assembler. An interesting machine, the PDP-1. It had one general-purpose register, one IO register that could be used for scratch space, and no stack pointer.

In the workshop, we read parts of Peter Deutsch's first Lisp for the PDP-1, struggling through the unfamiliar idioms. Even for people who know assembly, there's a big difference between idioms that assume at least six available registers + a stack pointer (the PDP-11) and those that assume two.

One idiom looked something like this (eliding any complications due to having such a small peephole to memory):

  104:	store 106 in 100
  105:  goto 203
  106:  next instruction in the computation
  ...
  
  203: do something
  204: goto 303
  ...

  303: do something
  304: goto 404
  ...

  404: do something
  405: goto the instruction stored in 100

The main program invokes a subcomputation by storing the eventual return address and jumping to the first subroutine. All the components of the subroutine know they're part of a chain of computation, so they just jump to the next link. The final one looks in a known place to find where the main program's next instruction is and jumps there. No stack.

When we figured out what was going on (I think Dick Gabriel had to explain it), the thought that flashed through my brain was "call/cc!" It's not - it's closer to setjmp/longjmp - but I wondered whether experience at that low level primed the Lisp hackers to be receptive to ideas like call/cc. The idea of a function call is sort of a closed conceptual universe. It encourages you think about what you can do with function calls, not necessarily what you can do that's like function calling. But if you know assembler, especially from before there were modern-day function calls, you're perhaps more likely to think of a function call as a bricolage: something made up of pieces, pieces that can be assembled in different ways or used independently in combination with new pieces. Maybe call and return don't have to go together.

I suspect that's all bogus. Call/cc probably has more to do with Lisper's tendencies to try to make everything a function. (Witness Steele and Sussman's Lambda the Ultimate papers.) And there's all that denotational semantics / lambda calculus stuff. Perhaps experience using assembly to code something vaguely similar didn't till the soil for call/cc. But isn't it pretty to think so?

## Posted at 12:51 in category /misc [permalink] [top]