Spolsky (and Usdin and Piez) on specs

Posted on by

Joel Spolsky (of Joel on Software) has put up a talk he gave at the Yale Computer Science department a few weeks ago. (Actually, he put it up a few weeks ago, too, shortly after giving the talk. I’m just slow seeing it.)

In it, he has an interesting riff on specifications and their discontents, which feels relevant to the perennial topics of improving the quality of W3C (and other) specs, and of the possible uses of formalization in that endeavor.

If the spec defines precisely what a program will do, with enough detail that it can be used to generate the program itself, this just begs the question: how do you write the spec? Such a complete spec is just as hard to write as the underlying computer program, because just as many details have to be answered by spec writer as the programmer.

This is not the whole story, by any means, if only because specs can and often do explicitly refrain from specifying everything a conforming implementation is to do. But it raises an important point, which is that the more precise one tries to make a spec, the easier it can be for contradictions or other problems to creep into it. (In my experience, this is particularly likely to wreak havoc with later attempts to correct errata.)

In their XML 2007 talk on “Separating mapping from coding in transformation tasks”, Tommie Usdin and Wendell Piez talk about the utility of separating the specification of an XML-to-XML transform (“mapping”) from its implementation (“coding”), and provide a lapidary argument against one common way of trying to make a specification more precise: “Code-like prose is hard to read.” (Has there ever been a more concise diagnosis of many reader’s problems with the XML Schema spec? I am torn between the pleasure of insight and the feeling that my knuckles have just been rapped, really hard. [Deep breath.] Thank you, ma’am, may I have another?)

How do we make specs precise and complete without making them as hard to write, and as hard to read, and as likely to contain insidious bugs, as the source code for a reference implementation?

Cycles in multiplication graphs

Posted on by

[30 December 2007]

I’ve been wondering why there are no cycles longer than 4 steps in multiplication graphs.

I’m not sure that what follows counts as a reason, but it’s been interesting thinking about some properties of multiplication graphs, and the result is a chain of observations that runs like this:

  1. Any number can be multiplied by any number, and produces exactly one result. So in each multiplication graph each node has one outgoing arc, and (in decimal graphs) there are exactly ten arcs.
  2. Since each node has an outgoing arc, there are no dead ends: each path through the graph can be extended indefinitely. One step, two, …, nine, ten, eleven.
  3. Since there are paths of length ten and greater, there must be cycles in the graph. (If a path of length n contains no cycles, then it is incident to n + 1 vertices. So any path of length ten that has no cycles must touch eleven different nodes. We only have ten nodes, so the path must necessarily contain a cycle.)
  4. Multiplication of evens by evens, or evens by odds, produces even numbers. So in the even-numbered graphs (i.e. those for 0, 2, 4, 6, and 8), every arc points to an even digit. And in the odd-numbered graphs, arcs which start at even digits point to even digits.
  5. Multiplication of odds by odds produces odds. So in odd-numbered graphs, arcs which start at odd digits point to odd digits. And these are the only arcs that point to odd-numbered nodes, in any (decimal) multiplication graphs. I repeat: no arcs ever run from even-numbered digits to odd-numbered digits. The even digits form a sort of black hole: once you get in, you never get out.
  6. As a consequence, any cycle must either visit only even digits, or only odd digits. (If it starts on an even digit, then the path can never reach an odd digit. If the cycle starts on an odd digit, and then continues to an even digit, it can never get back to any odd digit, and therefore cannot get back to its starting point.)
  7. So there is an upper bound on the length of cycles in decimal multiplication graphs: five (for the five even digits or the five odd digits). Any cycle of length five must visit either all five even digits or all five odd digits.
  8. Multiplying any number by (a number ending in) zero produces (a number ending in) zero. So in any multiplication graph, the arc that starts at 0 goes to 0, creating a cycle of length 1. In other words, zero is also a kind of black hole.
  9. Because zero is a black hole, no cycle of length > 1 through the even digits can visit the 0 node.
  10. Any cycle of length 5 over the even digits must (as noted above in item 7) visit all the even digits, and thus must visit 0. But no cycle that visits 0 can have length > 1. So: no cycle of length 5 over the even digits can exist.
  11. Multiplying a number ending in 5 by any number produces a number ending in either 0 or 5. (Or, equivalently, every arc beginning at 5 in any decimal multiplication graph goes either to 5 or to 0.) So the set {0, 5} is also a black hole.
  12. Because {0, 5} is a black hole, no cycle of length > 1 through the odd numbers can visit 5.
  13. Any cycle of length 5 over the odd digits must visit 5. But no cycle of length > 1 can visit 5. So: no cycle of length 5 over the odd digits can exist.

