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:
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.