Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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 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 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.

REFERENCES

• 1: Arthur Baars and S. Doaitse Swierstra. Typed transformations of typed abstract syntax. UU-CS 21, Utrecht University, 2008.
• 2: Arthur I. Baars , S. Doaitse Swierstra, Typing dynamic typing, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.157-166, October 04-06, 2002, Pittsburgh, PA, USA [doi>10.1145/581478.581494]
• 3: Arthur I. Baars , S. Doaitse Swierstra, Type-safe, self inspecting code, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017485]
• 4: Arthur I. Baars, S. Doaitse Swierstra, and Marcos Viera. TTTAS HackageDB package. URL http://hackage.haskell.org/cgi-bin/hackage-scripts/package/TTTAS.
• 5: Chiyan Chen , Hongwei Xi, Implementing typeful program transformations, Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.20-28, June 07-07, 2003, San Diego, California, USA [doi>10.1145/777388.777392]
• 6: James Cheney and Ralf Hinze. First-Class Phantom Types. Technical report TR2003-1901, Cornell University, 2003. http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.c%is/TR2003-1901.
• 7: EHC. Essential haskell compiler. URL http://www.cs.uu.nl/wiki/Ehc.
• 8: GHC. Glasgow haskell compiler. URL http://www.haskell.org/ghc/.
• 9: Hackage. Hackage. URL http://hackage.haskell.org/.
• 10: John Hughes, Generalising monads to arrows, Science of Computer Programming, v.37 n.1-3, p.67-111, May 2000 [doi>10.1016/S0167-6423(99)00023-4]
• 11: Hugs. Hugs. URL http://www.haskell.org/hugs/.
• 12: John Launchbury , Simon L. Peyton Jones, Lazy functional state threads, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.24-35, June 20-24, 1994, Orlando, Florida, United States [doi>10.1145/178243.178246]
• 13: Emir Pasalic and Nathan Linger. Meta-programming with typed object-language representations. In Generative Programming and Component Engineering (GPCE'04), volume LNCS 3286, pages 136--167, October 2004.
• 14: Ross Paterson, A new notation for arrows, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy [doi>10.1145/507635.507664]
• 15: Simon Peyton Jones , Dimitrios Vytiniotis , Stephanie Weirich , Geoffrey Washburn, Simple unification-based type inference for GADTs, ACM SIGPLAN Notices, v.41 n.9, September 2006 [doi>10.1145/1160074.1159811]
• 16: Marcos Viera , S. Doaitse Swierstra , Eelco Lempsink, Haskell, do you read me?: constructing and composing efficient top-down parsers at runtime, Proceedings of the first ACM SIGPLAN symposium on Haskell, September 25-25, 2008, Victoria, BC, Canada [doi>10.1145/1411286.1411296]
• 17: Stephanie Weirich, Type-safe cast: (functional pearl), Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.58-67, September 2000 [doi>10.1145/351240.351246]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures; Polymorphism

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Algorithms, Languages, Verification

Keywords:
common subexpression elimination, gadt, meta-programming, type systems, typed transformations