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

[Stephane Bortzmeyer]

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" <joe at bitworking.org>
>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 -----