Room: BBL room 471
Speaker: S. Doaitse Swierstra
Title: Typed Transformations of Typed Abstract Syntax
(joint work with Arthur Baars and Marcos Viera)
Advantages of embedded domain-specific languages (EDSLs) are that one
does not have to
implement a separate type system nor an abstraction
mechanism, since these are directly borrowed from the host language.
Straightforward implementations of
embedded domain-specific languages map the
semantics of the embedded language onto a function in the host
language. The semantic mappings are usually compositional, i.e. they
directly follow the syntax of the embedded language.
One of the questions which arises is whether conventional compilation
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
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
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 we present a case study comparing the
instances generated by Haskells
construct with instances on which run-time grammar transformations
(precedence resolution, left-factorisation and left-corner
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.