eighty-twenty

I recently, upon reading something somewhere that irked me, tweeted the old adage

1. Make it work 2. Make it right 3. Make it fast. So many projects start at 1 and skip to 3, or worse, start at 3… :-(

In reply, Conal Elliott tweeted

What does it mean to work but not be right?

which is a great question. If a program can be said to be “working”, what can that possibly mean except that it is in some sense a “right” program?¹

That’s a pretty decent point. Software is a tool for getting stuff done, after all.

However, I’m not quite ready to abandon my idealism about these things, so let me have a stab at expressing myself more clearly: a “right” program follows the design implied by its own implementation. Implementing programs can lead to improved designs through deeper understanding of the underlying domains.

Now, programs can “work” just fine and yet not follow (or not expose) their own internal logic. It’s when programs are composed that their little warts and kinks start to add up quickly into serious distortions. Let’s revisit the adage:

• Step 1: make it work;
• Step 2: make it right;
• Step 3: make it fast.

I have in my mind the image of two mirrors roughly facing each other (step 1): improving their alignment even slightly (step 2) can cause the tail of reflected images to grow asymptotically longer. Polishing the mirrors (step 3) helps sometimes, but only if they’re in good-enough alignment to begin with.

I don’t care about step 2 for every piece of software. For example, most embedded systems software (microwave controllers, digital watches) is so throwaway and terminal that polishing it beyond a certain point isn’t worth it.²

Foundational software, though, is where a “make it right” step becomes crucial. Software upon which other software is constructed³ has to be made right because of the costs of correcting for design flaws downstream. The total effort involved in working around kinks and warts in a foundational artifact often exceeds the effort required to fix the foundations.⁴

There are countless examples where an almost-right product has gained wide influence without being “made right”: Unix, whose distortions have led to X-windows and monolithic walled-garden applications; Excel, whose distortions particularly with respect to naming and scope have led to horrible kludges and workarounds in any application beyond the trivially simple; AMQP, whose original model was simple and promising, but which is now moving in the direction of the irredeemably complicated; and on, and on.

In each case, lots (and lots) of effort has been spent on optimizing the current artifact, and because very little effort has been spent on learning more about the domain and revisiting the artifact’s design decisions, even more effort has been spent downstream on workarounds for each system’s design flaws.

Lots of these cases have been successful because the software involved has happened to line up well enough with the underlying domain that new kinds of useful work can be done: getting the foundations closer to being “right” has opened up previously-unimagined spaces for new applications. Getting the foundations “right” really does increase the power and the reach of a system.

This is a dialog that popped up just now from iTunes:

It has several noteworthy interactive features:

1. It is not resizable.
2. The two choices are visually identical.
3. Copy-and-paste is disabled for the text of interest.

It also possesses a few less visible but no less interesting attributes:

1. There is no undo once I click OK.
2. iTunes remembers my choice¹ for future insertions of the same CD.

I shall choose at random.

Moral: Current environments for interacting with computers are, putting it mildly, irretrievably broken. Our only hope lies in disruptive innovation.

I’ve just finished building and deploying this website. It uses jekyll to render the content, and the content author uses git to push the changes up to the hosting machine. From there, a nice little chain of programs arranges for the site to be rebuilt on the server and made live:

• A git post-receive hook uses curl to HTTP POST an empty message into a RabbitMQ exchange via the RabbitHub plugin.

• D. J. Bernstein’s daemontools supervises an instance of amqp-consume, which connects to a queue bound to the exchange the post-receive hook delivers into, and whenever a message is received, invokes a shell-script. The command-line for invoking amqp-consume is roughly

  amqp-consume \
      -s localhost \
      --username=... --password=... \
      -e exchangename \
      -A \
      /path/to/rebuild-website-script

• The shell-script invoked for every message from RabbitMQ checks out a fresh copy of the website, compiles it, and deploys the resulting static HTML into the correct location on the file system for Apache to pick up.

• I’m also monitoring the RabbitMQ exchange using the rabbitmq-xmpp plugin talking to my desktop XMPP client, Adium, so whenever anyone does a git push, I get a message appearing in my IM client from exchangename@my.rabbitmq.hostname letting me know a new version of the site has just gone live.

A few days ago, I chanced across http://i.imgur.com/WKeVH.gif on twitter¹. It occurred to me that you could use the same style of diagram to show all three of sin, cos and tan simultaneously. If you project downward at the same time as you project sideways, the two projections will be 90 degrees out-of-phase, just as sine and cosine are.

An hour or so’s hacking in Squeak resulted in the following. (Click here to hide the animation.)

The source code is available for the curious. (Automatic syntax-highlighting courtesy of github. If the previous link doesn’t work for some reason, a less-pretty but almost certainly available link is this one.)

I’ve installed comments, courtesy of disqus. It looks like a very cool system; certainly, installing it and getting it running the way I wanted it was dead straightforward.

Update 2014-08-23: I’ve removed disqus again, in favour of other methods of feedback.

Hee hee! This paper, on Scheme Program Documentation Tools, references docscm :-)

