Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 18

Proceedings of the 2019 Federated Conference on Computer Science and Information Systems

Composition of Languages Embedded in Scala


DOI: http://dx.doi.org/10.15439/2019F61

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 399410 ()

Full text

Abstract. Composition is amongst the major challenges faced in language engineering. Erdweg et al. offered a taxonomy for language composition. Mernik catalogued the use of the Language Definitional Framework LISA for composition sorts in that taxonomy. We produce a similar catalogue for embedded language engineering in Scala.


  1. S. Erdweg, P. G. Giarrusso, and T. Rendel, “Language Composition Untangled,” in 12th LDTA, A. Sloane and S. Andova, Eds. ACM, Mar. 2012, p. 7.
  2. T. Rompf and M. Odersky, “Lightweight Modular Staging: a Pragmatic Approach to Runtime Code Generation and Compiled DSLs,” in 9th GPCE. Eindhoven, Holland: ACM, 2010, pp. 127–136.
  3. W. R. Cook, “Object-Oriented Programming Versus Abstract Data Types,” in FOOL, ser. LNCS, J. W. de Bakker, W. P. de Roever, and G. Rozenberg, Eds., vol. 489, Holland, Jun. 1990, pp. 151–178.
  4. J. C. Reynolds, “User-Defined Types and Procedural Data Structures as Complementary Approaches to Type Abstraction,” in New Direc. Algo. Lang., S. A. Schuman, Ed. INRIA, 1975, pp. 157–168.
  5. P. Wadler, “The Expression Problem,” Nov. 1998, Java Genericity Mailing List.
  6. M. Mernik, “An Object-Oriented Approach to Language Compositions for Software Language Engineering,” J. Sys. & Soft., vol. 86, no. 9, pp. 2451–2464, 2013.
  7. M. Mernik, M. Lenic, E. Avdicausevic, and V. Zumer, “LISA: An Interactive Environment for Programming Language Development,” in 11th CC, ser. LNCS, R. N. Horspool, Ed., vol. 2304. Springer, Apr. 2002, pp. 1–4.
  8. D. E. Knuth, “Semantics of Context-Free Languages,” Math. Sys. Theo., vol. 2, no. 2, pp. 127–145, 1968.
  9. J. Paakki, “Attribute Grammar Paradigms - A High-Level Methodology in Language Implementation,” ACM Comp. Surv., vol. 27, no. 2, pp. 196–255, 1995.
  10. P. Trinder, K. Hammond, H.-W. Loidl, and S. Peyton Jones, “Algorithm + Strategy = Parallelism,” JFP, vol. 8, no. 1, pp. 23–60, Jan. 1998.
  11. A. Dijkstra, J. Fokker, and S. D. Swierstra, “The Architecture of the Utrecht H ASKELL Compiler,” in 2nd HASKELL, S. Weirich, Ed. Edinburgh, Scotland: ACM, 2009, pp. 93–104.
  12. M. Odersky, “Pimp my Library,” Artima Developer Blog, vol. 9, Oct. 2006.
  13. S. H. Haeri and S. Schupp, “Expression Compatibility Problem,” in 7th SCSS, ser. EPiC Comp., J. H. Davenport and F. Ghourabi, Eds., vol. 39. EasyChair, Mar. 2016, pp. 55–67.
  14. J. Jeuring, S. Leather, J. P. Magalhães, and A. R. Yakushev, “Libraries for Generic Programming in HASKELL,” in Adv. Func. Prog., 6th Int. School, AFP, ser. LNCS, P. W. M. Koopman, R. Plasmeijer, and S. D. Swierstra, Eds., vol. 5832. Springer, May 2008, pp. 165–229.
  15. C. Hofer, K. Ostermann, T. Rendel, and A. Moors, “Polymorphic Embedding of DSLs,” in 7th GPCE, Y. Smaragdakis and J. G. Siek, Eds. Nashville, TN, USA: ACM, Oct. 2008, pp. 137–148.
  16. M. Odersky and M. Zenger, “Scalable Component Abstractions,” in 20th OOPSLA. San Diego, CA, USA: ACM, 2005, pp. 41–57.
  17. E. Ernst, “Family Polymorphism,” in 15th ECOOP, ser. LNCS, J. Lind- skov Knudsen, Ed., vol. 2072. Springer, Jun. 2001, pp. 303–326.
  18. C. Saito, A. Igarashi, and M. Viroli, “Lightweight Family Polymor- phism,” J. Func. Prog., vol. 18, no. 3, pp. 285–331, 2008.
  19. M. Fowler, “Refactoring: Improving the Design of Existing Code,” in 2nd XP/Agile, ser. LNCS, D. Wells and L. A. Williams, Eds., vol. 2418. Springer, Aug. 2002, p. 256.
  20. S. H. Haeri and S. Schupp, “Reusable Components for Lightweight Mechanisation of Programming Languages,” in 12th SC, ser. LNCS, W. Binder, E. Bodden, and W. Löwe, Eds., vol. 8088. Springer, Jun. 2013, pp. 1–16.
  21. S. H. Haeri, “Component-Based Mechanisation of Programming Lan- guages in Embedded Settings,” Ph.D. dissertation, STS, TUHH, Ger- many, Dec. 2014.
  22. P. D. Mosses, “Modular Structural Operational Semantics,” JLAP, vol. 60–61, pp. 195–228, 2004.
  23. P. Wadler and S. Blott, “How to Make ad-hoc Polymorphism Less ad- hoc,” in 16th POPL. ACM Press, Jan. 1989, pp. 60–76.
  24. B. C. d. S. Oliveira, A. Moors, and M. Odersky, “Type Classes as Objects and Implicits,” in 25th OOPSLA, W. R. Cook, S. Clarke, and M. C. Rinard, Eds. ACM, Oct. 2010, pp. 341–360.
  25. B. C. d. S. Oliveira, S.-C. Mu, and S.-H. You, “Modular Reifiable Matching: A List-of-Functors Approach to Two-Level Types,” in 8th H ASKELL , B. Lippmeier, Ed. ACM, Sep. 2015, pp. 82–93.
  26. T. Sheard and E. Pasalic, “Two-Level Types and Parameterized Mod- ules,” JFP, vol. 14, no. 5, pp. 547–587, 2004.
  27. S. H. Haeri and S. Schupp, “Integration of a Decentralised Pattern Matching: Venue for a New Paradigm Intermarriage,” in 8th SCSS, ser. EPiC Comp., M. Mosbah and M. Rusinowitch, Eds., vol. 45. EasyChair, Apr. 2017, pp. 16–28.
  28. I. Sommerville, Software Engineering, 9th ed. Addison-Wesley, 2011.
  29. R. S. Pressman, Software Engineering: A Practitioner’s Approach, 7th ed. McGraw-Hill, 2009.
  30. R. C. Martin, “Design Principles and Design Patterns,” 2000, online article available from the ObjectMentor website.
  31. B. C. d. S. Oliveira and W. R. Cook, “Extensibility for the Masses – Practical Extensibility with Object Algebras,” in 26th ECOOP, ser. LNCS, vol. 7313. Springer, 2012, pp. 2–27.
  32. P. Bahr and T. Hvitved, “Parametric Compositional Data Types,” in 4th MSFP, ser. ENTCS, J. Chapman and P. B. Levy, Eds., vol. 76, Feb. 2012, pp. 3–24.
  33. Y. Wang and B. C. d. S. Oliveira, “The Expression Problem, Trivially!” in 15th Modularity. New York, NY, USA: ACM, 2016, pp. 37–41.
  34. M. Torgersen, “The Expression Problem Revisited,” in 18th ECOOP, ser. LNCS, M. Odersky, Ed., vol. 3086, Oslo (Norway), Jun. 2004, pp. 123–143.
  35. M. Odersky and M. Zenger, “Independently Extensible Solutions to the Expression Problem,” in FOOL, Jan. 2005.
  36. W. Swierstra, “Data Types à la Carte,” JFP, vol. 18, no. 4, pp. 423–436, 2008.
  37. B. C. d. S. Oliveira, “Modular Visitor Components,” in 23rd ECOOP, ser. LNCS, vol. 5653. Springer, 2009, pp. 269–293.
  38. T. Rompf, “Reflections on LMS: Exploring Front-End Alternatives,” in 7th SIGPLAN Symp. Scala, A. Biboudis, M. Jonnalagedda, S. Stucki, and V. Ureche, Eds. ACM, Nov. 2016, pp. 41–50.
  39. M. Völter, “Language and IDE Modularization and Composition with MPS,” GTTSE, vol. 7680, pp. 383–430, 2011.
  40. E. Barrett, C. F. Bolz, and L. Tratt, “Approaches to Interpreter Compo- sition,” Comp. Lang., Sys. & Struct., vol. 44, pp. 199–217, 2015.
  41. H. Zhang, Z. Chu, B. C. d. S. Oliveira, and T. van der Storm, “Scrap Your Boilerplate with Object Algebras,” in 29th OOPSLA, J. Aldrich and P. Eugster, Eds., Oct. 2015, pp. 127–146.
  42. Guttag, J. V. and Horning, J. J., “The Algebraic Specification of Abstract Data Types,” Acta Informatica, vol. 10, pp. 27–52, 1978.
  43. T. Degueule, B. Combemale, A. Blouin, O. Barais, and J.-M. Jézéquel, “Melange: A Meta-Language for Modular and Reusable Development of DSLs,” in 8th SLE, R. F. Paige, D. Di Ruscio, and M. Völter, Eds., Oct. 2015, pp. 25–36.
  44. P. D. Mosses, “Component-Based Description of Programming Lan- guages,” in BCS Int. Acad. Conf., E. Gelenbe, S. Abramsky, and V. Sassone, Eds. Brit. Comp. Soc., 2008, pp. 275–286.
  45. P. D. Mosses and F. Vesely, “FunKons: Component-Based Semantics in K,” in WRLA, ser. LNCS, S. Escobar, Ed., vol. 8663. Springer, Apr. 2014.
  46. M. Churchill, P. D. Mosses, N. Sculthorpe, and P. Torrini, “Reusable Components of Semantic Specifications,” Trans. Aspect-Orient. Soft. Dev. XII, vol. 12, pp. 132–179, 2015.
  47. M. D. McIlroy, “Mass Produced Software Components,” in Proc. NATO Conf. Soft. Eng. New York, US: Petrocelli/Charter, 1969, pp. 138–155.
  48. W. Cazzola and E. Vacchi, “Language Components for Modular DSLs using Traits,” ComLan, vol. 45, pp. 16 – 34, 2016.
  49. J. Saraiva and D. Swierstra, “Generic Attribute Grammars,” in 2nd WAGA, vol. 99, 1999, pp. 185–204.
  50. J. Saraiva, “Component-Based Programming for Higher-Order Attribute Grammars,” in 1st GPCE, ser. LNCS, D. S. Batory, C. Consel, and W. Taha, Eds., vol. 2487. Springer, Oct. 2002, pp. 268–282.
  51. M. Viera and D. Swierstra, “Attribute Grammar Macros,” Sci. Comp. Prog., vol. 96, pp. 211–229, 2014.
  52. P. Martins, J. P. Fernandes, J. Saraiva, E. Van Wyk, and A. Sloane, “Embedding Attribute Grammars and their Extensions using Functional Zippers,” Sci. Comp. Prog., vol. 132, pp. 2–28, 2016.
  53. J. P. Fernandes, P. Martins, A. Pardo, J. Saraiva, and M. Viera, “Memoized Zipper-Based Attribute Grammars and their Higher Order Extension,” Sci. Comp. Prog., vol. 173, pp. 71–94, 2019.
  54. A. Middelkoop, A. Dijkstra, and D. Swierstra, “Iterative Type Inference with Attribute Arammars,” in 9th GPCE, E. Visser and J. J., Eds. ACM, Oct. 2010, pp. 43–52.
  55. A. M. Sloane, “Lightweight Language Processing in Kiama,” in GTTSE III, ser. LNCS, J. M. Fernandes, R. Lämmel, J. Visser, and J. Saraiva, Eds., vol. 6491. Springer, Jul. 2009, pp. 408–425.
  56. N. Wirth, Compiler Construction, ser. Int. Comp. Sci. Series. Addison- Wesley, 1996.
  57. A. M. Sloane and M. Roberts, “Oberon-0 in Kiama,” Sci. Comp. Prog., vol. 114, pp. 20–32, 2015.
  58. B. C. d. S. Oliveira, T. van der Storm, A. Loh, and W. R. Cook, “Feature- Oriented Programming with Object Algebras,” in 27th ECOOP, ser. LNCS, G. Castagna, Ed., vol. 7920. Montpellier, France: Springer, 2013, pp. 27–51.
  59. T. Rendel, J. I. Brachthäuser, and K. Ostermann, “From Object Algebras to Attribute Grammars,” in 28th OOPSLA, A. P. Black and T. D. Millstein, Eds. ACM, Oct. 2014, pp. 377–395.
  60. A. P. Black, “The Expression Problem, Gracefully,” in MASPEGHI@ECOOP 2015, M. Sakkinen, Ed. ACM, Jul. 2015, pp. 1–7.