Points 6, 10, and 13 seem to prove that for decimal multiplication graphs, the upper bound on cycle length is four. (And in fact there are several cycles of length four, as may be seen by inspection.)

What about multiplication graphs for positional number systems with bases other than ten?

It seems obvious that zero will be a black hole in any positional number system, so there will never be cycles that cover all the digits in the system; for numbers written in base b, there’s an upper bound on cycle length of b – 1.

Also, if b is divisible by two, then the distinction between odds and evens will be visible in the final digit of any number written in base b, in which case there will be an upper bound on cycle length of b / 2, or possibly (b / 2) – 1.

More generally, whenever b is divisible by some number n, the set of multiples of n become a black hole and limit the length of cycles.

Several new questions now come up to occupy our thoughts.

In decimal notation, the fifth power of any number ends with the same digit as the number. Is this true of fifth powers in any positional notation? It seems unlikely.

But is there always, for any base, some power with this property? That is, for any base b is there a power p such that we can usefully write an exercise like the one from Oystein Ore from which we started?

Prove that in the [base b] number system, the [nth] power of any number has the same last digit as the number itself.

It seems plausible, but why should this be so?

And on closer examination, I find it’s not true. But why not?

Here’s the first counter-example I found. For octal numbers, there is no power with this property. In octal, no higher power of a number ending in 2 ends in 2; they all end in 4 or 0.

What property of the base determines (a) whether there is such a p, and (b) what the value of p is? (Conjecture: it has something to do with the factors and the prime factors of b. But what?)

Multiplication graphs, exponentiation graphs, power graphs

Posted on by

[29 December 2007]

As mentioned elsewhere, I’ve been amusing myself reading Oystein Ore, Number theory and its history (New York: McGraw-Hill, 1948; reprint New York: Dover, 1988). I’m not making fast progress, because I’m stuck thinking about some implications of exercise 5 in section 2-3:

Prove that in the decadic number system the fifth power of any number has the same last digit as the number itself.

This has led me to spend time thinking about various kinds of graphs which seem somehow related to this problem and to the more general topics of number theory it illustrates.

Exponentiation graphs

Simplest are perhaps what I’ll call ‘exponentiation graphs‘, one graph for each decimal digit. They show what happens to the last digit of a number when it’s raised to a (non-negative, integral) power. (Brief digression. Yes, to be correct I should say “the last digit in the decimal representation of a number”, not just “the last digit of the number”. But the shorter form is shorter, and in context not really less clear. So if your inner pedant was wanting to correct me just now, please forgive me this informality. And if not, please forgive me for the eighty-three words it is costing me to tell my own inner pedant to put a sock in it.)

The exponentiation graph for the digit 3, for example, starts with (a node for) the digit 1 (which is the final digit of 3, or any number ending in 3, raised to the 0th power), then a node for the digit 3 itself (the first power), then 9 (for any number ending in 3, the square ends in 9), then 7, then 1 again.

Exponentiation graph for the digit 3

Each exponentiation graph starts with (a node for) the digit 1, and in each we can trace a path n steps long to find the digit that will end the nth power of any number which ends in the digit for which the graph is constructed.

All ten of the graphs are drawn on a separate page, if you want them.

Multiplication graphs

Each exponentiation graph is actually just part of a larger graph, which shows for (numbers ending in) each digit d what the final digit x will be when that number is multiplied by a number ending in digit y: there is an arc from y to x.

The full multiplication graph for 3 is as follows; you can see that the exponentiation graph shown above is a subgraph of this.

Multiplication graph for the digit 3

These graphs I’ve also drawn; they are also on a separate page, if you want them. Thank heavens for graphviz!

Power graphs

We can imagine yet another kind of graph, which I’ll call a power graph. One power graph for each non-negative integer n; each graph has ten nodes 0-9, and in each case there is an arc from x to y if and only if a number whose last digit is x, when raised to the power n, produces a result whose last digit is y.

Drawing these is an exercise left for the reader and/or the future.

Ore’s question, recast

