DSL implementation using staging and monads

ABSTRACT

The impact of Domain Specific Languages (DSLs) on software design is considerable. They allow programs to be more concise than equivalent programs written in a high-level programming languages. They relieve programmers from making decisions about data-structure and algorithm design, and thus allows solutions to be constructed quickly. Because DSL's are at a higher level of abstraction they are easier to maintain and reason about than equivalent programs written in a high-level language, and perhaps most importantly they can be written by domain experts rather than programmers.

The problem is that DSL implementation is costly and prone to errors, and that high level approaches to DSL implementation often produce inefficient systems. By using two new programming language mechanisms, program staging and monadic abstraction, we can lower the cost of DSL implementations by allowing reuse at many levels. These mechanisms provide the expressive power that allows the construction of many compiler components as reusable libraries, provide a direct link between the semantics and the low-level implementation, and provide the structure necessary to reason about the implementation.

References

1. 1.Anders Bondorf and Jens Palsberg. Compiling actions by partial evaluation. In Conference on Functwnal Programmzng Languages and Computer Architecture, pages 308-320, New York, June 1993. ACM Press. Copenhagen.
2. 2.Gracly Campbell. Abstraction-based reuse repositories. Technical Report REUSE- REPOSITORIES-89041-N, Software Productivity Consortium Services Corporation, 2214 Rock Hill Road, Herndon, Virginia 22070, June 1989.
3. 3.Grady Campbell, Stuart Faulk, and David Weiss. introduction to Synthesis. Technical Report INTRO-SYNTHESIS-PROCESS- 90019-N, Software Productivity Consortium Services Corporation, 2214 Rock Hill Road, Herndon, Virginia 22070, 1990.
4. 4.Charles Consel and Francois No/~l. A general approach for run-time specialization and its application to C. In Conference Record of POPL '96: The 23ra A CM SIGPLAN-SIGA CT Symposium on Prtnctples of Programmsng Languages, pages 145-156, St. Petersburg Beach, Florida, 21-24 January 1996.
5. 5.O Danvy, J Koslowski, and K Malmkjaer. Compiling monads. Technical Report CIS-92-3, Kansas State University, Manhattan, Kansas, December 91.
6. 6.Robert Gliick and Jesper J0rgensen Efficient multi-level generating extensions for program specialization, in S. D. Swierstra and M. Hermenegildo, editors, Programmsn9 Languages: {mplementatzons, Logzcs and Programs (PLILP'95), volume 982 of Lecture Notes tn Computer Sctence, pages 259-278. Springer- Verlag, 1995.
7. 7.Mark P. Jones. A system of constructor classes. overloading and implicit higher-order polymorphism. In In FPCA '93: Conference on Functtonal Programmtng Languages and Computer Archztecture, pages 52-64. ACM Press, 1993. (Appears, in extended form, in the journal of Functional Programming, 5, l, Cambridge University Press, january 1995.).
8. 8.Nell D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluatzon and Automatic Program Generation. Series editor C. A. R. Hoare. Prentice Hall International, International Series in Computer Science, June 1993. ISBN number 0-13-020249-5 (pbk).
9. 9.Paul Hudak Simon Peyton Jones, Philip Wadler, Brian Boutel, John Fairbairn, Joseph Fasel, Maria M. Guzman, Kevin Hammond, John Hughes, Thomas 3ohnsson, Dick Kieburtz, Rishiyur Nikhil, Will Partain, and John Peterson. Report on the programming language Haskell. SIGPLAN Notwes, 27(5):Section R, 1992.
10. 10.Peter Lee. Realzstw Compzler Generation. Foundations of Computing Series. MIT Press, 1989.
11. 11.Mark Leone and Peter Lee. A declarative approach to run-time code generation. In Workshop on Compder Support for System Software (WCSSS), February 1996.
12. 12.Sheng Liang and Paul Hudak. Modular denota- ESOP'96: 6th European Symposium on Programmzng, number 1058 in LNCS, pages 333- 343, Linkoping, Sweden, January 1996.
13. 13.Sheng Liang, Paul Hudak, and Mark Jones. Monad transformers and modular interpreters. In A CM Symposzum on Principles of Programmtn9 Languages, pages 333-343, San Francisco, California, January 1995.
14. 14.P. Mosses. Denotational semantics. In J. van Leeuwen, editor, Handbook of Theoretzcal Cornputer Sctence. Elsevier Science Publishers B. V (North-Holland), 1990.
15. 15.Peter D. Mosses. SIS-semantics implementation system, reference manual and users guide Technical Report DAIMI report MD-30, University of Aarhus, Aarhus, Denmark, 1979.
16. 16.Peter D. Mosses. Action semantics. Cambrtdge Tracts tn Theoretical Computer Science, (26), 1992.
17. 17.Martin Odersky and Konstantin LKufer. Putting type annotations to work. In 23rd A CM Sympostum on Pr2nc~ples of Programm~ng Languages, St. Petersburg, Florida, January 1996.
18. 18.L. Paulson. Methods and Tools/or Compiler Constructzon, B. Lorho (e&tor). Cambridge University Press, 1984.
19. 19.Lawrence Paulson. A sematics directed compiler generator. In Conference Record o/ the Ntnth Annual A CM Symposium on Pr~nczples of Programmzng Languages, pages 224-233. ACM, January 1982.
20. 20.John Peterson, Kevin Hammond, et al. Report on the programming language haskell, a non-strict purely-functional programming language, version 1.3. Technical report, Yale University, May 1996.
21. 21.Frank Pfenning, Jolle Despeyroux, and Carsten Schrmann. Primitive recursion for higher-order abstract syntax. In Third internatzonal Conference on Typed Lambda Calcuh and Apphcat,ons (TLCA'97), pages 147-163, Nancy, France, April 1997.
22. 22.Frank Pfenning, Gilles Dowek, Thrse Hardin, and Claude Kirchner. Unification via explicit substitutions: The case of higher-order patterns. In Joint Internattonal Conference and Sympos,um on Logtc Programming (JIC- SLP'96), Bonn, Germany, September 1996.
23. 23.Calton Pu and Jonathan WMpole. A study of dynamic optimization techniques: Lessons and directions in kernel design Technical Report OGI-CSE-93-007: Oregon Graduate Institute of Science and Technology, 1993.
24. 24.Guy Steele. Building interpreters by composing monads. In 21st Annual A CM Symposium on Pr~nczples of Programming Languages (POPL'94), Portland, Oregon, January 1994.
25. 25.Joseph E. Stoy. Denotatzonal Semantics: The Scott-Strachey Approach to Programming Language Theory. The MIT Press, Cambridge, Massachusetts, 1977.
26. 26.Wnlid Taha, Zine-EI-Abidine Benaissa, and Tim Sheard. Multi-stage programming: A xiomatization and type-safety. In 25th Internatzonal Colloquium on Automata, Languages, and Programming, Aalborg, Denmark, 13- 17July 1998.
27. 27.Walid Taha and Tim Sheard. Multi-stage programming with explicit annotations. In Proceed~ngs of the A CM-SIGPLAN Symposzum on Partial Evaluation and semantzc based program manzpulattons PEPM'97, Amsterdam, pages 203-217. ACM, 1997.
28. 28.Philip Wadler Comprehending monads. Proceed~ngs o~ the A CM Symposzum on L~sp and Functional Programmzng, Nzce, France, pages 61-78, June 1990.
29. 29.Philip Wadler. Comprehending monads. Proceed~ngs o/the A CM Symposium on Lzsp and Functional Programmzng, N, ce, France, pages 61-78, June 1990.
30. 30.Philip Wadler. The e~sence of functional prograrnming (invited talk). In 19 'th A CM Symposzum on Principles of Programmzn9 Languages, Albuquerque, New Mexico, January 1992.
31. 31.Philip ~Vad}er. Monads for flmctional programming In J Jeuring and E. Meijer, editors, Advanced Functional Programming, volume 925 of LNCS. Springer Verlag, 1995.
32. 32.Tanya Widen. Formal language design in the context of domain engineering. Master's thesis, Department of Computer Science and Engineering, Oregon Graduate Institute, October 1997.
33. 33.Tanya Widen and James Hook. Software design automation: Language design in the context of domain engenieering. In The lOth lnternat,onal Conference on Software Engmeerzng ~ Knowledge Engzneermg (SEKE'98), pages 308-317, San Francisco Bay, California, June 1998.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Verification

• Software and its engineering

  • Software creation and management

    • Software development process management

    • Software verification and validation

      • Formal software verification

  • Software notations and tools

    • Compilers

    • Development frameworks and environments

  • Software organization and properties

    • Software functional properties

      • Formal methods

        • Software verification

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program verification