More Web Proxy on the site http://driver.im/

research-article

Abstract syntax graphs for domain specific languages

Authors:

Bruno C. d. S. Oliveira,

Andres LöhAuthors Info & Claims

PEPM '13: Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation

Pages 87 - 96

https://doi.org/10.1145/2426890.2426909

Published: 21 January 2013 Publication History

Abstract

This paper presents a representation for embedded domain specific languages (EDSLs) using abstract syntax graphs (ASGs). The purpose of this representation is to deal with the important problem of defining operations that require observing or preserving sharing and recursion in EDSLs in an expressive, yet easy-to-use way. In contrast to more conventional representations based on abstract syntax trees, ASGs represent sharing and recursion explicitly as binder constructs. We use a functional representation of ASGs based on structured graphs, where binders are encoded with parametric higher-order abstract syntax. We show how adapt to this representation to well-typed ASGs. This is especially useful for EDSLs, which often reuse the type system of the host language. We also show an alternative class-based encoding of(well-typed) ASGs that enables extensible and modular well-typed EDSLs while allowing the manipulation of sharing and recursion.

References

[1]

T. Altenkirch and B. Reus. Monadic presentations of lambda terms using generalized inductive types. In CSL'99, 1999.

Digital Library

[2]

A. I. Baars and S. D. Swierstra. Type-safe, self inspecting code. In Haskell'04, 2004.

Digital Library

[3]

A. I. Baars, S. D. Swierstra, and M. Viera. Typed transformations of typed grammars: The left corner transform. Electron. Notes Theor. Comput. Sci., 253(7), 2010.

Digital Library

[4]

P. Bjesse, K. Claessen, M. Sheeran, and S. Singh. Lava: hardware design in Haskell. In ICFP'98, 1998.

Digital Library

[5]

J. Carette, O. Kiselyov, and C. Shan. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J. Funct. Program., 19(5), 2009.

Digital Library

[6]

J. Cheney and R. Hinze. A lightweight implementation of generics and dynamics. In Haskell 2002, 2002.

Digital Library

[7]

A. Chlipala. Parametric higher-order abstract syntax for mechanized semantics. In ICFP'08, 2008.

Digital Library

[8]

K. Claessen and D. Sands. Observable sharing for functional circuit description. In In Asian Computing Science Conference. Springer Verlag, 1999.

Digital Library

[9]

D. Devriese and F. Piessens. Finally tagless observable recursion for an abstract grammar model. Journal of Functional Programming, 22(6):757--796, November 2012.

Digital Library

[10]

D. Devriese, I. Sergey, D. Clarke, and F. Piessens. Fixing idioms: A recursion primitive for applicative dsls. In PEPM'13, 2013.

Digital Library

[11]

A. Gill. Type-safe observable sharing in Haskell. In Haskell'09, 2009.

Digital Library

[12]

R. Hinze. Generics for the masses. J. Funct. Program., 16(4-5), 2006.

Digital Library

[13]

C. Hofer, K. Ostermann, T. Rendel, and A. Moors. Polymorphic embedding of dsls. In GPCE'08, 2008.

Digital Library

[14]

P. Hudak. Building domain-specific embedded languages. ACM Computing Surveys, 28, 1996.

Digital Library

[15]

P. Jansson and J. Jeuring. Polyp - a polytypic programming language extension. In POPL'97, 1997.

Digital Library

[16]

O. Kiselyov. Implementing explicit and finding implicit sharing in embedded DSLs. In Proceedings IFIP Working Conference on Domain-Specific Languages, 2011.

[17]

E. Meijer and G. Hutton. Bananas in space: extending fold and unfold to exponential types. In FPCA'95, 1995.

Digital Library

[18]

M. Might, D. Darais, and D. Spiewak. Parsing with derivatives: a functional pearl. In ICFP'11, 2011.

Digital Library

[19]

J. T. O'Donnell. Overview of Hydra: A concurrent language for synchronous digital circuit design. In IPDPS'02, 2002.

Digital Library

[20]

B. C. d. S. Oliveira and W. R. Cook. Functional programming with structured graphs. In ICFP'12, 2012.

Digital Library

[21]

B. C. d. S. Oliveira and J. Gibbons. Typecase: a design pattern for type-indexed functions. In Haskell'05, 2005.

Digital Library

[22]

B. C. d. S. Oliveira, R. Hinze, and Andres Löh. Extensible and Modular Generics for the Masses. In TFP'06, 2006.

[23]

S. Peyton Jones, D. Vytiniotis, S. Weirich, and G. Washburn. Simple unification-based type inference for gadts. In ICFP'06, 2006.

Digital Library

[24]

F. Pfenning and C. Elliot. Higher-order abstract syntax. In PLDI'88, 1988.

Digital Library

[25]

F. Pottier. Lazy least fixed points in ML. Unpublished, 2009.

[26]

P.Wadler. The essence of functional programming. In POPL'92, 1992.