Ore’s exercise 2-3.5, translated into graph terms, amounts to this: prove that for each of the ten exponentiation graphs (or: each of the ten multiplication graphs), the paths starting at node 1 with length 1 and length 5 end up at the same node.

This will be true whenever there is a cycle of length 1, 2, or 4 starting from the node after 1 (which is always the node for the digit whose graph this is).

Or another formulation: prove that for the fifth-power graph, each node has an outgoing arc leading back to itself.

And now I can repeat the question that struck me when I started thinking about these graphs the other day: why do all the cycles in the multiplication graphs have length 1, 2, or 4? Why do none of them have length > 4?

I don’t know exactly what a satisfactory answer to this question will look like: what I want is an explanation, any explanation, that makes me say “Oh, right. Of course.“ (In the back of my mind, I’m remembering that morning when I first encountered the proof of the formula for the sum of the interior angles of a convex polygon, and the quiet click my mind made when I understood it. But I’ll take what I can get, click or no click.)

I do have some ideas. But this post is already longer than I intended, and what with drawing the pictures it has taken a lot longer to prepare than I expected. So my current attempts at understanding why there can’t be cycles of length > 4 will have to wait for another entry.

Gravity never sleeps (notations that use eval)

Posted on by

At the opening panel of XML 2007, Doug Crockford waxed eloquent on the weak security foundations of the Web (and managed, in a truly mystifying rhetorical move, to blame XML for them; apparently if XML had not been developed, people’s attention would not have been distracted from what he regards as core HTML development topics).

So during the discussion period I asked him “If you are concerned about security (and right you are to be so), then what on earth can have possessed you to promote a notation like JSON, which is most conveniently parsed using a call to eval? It’s very easy, very concise, and the moment you’ve done it there’s a huge Javascript injection hole in your application.”

Digression: before I go any further I should point out that JSON is easy to parse, and people have indeed provided parsers for it, so that the developer doesn’t have to use eval. And last April, Doug Crockford argued in a piece on JSON and browser security that JSON is security neutral (as near as I can make out, because the security problem is in the code that calls eval when it shouldn’t, so it’s really not JSON’s fault, JSON is just an innocent bystander). So there is no necessary relation between JSON and eval and code injection attacks.

And yet.

Those of sufficient age will well remember the GML systems shipped by IBM (DCF GML) and the University of Waterloo, and lots of people are still using LaTeX (well, some anyway, lots of them in computer science departments). These systems still exist, surely, on some machines, but I will describe them, as I think of them, in the past tense; apologies to those for whom they are still living systems. LaTeX and GML both supported descriptive markup; both provided extensible vocabularies for document structure that you could use to make reusable documents. And both were built on top of a lower-level formatting system, so in both systems it was possible, whenever it turned out to seem necessary, to drop down into the lower-level system (TeX in the case of LaTeX, Script in the case of GML).

Now, in both systems dropping down into the lower level notation was considered a little doubtful, a slightly bad practice that was tolerated because it was often so useful. It was better to avoid it if you could. And if you were disciplined, you could write a LaTeX or GML document without ever lapsing into the lower-level procedural notation. But the quality of your results depended very directly on the level of self-discipline you were able to maintain.

The end result turned out, in both cases, to be: almost no GML or LaTeX documents of any size are actually pure descriptive markup. At least, not the ones I have seen; and I have seen a few. Almost all documents end up a mixture of high- and low-level markup that cannot be processed in a purely declarative way. Why? Because there was no short-term penalty for violating the declarativity of the markup, and there was often a short-term gain that, at the crucial moment, masked the long-term cost. In this respect, JSON seems to be re-inventing the flaws of notations first developed a few decades ago.

To keep systems clean, you need to drive the right behavior.

JSON makes very good use of Javascript’s literal object notation. But it’s a consequence of this fact that a JSON message can conveniently be processed by reading it into a variable and then running eval on the variable. (This is where we came in.) The moment you do this, of course, you expose your code to a Javascript injection attack.

To say “You don’t have to use eval — JSON has a very simple syntax and you can parse it yourself, or use an off the shelf parser, and in so doing protect yourself against the security issue,” seems to ignore an important fact about notations: they make some things easier and (necessarily) some things harder. They don’t force you to do things the easy way; they don’t prevent you from doing them the hard way. They don’t have to. The gentle pressure of the notation can be enough. It’s like gravity: it never lets up.

If the notation makes a dangerous or dirty practice easy, then the systems built with it will be spotlessly clean if the users have the self-discipline to keep it clean. For most of us, that means: not very clean.

OK, end of digression.

When I asked my question, Doug Crockford answered reasonably enough that browsers already execute whatever Javascript they find in HTML pages they load. So JSON doesn’t make things any worse than they already were. (I’m not sure I can put into words just why I’m not finding much comfort in that observation.)

But there is a slight snag: Javascript isn’t used only in the browser. Since the conference, my colleague Thomas Roessler has written a number of blog entries outlining security problems in widgets which use Javascript; most recent is his lightning talk at the 24th Chaos Communication Congress.

Be careful about slopes, slippery or otherwise. Gravity never sleeps.

Does XML have a future on the Web?

Posted on by

Earlier this month, the opening session of the XML 2007 conference was devoted to a panel session on the topic “Does XML have a future on the Web?” Doug Crockford (of JSON fame) and Michael Day (of YesLogic) and I talked for a bit, and then the audience pitched in.

(By the way — surely there is something wrong when the top search result for “XML 2007 Boston” is the page on the 2006 conference site that mentions the plans for 2007, instead of a page from the 2007 conference site. Maybe people are beginning to take the winter XML conference for granted, and not linking to it anymore?)

Michael Day began by pointing out that in the earliest plans, the topic for the session had included the word “still”, which had made him wonder: “Did XML ever have a future on the Web?” He rather thought not: XML, he said, was yet another technology originally intended for the browser that ended up on the server, instead. No one serves XML on the Web, he said, and when they try to something as simple as XHTML, it’s not well-formed. (This, of course, is a simplistic caricature of his remarks, which were a lot more nuanced and thoughtful than this. But of course, while he was speaking I was trying to remember what I was supposed to say; these are the bits of his opening that penetrated my skull and stuck.)

Doug Crockford surprised me a bit; from what I had read about JSON and his sometimes fraught relations with XML, I had expected him to answer “No” to the question in the session title. But he began by saying quite firmly that yes, he thought XML had a very long future on the Web. He paused while we chewed on that a moment, before putting in the knife. We know this, he said, because once any technology is deployed, it can take forever to get rid of it again. (You can still buy Cobol compilers, he pointed out.) If I understood him correctly, his view is that XML (or XHTML, or the two together with all their associated technologies) has been a huge distraction for the Web community, and nothing to speak of has been done on HTML or critical Web technologies for several years as a result. We need, he thought, to rebuild the Web from its foundations to improve reliability and security.

It gives me some regret now that I did not interrupt at this moment to point out that XHTML and XForms are precisely an effort (all in all, a pretty good one) to improve the foundations of the Web, but I wasn’t quick enough to think of that then. (I also didn’t think to say that being compared to Grace Murray Hopper, however indirectly and with whatever intention, is surely one of the highest compliments anyone has ever paid me. Thank you, Doug!) And besides, it’s bad form to interrupt other panelists, especially when it’s your turn to speak next.

Since I have cut so short what Michael Day and Doug Crockford said, I ought in perfect fairness to truncate my own remarks just as savagely, so the reader can evaluate what we said on some sort of equal footing. But this is my blog, so to heck with that.

Revised slightly for clarity, my notes for the panel read something like the following (I have added some material in italics, either to reflect extempore additions during the session or to reflect later pentimenti). I’d like to have given some account of the ensuing discussion, as well, but this post is already a bit long; perhaps in a different post.

I agree with Doug Crockford in answering “Yes” to the question, but we have different reasons. I don’t think just that XML has a future because we can’t manage to get rid of it; I think it ought to have a future, because it has some properties it’s hard to find elsewhere.

1 What do we mean by “the Web”?

A lot depends on what we mean by “the Web”. If we mean Web 2.0 Ajax applications, we may get one answer. If we mean the universe of data publicly accessible through HTTP, the answer might be different. But neither of these, in reality, is “the Web”.

If there is a single central idea of the Web, it’s that of a single connected information space that contains all the information we might want to link to — that means, in practice, all the information we care about (or might come to care about in future): not just publicly available resources, but also resources behind my enterprise firewall, or on my personal hard disk. If there is a single technical idea at the center of the Web, it’s not HTTP (important though it is) but the idea of the Uniform Resource Identifier, a single identifier space with distributed responsibility and authority, in which anyone can name things they care about, and use their own names or names provided by others, without fear of name collisions.

