Spelunking CACM, vol. 6 (1963): Doubly-linked lists, CAM, and insights into computers and society

The 1963 volume includes a lot of short takes certifying various algorithms, but without a lot of details. There is also quite a bit on implementing algorithms in ALGOL, and articles on advancing the FORTRAN language and runtime. The entire May issue is dedicated to sorting and merging, but I don't see anything at a glance that looks like a revolutionary advance. There are still a lot of articles on algorithms for calculating basic math functions, such as complex arithmetic. And, a perennial favorite, calendar calculations.

I don't know if this article by Weizenbaum himself is the origin of doubly-linked lists (referred to as "symmetric lists" in this paper) or not, but it's an early version, for sure, and includes FORTRAN code implementing it and an extensive discussion implying that other, related work is only singly-linked lists. The editor comments that there was considerable interest, making it valuable to include the source code. The basic list element:

In fact, this seems to be far more sophisticated than just doubly-linked lists. Sublists are possible and reference counts are included, and garbage collection is mentioned. I'm not sure if cycles are permitted. Here is a list with a sublist and a data structure for managing tree traversal:

Garbage collection is explicitly mentioned early, but only once, so it must have been considered a well-known technique by 1963. It's interesting to think about what would have happened if list processing had become a mainstream feature of FORTRAN. In fact, Weizenbaum packaged this as the language SLIP, a set of extensions to FORTRAN, and according to Wikipedia it was the language for the first implementation of Eliza!

In a related (to me, anyway) article from the January issue, Scidmore and Weinberg propose something that sounds like a CAM (content-addressable memory) to me.

Finally, Perlis's address to the national conference is an insightful, foresightful (is that a word?) look at computing's place in society. Worth a read!