Scala-Virtualized: linguistic reuse for deep embeddings
Tóm tắt
Scala-Virtualized extends the Scala language to better support hosting embedded DSLs. Scala is an expressive language that provides a flexible syntax, type-level computation using implicits, and other features that facilitate the development of embedded DSLs. However, many of these features work well only for shallow embeddings, i.e. DSLs which are implemented as plain libraries. Shallow embeddings automatically profit from features of the host language through linguistic reuse: any DSL expression is just as a regular Scala expression. But in many cases, directly executing DSL programs within the host language is not enough and deep embeddings are needed, which reify DSL programs into a data structure representation that can be analyzed, optimized, or further translated. For deep embeddings, linguistic reuse is no longer automatic. Scala-Virtualized defines many of the language’s built-in constructs as method calls, which enables DSLs to redefine the built-in semantics using familiar language mechanisms like overloading and overriding. This in turn enables an easier progression from shallow to deep embeddings, as core language constructs such as conditionals or pattern matching can be redefined to build a reified representation of the operation itself. While this facility brings shallow, syntactic, reuse to deep embeddings, we also present examples of what we call deep linguistic reuse: combining shallow and deep components in a single DSL in such a way that certain features are fully implemented in the shallow embedding part and do not need to be reified at the deep embedding level.
Tài liệu tham khảo
Ackermann, S., Jovanovic, V., Rompf, T., Odersky, M.: Jet: an embedded DSL for high performance big data processing. BigData (2012). http://infoscience.epfl.ch/record/181673/files/paper.pdf
Armstrong, J.: Erlang. Commun. ACM 53(9), 68–75 (2010)
Axelsson, E., Claessen, K., Sheeran, M., Svenningsson, J., Engdal, D., Persson, A.: The design and implementation of feldspar an embedded language for digital signal processing. In: Proceedings of the 22nd International Conference on Implementation and Application of Functional Languages, IFL’10, pp. 121–136. Springer, Berlin (2011)
Bassetti, F., Davis, K., Quinlan, D.J.: C++ expression templates performance issues in scientific computing. In: IPPS/SPDP, pp. 635–639 (1998)
Bravenboer, M., Visser, E.: Concrete syntax for objects: domain-specific language embedding and assimilation without restrictions. In: Vlissides, J.M., Schmidt, D.C. (eds.) OOPSLA, pp. 365–383. ACM, New York (2004)
Brown, K.J., Sujeeth, A.K., Lee, H., Rompf, T., Chafi, H., Odersky, M., Olukotun, K.: A heterogeneous parallel framework for domain-specific languages. In: PACT, October (2011)
Burmako, E., Odersky, M.: Scala Macros, a Technical Report. In: Third International Valentin Turchin Workshop on Metacomputation (2012)
Carette, J., Kiselyov, O., Shan, C.-c.: Finally tagless, partially evaluated: tagless staged interpreters for simpler typed languages. J. Funct. Program. 19(5), 509–543 (2009)
Chafi, H., DeVito, Z., Moors, A., Rompf, T., Sujeeth, A.K., Hanrahan, P., Odersky, M., Olukotun, K.: Language virtualization for heterogeneous parallel computing. Onward! (2010)
Crotinger, J., Haney, S., Smith, S., Karmesin, S.: PETE: The portable expression template engine. Dr. Dobb’s J. (Oct. 1999)
Oliveira, B.C.d.S., Moors, A., Odersky, M.: Type classes as objects and implicits. In: Cook, W.R., Clarke, S., Rinard, M.C. (eds.) OOPSLA, pp. 341–360. ACM, New York (2010)
Davis, K., Rose, D.J.Q.: An optimizing transformation system for C++ array-class libraries. In: ECOOP Workshops, pp. 452–453 (1998)
Dubochet, G.: Embedded domain-specific languages using libraries and dynamic metaprogramming. PhD thesis, Lausanne (2011)
Emir, B., Odersky, M., Williams, J.: Matching objects with patterns. In: ECOOP, pp. 273–298 (2007)
Erdweg, S., Giarrusso, P.G., Rendel, T.: Language composition untangled. In: Proceedings of the 12th Workshop on Language Descriptions, Tools and Applications (LDTA) (2012)
Erdweg, S., Rendel, T., Kästner, C., Ostermann, K.: SugarJ: library-based syntactic language extensibility. In: Lopes, C.V., Fisher, K. (eds.) OOPSLA, pp. 391–406. ACM, New York (2011)
Filinski, A.: Representing monads. In: POPL, pp. 446–457 (1994)
Filinski, A.: Monads in action. In: POPL, pp. 483–494 (2010)
Haller, P., Odersky, M.: Scala actors: unifying thread-based and event-based programming. Theor. Comput. Sci. 410(2–3), 202–220 (2009)
Hofer, C., Ostermann, K., Rendel, T., Moors, A.: Polymorphic embedding of DSLs. In: GPCE (2008)
Hudak, P.: Building domain-specific embedded languages. ACM Comput. Surv. 28, 196 (1996)
Hudak, P.: Modular domain specific languages and tools. In: Proceedings. Fifth International Conference on Software Reuse, 1998, pp. 134–142 (1998)
Karmesin, S., Crotinger, J., Cummings, J., Haney, S., Humphrey, W., Reynders, J., Smith, S., Williams, T.J.: Array design and expression evaluation in POOMA II. In: ISCOPE, pp. 231–238 (1998)
Kiselyov, O., chieh Shan, C.: Embedded probabilistic programming. In: Taha, W.M. (ed.) DSL. Lecture Notes in Computer Science, vol. 5658, pp. 360–384. Springer, Berlin (2009)
Kossakowski, G., Amin, N., Rompf, T., Odersky, M.: Javascript as an embedded DSL. In: ECOOP (2012)
Krishnamurthi, S.: Linguistic reuse. PhD thesis, Computer Science, Rice University, Houston (2001)
Landin, P.J.: The next 700 programming languages. Commun. ACM 9(3), 157–166 (1966)
Lee, H., Brown, K.J., Sujeeth, A.K., Chafi, H., Rompf, T., Odersky, M., Olukotun, K.: Implementing domain-specific languages for heterogeneous parallel computing. IEEE MICRO 31(5), 42–53 (2011)
Moggi, E.: Notions of computation and monads. Inf. Comput. 93(1), 55–92 (1991)
Moors, A., Piessens, F., Odersky, M.: Parser combinators in Scala. Technical Report CW491, Department of Computer Science, K.U. Leuven (2008). http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW491.abs.html
Moors, A., Rompf, T., Haller, P., Odersky, M.: Scala-Virtualized. In: PEPM, pp. 117–120 (2012)
Odersky, M., Moors, A.: Fighting bit rot with types (experience report: Scala collections). In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15–17, 2009, IIT Kanpur, India, vol. 4, pp. 427–451 (2009)
Odersky, M., Spoon, L., Venners, B.: Programming in Scala, 2nd edn. Artima Press (2010)
Odersky, M., Zenger, M.: Scalable component abstractions. In: Johnson, R.E., Gabriel, R.P. (eds.) OOPSLA, pp. 41–57. ACM, New York (2005)
Petricek, T., Syme, D.: Syntax matters: writing abstract computations in F#. In: TFP (2012)
Peyton Jones, S. [editor], Hughes, J. [editor], Augustsson, L., Barton, D., Boutel, B., Burton, W., Fraser, S., Fasel, J., Hammond, K., Hinze, R., Hudak, P., Johnsson, T., Jones, M., Launchbury, J., Meijer, E., Peterson, J., Reid, A., Runciman, C., Wadler, P.: Haskell 98—A non-strict, purely functional language. http://www.haskell.org/definition/ (February 1999)
Popek, G.J., Goldberg, R.P.: Formal requirements for virtualizable third generation architectures. Commun. ACM 17(7), 412–421 (1974)
Ramsey, N., Pfeffer, A.: Stochastic lambda calculus and monads of probability distributions. In: POPL, pp. 154–165 (2002)
Reynolds, J.: User-defined types and procedural data structures as complementary approaches to data abstraction (1975)
Rompf, T.: Lightweight modular staging and embedded compilers. PhD thesis, IC, Lausanne (2012)
Rompf, T., Maier, I., Odersky, M.: Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform. In: Hutton, G., Tolmach, A.P. (eds.) ICFP, pp. 317–328. ACM, New York (2009)
Rompf, T., Odersky, M.: Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLS. In: Visser, E., Järvi, J. (eds.) GPCE, pp. 127–136. ACM, New York (2010)
Rompf, T., Odersky, M.: Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLS. Commun. ACM 55(6), 121–130 (2012)
Rompf, T., Sujeeth, A.K., Amin, N., Brown, K., Jovanovic, V., Lee, H., Jonnalagedda, M., Olukotun, K., Odersky, M.: Optimizing data structures in high-level programs. In: POPL (2013)
Rompf, T., Sujeeth, A.K., Lee, H., Brown, K.J., Chafi, H., Odersky, M., Olukotun, K.: Building-blocks for performance oriented DSLS. In: DSL, pp. 93–117 (2011)
Scholz, S.-B.: Single assignment C: efficient support for high-level array operations in a functional setting. J. Funct. Program. 13(6), 1005–1059 (2003)
Sheard, T., Jones, S.L.P.: Template meta-programming for Haskell. SIGPLAN Not. 37(12), 60–75 (2002)
Siek, J.G.: General purpose languages should be metalanguages. In: Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM ’10, pp. 3–4. ACM, New York (2010)
Siek, J.G., Lumsdaine, A.: The Matrix Template Library: a generic programming approach to high performance numerical linear algebra. In: International Symposium on Computing in Object-Oriented Parallel Environments. Lecture Notes in Computer Science, vol. 1505, pp. 59–70 (1998)
Smith, B.C.: Procedural reflection in programming languages. PhD thesis, MIT (1982)
Steele, G.: Growing a language. High.-Order Symb. Comput. 12(3), 221–236 (1999)
Sujeeth, A.K., Lee, H., Brown, K.J., Rompf, T., Wu, M., Atreya, A.R., Odersky, M., Olukotun, K.: OptiML: an implicitly parallel domain-specific language for machine learning. In: Proceedings of the 28th International Conference on Machine Learning, ICML (2011)
Swadi, K.N., Taha, W., Kiselyov, O., Pasalic, E.: A monadic approach for avoiding code duplication when staging memoized functions. In: PEPM, pp. 160–169 (2006)
Syme, D., Granicz, A., Cisternino, A.: Expert F#. Apress (2007)
Taha, W.: A sound reduction semantics for untyped CBN multi-stage computation. or, the theory of MetaML is non-trivial (extended abstract). In: PEPM, pp. 34–43 (2000)
Taha, W., Sheard, T.: MetaML and multi-stage programming with explicit annotations. Theor. Comput. Sci. 248(1–2), 211–242 (2000)
Tobin-Hochstadt, S., Felleisen, M.: The design and implementation of typed scheme. In: Necula, G.C., Wadler, P. (eds.) POPL, pp. 395–406. ACM, New York (2008)
Tobin-Hochstadt, S., St-Amour, V., Culpepper, R., Flatt, M., Felleisen, M.: Languages as libraries. In: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, pp. 132–141. ACM, New York (2011)
Torreborre, E.: Specs: software specifications for Scala (2011)
Ureche, V., Rompf, T., Sujeeth, A.K., Chafi, H., Odersky, M.: Stagedsac: a case study in performance-oriented DSL development. In: PEPM, pp. 73–82 (2012)
Veldhuizen, T.L.: Expression templates. C++ Rep. 7(5), 26–31 (1995). Reprinted in C++ Gems, ed. S. Lippman
Vogt, J.C.: Type safe integration of query languages into Scala. Diplomarbeit, RWTH Aachen, Germany (2011)
Wadler, P.: Comprehending monads. Math. Struct. Comput. Sci. 2(4), 461–493 (1992)
Wadler, P., Blott, S.: How to make ad-hoc polymorphism less ad-hoc. In: POPL, pp. 60–76 (1989)