The purported easiness of well-formedness

Posted on by

When I started learning HTML around 2002 I was told that HTML was on the way out and would eventually be replaced by a new version known as XHTML:

If you want your site to work well in today’s browsers and non–traditional devices, and to continue to work well in tomorrow’s, it’s a good idea to author new sites in XHTML…

Jeffrey Zeldman

XHTML is HTML reformulated to adhere to the XML standard. It is the foundation language for the future of the Web.

Musciano and Kennedy

It turns out this never really came to pass. XHTML was quite popular for a time but has lately fallen out of favour. For example, W3Techs offers data showing that XHTML usage peaked in 2012 when it was used in over 65% of the websites that they surveyed. Today their data shows that it is used in under 7% of websites.

XHTML has the interesting feature that it is based on XML, and XML processors are required to handle syntax errors incredibly strictly:

…if your document contains a parse error, the entire document is invalid. That means if you bank on XHTML and make a single typo somewhere, nothing at all renders. Just an error.

This sucked. It sounds okay on the face of things, but consider: […] generating it dynamically and risking that particular edge cases might replace your entire site with an unintelligible browser error? That sucks.

Eevee

Back when XML was being standardized a few people thought this was not a good idea, and the issue was hotly contested. In this post I want to consider one of the claims put forward by those in favour of XML’s lack of error-handling: that it is very easy to make well-formed XML documents. This was repeatedly stated as a point in favour of requiring no error recovery in XML:

Well-formedness should be easy for a document to attain.

Tim Bray

We went to a lot of work to make well-formedness easy. It is a very low bar to get over […] the standard required to achieve reliable interoperability is so easy to explain and to achieve.

Tim Bray

well-formedness is so easy that it isn’t a significant burden on anyone

Tim Bray

No information provider who does even the most cursory checking will publish non-WF docs […] no user will ever be in the position that he can’t see an “interesting” doc just because it’s non-WF, because there won’t be any

Tim Bray

Anyone who can’t make a syndication feed that’s well-formed XML is an incompetent fool.

Tim Bray

Even back then not everyone was convinced about the easiness of producing well-formed XML:

the argument seems to be, don’t worry. Since most if not all XML documents will be machine generated they will all be well formed. I don’t buy it! Programmers are human to and make as many errors as prose authors.

Dave Hollander

Anyone who has a single error in his document is a bozo? Ahem. I don’t buy any of this.

Terry Allen

I like the concept of WF very much, but I’m by no means confident that what goes towards WF in XML really meets my intuitive notion. Indeed, I believe that WF in XML may not be quite as easy to achieve as it’s made out.

Arjun Ray

These kinds of arguments seem hard to settle one way or the other. Bray says that XML well-formedness is easy to obtain. Others disagree. No hard evidence is offered either way, though Bray has four rules that he claims are easy and enforce XML well-formedness. Even if we assume the rules are easy I’ve learned that “easy” is not an intrinsic property; what is easy to one person is not at all easy to another. It would seem as if there is no way to resolve the issue of how easy well-formedness really is.

However, this discussion took place in 1997. We now don’t have to speculate about how easy it is to author XML: we have the benefit of being able look back at history and see what actually happened. The XML specification was published as a W3C recommendation in 1998. XHTML reformulated HTML in XML and was published as a W3C recommendation in 2000. With over 2 decades of XHTML documents being published we don’t need to argue how hard or easy it is to obtain well-formedness—we can determine how hard it is in practice.

Now, in most cases XHTML documents are likely parsed by a browser as HTML and not as XML. This means that well-formedness errors would not be shown on the page because HTML parsers are lenient. Nevertheless, an XHTML document is—by virtue of being XHTML—also an XML document, regardless of how it is parsed. Those authoring XHTML are therefore also subject to the well-formedness rules of XML. Of course, that shouldn’t be a burden for most documents if well-formedness is such a low bar.

Since most modern websites don’t use XHTML anymore I collected data from the Wayback Machine archive. I collected the list of the top websites in the world published by Alexa at the end of 2009. Then I downloaded the homepage of the top 200 sites as they appeared on January 1, 2010 (or the closest date available in the Wayback Machine). Of the top 200 sites I was successful in retrieving data for 195 of them. Of those, 81 websites used XHTML 1.0 Transitional, 21 sites used XHTML 1.0 Strict, and 1 website (bet9ja.com) used XHTML+RDFa 1.0.

