Declarative Metaprogramming

DeclarativeMetaprogramming is using declarative languages (including FunctionalProgramming, but especially referring to LogicProgramming, ConstraintProgramming, and ConstraintLogicProgramming) to write programs that write programs (MetaProgramming). Examples of programs that write programs include compilers, optimizers, aspect-oriented languages, disassemblers, and DeclarativeDeviceDrivers.

The basic requirements of logical DeclarativeMetaprogramming are an inference database of actions & consequences and a specification of policy (desired properties of the system, possibly represented as another database), which may usually be kept distinct. For example, if you have a declarative compiler, you would have a database with properties regarding the OperatingSystem, CPU, Hardware, and link-environment for the target object-file: this would constitute the database of 'actions & consequences'. Second, you would have a specification of policy - for a compiler, this would be a program written in a programming language.

Additional components are necessary to optimize DeclarativeMetaprogramming - and it must be optimized for it to be practical for application to very large systems. The keywords here are: heuristics and strategies. These can be hard-coded into the DeclarativeMetaprogramming itself (e.g. common strategies for performing a search), but they are better represented externally (e.g. in a database of heuristics and strategies) or as annotations to the 'input' to the program (e.g. taking profiler information along with a program as input to an optimizer - the profiler information offers details equivalent to heuristics for making one optimization decision over another). Note that these DO NOT optimize the OUTPUT (the result program); the use of heuristics and strategies as described here only optimizes the declarative metaprogram, reducing the time and resources to get from the input to the result program.

In a sense, heuristics and strategies connect policy to mechanism. They say: "If I want result A,B,C, a good way to do it is to X then Y then Z".

For a traditional compiler, certain strategies are embedded and hard-coded, by hand, directly into the compiler... e.g. "If I need to increment a memory-cell that is the size of one word and aligned on word borders, and I'm using processor of class, I need to call a special memory-increment instruction." These rules are embedded deep inside if/then statements, are difficult to find, are difficult to change, manipulate, or extend. It is a better idea to keep these strategies and heuristics external to the declarative program because they allow for academics and hackers to usefully add new strategies and even program-specific strategies. This can allow programmers to raise the abstraction-level of their programs. That isn't to say some strategies can't be embedded into the declarative metaprogram, but why do it by hand? Write a declarative meta-metaprogram that takes strategies and creates a blazing-fast hardcoded compiler! And even then you can make it so it still accepts 'new' strategies beyond those embedded directly into the compiler (for people who like bootstrapping: one could presumably bootstrap a super-compiler that absorbs new strategies very readily and basically creates a 'successor' super-compiler with which to replace itself.)

Finally, to make DeclarativeMetaprogramming practical for day-to-day use, or especially real-time use, and get it to be blazing fast, it needs to 'learn' heuristics and strategies that weren't embedded into the initial database by hand - even (and especially) program-specific strategies are good things: a desire to optimize an edit-test-compile cycle to the point that it is just as fast as any other (equivalently flexible) language, or perhaps so the optimizer spends 70% of each edit-test-compile cycle finding new optimizations instead of rediscovering old ones (so every edit-test-compile cycle makes the result-program faster every time). Also, keeping program-specific heuristics and strategies for several programs provides the basis for learning: for abstracting program-specific strategies into cross-program strategies based on properties identified as similar across programs. (And even better, since they ARE just heuristics and strategies, there is very little cost if these 'learned' strategies or heuristics turn out to be wrong. A bad strategy simply results in a negative search and thus the only cost is that it wastes a little bit of computation time - and a proper 'learning' system would eventually dismiss a 'strategy' that doesn't appear to be working. This is one of the areas where modern learning AI design would be remarkably successful because the consequences of its predictions become available right away in the form of 'discarded' & 'successful' searches. There are research groups that are exploring the use of DeclarativeMetaprogramming. A lot of work they do is involved in languages to describe the metaprograms themselves - building the tools to build the tools, so to speak.

At the moment, DeclarativeMetaprogramming is in its infancy. I expect, however, that within 20 years it will be the primary means of writing programs that output programs.

At first glance, this seems to be Haskell's monads + logic programming.

That seems an oversimplification - DeclarativeMetaprogramming is not limitied to 'Haskell's monads + logic programming'. But that is one approach that supports some DeclarativeMetaprogramming; it has the necessary ingredients: monads are values describing procedure, thus one can apply a LogicProgramming to automatically construct them relative to some declared goals and a database full of domain facts. More generally, LogicProgramming + FirstClass procedures + PartialEvaluation will, together, buy you DeclarativeMetaprogramming.

In any case, beware the TuringTarpit, and pay attention to ExpressivePower and optimization issues. Even if some dialect of Haskell provides logic programming, it doesn't make it a suitable language for DeclarativeMetaprogramming.

I've found that attribute-driven declarative programming is difficult to get right. The EightyTwentyRule reigns supreme. It seems to me that some kind of imperative "intercept" is needed for the times when declarative is not good enough. EventDrivenProgramming may be promising in this area because it allows one to intercept a process and override it with imperative modifications that the declarative framework cannot handle. An imperative "back door" is probably imperative (pun). I've been leaning toward SoftAbstraction of late as a comprise between reality and idealism. --top

I'm not entirely sure you grokked the meta in DeclarativeMetaprogramming. There isn't any reason you couldn't declaratively describe an EventDrivenProgramming framework or hooks for imperative operations. There is one place where 'imperative' is good for DeclarativeMetaprogramming, but it's the same sort of place where it is good for compilers of any sort: acquisition of resources, linking, etc. It would be nice if compilers could easily reach out and grab, at compile-time, such things as SQL queries to remote databases. But remember that meta is what separates DeclarativeMetaprogramming from DeclarativeProgramming, making it a very clear specialization. You likely wouldn't want your compiler trying to also be your OperatingSystem or WordProcessor.

With regards to the EightyTwentyRule, I certainly would expect it to "reign supreme". Even having a database that describes hardware or operating-system interfaces and relates actions to consequences would be subject to the EightyTwentyRule - once you start listing idiosyncrasies in various pieces of hardware or interfaces, there is simply no getting around it. But you'd need to add these rules somewhere, somehow, no matter which programming paradigm you're using - and for most paradigms, the rules - well, not the rules themselves so much as 'solutions' based on those rules - would be embedded deep in cryptic imperative structures, quite possibly lacking much clear indication of their purpose. One of the very nice properties about DeclarativeMetaprogramming is that these details end up in a readily queryable database - one that has significant value on its own, and one that is far more readily updated or tweaked.

I agree the exceptions to the rule have to go somewhere but at least there are known techniques for dealing with them in imperative programming. See "Dealing with Deviations from Framework" under HelpersInsteadOfWrappers for an example. You basically slip lower into the StepwiseRefinement tree, as low as necessary but not lower. In the worse case you end up re-implementing a leaf, but at least there's a fairly strait-forward pattern to follow that often allows at least partial usage of existing abstractions. I don't know of any such patterns for declarative frameworks: to somewhat gracefully and consistently deal with the exceptions to the rule. -t

There are many patterns for declarative frameworks, TopMind. You have developed a few yourself, such as placing 'device driver' scripts or 'draw shape' scripts in a database, or keeping separate tables to support multi-lingual applications. Common approaches to dealing with problems that don't fit the normal declarative mold include: monads or arrows, linear typing (which restricts how values are copied, thus allows in-place mutations), delayed binding of constraints (single assignment variables or parameterization), various mechanisms to 'hide' parameters so you don't need to explicitly pass them around (SyntacticSugar or macros, DynamicScoping, typeful meta-programming), integration with external resources (as per FRP or IOMonad), typeful metaprogramming, strategies and heuristics, specializations (such as multi-methods), and even humble function passing. Function passing can cover a wide variety of OO and procedural patterns and serves many of the same roles as sticking scripts in the database. Integrating external resources can make it feasible to integrate multiple declarative systems - each using its own abstractions and models - into a larger one... and may do so either directly or via an intermediate pluggable backbone (such as an intermediate database, as with BlackboardMetaphor). In DeclarativeMetaprogramming in particular, provision of strategies is such an important 'out' that it is often given first-class support, allowing one to handle corner cases by writing up an 'initial' whole or partial strategy for them - one that the interpreter is free to fall back upon as a 'default implementation' in the event it is not a SufficientlySmartCompiler that can do you one better. Specialization is also useful, allowing one to describe and integrate corner cases separately from the default strategy, and tends to be used by expressing a specialized 'strategy'.

Patterns are something you learn by doing, that you research or invent when you have need of them. You say you do not know such patterns, but I suspect this stated lack of knowledge is a combination of three things: (1) you don't consider some of the patterns you do know as 'patterns for declarative frameworks', (2) you don't consider some of the declarative frameworks you know (such as HTML) as 'declarative frameworks', (3) you haven't often used declarative languages in the places where you currently favor procedural ones and so you simply haven't had much need to learn corresponding declarative patterns.

If HTML was sufficient, we wouldn't need JavaScript. Although I believe a more powerful markup language, such as something like GuiMarkupProposal, could cover many more common desktop/CRUD idioms, it will probably need some kind of external programming (server or client-side scripting/app) and/or custom widgets for exceptions. -t

We don't need JavaScript, nor do we need HTML. That is to say: HTML is one example of a declarative framework for GUIs, but is hardly a best example, and while its jump to JavaScript was historically convenient, it was in many ways quite premature. One would do well to also observe some of the declarative extensions and variations on HTML, such as CSS and XSLT and SVG and VRML. But there are many other pages dedicated to discussion of GUIs in particular... so we should allow that HobbyHorse to trot on its merry way and attempt to remain on topic.

{CSS is an example of adding structure to an absolute mess to try and clean it up. CSS is like structs in C, or objects in other languages. Thankfully, CSS is not xml or html, it's more like objects or structs. CSS is proof that HTML/XML is a gigantic mess that someone at least tried to add some clarity to. CSS files are easy on the eyes, XML and HTML are bloated with tag crap and less than/greater than signs all over the place.}
See also: DeclarativeProgramming, ConstraintProgramming, ConstraintLogicProgramming, LogicProgramming, DeclarativeDeviceDriver, BusinessRulesMetabase

To a lesser degree: TableOrientedProgramming, DataDictionary

External Resources:

View edit of February 11, 2012 or FindPage with title or text search