(Update: Shortly after I posted this, I contacted the working-group chair, and he quickly replied to let me know that the group’s settings have been changed. It’s now possible to subscribe to group activity as a spectator. Posting is still restricted to group members, of course, but now others can follow along, which makes me happy.)

It’s almost impossible to follow the scheme-reports-wg1 Google Group, because

• you can’t join the google-group unless you’re part of the working group itself (no joining as a spectator)
• the interfaces available to non-google-group members are insufficient:
  • the RSS/Atom feeds truncate posts, meaning you have to click through to the google-group webpage for reading threads
  • the thread-reading pages themselves are not easy to catch up on (compare Thunderbird, an NNTP client, or even Google Reader here)
• the volume of the list is very high at the moment.

I’d be happy if there were

• a full-content RSS/Atom feed somewhere (for some reason I don’t trust that the existing feed (or perhaps Google Reader) is doing well in keeping posts in chronological order, either); or,
• an NNTP feed of the group (!); or,
• a regular mailman-style mailing list for the group.

The current setup really doesn’t work well for me at all, which is disappointing, as lots of the discussions I’ve overcome the awkwardness of the interface to read are really very interesting.

I’ve just finished reading “Xoc, an Extension-Oriented Compiler for Systems Programming”, by Russ Cox, Tom Bergany, Austin T. Clements, Frans Kaashoek, and Eddie Kohlery. It’s a description of an interesting approach to extensible compilation, for C in this case, that refines a lot of ideas that have been explored previously, bringing them together in a more compositional style than previous extensible compilers have managed to achieve.

One of the key themes in the paper is how to control extension visibility. They describe a couple of approaches they take: one, a type system used to ensure that extensions to abstract syntax are only visible to other extensions when those extensions explicitly declare knowledge of them; and two, an approach from Warth et al.’s “Statically scoped object adaptation with expanders” paper for controlling visibility of extensions to core data structures. I wonder if the latter is used to underpin the former at all.

Regarding the type system approach they take, it’s interesting how it lets the extension writer provide analyses directly in terms of extension abstract syntax, rather than forcing translation to a core language before performing any analysis. We did the latter in Highwire, and the error messages referred to core-language constructs which didn’t map well to source-language syntax: the user was forced to unexpand the macro in their heads to make sense of the output of the compiler. The paper refers to this problem in section 5.2, where the authors write “Since macros cannot access compiler internals, they typically do not even type check their arguments, producing cryptic errors when invoked incorrectly.”

Their compiler, xoc, is a source-to-source translator at the moment, which means it’s not integrated with code generation and backend optimisations and rewrites. It’d be fascinating to build a complete compiler in this style. It’d also be neat to relate this approach to extensible semantics. At the moment the extensions look quite ad-hoc. How could this framework be used, for example, to extend Scheme or ML, where there’s a real semantics underneath it?

