What is Declarative Programming?
The Wikipedia entry Declarative Programming is a good place to start. To quote from that entry
| Quote: |
| … declarative programming is interested in the what, but leaves the how up to interpretation. This is why declarative solutions are said to have two independent phases: declaration and interpretation.Declarative languages describe relationships between variables in terms of functions, inference rules, or term-rewriting rules. The language executor (an interpreter or compiler) applies a fixed algorithm to these relations to produce a result. |
Among the languages listed as being declarative in the Wikipedia are Haskell, SQL, WSDL and XML style-sheet transformation. HTML would qualify too. As we can see from that list, there is nothing obviously in common across these languages (consider SQL vs XSLT for example) except that they are all Turing-incomplete. From the Wikipedia entry again
| Quote: |
| The major disadvantage of declarative programming is that it is not Turing-complete � an imperative language can solve any computable problem, but a declarative language can solve only a narrow subset of special problems (those that the very non-universal engine was designed to solve). For example, among imperative languages, Cobol or assembly language can, however awkwardly, solve any problem solvable by Java or Ruby; but any particular declarative language can only solve a problem of optimization, of business rules, of data storage, of data access, of formal logic, or of some small and miscellaneous category. |
But I don’t view the Turing incompleteness as a disadvantage at all. In my earlier post HTML + Javascript: The Benfits of Turing Incompleteness I discuss how combining a Turing incomplete language (HTML) with a Turing complete language (Javascript) results in a better solution than doing everything in Javascript alone (which is technically possible, of course). The HTML interpreter in the browser lets us specify the UI more easily and at a higher level of abstraction. In effect, the HTML is acting like a declarative JFC or MFC API (APIs are declarative sub-languages, a subject for another day!). But unlike the situation with JFC or MFC APIs, the HTML sits in a separatic syntactic space from the Javascript, and that separation proves crucial. Typically a visual aesthetics person designs the HTML while a programmer codes up the Javascript and both are happy.
It is the same story with SQL and Java/C#/PHP/Ruby - the SQL sits in a separate syntactic space, so queries can be optimized after-the-fact by a trained database administrator.
OK coming to some questions I have: Is there a mathematically rigorous definition of declarative programming or is it an imprecise human notion whose only real mathematical property is that it is Turing-incomplete? But that is not a very satisfying definition. And to add to the difficulty, would any Turing-incomplete language qualify as being declarative? Very likely not, yet, any given Turing-incomplete language may be equivalent to or be transformable into a declarative language.
If there is indeed a mathematical definition, is there an algorithm for deciding when a language is declarative? I suspect not.
Apart from their relative ease, one interesting property of declarative languages is that they are provably halting (and therefore provably secure). HTML and SQL are both secure (provably secure?). Could this be the basis of an operational definition of declarative - that every program written in a declarative language provably halts?