MadMode

Remembering Modula-3

Systems Programming with Modula-3 has been on my wishlist for years, but after reading the feedback from Tim Bray's Wide Finder project, I finally got my very own copy.

One of the reactions, Finding Lisp, observes:

Most popular programming languages have the same simple threads+locks paradigm that was popularized with pthreads and Java.

But Java made everything a monitor.

I learned pthreads while working on a big horrible C++/DCE project, Dazel (later bought by HP). One of the guys there (Jim W?) loaned me his copy of Systems Programming with Modula-3, where chapter 4 is a copy of An Introduction to Programming with Threads by Birrell. It's probably a good thing that we never followed thru on our dreams to rewrite the whole project in Modula-3, but it was good to know about partial orders on locks and such while taming the pthread libraries (... and the C++ exception runtimes; what a nightmare!)

And anybody who had studied the Modula-3 Thread and IO design would know better than to make everything a monitor.

A lot of good stuff from Modula-3 lives on in python, and some in Java, but DEC got bought by Compaq which got bought by HP, and a lot of the DEC SRC goodies seem to be disapearing from the net.

The wikipedia article on Modula-3 has a "This article does not cite any references or sources" tag since July 2006. That looks silly, since a number of books and articles are listed. I can see some unsupported claims, though, so I ordered my own copy of SPwM3 so I can separate some of the verifyable claims from the speculation.

I'd also really like to find a host (other than the wayback machine) for the hypertext version of the SRC Modula-3 sources; it's a gold-mine of software engineering theory and practice; for example, from Fingerprint.m3:

The original fingerprint interface offered at SRC did not include the procedure Combine. The Vesta configuration management project built a system that cached intermediate results for large software builds. Abstractly, this is a special case of the common subexpression problem mentioned previously, and the project used fingerprints as keys in the cache. It is instructive to learn what happened.

You might think that a simple way to solve the common subexpression problem without Combine would be to fingerprint the texts that result from printing the expressions represented by the nodes of the DAG. But if the DAG is not a tree, this is a serious error, since the length of the strings produced by printing a DAG can grow geometrically with its size, and therefore the probabilistic guarantee becomes useless even for quite small DAGs.

Avoiding this error, the Vesta group computed the fingerprint of a node by concatenating the node's label with the {\it fingerprints} of its children---treating these fingerprints as 8-byte texts--- and fingerprinted the resulting text. With this strategy, the number of texts fingerprinted is proportional to the number of nodes of the DAG, and the total length of these texts is proportional to the number of edges of the DAG. Thus the method appears efficient and sound.

Alas, the method is not sound. Recall that the probabilistic guarantee is valid only if the strings being fingerprinted are independent of the magic number. But fingerprints themselves are dependent on the magic number, so the probabalistic guarantee is invalid whenever fingerprints are fingerprinted. The Vesta group was soon debugging an unexpected collision.

The moral is simple: the procedure Combine is a convenience, but it is also much more than a convenience. It should be the only way that you ever generate a fingerprint from another fingerprint. In particular, never treat a fingerprint as text to be passed to FromText.

Maybe the python foundation would like to host it? I'm pretty sure Guido has a fondness for Modula-3.