One nice feature of xoc is that it tries to preserve hygiene during rewriting. I’m curious as to whether it preserves hygiene to the degree that, say, syntax-case does; their description of the feature was a bit terse for me to be able to tell. In particular I’m interested in how it treats keywords, and where “fresh names” come in to the picture; the paper speaks simply of the code emitter renaming variables “when two distinct variables share a name”.

They use a GLR parser for converting concrete syntax to abstract syntax. One of the benefits of this is its ability to deal with ambiguity, which they exploit in a couple of ways, most ingeniously in their approach to type inference (if you like) for syntax pattern variables. I’d like to learn more about how xoc computes the type of a syntax pattern variable; I wonder if a similar system could be ginned up for use with OMeta?

The laziness of most of xoc’s attribute computations is rather nifty. Code generated relatively late in a compilation, when earlier passes are complete for the rest of the code, can have necessary information filled in lazily on demand, running just those parts of the previous analyses that are required.

I’d like to see some of the pattern-matching and reconstruction features of xoc employed in the context of general purpose computing. It seems to me that using a GLR parser the way they do could effectively provide concrete domain-specific syntax for algebraic data types, not just abstract syntax trees. (The question arises: when is an AST an ADT? Always?) Being able to cons up syntax for new types as easily as Haskell and ML cons up the types themselves seems like a win it’s worth experimenting with. OMeta goes a step in this direction; I hope to explore it myself sometime soon.

This article is an excellent, excellent introduction to Git. It covers the low-level basics, which are much simpler and more elegant than you might be expecting¹, and then reaches up to the less elegant but very powerful world of the Git user interface. Highly recommended.

Most thinking about messaging seems to be framed in terms of process languages, like the π-calculus. In the π-calculus, processes evolve according to an internal clock, the ticks of which correspond to communication events between subprocesses. Many real programming languages based around messaging, like Erlang, are based around similar models, meaning that programmers write programs whose notion of time is implicit, rather than explicit. This can make it difficult to write programs which can reason about differing orders of events or cope with contradictory assertions about the state of the outside world.

An alternative way of dealing with messaging is to take an epistemic reasoning approach closely connected with Functional Reactive Programming (FRP): instead of writing programs that wait for the arrival of specific messages, one at a time, write programs that deal with a queryable monotonically increasing collection of all messages that have arrived or departed so far. Metadata about each message—the sender, the recipient, the time of receipt—are reified as queryable fields attached to each datum in the collection. The state of the program’s world is directly derivable from the program itself and the collection of messages that have been exchanged thus far.

By letting programs step back from the low-level detail of the exchange of messages and take a broader overview of the whole conversation thus far, we let programs behave much more flexibly in the face of such common distributed-systems challenges as lost messages, duplicated messages, out-of-order messages, inconsistent data, and timeouts.

I’ve been off-and-on thinking about these timeless ‘epistemic messaging’ systems for a couple of years now, since a customer project let us investigate their potential suitability for a particular style of long-lived database; while I could write more, and hope to in future, I want to record an observation that occurred to me a couple of days ago about a connection between modeless user interfaces and timeless messaging systems.

In the same way that modal user interfaces constrain the interaction between the user and program into a sequential, question-and-answer style, π-calculus-style programs constrain the interaction between programs in a distributed system into a similar one-thing-at-a-time sequential style, which can lead to programs having a sensitive dependence on message arrival order. Modeless user interfaces, by contrast, make possible a more open-ended, non-linear style of interaction with the user, and epistemic messaging does the same thing for program-to-program interaction: because the state of each program (and thereby its next action) is derived from the collection of messages that have been exchanged, the program can more easily be written to cope with messages arriving in an unusual order. Epistemic-messaging programs can even be written to be able to re-plan (and maybe even re-execute) their actions if received messages were to be permitted to be replaced mid-run.

(Aside: I wonder if there’s a connection here to the Curry-Howard isomorphism? A program operating epistemically over a collection of messages feels like a kind of type/formula, where a similar program in a π-calculus-like system feels like a program/proof.)