Typed Transformations of Typed Grammars: The Left Corner Transform - Baars, A.I.; Swierstra, S.D.; Viera, M. (Elsevier BV, 2010)
One of the questions which comes up when using embedded domain specific languages is to what extent we can analyze and transform embedded programs, as normally done in more conventional compilers. Special problems arise when the host language is strongly typed, and this host type system is used to type the embedded language. In this paper we describe how we can use a library, which was designed for constructing transformations of typed abstract syntax, in the removal of left recursion from a typed grammar description. The algorithm we describe is the Left-Corner Transform, which is small enough to be fully explained, involved enough to be interesting, and complete enough to serve as a tutorial on how to proceed in similar cases. The described transformation has been successfully used in constructing a compositional and efficient alternative to the standard Haskell read function.
Keywords: GADT; Left-Corner Transform; Meta Programming; Type Systems; Typed Abstract Syntax; Typed Transformations