Looked at in this way, “the Web” becomes a rough synonym for ‘data we care about’, or ‘the data we process, store, or manage using information technology’. And the question “Does XML have a future on the Web?” becomes another way of asking “Does XML have a future?”

Not all parts of the Web resemble each other closely. In some neighborhoods, rapid development is central, and fashion rules all things. In others, there are large enterprises for whom fashion moves more slowly, if at all. Data quality, fault tolerance, fault detection, reliability, and permanence are crucial in a lot of enterprises.

The Web is for everyone. So a data format for the Web has to have good support for internationalization and accessibility.

Any data format for “the Web” must satisfy a lot of demands beyond loading configuration data or objects in a client-side Javascript program. As Murata Makoto has often said, one reason to be interested in XML is that it offers us the possibility of managing in a single notation data that for a long time we held separately, in databases and in documents, managed by separate tool sets. General-purpose tools are sometimes cumbersome for particular specialized forms of data, but the provision of a common model and notation is a huge win; before I decide to use another specialized notation, I want to think hard about the costs of yet another notation.

I think XML has a future on the Web because it is the only format around that can plausibly be used for such a broad range of different kinds of data.

2 Loose coupling, tight coupling

One of the important technical properties of the Web is that it encourages a relatively loose coupling between parts of the larger system. Because the server and the client communicate through a relatively narrow channel, and because the HTTP server is stateless, client and server can develop independently of each other.

In a typical configuration there are lots of layers, so there are lots of points of flexibility, lots of places where we can intervene to process requests or data in a different way. By and large, the abstractions are not very leaky, so we can change things at one layer without disturbing (very much) things in the adjoining layers.

In information systems, as in physical systems [or so I think — but I am not a mechanical engineer], loose couplings incur a certain efficiency cost, and systems with tighter couplings are often more efficient. But loose coupling turns out to be extremely useful for allowing diverse communities to satisfy diverse needs on the Web. It turns out to be extremely useful in allowing the interchange of information between unlike devices: if the Web had tighter coupling, it would be impossible to provide Web access to new kinds of devices. And, of course, loose coupling turns out to be a good way of allowing a system to evolve and grow.

One of the secrets of loose coupling is not to expose more information between the two partners in information exchange than you want to.

And in this context, some of the notations sometimes offered as alternatives to XML (at least in some contexts) — or for that matter, as uses of XML — have always made me nervous. We’re building a distributed system; we want to exchange information between client and server, while limiting their mutual dependencies, so that we can refactor either side whenever we need to. And you want me to expose my object structures?! Are you out of your mind? In polite company there is such a thing as too much information. And exhibiting my object structures for the world to see is definitely a case of too much information. I don’t want to see yours, and I don’t want you to see mine. Sorry. Let’s stick to the business at hand, and leave my implementation details out of it.

So, second, I think XML has a future on the Web because (for reasons I think are social as much as technical) the discipline of developing XML vocabularies has a pretty good track record as a way of defining interfaces with loose coupling and controlled exposure of information.

3 Publication without lossy down-translation

There were something like two hundred people actively involved in the original design of XML, and among us I wouldn’t be surprised to learn that we had a few hundred, or a few thousand, different goals for XML.

One goal I had, among those many, was to be able to write documents and technical papers and essays in a descriptive vocabulary I found comfortable, and to publish them on the Web without requiring a lossy down-translation into HTML. I made an interesting discovery a while ago, about that goal: we succeeded.

XML documents can now be read, and styled using XSLT, by the large majority of major browsers (IE, Mozilla and friends, Opera, Safari). It’s been months since I had to generate an HTML form of a paper I had written, in order to put it on the Web.

I know XML has a future on the Web because XML makes it easier for publishers to publish rich information and for readers to get richer information. No one who cares about rich information will ever be willing to go back. XML will go away only after you rip it out of my cold, dead hands.

[After the session, Norm Walsh remarked “and once they’re done with your cold dead hands, they’ll also have to pry it out of mine!”]

One reason to think that XML has found broad uptake is the sheer variety of people complaining about XML and the contradictory nature of the problems they see and would like to fix. For some, XML is too complicated and they seek something simpler; for others, XML is too simple, and they want something that supports more complex structures than trees. Some would like less draconian error handling; others would like more restrictive schema languages.

Any language that can accumulate so many different enemies, with such widely different complaints, must be doing something right. Long life to descriptive markup! Long life to XML!