research-article

Open access

HasChor: Functional Choreographic Programming for All (Functional Pearl)

Authors:

Lindsey KuperAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 7, Issue ICFP

Article No.: 207, Pages 541 - 565

https://doi.org/10.1145/3607849

Published: 31 August 2023 Publication History

Abstract

Choreographic programming is an emerging paradigm for programming distributed systems. In choreographic programming, the programmer describes the behavior of the entire system as a single, unified program -- a choreography -- which is then compiled to individual programs that run on each node, via a compilation step called endpoint projection. We present a new model for functional choreographic programming where choreographies are expressed as computations in a monad. Our model supports cutting-edge choreographic programming features that enable modularity and code reuse: in particular, it supports higher-order choreographies, in which a choreography may be passed as an argument to another choreography, and location-polymorphic choreographies, in which a choreography can abstract over nodes. Our model is implemented in a Haskell library, HasChor, which lets programmers write choreographic programs while using the rich Haskell ecosystem at no cost, bringing choreographic programming within reach of everyday Haskellers. Moreover, thanks to Haskell's abstractions, the implementation of the HasChor library itself is concise and understandable, boiling down endpoint projection to its short and simple essence.

References

[1]

Peter A. Alsberg and John D. Day. 1976. A Principle for Resilient Sharing of Distributed Resources. In Proceedings of the 2nd International Conference on Software Engineering (ICSE ’76). IEEE Computer Society Press, Washington, DC, USA. 562–570.

[2]

Davide Ancona, Viviana Bono, Mario Bravetti, Joana Campos, Giuseppe Castagna, Pierre-Malo Deniélou, Simon J. Gay, Nils Gesbert, Elena Giachino, Raymond Hu, Einar Broch Johnsen, Francisco Martins, Viviana Mascardi, Fabrizio Montesi, Rumyana Neykova, Nicholas Ng, Luca Padovani, Vasco T. Vasconcelos, and Nobuko Yoshida. 2016. Behavioral Types in Programming Languages. Foundations and Trends® in Programming Languages, 3, 2-3 (2016), 95–230. issn:2325-1107 https://doi.org/10.1561/2500000031

Digital Library

[3]

Samik Basu and Tevfik Bultan. 2016. Automated Choreography Repair. In Fundamental Approaches to Software Engineering, Perdita Stevens and Andrzej Wąsowski (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 13–30. isbn:978-3-662-49665-7

[4]

Marco Carbone, Kohei Honda, and Nobuko Yoshida. 2007. Structured Communication-Centred Programming for Web Services. In Programming Languages and Systems, Rocco De Nicola (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 2–17. isbn:978-3-540-71316-6

[5]

Marco Carbone, Kohei Honda, and Nobuko Yoshida. 2012. Structured Communication-Centered Programming for Web Services. ACM Trans. Program. Lang. Syst., 34, 2 (2012), Article 8, June, 78 pages. issn:0164-0925 https://doi.org/10.1145/2220365.2220367

Digital Library

[6]

Marco Carbone and Fabrizio Montesi. 2013. Deadlock-Freedom-by-Design: Multiparty Asynchronous Global Programming. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’13). Association for Computing Machinery, New York, NY, USA. 263–274. isbn:9781450318327 https://doi.org/10.1145/2429069.2429101

Digital Library

[7]

Adam Chlipala. 2015. Ur/Web: A Simple Model for Programming the Web. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’15). Association for Computing Machinery, New York, NY, USA. 153–165. isbn:9781450333009 https://doi.org/10.1145/2676726.2677004

Digital Library

[8]