I then checked for well-formedness of each document using xmlwf. 11/81 of the XHTML 1.0 Transitional sites were well-formed, 7/21 of the XHTML 1.0 Strict sites were well-formed, and the single XHTML+RDFa 1.0 document was well-formed. That’s right: 82% of websites were ill-formed.

Regardless of how low a bar you consider well-formedness, the fact of the matter is that most webpages didn’t meet that bar in 2010, when XML had already been out for over a decade. And these weren’t pages designed by clueless developers, either. Just imagine how much effort goes into the development of the a top-200 webpage!

I wasn’t able to find much previous work on well-formedness in practice but a 2005 post on the Google Reader blog did a similar thing for RSS and Atom feeds which are typically sent to browsers as XML. In that post they tabulate the top 22 separate errors they found which prevented feeds from being well-formed and estimated that 7% of all feeds had at least one of those errors.

Hence, Bray’s prediction that “there won’t be any” non-wellformed XML documents was unrealistically optimistic. Bray also goes as far as calling anyone who doesn’t produce well-formed XML an “incompetent fool” on his blog. Note that Bray is the co-editor of the XML specification and one of the foremost XML experts in the world. He more than perhaps anyone else in the world is in a position of being able to publish well-formed XML documents and—naturally enough—his blog is published in XHTML 1.1. Amusingly, the post claiming those who don’t create well-formed XML are incompetent contains an unescaped & and as a result is itself not well-formed.

<p>By the way, it doesn’t make any difference whether the ill-formedness is grossly-missing tags as above or a single unescaped <code>&</code>; in these kinds of apps, if it isn’t XML, this is evidence of serious breakage.</p>

Irony: forgetting to escape the & in a blog post claiming that a single unescaped & is incompetence.

In the blog post Bray claims to have run the post through an XML checker and in fact uses this very example to argue why well-formedness is so easy to achieve in practice. But his blog post was written nearly twenty years ago and in that time there has undoubtedly been many server upgrades, edits to posts, software updates to his blogging scripts, etc. Any number of subtle and nearly imperceptible changes could introduce a well-formedness error and indeed it seems that page has been ill-formed for years.

I think this underscores just how poor humans are at technical details like well-formedness. Yes, the rules might seem simple in the abstract, but what about a minor typo you make two decades from now as a part of a routine update? What about the thousands of edge cases you didn’t consider at first? The unfortunate lesson that we can take from the history of computing is that bugs fester in even the very simplest programs. Yes, the rules may be easy—but that makes them deceptive if you need to get them exactly right.

Ramanujan summation

Posted on by

I just came across a way that the amazing mathematician Ramanujan developed of assigning a value to certain divergent series. I found it interesting, so I want to share a short summary of it here. It is based on the Euler–Maclaurin formula
\begin{align*} \sum_{k=\alpha}^\beta f(k) &= \int_\alpha^\beta f(t)\,dt + \frac{f(\alpha)+f(\beta)}{2} \\ &\quad+ \sum_{k=1}^n \frac{B_{2k}}{(2k)!}\Bigl(f^{(2k-1)}(\beta)-f^{(2k-1)}(\alpha)\Bigr) + R_n \end{align*}where $B_{2k}$ denotes the $(2k)$th Bernoulli number, $f$ has $2n+1$ continuous derivatives on $[\alpha,\beta]$ with $\alpha$, $\beta$, and $n\geq0$ being integers, and $R_n$ is the remainder term given by
\[ R_n = \int_\alpha^\beta \frac{B_{2n+1}(t-\lfloor t\rfloor)}{(2n+1)!}f^{(2n+1)}(t)\,dt . \] Continue reading →

The importance of direction

Posted on by

Lately I’ve been reflecting on the impact that having a direction (or lack of it) has had in my life. For a long time now—since around the time I first set foot on a university campus—it’s been clear to me that I would be doing and writing about mathematics for the rest of my life. However, perhaps because I have never been particularly interested in thinking about money I never necessarily assumed that I would be paid to do mathematics. My expectation was that I might need to have a day job to support myself and my mathematical hobby.

