Spelunking CACM, Vol. 15 (1972)

In January, Duda and Hart wrote about using a variant of the Hough transform for finding lines in a pixelated image. More than fifty years later, this is still a standard approach to the problem. A line can be defined in terms of theta and rho, such that x cos theta + y sin theta = rho. First, transform every non-blank point (this algorithm is originally defined for black & white images) into a sinusoidal curve in the (theta, rho) parameter space. With a line, a set of those curves will all intersect at a point in that space. Finding those intersections can be expensive, but they give techniques for making this tractable, as well as allowing some slack in the parameters to account for imperfections or approximations.

David Pager proposed a computer-based interactive scientific community that is basically a queryable database of mathematical theorems that will provide you with a list of mathematical theorems you need to know in order to understand a particular paper you are reading. This paper seems to have had little impact, but the GOFAI people, including Cyc, should have loved it!

And the March issue was a special issue with eight of the 23 papers from the third SOSP, including a paper on TENEX and one by Liskov. Wow, I'm going to have to read all of these in more detail!

Who can argue with the early introduction of a course on computers and society?

As I noted in spelunking 1970, all of this is starting to feel very modern -- or maybe I'm just old. But it's getting to the point where so many articles feel relevant that it's hard to choose! However, many of these early CACM articles have only single-digit numbers of citations (ACM counting), which I find surprising.

Let me close with an obvious one: Dijkstra's humble programmer. We should all heed the words of the titans, and their Turing Award lectures are a great source of wisdom. "Programs should be constructed correctly, not just debugged into correctness," indeed!  (Would that it were so easy...)

Movies & Other Culture, 2023

I don't think I saw any major live music, dance or theater performances in 2023. The only place "new" I went, as best I recall, was ITB (Institut Teknologi Bandung) in Indonesia, where I hope to be going more often in coming years. I did read my usual thirty or so books, listed over on Goodreads (but zero so far in December? I should finish a couple by the end of tomorrow to get to thirty...).

The other major cultural source of entertainment is, of course, moving images. I watched almost no movies on small screens, though my wife and I did watch and enjoy Ōoku (大奥) and Whatcha Gonna Do, Ieyasu? (どうする家康?). I watched a little of Star Trek: Deep Space 9, but it has so far failed to captivate me as much as it has many other people. Beyond that...I pay for a lot of media services and rarely find things I am eager to watch.

So, movies...I think I perhaps saw only seven in theaters this year? Loosely ordered by ranking:

• Oppenheimer: This really is as astounding as everyone says. Among other things, Nolan uses sound (and lack thereof) to isolate characters, in a technique that very much makes going to a theater worthwhile. Looking forward to it coming to Japan and seeing it again, hoping I can get my wife to go with me. There are one or two anti-Japanese lines in it, consistent with the times, and it does focus on the title character rather than the bombings in Japan, but that's its intent -- there are plenty of other movies about Hiroshima, Nagasaki, or the war in general.
• Everything Everywhere All at Once: This is good, and I always love Michelle Yeoh, but when I first saw it I didn't automatically think, "This is the best movie of the year." But it stayed with me.
• Godzilla Minus One: Also fully as good as the praise. My Godzilla-seeing pal and I saw this on the biggest screen in eastern Japan, and we are glad we did. It truly does have characters that resonate.
• RRR: The most AMAZING movie you will ever see! Well, maybe not quite, but pretty close. It's as over the top as can possibly be, and huge fun. Also, if you thought the volleyball scene in Top Gun was, um, gay friendly, wait until you see the leg squats here! Speaking of Tom Cruise...
• Mission Impossible: Worth seeing, but I think some of the editing choices around the money shot are a little odd.
• A Haunting in Venice: Branagh was born to play Poirot, but should have let someone else direct this one.
• Indy Jones: Even bringing up the bottom of my list, it was okay. But there really wasn't any need to make this, it doesn't really add anything. It is kind of interesting to see an aging Indy out of his time and place in the 1960s.