Ezra Cooper, Sam Lindley, Philip Wadler, and Jeremy Yallop. 2007. Links: Web Programming Without Tiers. In Formal Methods for Components and Objects, Frank S. de Boer, Marcello M. Bonsangue, Susanne Graf, and Willem-Paul de Roever (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 266–296. isbn:978-3-540-74792-5

Digital Library

[9]

Ricardo Corin, Pierre-Malo Denielou, Cedric Fournet, Karthikeyan Bhargavan, and James Leifer. 2007. Secure Implementations for Typed Session Abstractions. In 20th IEEE Computer Security Foundations Symposium (CSF’07). 170–186. https://doi.org/10.1109/CSF.2007.29

Digital Library

[10]

Luís Cruz-Filipe, Eva Graversen, Lovro Lugović, Fabrizio Montesi, and Marco Peressotti. 2022. Functional Choreographic Programming. In Theoretical Aspects of Computing – ICTAC 2022, Helmut Seidl, Zhiming Liu, and Corina S. Pasareanu (Eds.). Springer International Publishing, Cham. 212–237. isbn:978-3-031-17715-6

Digital Library

[11]

Luís Cruz-Filipe and Fabrizio Montesi. 2020. A core model for choreographic programming. Theoretical Computer Science, 802 (2020), 38–66. issn:0304-3975 https://doi.org/10.1016/j.tcs.2019.07.005

Digital Library

[12]

Mila Dalla Preda, Maurizio Gabbrielli, Saverio Giallorenzo, Ivan Lanese, and Jacopo Mauro. 2016. Dynamic Choreographies: Theory And Implementation. Logical Methods in Computer Science, Volume 13, Issue 2 (April 10, 2017) lmcs:3263. https://doi.org/10.23638/LMCS-13(2:1)2017 arxiv:arXiv:1611.09067.

[13]

Mila Dalla Preda, Saverio Giallorenzo, Ivan Lanese, Jacopo Mauro, and Maurizio Gabbrielli. 2014. AIOCJ: A Choreographic Framework for Safe Adaptive Distributed Applications. CoRR, abs/1407.0975 (2014), arXiv:1407.0975. arxiv:1407.0975

[14]

W. Diffie and M. Hellman. 1976. New directions in cryptography. IEEE Transactions on Information Theory, 22, 6 (1976), 644–654. https://doi.org/10.1109/TIT.1976.1055638

Digital Library

[15]

The GHC Team. 2023. 6.1.1. Controlling extensions — Glasgow Haskell Compiler 9.7.20230225 User’s Guide. https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/control.html##extension-GHC2021

[16]

Saverio Giallorenzo, Fabrizio Montesi, and Marco Peressotti. 2020. Object-Oriented Choreographic Programming. https://doi.org/10.48550/ARXIV.2005.09520

[17]

Saverio Giallorenzo, Fabrizio Montesi, Marco Peressotti, David Richter, Guido Salvaneschi, and Pascal Weisenburger. 2021. Multiparty Languages: The Choreographic and Multitier Cases. In 35th European Conference on Object-Oriented Programming (ECOOP 2021), Anders Møller and Manu Sridharan (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 194). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 22:1–22:27. isbn:978-3-95977-190-0 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ECOOP.2021.22

[18]

Eva Graversen, Andrew K. Hirsch, and Fabrizio Montesi. 2023. Alice or Bob?: Process Polymorphism in Choreographies. https://doi.org/10.48550/ARXIV.2303.04678

[19]

J. N. Gray. 1978. Notes on data base operating systems. Springer Berlin Heidelberg, Berlin, Heidelberg. 393–481. isbn:978-3-540-35880-0 https://doi.org/10.1007/3-540-08755-9_9

[20]

Andrew K. Hirsch and Deepak Garg. 2022. Pirouette: Higher-Order Typed Functional Choreographies. Proc. ACM Program. Lang., 6, POPL (2022), Article 23, Jan., 27 pages. https://doi.org/10.1145/3498684

Digital Library

[21]

Kohei Honda, Nobuko Yoshida, and Marco Carbone. 2008. Multiparty Asynchronous Session Types. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’08). Association for Computing Machinery, New York, NY, USA. 273–284. isbn:9781595936899 https://doi.org/10.1145/1328438.1328472

Digital Library

[22]

Hans Hüttel, Ivan Lanese, Vasco T. Vasconcelos, Luís Caires, Marco Carbone, Pierre-Malo Deniélou, Dimitris Mostrous, Luca Padovani, António Ravara, Emilio Tuosto, Hugo Torres Vieira, and Gianluigi Zavattaro. 2016. Foundations of Session Types and Behavioural Contracts. ACM Comput. Surv., 49, 1 (2016), Article 3, apr, 36 pages. issn:0360-0300 https://doi.org/10.1145/2873052

Digital Library

[23]

Oleg Kiselyov and Hiromi Ishii. 2015. Freer Monads, More Extensible Effects. In Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell (Haskell ’15). Association for Computing Machinery, New York, NY, USA. 94–105. isbn:9781450338080 https://doi.org/10.1145/2804302.2804319

Digital Library

[24]

