Declarative vs Imperative

Abelson and Sussman called computer science the study of imperative knowledge, as opposed to the declarative knowledge which constituted the whole of mathematics and the sciences previously. What we’re finding in computing, though, is that the more declarative you are, the better. Declarative code tends to be easier to understand and maintain, even if the implementation of the declarative layer is more complex.

I thought about this when I was thinking about how you’d make an English Rechtschreibung. Should spelling-to-sound rules be given declaratively or imperatively? I thought that imperative rules would be easier to follow in complex cases, like the infamous ‘ough’. But do imperative rules mix as well? It’s also hard to explain the V..e digraph of English imperatively, given how it interacts with suffixes like ‘-ed’, ‘-ing’, ‘-able’, and so on.

URLs, the key innovation of the World Wide Web, were a great invention because they described how to fetch a file, but did it declaratively. Previously you could have shared a shell script or something, but it’s risky to just run random shell code from the internet. But should URLs have been imperative? Even declarative systems tend towards Turing-completeness. HyperCard’s links were imperative — they were written in HyperTalk and thus had the full run of anything you could do with HyperCard. They could thus also depend on outside state. The web equivalent would be if every link was of the form <a href="javascript:window.location='...'">. The fact that web page links generally don’t depend on external state, and the format for their targets is declarative and Turing-incomplete, was undoubtedly a great help to Page and Brin in designing PageRank. Would Google have been invented if the web had Turing-complete links? Backlink tracking in general (which Ted Nelson famously complained about as a missing feature of HTML) would become very hard.

Unfortunately purely-declarative programming languages (in the style of XSLT) tend to be unwieldy to work with for Turing-complete applications.

For parsing data, Björn stipulates that declarative expression as a grammar from which a parser can be generated is superior to writing a parser imperatively. He’s probably right, since even the simplest recursive-descent parsers can have subtle bugs. But it was only once the HTML5 spec imperatively laid a parsing algorithm out in painstaking detail that browsers finally agreed on a single parsing system for HTML, even though the SGML grammar and DTD had been around for years. Also, specifying an error handling and recovery model for a grammar is probably easier if you do it imperatively. The alternative is having to create a grammar that matches every string.