Why is declarative programming so limited?

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com, or follow me on Twitter.

Interesting idea, though strange that this has not caught on decades ago:

Today’s computers don’t have enough contextual knowledge to make me a sandwich but there are lots of domains where this approach excels. The classic example is SQL databases. Rather than specifying exact data-structures and operations, the user specifies a high-level schema and sends descriptions of queries. It is the responsibility of the database to choose storage types, manage concurrent changes and generate query plans. It makes these decisions based on cost models, runtime information and constrained search (e.g., postgres uses a genetic search algorithm to choose efficient plans for large queries). If the database makes bad decisions, the user can help it out by adding size hints, specifying indexes and overriding query plans. So long as the process of turning intent into plans is transparent and interactive there is no need to invoke a sufficiently smart compiler. A dumb compiler can do the easy but tedious legwork and the human can supervise and correct mistakes. This saves programmer time, makes the intent of the resulting program easier to understand (because it is not cluttered with irrelevant details) and makes it easier to change parts of the system independently (eg adding an index does not require rewriting all of your queries). There is a reason why SQL databases became a standard storage mechanism – this model of programming works incredibly well in this domain.

Indeed, the most painful part of using an SQL database is the interface back to purely imperative programming. The Object-Relational mismatch is often seen as a failure of SQL databases. But consider the relative strengths and learning curves of the two technologies. SQL is often still used for its original goal: enabling non-programmers to mine data. The database handles choice of serialization protocol, data structures for storage and indexing, query algorithms and manages concurrency. For the majority of applications it makes good enough decisions that the user never needs to provide any hints beyond index choice. Imperative programming, on the other hand, requires the user to handle all of these decisions and requires years of practice before the user can reliably build the same kinds of applications. In that light, it is interesting that the popular trend is towards making databases more like imperative languages (NoSQL, object databases) rather than making programming look more like SQL.

To be clear, SQL is a mess. I claim that it is successful despite its many flaws because of the power of the core ideas:

separate goals from plans

separate logical data models from physical data-structures

automatically handle the translation from goals to plans and from logical to physical models

make the translation transparent and allow the user to provide hints or override sections

These ideas allow the programming environment to capture the correct level of detail (‘make me a sandwich’ rather than ‘go to the kitchen, open the cupboard…’). This separates meaning from optimisation giving both the user and the compiler more leeway to change the operational details of the program without modifying the specification. The transparency allows us to build this without requiring a SufficientlySmartCompiler™.

This model is well understood in the database world and is the subject of decades of research. Unfortunately the database world and the programming language world rarely interact and so the results are mostly confined to data management systems and rarely extend to general purpose programming, with the possible exception of the recent revival of the datalog family.

So what would a general purpose language look like if it took these ideas to heart? Our current prototype takes inspiration from Out of the Tar Pit and Programming as Planning, using a temporal logic language to write specifications and a variety of extensible constraint solvers to execute plans. That may sound complicated, but the interface for most users looks like a cross between IFTTT and a simplified version of SQL. Like SQL, the compiler is able to make good decisions for simple programs so the user doesn’t need to think about data structures, algorithms or concurrency. We haven’t yet begun to work on surfacing and altering its decisions in the cases where it needs help, but I’m hopeful that by bootstrapping the compiler and by providing data provenance in the IDE we can go a long way towards easing the learning curve on that front too.

Post external references

  1. 1
    http://lighttable.com/2014/07/18/imperative-thinking/
Source