Butler Lampson and Howard E. Sturgis. 1979. Crash Recovery in a Distributed Data Storage System. June, https://www.microsoft.com/en-us/research/publication/crash-recovery-in-a-distributed-data-storage-system/ This unpublished paper was widely circulated in samizdat

[25]

Ivan Lanese, Claudio Guidi, Fabrizio Montesi, and Gianluigi Zavattaro. 2008. Bridging the Gap between Interaction- and Process-Oriented Choreographies. In Proceedings of the 2008 Sixth IEEE International Conference on Software Engineering and Formal Methods (SEFM ’08). IEEE Computer Society, USA. 323–332. isbn:9780769534374 https://doi.org/10.1109/SEFM.2008.11

Digital Library

[26]

Ivan Lanese, Fabrizio Montesi, and Gianluigi Zavattaro. 2013. Amending Choreographies. In Proceedings 9th International Workshop on Automated Specification and Verification of Web Systems, WWV 2013, Florence, Italy, 6th June 2013, António Ravara and Josep Silva (Eds.) (EPTCS, Vol. 123). 34–48. https://doi.org/10.4204/EPTCS.123.5

[27]

Jay McCarthy and Shriram Krishnamurthi. 2008. Cryptographic Protocol Explication and End-Point Projection. In Computer Security - ESORICS 2008, Sushil Jajodia and Javier Lopez (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 533–547. isbn:978-3-540-88313-5

Digital Library

[28]

Jan Mendling and Michael Hafner. 2005. From Inter-organizational Workflows to Process Execution: Generating BPEL from WS-CDL. In On the Move to Meaningful Internet Systems 2005: OTM 2005 Workshops, Robert Meersman, Zahir Tari, and Pilar Herrero (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 506–515. isbn:978-3-540-32132-3

[29]

Alp Mestanogullari, Sönke Hahn, Julian K. Arni, and Andres Löh. 2015. Type-Level Web APIs with Servant: An Exercise in Domain-Specific Generic Programming. In Proceedings of the 11th ACM SIGPLAN Workshop on Generic Programming (WGP 2015). Association for Computing Machinery, New York, NY, USA. 1–12. isbn:9781450338103 https://doi.org/10.1145/2808098.2808099

Digital Library

[30]

Fabrizio Montesi. 2013. Choreographic Programming. IT University of Copenhagen. https://www.fabriziomontesi.com/files/choreographic-programming.pdf

[31]

Fabrizio Montesi. 2023. Introduction to Choreographies. Cambridge University Press. https://doi.org/10.1017/9781108981491

[32]

Tom Murphy, VII, Karl Crary, and Robert Harper. 2007. Type-Safe Distributed Programming with ML5. In Trustworthy Global Computing, Third Symposium, TGC 2007, Sophia-Antipolis, France, November 5-6, 2007, Revised Selected Papers. 108–123. https://doi.org/10.1007/978-3-540-78663-4_9

[33]

Zongyan Qiu, Xiangpeng Zhao, Chao Cai, and Hongli Yang. 2007. Towards the Theoretical Foundation of Choreography. In Proceedings of the 16th International Conference on World Wide Web (WWW ’07). Association for Computing Machinery, New York, NY, USA. 973–982. isbn:9781595936547 https://doi.org/10.1145/1242572.1242704

Digital Library

[34]

Manuel Serrano, Erick Gallesio, and Florian Loitsch. 2006. Hop: a language for programming the web 2.0. In Companion to the 21th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2006, October 22-26, 2006, Portland, Oregon, USA. 975–985. https://doi.org/10.1145/1176617.1176756

Digital Library

[35]

Manuel Serrano and Vincent Prunet. 2016. A Glimpse of Hopjs. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). Association for Computing Machinery, New York, NY, USA. 180–192. isbn:9781450342193 https://doi.org/10.1145/2951913.2951916

Digital Library

[36]

Konstantin Shvachko, Hairong Kuang, Sanjay Radia, and Robert Chansler. 2010. The Hadoop Distributed File System. In 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST). 1–10. https://doi.org/10.1109/MSST.2010.5496972

Digital Library

[37]

Robbert van Renesse and Fred B. Schneider. 2004. Chain Replication for Supporting High Throughput and Availability. In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation - Volume 6 (OSDI’04). USENIX Association, USA. 7.

[38]

