Implementing Explicit and Finding Implicit Sharing in Embedded DSLs
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 def...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2011-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1109.0784v1 |
| _version_ | 1818276992980615168 |
|---|---|
| author | Oleg Kiselyov |
| author_facet | Oleg Kiselyov |
| author_sort | Oleg Kiselyov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T22:54:28Z |
| format | Article |
| id | doaj.art-5322b7f4f84f44f0bc61cd505bfc3bde |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-12T22:54:28Z |
| publishDate | 2011-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-5322b7f4f84f44f0bc61cd505bfc3bde2022-12-22T00:08:58ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802011-09-0166Proc. DSL 201121022510.4204/EPTCS.66.11Implementing Explicit and Finding Implicit Sharing in Embedded DSLsOleg KiselyovAliasing, 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.http://arxiv.org/pdf/1109.0784v1 |
| spellingShingle | Oleg Kiselyov Implementing Explicit and Finding Implicit Sharing in Embedded DSLs Electronic Proceedings in Theoretical Computer Science |
| title | Implementing Explicit and Finding Implicit Sharing in Embedded DSLs |
| title_full | Implementing Explicit and Finding Implicit Sharing in Embedded DSLs |
| title_fullStr | Implementing Explicit and Finding Implicit Sharing in Embedded DSLs |
| title_full_unstemmed | Implementing Explicit and Finding Implicit Sharing in Embedded DSLs |
| title_short | Implementing Explicit and Finding Implicit Sharing in Embedded DSLs |
| title_sort | implementing explicit and finding implicit sharing in embedded dsls |
| url | http://arxiv.org/pdf/1109.0784v1 |
| work_keys_str_mv | AT olegkiselyov implementingexplicitandfindingimplicitsharinginembeddeddsls |