| START Conference Manager |
One of the questions which arises is whether conventional compilation techniques, such as global analysis and resulting transformations, can be applied in the context of EDSLs. The approach we take is that, instead of mapping the embedded language directly onto a function, we first build a representation of the abstract syntax tree of the embedded program fragment. This syntax tree is subsequently analyzed and transformed, and finally mapped onto a function representing its denotational semantics. In this way we achieve run-time ``compilation'' of the embedded language.
Run-time transformations on the embedded language can have a huge effect on performance. In previous work (Viera et al. 2008) we present a case study comparing the Read instances generated by Haskells deriving construct with instances on which run-time grammar transformations (precedence resolution, left-factorisation and left-corner transformation) have been applied.
In this paper we present the library, which has an arrow like interface, which supports in the construction of analyses and transformations, and we demonstrate its use in implementing a common sub-expression elemination transformation. The library uses typed abstract syntax to represent fragments of embedded programs containing variables and binding structures, while preserving the idea that the type system of the host language is used to emulate the type system of the embedded language. The tricky issue is how to keep a collection of mutually recursive structures well-typed while it is being transformed.
We finally discuss the typing rules of Haskell, its extensions and those as implemented by the GHC and show that pure System-F based systems are sufficiently rich to express what we want to express, albeit at the cost of an increased complexity of the code.
START Conference Manager (V2.56.8 - Rev. 399)