Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-21T22:31:26.011Z Has data issue: false hasContentIssue false
  • English
  • Français

Acute: High-level programming language design for distributed computation

Published online by Cambridge University Press:  01 July 2007

PETER SEWELL ,
JAMES J. LEIFER ,
KEITH WANSBROUGH ,
FRANCESCO ZAPPA NARDELLI ,
MAIR ALLEN-WILLIAMS ,
PIERRE HABOUZIT  and
VIKTOR VAFEIADIS
PETER SEWELL
Affiliation:
University of Cambridge, Cambridge, England, UK (e-mail: Peter.Sewell@cl.cam.ac.uk)
JAMES J. LEIFER
Affiliation:
INRIA Rocquencourt, France
KEITH WANSBROUGH
Affiliation:
University of Cambridge, Cambridge, England, UK (e-mail: Peter.Sewell@cl.cam.ac.uk)
FRANCESCO ZAPPA NARDELLI
Affiliation:
INRIA Rocquencourt, France
MAIR ALLEN-WILLIAMS
Affiliation:
University of Cambridge, Cambridge, England, UK (e-mail: Peter.Sewell@cl.cam.ac.uk)
PIERRE HABOUZIT
Affiliation:
INRIA Rocquencourt, France
VIKTOR VAFEIADIS
Affiliation:
University of Cambridge, Cambridge, England, UK (e-mail: Peter.Sewell@cl.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Existing languages provide good support for typeful programming of stand-alone programs. In a distributed system, however, there may be interaction between multiple instances of many distinct programs, sharing some (but not necessarily all) of their module structure, and with some instances rebuilt with new versions of certain modules as time goes on. In this paper, we discuss programming-language support for such systems, focussing on their typing and naming issues. We describe an experimental language, Acute, which extends an ML core to support distributed development, deployment, and execution, allowing type-safe interaction between separately built programs. The main features are (1) type-safe marshalling of arbitrary values; (2) type names that are generated (freshly and by hashing) to ensure that type equality tests suffice to protect the invariants of abstract types, across the entire distributed system; (3) expression-level names generated to ensure that name equality tests suffice for type safety of associated values, for example, values carried on named channels; (4) controlled dynamic rebinding of marshalled values to local resources; and (5) thunkification of threads and mutexes to support computation mobility. These features are a large part of what is needed for typeful distributed programming. They are a relatively lightweight extension of ML, should be efficiently implementable, and are expressive enough to enable a wide variety of distributed infrastructure layers to be written as simple library code above the byte-string network and persistent store APIs. This disentangles the language run-time from communication intricacies. This paper highlights the main design choices in Acute. It is supported by a full language definition (of typing, compilation, and operational semantics), by a prototype implementation, and by example distribution libraries.

Type
Article
Information
Journal of Functional Programming , Volume 17 , Issue 4-5 , July 2007 , pp. 547 - 612
Copyright
Copyright © Cambridge University Press 2007

References

The Acute team. (2005) Acute. Available at: http://www.cl.cam.ac.uk/users/pes20/acute.Google Scholar
Armstrong, J., Virding, R., Wikstrom, C. & Williams, M. (1996) Concurrent Programming in Erlang. 2nd ed. Englewood Cliffs, NJ, UK: Prentice Hall.Google Scholar
Benton, N., Cardelli, L. & Fournet, C. (2002) Modern concurrency abstractions for C♯. In Proc. 16th European Conference on Object-Oriented Programming (ECOOP), Máalaga, Spain, vol. 2374. Springer Verlag, pp. 415–440.Google Scholar
Bierman, G., Hicks, M., Sewell, P., Stoyle, G. & Wansbrough, K. (2003) Dynamic rebinding for marshalling and update, with destruct-time λ. In Proc. 8th ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden. ACM Press, 99–110.Google Scholar
Billings, J. (2005) A Bytecode Compiler for Acute, Computer Science Tripos Part II Dissertation. Cambridge, England: University of Cambridge.Google Scholar
Billings, J, Sewell, P., Shinwell, M. & Strnisa, R. (2006) Type-safe distributed programming for OCaml. In Proc. ML'06, 2006 ACM SIGPLAN Workshop on ML. pp. 20–31.CrossRefGoogle Scholar
Boudol, G. (2003) ULM: A core programming model for global computing. In Proc. European Symposium on Programming (ESOP'04), LNCS 2986, Springer-Verlag.Google Scholar
Buckley, A., Murray, M., Eisenbach, S. & Drossopoulou, S. (2005) Flexible bytecode for linking in .NET. Electr. Notes Theor. Comput. Sci., 141 (1), 75–92.CrossRefGoogle Scholar
Cardelli, L. (1995) A language with distributed scope. In Proc. 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language (POPL), San Francisco, California, ACM Press, pp. 286–297.Google Scholar
Cardelli, L. & Gordon, A. D. (1998) Mobile ambients. In Proc. Foundations of Software Science and Computation Structure (FoSSaCS), LNCS 1378, Lisbon, Portugal, Springer, pp. 140–155.Google Scholar
Conchon, S. & Le Fessant, F. (1999) Jocaml: Mobile agents for objective-caml. In Proc. 1st International Symposium on Agent Systems and Applications/3rd International Symposium on Mobile Agents (ASA/MA), Palm Springs, CA. IEEE Computer Society, pp. 22–29.Google Scholar
Deniélou, P.-M. & Leifer, J. J. (2006) Abstraction preservation and subtyping in distributed languages. In Proc.@ 11th ICFP.CrossRefGoogle Scholar
Dot03. (2003). Packacking and Deploying .Net Framework Applications (.Net Framework Tutorials, MSDN), http://msdn2.microsoft.com/cn-us/library/aa309395(V5.71).aspx.Google Scholar
Drossopoulou, S.Eisenbach, S. & Wragg, D. (1999) A fragment calculus — towards a model of separate compilation, linking and binary compatibility. In Proc. 14th IEEE Symp. on Logic in Computer Science (LICS). IEEE Computer Society Press, pp. 147–156.Google Scholar
Fournet, C., Gonthier, G., Lévy, J.-J., Maranget, L. & Rémy, D. (1996) A calculus of mobile agents. In Proc. CONCUR, LNCS 1119. Pisa, Italy, Springer, pp. 406–421.Google Scholar
Furuse, J. & Weis, P. (2000) Entrées/sorties de valeurs en Caml. In Proc. Journées francophones des langages applicatifs, pp. 79–98. http://jfla.inria.fr/2000/actes.html.Google Scholar
Grossman, D., Morrisett, G. & Zdancewic, S. (2000) Syntactic type abstraction. ACM TOPLAS 22 (6), 1037–1080.CrossRefGoogle Scholar
Harper, R. & Lillibridge, M. (1994) A type-theoretic approach to higher-order modules with sharing. In Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). Portland, OR: ACM Press, pp. 123–137.CrossRefGoogle Scholar
Harper, R. & Pierce, B. C. (2005) Design issues in advanced module systems. In Advanced Topics in Types and Programming Languages, Pierce, B. C. (ed). Cambridge (MA): The MIT Press, chapter 8.Google Scholar
Harper, R. & Stone, C. (2000) A type-theoretic interpretation of standard ML. In Proof, Language and Interaction: Essays in Honour of Robin Milner. Cambridge (MA): The MIT Press, chapter 12.Google Scholar
Hennessy, M., Rathke, J. & Yoshida, N. (2004) Safedpi: A language for controlling mobile code. In Proc. Foundations of Software Science and Computation Structure (FoSSaCS), part of ETAPS, LNCS 2987. Barcelona, Spain, Springer, pp. 241–256.Google Scholar
Heydon, A., Levin, R., Mann, T. & Yu, Y. (2006) Software Configuration Management Using Vesta. New York: Springer-Verlag.CrossRefGoogle Scholar
Hosoya, H., & Pierce, B. C. (1999) How Good Is Local Type Inference? Tech. Rept. MS-CIS-99-17. Philadalphia: University of Pennsylvania.Google Scholar
Le Botlan, D. & Rémy, D. (2003) MLF: Raising ML to the power of System-F. In Proceedings of the International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden. New York: ACM Press, pp. 27–38.Google Scholar
Le Fessant, F. (2001) Detecting distributed cycles of garbage in large-scale systems. In Proc. Principles of Distributed Computing (PODC).CrossRefGoogle Scholar
Lee, D. K., Crary, K. & Harper, R. (2007) Towards a mechanized metatheory of Standard ML. In Proc. 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM Press, pp. 173–184.Google Scholar
Leifer, J. J., Peskine, G., Sewell, P. & Wansbrough, K. (2003a) Global abstraction-safe marshalling with hash types. In Proc. 8th ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden, ACM Press, pp. 87–98.Google Scholar
Leifer, J. J., Peskine, G., Sewell, P. & Wansbrough, K. (2003b) Global Abstraction-Safe Marshalling With Hash Types. Tech. Rept. RR-4851. INRIA Rocquencourt. Available at: http://moscova.inria.fr/leifer/research.html. Also published as UCAM-CL-TR-569.CrossRefGoogle Scholar
Leroy, X. (1994) Manifest types, modules, and separate compilation. In Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM Press, pp. 109–122.CrossRefGoogle Scholar
Milner, R., Tofte, M. & Harper, R. (1990) The definition of Standard ML. Cambridge, MA:MIT Press.Google Scholar
Murphy, T., Crary, K., Harper, R. & Pfenning, F. (2004) A symmetric modal lambda calculus for distributed computing. In Proc. 19th IEEE Symp. on Logic in Computer Science (LICS). IEEE Computer Society Press, pp. 286–295.Google Scholar
Odersky, M., Zenger, C. & Zenger, M. (2001) Colored local type inference. ACM SIGPLAN Notices 36 (3), 41–53.CrossRefGoogle Scholar
Ohori, A. & Kato, K. (1993) Semantics for communication primitives in a polymorphic language. In Proc. 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM Press, pp. 99–112.CrossRefGoogle Scholar
Peskine, G. (Forthcoming) HOS: un calcul de modules adapté aux environnements répartis. Ph.D. thesis.Google Scholar
Pierce, B. C. & Turner, D. N. (1998) Local type inference. In Proc. POPL. Full version in ACM Trans. Programming Lang. Syst. (TOPLAS) 22 (1), 2000, 1–44.Google Scholar
Pierce, B. C. & Turner, D. N. (2000) Pict: A programming language based on the pi-calculus. In Proof, Language and Interaction: Essays in Honour of Robin Milner. Cambridge (MA): The MIT Press, chapter 15.Google Scholar
Rémy, D. (2002) Using, understanding, and unraveling the ocaml language. In Applied Semantics. Advanced Lectures. LNCS 2395, Barthe, G. (ed). pp. 413–537.Google Scholar
Reppy, J. H. (1999) Concurrent programming in ML. Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Rossberg, A. (2003) Generativity and dynamic opacity for abstract types. In Proc. 5th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP). ACM Press, pp. 241–252.Google Scholar
Rossberg, A., Le Botlan, D., Tack, G., Brunklaus, T. & Smolka, G. (2006) Alice through the looking glass. In Trends in Functional Programming, vol. 5. Munich, Germany: Intellect Books, pp. 79–96.Google Scholar
Sekiguchi, T. & Yonezawa, A. (1997) A calculus with code mobility. In Proc. 2nd IFIP TC6 WG6.1 International Conference on Formal Methods for Open Object-based Distributed Systems (FMOODS). Chapman and Hall, pp. 21–36.CrossRefGoogle Scholar
Sewell, P. (2000) Applied π—A Brief Tutorial. Tech. Rept. 498. Computer Laboratory, University of Cambridge. An extract appeared as Chapter 9, Formal Methods for Distributed Processing, A Survey of Object-oriented Approaches.Google Scholar
Sewell, P. (2001) Modules, abstract types, and distributed versioning. In Proc. 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM Press, pp. 236–247.Google Scholar
Sewell, P., Wojciechowski, P. T. & Pierce, B. C. (1999) Location-independent communication for mobile agents: a two-level architecture. In Internet Programming Languages, LNCS 1686. pp. 1–31.CrossRefGoogle Scholar
Sewell, P., Leifer, J. J., Wansbrough, K., Allen-Williams, M., Nardelli, Z., Francesco Habouzit, P. & Vafeiadis, V. (2004) Acute: High-level Programming Language Design for Distributed Computation. Design Rationale and Language Definition. Tech. Rept. 605. Cambridge, England: Computer Laboratory, University of Cambridge. Also published as INRIA RR-5329, 193pp.Google Scholar
Sewell, P., Leifer, J. J., Wansbrough, K., Allen-Williams, M., Zappa Nardelli, F., Habouzit, P. & Vafeiadis, V. (2005a) Source release of the Acute system. Available at: http://www.cl.cam.ac.uk/users/pes20/acute/.CrossRefGoogle Scholar
Sewell, P., Leifer, J. J., Wansbrough, K., Zappa, Nardelli F., Allen-Williams, M., Habouzit, P. & Vafeiadis, V. (2005b) Acute: High-level programming language design for distributed computation. In Proceedings of ICFP 2005: International Conference on Functional Programming (Tallinn).CrossRefGoogle Scholar
Shinwell, M. R. (2005) The Fresh Approach: Functional Programming With Names and Binders. Tech. Rept. UCAM-CL-TR-618. Cambridge, England: Computer Laboratory, University of Cambridge.Google Scholar
Shinwell, M. R., Pitts, A. M. & Gabbay, M. J. (2003)FreshML: Programming with binders made simple. In Proc. 8th ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden, ACM Press, pp. 263–274.Google Scholar
Stoyle, G. (2006) A Theory of Dynamic Software Updates, Ph.D. thesis. Cambridge, England: University of Cambridge.Google Scholar
Thomsen, B., Leth, L. & Kuo, T.-M. (1996) A facile tutorial. In: Proc. CONCUR LNCS 1119, Pisa, Italy, Springer Verlag, pp. 278–298.Google Scholar
Unyapoth, A. & Sewell, P. (2001). Nomadic Pict: Correct communication infrastructure for mobile computation. Proc. 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM Press, pp. 116–127.Google Scholar
Weirich, S. (2002). Programming With Types, Ph.D. thesis. Ithaca, NY: Cornell University.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.