Tail Recursion and Magnetic Tapes

Early magnetic tapes (circa 1952) could be read backwards. See note at the end of this. Tapes for the IBM 360 regained this ability about 1965. I have just now (2009) realized a connection with this function and tail recursion.

There were two significant advantages to reading magnetic tapes backwards:

The computer need not wait for the tape to rewind when it needs to read what it has just written. This was a common situation when an application’s working storage was too large for main memory.
Many applications, on successive passes over the data, need to spread effects thru the data in one or the other directions thru the data—often in alternating directions. This pattern is needed in applications as diverse as physics simulations and compilers.

The basic pattern with mag tapes was to write the data on tape starting at beginning of the tape. Then on the next pass read the data backwards that you have just written, perhaps writing out the next phase of the data forwards on another mag tape.

Linked lists, like mag tape, are naturally read in the opposite temporal order that they are written. I suspect this explains some brain function too. It has only now occurred to me to recall some of the advantages of reading mag tape backwards.

The programming language LISP introduced a new paradigm for processing a stream of data. Linked lists were themselves quite new when John McCarthy introduced LISP. To generate a list of numbers each of which was twice that in another list, x, one writes (tl x) where tl is defined:

(define (tl x) (if (null? x) '() (cons (* 2 (car x)) (tl (cdr x)))))

Well that is Scheme which is very much like LISP. In OCaml it is:

let rec tl x = match x with
      [] -> []
  | a::b -> (2 * a)::(tl b);;

Both of these programs are recursive and the work, (multiplication) happens as the stack shrinks after having grown to a size comparable with the input’s size. It is a strength of such languages that the correctness of the program does not depend on reasoning about the order in which the multiplies happen. The program can be seen to be correct while ignoring such details. If time or space are important however, we may strive for something better. In either case the program builds a linked list of stack frames each locating an element of the input list. After that the output list is built backwards, from the end to the beginning. Here is a Scheme program that doubles every element of a list but the output list is in reverse order:

(define (db x) (let d ((x x)(y '())) (if (null? x) y
    (d (cdr x) (cons (* 2 (car x)) y)))))

In OCaml:

let db x = let rec d x y = match x with
    [] -> y
| a::b -> (d b ((2 * a)::y)) in
  d x [];;

Note that tail recursion means that the stack never grows; the calculation is done in the one and only pass. If db is invoked thus:(db (f x)) when the system is under storage pressure the processed input to db can be reclaimed before the calculation is finished. The new program is faster and more efficient of storage. The program is not quite so transparent as the first and alas the output is backwards. This may not make a difference, or other program logic may be able to compensate for the discrepancy. Our mag tape experience with mag tapes tells us that it is often an advantage to reverse the order of your data.

An example of compensating for the difference is a sort. Tape sorts used this trick when the hardware was willing. Applying von Neumann’s binary merge logic means that on alternate merges the data is in the reversed direction. Consequently the sort is done mainly in place when storage is dear. It is also faster. You may need an extra pass at the end if you must have your data in ascending order.

Here are more examples where access to data is necessarily in alternate directions.