Everything old is new again: quoted domain-specific languages

ABSTRACT

We describe a new approach to implementing Domain-Specific Languages(DSLs), called Quoted DSLs (QDSLs), that is inspired by two old ideas:quasi-quotation, from McCarthy's Lisp of 1960, and the subformula principle of normal proofs, from Gentzen's natural deduction of 1935. QDSLs reuse facilities provided for the host language, since host and quoted terms share the same syntax, type system, and normalisation rules. QDSL terms are normalised to a canonical form, inspired by the subformula principle, which guarantees that one can use higher-order types in the source while guaranteeing first-order types in the target, and enables using types to guide fusion. We test our ideas by re-implementing Feldspar, which was originally implemented as an Embedded DSL (EDSL), as a QDSL; and we compare the QDSL and EDSL variants. The two variants produce identical code.

References

1. J. Ankner and J. Svenningsson. An EDSL approach to high performance Haskell programming. In Haskell. ACM, 2013.
2. Z. Ariola and M. Felleisen. The call-by-need lambda calculus. JFP, 7(03), 1997.
3. E. Axelsson, K. Claessen, G. Dévai, Z. Horváth, K. Keijzer, B. Lyckeg˚ard, A. Persson, M. Sheeran, J. Svenningsson, and A. Vajda. Feldspar: A domain specific language for digital signal processing algorithms. In MEMOCODE. IEEE, 2010.
4. J. Bentley. Programming pearls: Little languages. CACM, 29(8), 1986.
5. A. Bondorf and O. Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. SCP, 16(2), 1991.
6. M. M. T. Chakravarty, G. Keller, S. L. P. Jones, and S. Marlow. Associated types with class. In POPL. ACM, 2005.
7. J. Cheney, S. Lindley, and P. Wadler. A practical theory of languageintegrated query. In ICFP. ACM, 2013.
8. J. Cheney, S. Lindley, G. Radanne, and P. Wadler. Effective quotation: relating approaches to language-integrated query. In PEPM. ACM, 2014.
9. J. Cheney, S. Lindley, and P. Wadler. Query shredding: efficient relational evaluation of queries over nested multisets. In SIGMOD, pages 1027– 1038. ACM, 2014.
10. K. Claessen and D. Sands. Observable sharing for functional circuit description. In ASIAN. Springer, 1999.
11. K. Claessen, M. Sheeran, and B. Svensson. Expressive array constructs in an embedded GPU kernel programming language. In DAMP. ACM, 2012.
12. E. Cooper. The script-writer’s dream. In DBPL. ACM, 2009.
13. O. Danvy. Type-directed partial evaluation. In POPL. ACM, 1996.
14. R. Davies and F. Pfenning. A modal analysis of staged computation. JACM, 48(3), 2001.
15. P. Dybjer and A. Filinski. Normalization and partial evaluation. In APPSEM. Springer, 2000.
16. J. Eckhardt, R. Kaiabachev, E. Paˇsali´c, K. Swadi, and W. Taha. Implicitly heterogeneous multi-stage programming. New Generation Computing, 25(3), 2007.
17. C. Flanagan, A. Sabry, B. F. Duba, and M. Felleisen. The essence of compiling with continuations. In PLDI. ACM, 1993.
18. M. Flatt. Reference: Racket. Technical Report PLT-TR-2010-1, PLT Inc., 2010.
19. G. Gentzen. Untersuchungen über das logische schließen. i. Mathematische zeitschrift, 39(1), 1935.
20. A. Gill. Type-safe observable sharing in Haskell. In Haskell. ACM, 2009.
21. A. Gill. Domain-specific languages and code synthesis using Haskell. CACM, 57(6), 2014.
22. G. Giorgidze and H. Nilsson. Embedding a functional hybrid modelling language in Haskell. In IFL. Springer, 2011.
23. T. Hart. MACRO definitions for LISP. Technical Report AIM-057, MIT, 1963.
24. W. Howard. The formulae-as-types notion of construction. In To H. B. Curry. Academic Press, 1980.
25. P. Hudak. Domain-specific languages. In Handbook of Programming Languages. MacMillan, 1997.
26. J. Hughes. Restricted data types in Haskell. In Haskell. ACM, 1999.
27. N. Jones, C. Gomard, and P. Sestoft. Partial evaluation and automatic program generation. Prentice Hall, 1993.
28. L. Kats and E. Visser. The spoofax language workbench. In OOPSLA. ACM, 2010.
29. S. Lindley and J. Cheney. Row-based effect types for database integration. In TLDI. ACM, 2012.
30. S. Lindley. Normalisation by Evaluation in the Compilation of Typed Functional Programming Languages. PhD thesis, University of Edinburgh, 2005.
31. S. Lindley. Extensional rewriting with sums. In TLCA. Springer, 2007.
32. G. Mainland and G. Morrisett. Nikola: embedding compiled GPU functions in Haskell. In Haskell. ACM, 2010.
33. G. Mainland. Explicitly heterogeneous metaprogramming with Meta-Haskell. In ICFP. ACM, 2012.
34. J. Maraist, M. Odersky, and P. Wadler. The call-by-need lambda calculus. JFP, 8(03), 1998.
35. J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. CACM, 3(4), 1960.
36. E. Meijer, B. Beckman, and G. Bierman. LINQ: reconciling object, relations and XML in the .NET framework. In SIGMOD. ACM, 2006.
37. E. Moggi. Notions of computation and monads. Inf. Comput., 93(1), 1991.
38. F. Nielson and H. Nielson. Two-level functional languages. Cambridge University Press, 1992.
39. J. O’Donnell. Generating netlists from executable circuit specifications in a pure functional language. In Functional Programming, Glasgow. Springer, 1993.
40. A. Persson, E. Axelsson, and J. Svenningsson. Generic monadic constructs for embedded languages. In IFL. Springer, 2011.
41. S. Peyton Jones, S. Marlow, and C. Elliott. Stretching the storage manager: Weak pointers and stable names in Haskell. In IFL. Springer, 2000.
42. F. Pfenning and C. Elliott. Higher-order abstract syntax. In PLDI. ACM, 1988.
43. D. Prawitz. Natural Deduction: A Proof-Theoretical Study. Almqvist and Wiksell, 1965.
44. T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs. In GPCE. ACM, 2010.
45. T. Rompf, N. Amin, A. Moors, P. Haller, and M. Odersky. Scala-Virtualized: linguistic reuse for deep embeddings. In HOSC. Springer, 2013.
46. T. Rompf. Lightweight Modular Staging and Embedded Compilers: Abstraction without Regret for High-Level High-Performance Programming. PhD thesis, EPFL, 2012.
47. D. Schoepe, D. Hedin, and A. Sabelfeld. SeLINQ: tracking information across application-database boundaries. In J. Jeuring and M. M. T. Chakravarty, editors, ICFP. ACM, 2014.
48. N. Sculthorpe, J. Bracker, G. Giorgidze, and A. Gill. The constrainedmonad problem. In ICFP. ACM, 2013.
49. A. K. Sujeeth, T. Rompf, K. J. Brown, H. Lee, H. Chafi, V. Popic, M. Wu, A. Prokopec, V. Jovanovic, M. Odersky, and K. Olukotun. Composition and reuse with compiled domain-specific languages. In ECOOP. Springer, 2013.
50. A. K. Sujeeth, K. J. Brown, H. Lee, T. Rompf, H. Chafi, M. Odersky, and K. Olukotun. Delite: a compiler architecture for performance-oriented embedded domain-specific languages. TECS, 13(4s), 2014.
51. K. Suzuki, O. Kiselyov, and Y. Kameyama. Finally, safely-extensible and efficient language integrated query. In PEPM. ACM, 2015.
52. J. Svenningsson and E. Axelsson. Combining deep and shallow embedding for EDSL. In TFP. Springer, 2012.
53. J. Svenningsson and B. Svensson. Simple and compositional reification of monadic embedded languages. In ICFP. ACM, 2013.
54. J. Svensson, M. Sheeran, and K. Claessen. Obsidian: A domain specific embedded language for parallel programming of graphics processors. In IFL. Springer, 2011.
55. D. Syme. Leveraging .NET meta-programming components from F#: integrated queries and interoperable heterogeneous execution. In ML. ACM, 2006.
56. W. Taha and T. Sheard. MetaML and multi-stage programming with explicit annotations. TCS, 248(1), 2000.
57. P. Wadler. Propositions as types. CACM, 2015.
58. L. Wong. Normal forms and conservative extension properties for query languages over collection types. JCSS, 52(3), 1996.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

    • General programming languages

      • Language types

        • Functional languages

• Theory of computation

  • Formal languages and automata theory