Compiled, Extensible, Multi-language DSLs (Functional Pearl)
Article No.: 238, Pages 64 - 87
Abstract
Implementations of domain-specific languages should offer both extensibility and performance optimizations. With the new syntax-spec metalanguage in Racket, programmers can easily create DSL implementations that are both automatically macro-extensible and subject to conventional compiler optimizations. This pearl illustrates this approach through a new implementation of miniKanren, a widely used relational programming DSL. The miniKanren community has explored, in separate implementations, optimization techniques and a wide range of extensions. We demonstrate how our new miniKanren implementation with syntax-spec reconciles these features in a single implementation that comes with both an optimizing compiler and an extension mechanism. Furthermore, programmers using the new implementation benefit from the same seamless integration between Racket and miniKanren as in existing shallow embeddings.
References
[1]
Robert Atkey, Sam Lindley, and Jeremy Yallop. 2009. Unembedding domain-specific languages. In Proc. Symposium on Haskell (Haskell ’09). 37–48. https://doi.org/10.1145/1596638.1596644
[2]
Jonathan Bachrach and Keith Playford. 1999. D-Expressions: Lisp Power, Dylan Style. https://people.csail.mit.edu/jrb/Projects/dexprs.pdf
[3]
W. W. Rouse Ball. 1914. Mathematical Recreations and Essays (6th Edition). MacMillan & Co., Limited.
[4]
Michael Ballantyne. 2024. faster-minikanren. https://github.com/michaelballantyne/faster-minikanren
[5]
Michael Ballantyne and Matthias Felleisen. 2023. Injecting Language Workbench Technology into Mainstream Languages. In Eelco Visser Commemorative Symposium. 3:1–3:11. https://doi.org/10.4230/OASIcs.EVCS.2023.3
[6]
Michael Ballantyne, Alexis King, and Matthias Felleisen. 2020. Macros for Domain-Specific Languages. Proc. ACM Program. Lang., 4, OOPSLA (2020), Article 229, 11, https://doi.org/10.1145/3428297
[7]
Langston Barrett, David Thrane Christiansen, and Samuel Gélineau. 2020. Predictable Macros for Hindley-Milner. In The Workshop on Type-Driven Development (TyDe ’20). https://davidchristiansen.dk/pubs/tyde2020-predictable-macros-abstract.pdf
[8]
Eugene Burmako. 2013. Scala macros: let our powers combine!: On how rich syntax and static types work with metaprogramming. In Proc. Workshop on Scala (Scala ’13). Article 3, https://doi.org/10.1145/2489837.2489840
[9]
William E. Byrd, Michael Ballantyne, Gregory Rosenblatt, and Matthew Might. 2017. A Unified Approach to Solving Seven Programming Problems (Functional Pearl). Proc. ACM Program. Lang., 1, ICFP (2017), Article 8, 8, https://doi.org/10.1145/3110252
[10]
William E. Byrd, Eric Holk, and Daniel P. Friedman. 2012. miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl). In Proc. Workshop on Scheme and Functional Programming (Scheme ’12). 8–29. https://doi.org/10.1145/2661103.2661105
[11]
Stephen Chang, Michael Ballantyne, Milo Turner, and William J. Bowman. 2019. Dependent type systems as macros. Proc. ACM Program. Lang., 4, POPL (2019), Dec., https://doi.org/10.1145/3371071
[12]
Stephen Chang, Alex Knauth, and Ben Greenman. 2017. Type systems as macros. In Proc. Principles of Programming Languages (POPL ’17). 694––705. https://doi.org/10.1145/3009837.3009886
[13]
David Christiansen and Edwin Brady. 2016. Elaborator reflection: Extending Idris in Idris. In Proc. International Conference on Functional Programming (ICFP ’16). 284––297. https://doi.org/10.1145/2951913.2951932
[14]
Koen Claessen and Peter Ljunglöf. 2001. Typed Logical Variables in Haskell. Electronic Notes in Theoretical Computer Science, 41, 1 (2001), 37. https://doi.org/10.1016/S1571-0661(05)80544-4
[15]
Ryan Culpepper. 2012. Fortifying macros. Journal of Functional Programming, 22, 4-5 (2012), 8, 439–476. https://doi.org/10.1017/s0956796812000275
[16]
Ryan Culpepper and Matthias Felleisen. 2010. Fortifying macros. In Proc. International Conference on Functional Programming (ICFP ’10). 235––246. https://doi.org/10.1145/1863543.1863577
[17]
Tim Disney, Nathan Faubion, David Herman, and Cormac Flanagan. 2014. Sweeten your JavaScript: Hygienic macros for ES5. In Proc. Symposium on Dynamic Languages (DLS ’14). 35–44. https://doi.org/10.1145/2661088.2661097
[18]
R. Kent Dybvig. 2004. The guaranteed optimization clause of the macro-writer’s bill of rights. https://www.youtube.com/watch?v=LIEX3tUliHw Presented at Dan Friedman’s 60th birthday conference
[19]
Conal Elliott, Sigbjørn Finne, and Oege de Moor. 2003. Compiling embedded languages. Journal of Functional Programming, 13, 3 (2003), 455–481. https://doi.org/10.1017/S0956796802004574
[20]
Matthias Felleisen. 1991. On the expressive power of programming languages. Science of Computer Programming, 17, 1-3 (1991), 35–75. https://doi.org/10.1016/0167-6423(91)90036-W
[21]
Robert Bruce Findler and Matthias Felleisen. 2002. Contracts for higher-order functions. In Proc. International Conference on Functional Programming (ICFP ’02). 48––59. https://doi.org/10.1145/581478.581484
[22]
Matthew Flatt. 2002. Composable and compilable macros: You want it when? In Proc. International Conference on Functional Programming (ICFP ’02). 72––83. https://doi.org/10.1145/581478.581486
[23]
Matthew Flatt, Taylor Allred, Nia Angle, Stephen De Gabrielle, Robert Bruce Findler, Jack Firth, Kiran Gopinathan, Ben Greenman, Siddhartha Kasivajhula, Alex Knauth, Jay McCarthy, Sam Phillips, Sorawee Porncharoenwase, Jens Axel Søgaard, and Sam Tobin-Hochstadt. 2023. Rhombus: A New Spin on Macros without All the Parentheses. Proc. ACM Program. Lang., 7, OOPSLA2 (2023), Article 242, Oct., https://doi.org/10.1145/3622818
[24]
Aleksandra Foksinska, Camerron M Crowder, Andrew B Crouse, Jeff Henrikson, William E Byrd, Gregory Rosenblatt, Michael J Patton, Kaiwen He, Thi K Tran-Nguyen, and Marissa Zheng. 2022. The precision medicine process for treating rare disease using the artificial intelligence tool mediKanren. Frontiers in Artificial Intelligence, 5 (2022), https://doi.org/10.3389/frai.2022.910216
[25]
Daniel P. Friedman, William E. Byrd, Oleg Kiselyov, and Jason Hemann. 2018. The Reasoned Schemer, Second Edition. The MIT Press. isbn:9780262535519
[26]
Jeremy Gibbons and Nicolas Wu. 2014. Folding domain-specific languages: Deep and shallow embeddings (functional Pearl). In Proc. International Conference on Functional Programming (ICFP ’14). 339–347. https://doi.org/10.1145/2628136.2628138
[27]
Ralf Hinze. 1998. Prological Features in a Functional Setting Axioms and Implementation. In Fuji International Symposium on Functional and Logic Programming (FLOPS ’98). 98–122. https://www.cs.ox.ac.uk/ralf.hinze/publications/FLOPS98.ps.gz
[28]
Siddhartha Kasivajhula and drym.org. 2024. Qi: An Embeddable Flow-Oriented Language. https://github.com/drym-org/qi
[29]
Andrew W Keep, Michael D Adams, Lindsey Kuper, William E Byrd, and Daniel P Friedman. 2009. A pattern matcher for miniKanren or how to get into trouble with CPS macros. In Proc. Workshop on Scheme and Functional Programming (Scheme ’09). 37–45. https://digitalcommons.calpoly.edu/csse_fac/83
[30]
Andrew W. Keep and R. Kent Dybvig. 2013. A nanopass framework for commercial compiler development. In Proc. International Conference on Functional Programming (ICFP ’13). 343––350. https://doi.org/10.1145/2500365.2500618
[31]
Oleg Kiselyov, William E. Byrd, Daniel P. Friedman, and Chung-chieh Shan. 2008. Pure, declarative, and constructive arithmetic relations (declarative pearl). In Proc. International Symposium on Functional and Logic Programming. 64–80. https://doi.org/10.1007/978-3-540-78969-7_7
[32]
Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry. 2005. Backtracking, interleaving, and terminating monad transformers: (functional pearl). In Proc. International Conference on Functional Programming (ICFP ’05). 192–203. https://doi.org/10.1145/1086365.1086390
[33]
Dmitrii Kosarev and Dmitry Boulytchev. 2018. Typed Embedding of a Relational Language in OCaml. In Proc. ML Family Workshop (ML/OCAML 2016). https://doi.org/10.4204/EPTCS.285.1
[34]
Peter Lozov and Dmitry Boulytchev. 2021. Efficient fair conjunction for structurally-recursive relations. In Proc. Partial Evaluation and Program Manipulation (PEPM 2021). https://doi.org/10.1145/3441296.3441397
[35]
Kim Marriott and Harald Søndergaard. 1989. On Prolog and the occur check problem. ACM SIGPLAN Notices, 24, 5 (1989), 76–82. https://doi.org/10.1145/66068.66075
[36]
Jacob Matthews and Robert Bruce Findler. 2007. Operational Semantics for Multi-Language Programs. In Proc. Principles of Programming Languages (POPL ’07). 3––10. https://doi.org/10.1145/1190216.1190220
[37]
Marjan Mernik, Jan Heering, and Anthony M. Sloane. 2005. When and How to Develop Domain-Specific Languages. Comput. Surveys, 37, 4 (2005), dec, 316–344. https://doi.org/10.1145/1118890.1118892
[38]
Shayan Najd, Sam Lindley, Josef Svenningsson, and Philip Wadler. 2016. Everything old is new again: Quoted domain-specific languages. In Proc. Partial Evaluation and Program Manipulation (PEPM ’16). 25–36. https://doi.org/10.1145/2847538.2847541
[39]
David Nolen, Rich Hickey, and contributors. 2020. clojure/core.logic: A logic programming library for Clojure and ClojureScript. https://github.com/clojure/core.logic
[40]
James T. Perconti and Amal Ahmed. 2014. Verifying an Open Compiler Using Multi-language Semantics. In European Symposium on Programming Languages and Systems (ESOP ’14). 128–148. https://doi.org/10.1007/978-3-642-54833-8_8
[41]
The Rust Project. 2024. The Rust Reference: Procedural Macros. https://doc.rust-lang.org/reference/procedural-macros.html
[42]
Jon Rafkind and Matthew Flatt. 2012. Honu: Syntactic extension for algebraic notation through enforestation. In Proc. Generative Programming and Component Engineering (GPCE ’12). 122–131. https://doi.org/10.1145/2371401.2371420
[43]
Tiark Rompf, Nada Amin, Adriaan Moors, Philipp Haller, and Martin Odersky. 2012. Scala-Virtualized: Linguistic reuse for deep embeddings. Higher-Order and Symbolic Computation, 25, 1 (2012), 01 Mar, 165–207. https://doi.org/10.1007/s10990-013-9096-9
[44]
Dmitry Rozplokhas and Dmitry Boulytchev. 2021. A Complexity Study for Interleaving Search. In Proc. miniKanren and Relational Programming Workshop (miniKanren ’21). http://minikanren.org/workshop/2021/minikanren-2021-final7.pdf
[45]
DiPanwita Sarkar, Oscar Waddell, and R. Kent Dybvig. 2005. Educational Pearl: A Nanopass framework for compiler education. Journal of Functional Programming, 15, 5 (2005), 653––667. https://doi.org/10.1017/S0956796805005605
[46]
Maximilian Scherr and Shigeru Chiba. 2014. Implicit Staging of EDSL Expressions: A Bridge between Shallow and Deep Embedding. In Proc. European Conference on Object-Oriented Programming (ECOOP ’14). 385–410. https://doi.org/10.1007/978-3-662-44202-9_16
[47]
Amir Shaikhha, Vojin Jovanovic, and Christoph Koch. 2018. A Compiler-Compiler for DSL Embedding. Aug., arXiv:1808.01344.
[48]
Olin Shivers. 2005. The anatomy of a loop: A story of scope and control. In Proc. International Conference on Functional Programming (ICFP ’05). 2–14. https://doi.org/10.1145/1086365.1086368
[49]
Harald Søndergaard. 1986. An application of abstract interpretation of logic programs: Occur check reduction. In Proc. European Symposium on Programming (ESOP ’86). 327–338. https://doi.org/10.1007/3-540-16442-1_25
[50]
Josef Svenningsson and Emil Axelsson. 2013. Combining Deep and Shallow Embedding for EDSL. In Proc. Trends in Functional Programming (TFP ’12). 21–36. https://doi.org/10.1007/978-3-642-40447-4_2
[51]
Sam Tobin-Hochstadt. 2011. Extensible Pattern Matching in an Extensible Language. arXiv:1106.2578.
[52]
Jesse A. Tov and Riccardo Pucella. 2010. Stateful Contracts for Affine Types. In Proc. European Symposium on Programming (ESOP ’10). 550–569. https://doi.org/10.1007/978-3-642-11957-6_29
[53]
Sebastian Ullrich and Leonardo de Moura. 2022. Beyond Notations: Hygienic Macro Expansion for Theorem Proving Languages. Logical Methods in Computer Science, 18, 2 (2022), April, https://doi.org/10.46298/lmcs-18(2:1)2022
[54]
Hendrik van Antwerpen, Casper Bach Poulsen, Arjen Rouvoet, and Eelco Visser. 2018. Scopes as types. Proc. ACM Program. Lang., 2, OOPSLA (2018), Oct., https://doi.org/10.1145/3276484
[55]
Peter Van Roy. 1994. 1983–1993: The wonder years of sequential Prolog implementation. The Journal of Logic Programming, 19-20 (1994), 385–441. https://doi.org/10.1016/0743-1066(94)90031-0
[56]
Ekaterina Verbitskaia, Daniil Berezun, and Dmitry Boulytchev. 2020. An Empirical Study of Partial Deduction for miniKanren. In Proc. miniKanren and Relational Programming Workshop (miniKanren ’20). http://minikanren.org/workshop/2020/minikanren-2020-paper2.pdf
[57]
Ekaterina Verbitskaia, Igor Engel, and Daniil Berezun. 2023. Semi-Automated Direction-Driven Functional Conversion. In Proc. miniKanren and Relational Programming Workshop (miniKanren ’23). http://minikanren.org/workshop/2023/minikanren23-final2.pdf
[58]
Artjoms Šinkarovs and Jesper Cockx. 2021. Choosing is Losing: How to combine the benefits of shallow and deep embeddings through reflection. arXiv:2105.10819.
Index Terms
- Compiled, Extensible, Multi-language DSLs (Functional Pearl)
Recommendations
A framework for extensible languages
GPCE '13: Proceedings of the 12th international conference on Generative programming: concepts & experiencesExtensible programming languages such as SugarJ or Racket enable programmers to introduce customary language features as extensions of the base language. Traditionally, systems that support language extensions are either (i) agnostic to the base ...
A framework for extensible languages
GPCE '13Extensible programming languages such as SugarJ or Racket enable programmers to introduce customary language features as extensions of the base language. Traditionally, systems that support language extensions are either (i) agnostic to the base ...
miniKanren, live and untagged: quine generation via relational interpreters (programming pearl)
Scheme '12: Proceedings of the 2012 Annual Workshop on Scheme and Functional ProgrammingWe present relational interpreters for several subsets of Scheme, written in the pure logic programming language miniKanren. We demonstrate these interpreters running "backwards"---that is, generating programs that evaluate to a specified value---and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
1031 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 August 2024
Published in PACMPL Volume 8, Issue ICFP
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF (National Science Foundation)
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 302Total Downloads
- Downloads (Last 12 months)302
- Downloads (Last 6 weeks)49
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in