What's a Simulator?

My students, and students in other labs, frequently do simulation work, but don't always have a clear idea in their heads about the purpose of simulation work. So, for the record, a quick definition:

A simulator is a microscope (letting you see details invisible with ordinary measurements), a telescope (letting you see things far away or at a larger scale than in the real world), a time machine (letting you look into the future), or an X-ray machine (letting you see the insides of things you can't otherwise look into).

But to be valuable, a simulation has to be believable. That means you need to validate it in some way. The ideal case is for equations, experiments, and simulation to all agree, but typically we simulate things because they are are hard to model analytically or to build and test at sufficient scale (in space, time, or dollars). So, a good way to do things is to simulate at small scale, and compare that to equations or experiments. If you can do that, and make a good argument for why the simulator continues to work as you scale up, then confidence in your simulation increases.

Spelunking CACM, vol. 7 (1964): blind programmers and animations on microfilm

1964 brought us a language for compilers, and a paper on a graph isomorphism program that acknowledges that "no efficient algorithm is known", even as computational complexity theory was just starting to get off the ground as a field. That GI paper is especially interesting as a historical read because of the highly qualitative, primordial language about how hard problems are; the famous Hartmanis-Stearns paper is still a year in the future. Perhaps the most lasting impact, or at least the biggest problem that is still open, was addressed in the October issue, which has several papers on patents and copyright on both materials such as books and on software.

There is also an issue (April) with a lot of papers on education, and one on technology to help blind persons become computer programmers. A lot of the language in that wouldn't fly today, but what struck me was that, as far as I can tell, they didn't actually involve blind people in the work, either in early development stages or even in a direct usability experiment. Intriguing suggestion that blind people carry around more information in their head that sighted people, and therefore would be better at carrying around software designs in their heads.

I'm particularly intrigued by a paper describing a system for creating short black and white computer graphics animations on microfilm. I don't know much about I/O systems of the early 1960s, but I would have thought that some sort of oscilloscope or CRT-based visualization would have been in use by then. They include a nice summary of the film they created:

The text mentions that the Earth is actually shaded in the film, I suppose this simpler version is due to limitations of CACM's publishing. There is a footnote saying a 16mm film is available for loan from Bell Labs. I hope that's still archived somewhere!

I've been impressed so far with how forward-looking some of the earliest CACM papers have been, but I'd say in 1964 the breadth and potential of computing started to really blossom.

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!

Books, 2021

 Looks like I read 34 books in 2021. It seemed like a long, long year of stasis; it feels like all I did was exist and work (maybe in the opposite order), but I read a reasonable amount and it feels like the entire first half year's reading was long, long ago.

A couple of truly stand out books:

• Best nonfiction: Failure to Disrupt. Super-relevant to my own work, a great discussion of how online learning works best in a well-supported student population. The taxonomy of instructor-directed, peer-directed, and algorithm-directed learning really clarifies and crystallizes things for me.
• Best fiction: a toss-up between Americanah and Dandelion Wine. Both are books about our place in time, space and family. Both books for me evoked such strong emotions that I kept having to put them down.