[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

Embedded interpreters

Published: 01 July 2005 Publication History

Abstract

This is a tutorial on using type-indexed embedding/projection pairs when writing interpreters in statically-typed functional languages. The method allows (higher-order) values in the interpreting language to be embedded in the interpreted language and values from the interpreted language may be projected back into the interpreting one. This is particularly useful when adding command-line interfaces or scripting languages to applications written in functional languages. We first describe the basic idea and show how it may be extended to languages with recursive types and applied to elementary meta-programming. We then show how the method combines with Filinski's continuation-based monadic reflection operations to define an ‚extensional’ version of the call-by-value monadic translation and hence to allow values to be mapped bidirectionally between the levels of an interpreter for a functional language parameterized by an arbitrary monad. Finally, we show how SML functions may be embedded into, and projected from, an interpreter for an asynchronous $\pi$-calculus via an ‘extensional’ variant of a standard translation from $\lambda$ into $\pi$.

References

[1]
Abadi, M., Cardelli, L., Pierce, B. & Plotkin, G. (1991) Dynamic typing in a statically-typed language. ACM Trans. Program. Lang. & Syst. 13(2), 237-268.
[2]
Abelson, H., Sussman, G. J. & Sussman, J. (1985) Structure and Interpretation of Computer Programs (first edition). MIT Press.
[3]
Abelson, H., Sussman, G. J. & Sussman, J. (1996) Structure and Interpretation of Computer Programs (second edition). MIT Press.
[4]
Bentley, J. (1986) Programming pearls: Little languages. Comm. ACM, 29(8), 711-721.
[5]
Benton, N., Kennedy, A. & Russell, G. (1998) Compiling Standard ML to Java bytecodes. Proceedings 3rd ACM SIGPLAN Conference on Functional Programming (ICFP).
[6]
Benton, N., Hughes, J. & Moggi, E. (2002) Monads and effects. In: Barthe, G., Dybjer, P., Pinto, L. and Saraiva, J. (eds.), Applied Semantics, Advanced Lectures: Lecture Notes in Computer Science 2395. Springer-Verlag.
[7]
Benton, P. N. & Wadler, P. (1996) Linear logic, monads and the lambda calculus. Proceedings 11th IEEE Symposium on Logic in Computer Science (LICS).
[8]
Boudol, G. (1992) Asynchrony and the ¿-calculus. Technical report, Research Report 1702. INRIA.
[9]
Boudol, G. (1997) The pi-calculus in direct style. Conference Record of the 24th ACM Symposium on Principles of Programming Languages (POPL), pp. 228-241.
[10]
Clinick, A. (2000) Introducing JScript.NET. MSDN Library: http://msdn.microsoft.com/ library/.
[11]
Cousot, P. & Cousot, R. (1977) Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. Conference Record 4th ACM Symposium on Principles of Programming Languages (POPL). ACM.
[12]
Danvy, O. (1996) Type-directed partial evaluation. Proceedings 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM.
[13]
Danvy, O. (1998a) Functional unparsing. J. Funct. Program. 8(6), 621-625.
[14]
Danvy, O. (1998b) A simple solution to type specialization (extended abstract). In: Larsen, Skyum and Winskel (eds.), Proceedings 25th International Colloquium on Automata, Languages, and Programming (ICALP): Lecture Notes in Computer Science 1443, pp. 908- 917. Springer-Verlag.
[15]
Fernandez, M., Siméon, J. & Wadler, P. (2001) A semistructured monad for semistructured data. In: Van den Bussche, J. and Vianu, V. (eds.), Proceedings 8th International Conference on Database Theory: Lecture Notes in Computer Science 1973. Springer-Verlag.
[16]
Filinski, A. (1996) Controlling effects. Technical report CMU-CS-96-119, Carnegie-Mellon University.
[17]
Filinski, A. (1999) Representing layered monads. Proceedings 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 175-188. ACM.
[18]
Filinski, A. (2001) An extensional CPS transform. In: Sabry, A. (ed.), Proceedings 3rd ACM SIGPLAN Workshop on Continuations. Technical Report 545, Computer Science Department, Indiana University.
[19]
Findler, R. & Felleisen, M. (2002) Contracts for higher-order functions. Proceedings International Conference on Functional Programming (ICFP).
[20]
Harper, R. & Morrisett, G. (1995) Compiling polymorphism using intensional type analysis. Conference Record 22nd ACM Symposium on Principles of Programming Languages (POPL).
[21]
Hatcliff, J., Mogensen, T. & Thiemann, P. (eds.) (1998) Proceedings DIKU 1998 International Summerschool on Partial Evaluation: Lecture Notes in Computer Science 1706. Springer-Verlag.
[22]
Henglein, F. (1992) Dynamic typing. In: Krieg-Brückner, B. (ed.), Proceedings 4th European Symposium on Programming (ESOP): Lecture Notes in Computer Science 582. Springer-Verlag.
[23]
Honda, K. & Tokoro, M. (1991) An object calculus for asynchronous communication. In: America, P. (ed.), Proceedings European Conference on Object-oriented Programming (ECOOP): Lecture Notes in Computer Science 512, pp. 133-147. Springer-Verlag.
[24]
Hudak, P. (1998) Modular domain specific languages and tools. Proceedings 5th International Conference on Software Reuse, pp. 134-142.
[25]
Hugunin, J. (1997) Python and Java: The best of both worlds. Proceedings 6th International Python Conference.
[26]
Jeuring, J. & Jansson, P. (1996) Polytypic programming. In: Launchbury, J., Meijer, E. and Sheard, T. (eds.), Advanced Functional Programming, Second International School: Lecture Notes in Computer Science 1129, pp. 68-114. Springer-Verlag.
[27]
Kennedy, A. J. (2004) Functional pearl: Pickler combinators. J. Funct. Program. 14(6), 681-695.
[28]
Leroy, X. (1992) Unboxed objects and polymorphic typing. Conference Record 19th ACM Symposium on Principles of Programming Languages (POPL), pp. 177-188. ACM.
[29]
Liang, S. & Hudak, P. (1996) Modular denotational semantics for compiler construction. Proceedings European Symposium on Programming (ESOP).
[30]
Liang, S., Hudak, P. & Jones, M. (1995) Monad transformers and modular interpreters. Proceedings 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL).
[31]
McCracken, N. (1979) An investigation of a programming language with a polymorphic type structure. PhD thesis, Syracuse University.
[32]
Milner, R. (1992) Functions as processes. Math. Struct. Comput. Sci. 2(2), 119-146.
[33]
Milner, R. (1999) Communicating and Mobile Systems: The pi-calculus. Cambridge University Press.
[34]
Milner, R., Parrow, J. & Walker, D. (1992) A calculus of mobile processes I/II. Infor. & Comput. 100(1), 1-77.
[35]
Moggi, E. (1991) Notions of computation and monads. Infor. & Comput. 93, 55-92.
[36]
Mozilla Organisation, The. (1998) Rhino: Javascript for Java. http://www.mozilla.org/ rhino/.
[37]
Ohori, A. & Kato, K. (1993) Semantics for communication primitives in a polymorphic language. Conference Record 20th ACM Symposium on Principles of Programming Languages (POPL), pp. 99-112.
[38]
Ousterhout, J. K. (1990) Tcl: An embeddable scripting language. Proceedings Winter USENIX Conference, pp. 133-146.
[39]
Ousterhout, J. K. (1998) Scripting: Higher-level programming for the 21st century. IEEE Comput. 31(3), 23-30.
[40]
Paulson, L. C. (1991) ML for the Working Programmer. Cambridge University Press.
[41]
Pierce, B. C. & Turner, D. N. (2000) Pict: A programming language based on the pi-calculus. In: Plotkin, G., Stirling, C. and Tofte, M. (eds.), Proof, Language and Interaction: Essays in honour of Robin Milner. MIT Press.
[42]
Ramsey, N. (2003) Embedding an interpreted language using higher-order functions and types. ACM SIGPLAN 2003 Workshop on Interpreters, Virtual Machines and Emulators.
[43]
Ramsey, N. (2004) ML module mania: A type-safe, separately compiled, extensible interpreter. http://www.eecs.harvard.edu/~nr/.
[44]
Reppy, J. H. (1999) Concurrent Programming in ML. Cambridge University Press.
[45]
Reynolds, J. C. (1972) Definitional interpreters for higher-order programming languages. Proceedings ACM Annual Conference, pp. 717-740. Boston, MA.
[46]
Reynolds, J. C. (1998) Definitional interpreters for higher-order programming languages. Higher-order & Symbolic Computation, 11(4), 363-397.
[47]
Reynolds, J. C. (2000) The meaning of types - from intrinsic to extrinsic semantics. Technical report BRICS RS-00-32, BRICS, University of Aarhus.
[48]
Rhiger, M. (2003) A foundation for embedded languages. ACM Trans. Program. Lang. & Syst. (TOPLAS), 25(3).
[49]
Rose, K. (1998) Type-directed partial evaluation in Haskell. In: Danvy, O. and Dybjer, P. (eds.), Preliminary Proceedings 1998 APPSEM Workshop on Normalization by Evaluation. BRICS Notes, nos. NS-98-1.
[50]
Sangiorgi, D. (1992) The lazy lambda calculus in a concurrency scenario. Proceedings 7th Annual IEEE Symposium on Logic in Computer Science.
[51]
Sangiorgi, D. & Walker, D. (2001) The pi-calculus: A theory of mobile processes. Cambridge University Press.
[52]
Scott, D. (1976) Data types as lattices. SIAM J. Comput. 5(3), 522-587.
[53]
Sheard, T. & Pasalic, E. (2004) Two-level types and parameterized modules. J. Funct. Program. 14(5), 547-587.
[54]
Shivers, O. (1996) A universal scripting framework, or lambda: The ultimate "little language". In: Jaffar, J. & Yap, R. H. C. (eds.), Concurrency and Parallelism, Programming, Networking, and Security: Lecture Notes in Computer Science 1179, pp. 254-265. Springer-Verlag.
[55]
Slind, K. (1991) Object language embedding in Standard ML of New Jersey. Proceedings 2nd ML Workshop. Revised February 1996.
[56]
Steele, G. L. Jr. (1994) Building interpreters by composing monads. Conference Record 21st ACM Symposium on Principles of Programming Languages (POPL).
[57]
Taha, W. & Sheard, T. (2000) MetaML and multi-stage programming with explicit annotations. Theo. Comput. Sci. 248(1-2), 211-242.
[58]
Trifonov, V., Saha, B. & Shao, Z. (2000) Fully reflexive intensional type analysis. Proceedings 5th ACM SIGPLAN International Conference on Functional Programming.
[59]
van Deursen, A., Klint, P. & Visser, J. (2000) Domain-specific languages: an annotated bibliography. ACM SIGPLAN Notices, 35(6), 26-36.
[60]
van Rossum, G. (2003) Extending and embedding the Python interpreter. Release 2.3 http: //www.python.org/doc/current/ext/ext.html.
[61]
Wadler, P. (1992) The essence of functional programming. Proceedings 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL).
[62]
Wand, M. (1980) Continuation-based multiprocessing. Proceedings 1980 ACM Conference on LISP and Functional Programming.
[63]
Weirich, S. (2004) Functional pearl: Type-safe cast. J. Funct. Program. 14(6), 727-739.
[64]
Weirich, S. (2001) Encoding intensional type analysis. In: Sands, D. (ed.), 10th European Symposium on Programming (ESOP): Lecture Notes in Computer Science 2028, pp. 92-106. Springer.
[65]
World Wide Web Consortium (2002) Web services activity. http://www.w3.org/2002/ws/.
[66]
Yang, Z. (1998) Encoding types in ML-like languages. Proceedings 3rd ACM SIGPLAN International Conference on Functional Programming (ICFP).

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Functional Programming
Journal of Functional Programming  Volume 15, Issue 4
July 2005
149 pages

Publisher

Cambridge University Press

United States

Publication History

Published: 01 July 2005

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2020)On Multi-language AbstractionStatic Analysis10.1007/978-3-030-65474-0_14(310-332)Online publication date: 18-Nov-2020
  • (2018)Graduality from embedding-projection pairsProceedings of the ACM on Programming Languages10.1145/32367682:ICFP(1-30)Online publication date: 30-Jul-2018
  • (2016)Fully abstract compilation via universal embeddingACM SIGPLAN Notices10.1145/3022670.295194151:9(103-116)Online publication date: 4-Sep-2016
  • (2016)Fully abstract compilation via universal embeddingProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951941(103-116)Online publication date: 4-Sep-2016
  • (2016)Proceedings of the 21st ACM SIGPLAN International Conference on Functional ProgrammingundefinedOnline publication date: 4-Sep-2016
  • (2013)Abstract Machines for Game Semantics, RevisitedProceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS.2013.63(560-569)Online publication date: 25-Jun-2013
  • (2012)Linguistic foundations for bidirectional transformationsProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems10.1145/2213556.2213568(61-64)Online publication date: 21-May-2012
  • (2011)Embedding an interpreted language using higher-order functions and typesJournal of Functional Programming10.1017/S095679681100021921:6(585-615)Online publication date: 1-Nov-2011
  • (2010)Three complementary approaches to bidirectional programmingProceedings of the 2010 international spring school conference on Generic and Indexed Programming10.1007/978-3-642-32202-0_1(1-46)Online publication date: 22-Mar-2010
  • (2009)Operational semantics for multi-language programsACM Transactions on Programming Languages and Systems10.1145/1498926.149893031:3(1-44)Online publication date: 21-Apr-2009
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media