...I think that's all I saw? Partly it was working too much (seven days a week most weeks), partly it was just lack of access to both information and good showings. I don't often hear about smaller movies and non-English, non-Japanese movies that I would definitely enjoy given the chance.

Gotta do better on all these fronts in 2024!

Spelunking CACM, Vol. 14 (1971)

 Let's start with a real gem from Niklaus Wirth, perhaps the greatest programming language designer of all time, who will turn ninety next year. In Program development by stepwise refinement, he lays out how to refine programs that perform combinatoric (although he never uses that word) searches, using the example of the 8 queens problem (a problem he attributes to Gauss in 1850). Begin with the general idea of iterating through all possible solutions, then progressively refine the generation of candidates so that the computer (whether electronic or human) doesn't have to do the full calculation on all candidates. He discusses backtracking. The term itself isn't referenced, but I doubt it was original to this paper. Wirth advocates deferring the actual data structure design until the development of the alogirhtm starts to make it clear what characteristics the data structure should have.

In the acknowledgments, Wirth mentions extensive discussions with Hoare and Dijkstra. Oh, to have been a fly on that wall -- but even with my current brain power, let alone that of a fly, I doubt I could even follow the depth of the discussions!

I couldn't figure out how to get the high-res version of the cover (which I presume still exists), but this article was the cover for the magazine in April 1971.

Michael J. Flynn proposed his taxonomy of parallelism the year I was born. In 1971, Allen B. Tucker and Flynn had an article in CACM that provides a clear description of microcoding in processor design, though tracing back references leads back to at least 1964 when Amdahl himself had a paper on the topic, so I don't think Flynn gets credit for the idea.

In an early premonition of Mechanical Turk, Krolak, Felts and Marble proposed A man-machine approach toward solving the traveling salesman problem. They don't make any mention of paying the human to contribute to the solution, though!

I am going to have to go back and look at Amarel's article on a CS curriculum. Off the top of my head, the view of the field itself is too simplistic, but the figure on applications looks pretty good. Maybe it's just very broad?

Also gotta say, it's impressive that there were multiple competing visions for how to get computers to do integrals for you, all the way back in 1971.

Hope you all have had a good 2023, and have a better 2024. I may try to do one or two more of these before the end of the year, but if don't, see you on the other side...

Annealing: Quantum and Simulated

I don't put a lot of faith in citation counts, but they are one measure of influence. Just a random tidbit on where we are...

Quantum annealing in the transverse Ising model, by Kadowaki and Nishimori, is the origin (as far as I am aware) of quantum annealing as a computational tool -- the technology used by D-Wave, one of the early quantum computing companies. It's a hugely influential idea in our field, though it is a single-purpose computational tool, useful only for finding the ground state of some system. However, it turns out that a lot of optimization problems can be mapped to this problem, so it can be wildly useful if it works well. Unfortunately, it is hard (but maybe not impossible) to do error correction on annealers, so scalability and fidelity are expected to be limited.

Kadowaki and Nishimori cite Optimization by simulated annealing, by Kirkpatrick, Gelatt and Vecchi as an inspiration. This paper is undoubtedly one of the most important papers in all of the history of computation. It probably needs no introduction, but it can be used for a plethora of optimization problems.

And so the scores -- citation counts according to Google Scholar:

• Quantum annealing: 2,159
• (Classical) simulating annealing: 57,085

Wow...

Passings

I just found out that a friend I have known since 1992 has passed away. About a decade older than me, he was a quiet, shy man with a wonderful family. His wife is as outgoing as he was shy, and they complemented each other perfectly. She will be lost without him. Their two daughters, both mid-thirties,  are well established in their lives.

Beyond these simple facts, I am at a loss for what else to say. How do you convey the warmth and intelligence of a friend? The times we spent together, mostly in the 1990s? John's passing will leave a hole in the lives of many.

Workin' on a Saturday

 

I am not the only one working on a Saturday! Dozens of egrets and herons in the Hikiji River -- word must be out that there is sashimi on the hoof (er, fin?) here.

Also, Fuji-san's snow cover was fantastic a couple of weeks ago, then almost disappeared, and is now thin but present.