Pascal Weisenburger, Mirko Köhler, and Guido Salvaneschi. 2018. Distributed System Development with ScalaLoci. Proc. ACM Program. Lang., 2, OOPSLA (2018), Article 129, oct, 30 pages. https://doi.org/10.1145/3276499

Digital Library

[39]

Pascal Weisenburger, Johannes Wirth, and Guido Salvaneschi. 2020. A Survey of Multitier Programming. ACM Comput. Surv., 53, 4 (2020), Article 81, sep, 35 pages. issn:0360-0300 https://doi.org/10.1145/3397495

Digital Library

[40]

The World Wide Web Consortium. 2004. WS Choreography Model Overview. https://www.w3.org/TR/ws-chor-model/

[41]

The World Wide Web Consortium. 2005. Web Services Choreography Description Language Version 1.0. https://www.w3.org/TR/ws-cdl-10/

[42]

The World Wide Web Consortium. 2006. Web Services Choreography Description Language: Primer. https://www.w3.org/TR/ws-cdl-10-primer/

Cited By

Krook RHammersberg SVazou NMorris J(2024)Welcome to the Parti(tioning) (Functional Pearl): Using Rewrite Rules and Specialisation to Partition Haskell ProgramsProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678276(27-40)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678276
Giallorenzo SMontesi FPeressotti M(2024)Choral: Object-oriented Choreographic ProgrammingACM Transactions on Programming Languages and Systems10.1145/363239846:1(1-59)Online publication date: 16-Jan-2024
https://dl.acm.org/doi/10.1145/3632398
GRAVERSEN EHIRSCH AMONTESI F(2024)Alice or Bob?: Process polymorphism in choreographiesJournal of Functional Programming10.1017/S095679682300011434Online publication date: 23-Jan-2024
https://doi.org/10.1017/S0956796823000114
Show More Cited By

Index Terms

HasChor: Functional Choreographic Programming for All (Functional Pearl)
1. Computing methodologies

Index terms have been assigned to the content through auto-classification.

Recommendations

Functional Choreographic Programming
Theoretical Aspects of Computing – ICTAC 2022
Abstract
Choreographic programming is an emerging programming paradigm for concurrent and distributed systems, where developers write the communications that should be enacted and a compiler then automatically generates a distributed implementation.
...
Choral: Object-oriented Choreographic Programming
Choreographies are coordination plans for concurrent and distributed systems, which define the roles of the involved participants and how they are supposed to work together. In the paradigm of choreographic programming, choreographies are programs that ...
Exploring melody space in a live context using declarative functional programming
FARM '14: Proceedings of the 2nd ACM SIGPLAN international workshop on Functional art, music, modeling & design

This paper introduces Composer, a system offering composition capabilities for live performance, requiring no prior experience with composition and programming. Current research in computer assisted composition is focused on offline composition. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 7, Issue ICFP

August 2023

981 pages

EISSN:2475-1421

DOI:10.1145/3554311

Editor:
Michael Hicks
Amazon, USA

Issue’s Table of Contents

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 August 2023

Published in PACMPL Volume 7, Issue ICFP

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
4,700
Total Downloads

Downloads (Last 12 months)3,541
Downloads (Last 6 weeks)129

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Krook RHammersberg SVazou NMorris J(2024)Welcome to the Parti(tioning) (Functional Pearl): Using Rewrite Rules and Specialisation to Partition Haskell ProgramsProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678276(27-40)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678276
Giallorenzo SMontesi FPeressotti M(2024)Choral: Object-oriented Choreographic ProgrammingACM Transactions on Programming Languages and Systems10.1145/363239846:1(1-59)Online publication date: 16-Jan-2024
https://dl.acm.org/doi/10.1145/3632398
GRAVERSEN EHIRSCH AMONTESI F(2024)Alice or Bob?: Process polymorphism in choreographiesJournal of Functional Programming10.1017/S095679682300011434Online publication date: 23-Jan-2024
https://doi.org/10.1017/S0956796823000114
Zakhour GWeisenburger PSalvaneschi G(2023)Type-Safe Dynamic Placement with First-Class Placed ValuesProceedings of the ACM on Programming Languages10.1145/36228737:OOPSLA2(2142-2170)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622873
Gibbons JKidney DSchrijvers TWu NSperber MHutton G(2023)Phases in Software ArchitectureProceedings of the 1st ACM SIGPLAN International Workshop on Functional Software Architecture10.1145/3609025.3609479(29-33)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609025.3609479

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents