Wednesday, January 21, 2009

Domain specific solvers

In the post on indexed compositions i neglected to mention several key features of the constraint language that is generated from the term language. i did mention that we have a completeness property: any collection that can be generated ("relationally") will be generated as an expression in the generated language.

It also turns out that the language is very "tight". We don't have a lot of "fluff" in the sense of ad hoc operators. This has some pros and cons in terms of applications. In my experience, real world applications (or rather application developers) require richer languages. They need syntactic sugar to make code readable and maintainable. A good example is in the domain of communications. Certain kinds of communications-based application domain really, really benefit from synchronous communication patterns. If the underlying communications library provides asynchronous primitives then it is much better to pay the cost of developing the synchronous pattern as a library than to replicate the code over and over. This is standard practice for all the reasons we know and love. By way of analogy, the minimality of the generated constraint language might make it more of an intermediate language from the point of view of developing applications. For example, the constraint language generated from set gives a certain minimal presentation of the boolean operations. These can readily be extended with the usual DeMorgan laws to a much richer presentation of the boolean operations that might be more convenient for certain kinds of applications.

On the other hand, minimality is good from the point of view of automated analysis. This is one of the driving design considerations for having minimal intermediate languages. The number of examples of this is too numerous to list, so i won't. One application of automated analysis that is very appealing in the setting of indexed compositions is identifying domain specific solvers. Having a tight, minimal specification of the constraint language enables -- in principle -- a means to automatically deduce from the specification which of a population of solvers are candidates to find the solutions to the constraints. In fact, there is nothing in the semantics of indexed compositions that prevents the simultaneous application of multiple different domain specific solvers -- with some policy for how to merge results -- such as first reply wins. This is a direct consequence of a lazy interpretation of the underlying denotation of the comprehension.

No comments: