[Haskell-cafe] [IETF Apps meeting] A Theory of Templating Languages

The IETF (http://www.ietf.org/) holds a meeting of its Application Area and is looking for papers. In a position paper, Joe Gregorio asked for information about the theory of templating languages. Giving the interest here in DSLs and conceptualization, he may find on this list the help he wants and the references he searches:

From: "Joe Gregorio" Date: December 14, 2007 8:20:17 AM PST Subject: Re: Position papers due Dec 14

Here is my brief position paper:

Working on the URI Templating specification has made me realize that there is a pretty substantial hole in computer science theory: a lack of a theory of templating languages. For example, the current version of URI Templates is not Turing-complete, which excludes a whole bunch of possible attacks. In the specification I state:

On the balance, the template processing is not Turing complete, thus avoiding a number of security issues, ala the billion-laughs attack of XML DTDs.

I was rightly called out on this on the W3C URI mailing list:

This reads a little odd, as not being Turing-complete is not sufficient to avoid the attack. (And DTDs are not Turing-complete either.)

The criticism is correct. The problem is that I don't know of any finer grained levels of classifications of templating languages than Turing/non-Turing, and not only for security reasons, but for general capabilities.

For example, if there were classes of templating languages, I could say that URI Templates fell into 'class X', and if that class had a known set of limitations and capabilities then I could say that URI Templates thus had those limitations and capabilities. The weakness to the billion laughs attack comes from two facets of DTD usage, the first being that templates can be defined in terms of other templates, and the second is that the depth of template definition, in terms of other templates, isn't limited. But the converse isn't true, that is, I don't have a general theory of templating to lean on that says since URI Template expansions are never defined in terms of other expansions then URI Templates are immune to such resource exhaustion attacks.

I did find one paper that makes a start at such work, "Enforcing Strict Model-View Separation in Template Engines", but the theory is a little weak and it focuses on the nebulous idea of separation of model and view, as opposed to a classification of capabilities and limitations. In addition there seems to not be a lot of work on sub-turing languages, and most interestingly the contemporary work that is being done is on Membrane Computing Systems, which is in turn motivated by studying cell evolutions and chemical reactions. I am bringing this topic forward in the hopes of learning of other pointers into the literature, and also learning if this problem applies to others in the Apps area, of if I'm all alone with this problem in URI Templates.

----- End forwarded message -----