Recently, I’ve been thinking that being paid to do mathematics would be great because it would allow me to devote more time to it. For example, I am quite proud of my latest paper—but it took a lot of time to write, and would have taken even longer if I didn’t already have a job as a postdoctoral researcher. One of my previous papers was written during evenings and weekends since at the time I was working full-time at an internship and it wasn’t ideal.

Thus, I’ve been doing the things necessary to apply to academic positions like putting together a research statement. During this process the importance of direction has been made abundantly clear to me and I can’t help but lament the amount of time I spent as an undergraduate and graduate student with unclear direction and ridiculous misconceptions.

For example, as an undergraduate student I studied the Ramanujan–Nagell equation and came up with a new solution for it that I hadn’t seen published anywhere. My thought was: this is so cool, I have to share this with the world. So I wrote a short report, gave a copy to one of my professors who I thought might be interested, and uploaded a copy to my website. But what to do beyond that? My thinking was: I don’t know how to get it published somewhere, but I do know how to make it accessible to anyone who wants to read it via the Internet. I told myself that 99% of the value comes from writing the report and I didn’t need the additional 1% “seal of approval” that comes from getting it published. Now I know this is totally backwards—at least when it comes to job applications almost all of a paper’s value is derived from being published.

Looking back, my advice to myself would absolutely be to try to get the report published. Maybe I could’ve gotten it published and maybe not, but either way it would have been a very valuable learning experience. Incidentally, the report does seem to be of value to some people: it’s been cited by two OEIS entries, two published papers, a PhD thesis, and Noam Elkies recently gave a talk referencing it (!!!):

We state several finiteness theorems, outline some of the connections among them, explain how a finiteness proof can be ineffective, and (time permitting) sketch Nagell’s proof and an even more elementary one discovered only 12 years ago by C. Bright.

Maybe I’ll come back to that result and get it formally published some day, but I already have more than enough papers on the table. At the very least it’s encouraging to know that I’m in no danger of running out of material to research and write about anytime soon. Even more importantly, I’ve learned how important direction is to achieving your dreams.

Five years of dancing

Posted on by

Five years ago I decided to start a new project which was totally different than anything I’d done before in my life: I decided to become a salsa dancer. The impetus for this was a drive to improve my overall well-being by deliberately pushing my boundaries—up until 2013, I spent the majority of my life on academic pursuits and the extent to which I focused on this had created a severe imbalance. In short, I didn’t have many friends, I was generally uncomfortable socializing with people, and even more to the point: Girls didn’t like me, at least not in “that” way.

I signed up for and took my first salsa class on May 28, 2013. I was absolutely terrified and struggled with the class but nevertheless committed to giving it my best effort for at least five years. It felt like a last-ditch effort: I wanted to improve at forming relationships but I had no idea what I could do to change. I didn’t know if salsa dancing would help, but I reasoned that the terror and incompetence that I felt while salsa dancing was temporary and would disappear once I had years of dancing under my belt. In short, I expected that dancing would eventually become second-nature if I kept at it—and then if nothing else I would be in a better position to improve my social relationships.

I kept that commitment I made 5 years ago, and since then the longest I’ve gone without salsa dancing has been the 1–2 weeks during the Christmas break. The result? Not only has my hypothesis that salsa dancing would eventually feel natural been confirmed, the effects on the rest of my life have been nothing short of transformative. I have a healthy social circle of friends, I’m much less shy to the point I enjoy socializing, and I’m much more comfortable using my physical body for things, even starting other hobbies like weight lifting. And yes, I started getting attention from girls.

For me, salsa dancing was a vehicle for changing one of the things most resistant to change but probably the thing I most needed to change: my identity. Previously my identity was the nerd who excelled at school but struggled at social relationships and as long as I thought of myself in those terms my ability to form social relationships was severely crippled. I had prioritized academics to the exclusion of everything else, and I was proud of it.

What I came to learn was that while taking actions that are at odds with one’s identity feels incredibly awkward and painful, it is possible to rewire your identity with consistent effort applied over an extended period of time. This was far from easy, as my identity resisted the change at every step of the way, and I would often slip back into my older more comfortable identity that I had built up over two decades. It would happen reflexively: One Thursday when I had been dancing for over a year I remembered that I would be going out that night to dance. A sudden wave of fear swept over me as I realized that I was going to have to ask girls to dance that night—immediately followed by a wave of relief when I remembered that I did that every week.

Because I started from an identity of almost the polar opposite of a salsa dancer, my case essentially provides a lower-bound on the amount that it is possible to change. I’ve taught and assisted many people taking salsa classes and there are only a few I’ve seen that I would consider less skilled than myself when I started. Nowadays people don’t believe me when I tell them how much I struggled for years in ways which at the time felt scarring. As an example of how exceptionally incompetent I was when I started, my very first salsa social dance of my life was interrupted by a random bystander who asked if I was okay or needed help. 😂

In fact, I’m still struggling, because there is no end point you reach when you know it all. This is perhaps the biggest lesson I’ve learned from 5 years of dancing: the struggle itself is inherently meaningful, and I’ve learned to embrace the struggle as a purposeful and worthwhile part of learning and growing.

The value of the trigonometric harmonic series revisited

Posted on by

Shortly after my last post I realized there was a simpler way of determining the exact value of the series $\sum_{n=1}^\infty\cos n/n$. Instead of following the method I previously described which required the intricate analysis of some integrals, one can simply use the formula

\[ \sum_{n=1}^\infty\frac{a^n}{n} = -\ln(1-a) \]

which is valid for $a\in\mathbb{C}$ which satisfies $\lvert a\rvert\leq 1$ and $a\neq 1$. This comes from a simple rewriting of the so-called Mercator series (replace $x$ with $-x$ in the Taylor series of $\ln(1+x)$ and then take the negative).

Then we have

\begin{align*}
\sum_{n=1}^\infty\frac{\cos n}{n} &= \sum_{n=1}^\infty\frac{e^{in}+e^{-in}}{2n} \\
&= -\bigl(\ln(1-e^i)+\ln(1-e^{-i})\bigr)/2 \\
&= -\ln\bigl((1-e^i)(1-e^{-i})\bigr)/2 \\
&= -\ln(2-e^i-e^{-i})/2 \\
&= -\ln(2-2\cos1)/2 \\
&\approx 0.0420195
\end{align*}

since $\lvert e^i\rvert=\lvert e^{-i}\rvert=1$, but $e^i\neq1$ and $e^{-i}\neq1$.

The value of the trigonometric harmonic series

Posted on by

I’ve previously discussed various aspects of the “trigonometric harmonic series” $\sum_{n=1}^\infty\cos n/n$, and in particular showed that the series is conditionally convergent. However, we haven’t found the actual value it converges to; our argument only shows that the value must be smaller than about $2.54$ in absolute value. In this post, I’ll give a closed-form expression for the exact value that the series converges to.

Continue reading →

The names in boxes puzzle

Posted on by

This is one of the best puzzles I’ve come across:

100 prisoners have their names placed in 100 boxes so that each box contains exactly one name. Each prisoner is permitted to look inside 50 boxes of their choice, but is not allowed any communication with the other prisoners. What strategy maximizes the probability that every prisoner finds their own name?

I heard about this puzzle years ago, spent several days thinking about it, and never quite solved it. Actually, I did think of a strategy in which they would succeed with probability over 30% (!), which was the unbelievably-high success rate quoted in the puzzle as I heard it posed. However, I ended up discarding the strategy, as I didn’t think it could possibly work (and probably wouldn’t have been able to prove it would work in any case).

Revisiting a lemma

Posted on by

We’ve discussed before the “trigonometric harmonic” series $\sum_{n=1}^\infty\cos n/n$. In particular, we showed that the series converges (conditionally). The argument involved the partial sums of the sequence $\{\cos n\}_{n=1}^\infty$, and we denoted these by $C(m)$. The closed-form expression we found for $C(m)$ involved the quantity $\cos m-\cos(m+1)$; in this post we show that this expression can also be written in the alternative form $2\sin(1/2)\sin(m+1/2)$.

Continue reading →