26
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Implementing Explicit and Finding Implicit Sharing in Embedded DSLs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Aliasing, or sharing, is prominent in many domains, denoting that two differently-named objects are in fact identical: a change in one object (memory cell, circuit terminal, disk block) is instantly reflected in the other. Languages for modelling such domains should let the programmer explicitly define the sharing among objects or expressions. A DSL compiler may find other identical expressions and share them, implicitly. Such common subexpression elimination is crucial to the efficient implementation of DSLs. Sharing is tricky in embedded DSL, since host aliasing may correspond to copying of the underlying objects rather than their sharing. This tutorial summarizes discussions of implementing sharing in Haskell DSLs for automotive embedded systems and hardware description languages. The technique has since been used in a Haskell SAT solver and the DSL for music synthesis. We demonstrate the embedding in pure Haskell of a simple DSL with a language form for explicit sharing. The DSL also has implicit sharing, implemented via hash-consing. Explicit sharing greatly speeds up hash-consing. The seemingly imperative nature of hash-consing is hidden beneath a simple combinator language. The overall implementation remains pure functional and easy to reason about.

          Related collections

          Most cited references4

          • Record: found
          • Abstract: not found
          • Article: not found

          On programming of arithmetic operations

          A. Ershov (1958)
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Multi-stage programming with functors and monads: Eliminating abstraction overhead from generic code

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Compiling embedded languages

                Bookmark

                Author and article information

                Journal
                04 September 2011
                Article
                10.4204/EPTCS.66.11
                1109.0784
                ffb49a42-48d3-4a8c-89e1-8c44217cd13a

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                EPTCS 66, 2011, pp. 210-225
                In Proceedings DSL 2011, arXiv:1109.0323
                cs.PL cs.DS
                EPTCS

                Comments

                Comment on this article