Digital Library

[27]

P. Wadler. The expression problem. Note to Java Genericity mailing list, Nov. 1998.

[28]

B. A. Yorgey, S.Weirich, J. Cretin, S. Peyton Jones, D. Vytiniotis, and J. P. Magalhães. Giving Haskell a promotion. In TLDI'12, 2012.

Digital Library

Cited By

Sun YDhandhania UOliveira B(2022)Compositional embeddings of domain-specific languagesProceedings of the ACM on Programming Languages10.1145/35632946:OOPSLA2(175-203)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563294
Molesini ADenti EOmicini A(2021)MDE and MDA in a Multi-Paradigm Modeling PerspectiveAdvancements in Model-Driven Architecture in Software Engineering10.4018/978-1-7998-3661-2.ch004(64-87)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-3661-2.ch004
Wang SWatanabe T(2019)Functional Reactive EDSL with Asynchronous Execution for Resource-Constrained Embedded SystemsSoftware Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing10.1007/978-3-030-26428-4_12(171-190)Online publication date: 23-Aug-2019
https://doi.org/10.1007/978-3-030-26428-4_12
Show More Cited By

Index Terms

Abstract syntax graphs for domain specific languages
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

High performance embedded domain specific languages
ICFP '12

Today, all high-performance computer architectures are parallel and heterogeneous; a combination of multiple CPUs, GPUs and specialized processors. This creates a complex programming problem for application developers. Domain-specific languages (DSLs) ...
Virtual Domain Specific Languages via Embedded Projectional Editing
GPCE 2023: Proceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

Domain Specific Languages (DSLs) can be implemented as either internal DSL, i.e. essentially a library in a host general-purpose programming language (GPL), or as external DSL which is a stand-alone language unconstrained in its syntax. This choice ...
High performance embedded domain specific languages
ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programming

Today, all high-performance computer architectures are parallel and heterogeneous; a combination of multiple CPUs, GPUs and specialized processors. This creates a complex programming problem for application developers. Domain-specific languages (DSLs) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '13: Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation

January 2013

162 pages

ISBN:9781450318426

DOI:10.1145/2426890

Program Chairs:
Elvira Albert
Complutense University of Madrid, Spain
,
Shin-Cheng Mu
Academia Sinica, Taiwan

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '13

Sponsor:

SIGPLAN

POPL '13: The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 21, 2013

Rome, Italy

Acceptance Rates

PEPM '13 Paper Acceptance Rate 13 of 29 submissions, 45%;

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)6

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun YDhandhania UOliveira B(2022)Compositional embeddings of domain-specific languagesProceedings of the ACM on Programming Languages10.1145/35632946:OOPSLA2(175-203)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563294
Molesini ADenti EOmicini A(2021)MDE and MDA in a Multi-Paradigm Modeling PerspectiveAdvancements in Model-Driven Architecture in Software Engineering10.4018/978-1-7998-3661-2.ch004(64-87)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-3661-2.ch004
Wang SWatanabe T(2019)Functional Reactive EDSL with Asynchronous Execution for Resource-Constrained Embedded SystemsSoftware Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing10.1007/978-3-030-26428-4_12(171-190)Online publication date: 23-Aug-2019
https://doi.org/10.1007/978-3-030-26428-4_12
Blažević MLégaré J(2017)Packrats parse in packsACM SIGPLAN Notices10.1145/3156695.312295852:10(14-25)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3156695.3122958
Blažević MLégaré JDiatchki I(2017)Packrats parse in packsProceedings of the 10th ACM SIGPLAN International Symposium on Haskell10.1145/3122955.3122958(14-25)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122955.3122958
Ploeg AClaessen KBuiras P(2016)The Key monad: type-safe unconstrained dynamic typingACM SIGPLAN Notices10.1145/3241625.297600851:12(146-157)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/3241625.2976008
Ploeg AClaessen KBuiras PMainland G(2016)The Key monad: type-safe unconstrained dynamic typingProceedings of the 9th International Symposium on Haskell10.1145/2976002.2976008(146-157)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2976002.2976008
Bahr PAxelsson EAsai KSagonas K(2015)Generalising Tree Traversals to DAGsProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation10.1145/2678015.2682539(27-38)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2678015.2682539
Doma ESelic BLevy D(2015)Exploring Situation Theory Using InfonLabProceedings of the 2015 IEEE 18th International Symposium on Real-Time Distributed Computing10.1109/ISORC.2015.20(260-267)Online publication date: 13-Apr-2015
https://dl.acm.org/doi/10.1109/ISORC.2015.20
Erdweg SStorm TDai Y(2014)Capture-Avoiding and Hygienic Program TransformationsProceedings of the 28th European Conference on ECOOP 2014 --- Object-Oriented Programming - Volume 858610.1007/978-3-662-44202-9_20(489-514)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/978-3-662-44202-9_20
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents