research-article

Open access

Versatile event correlation with algebraic effects

Authors:

Oliver Bračevac,

Guido Salvaneschi,

Sebastian Erdweg,

Patrick Eugster,

Mira MeziniAuthors Info & Claims

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

Article No.: 67, Pages 1 - 31

https://doi.org/10.1145/3236762

Published: 30 July 2018 Publication History

Abstract

We present the first language design to uniformly express variants of n-way joins over asynchronous event streams from different domains, e.g., stream-relational algebra, event processing, reactive and concurrent programming. We model asynchronous reactive programs and joins in direct style, on top of algebraic effects and handlers. Effect handlers act as modular interpreters of event notifications, enabling fine-grained control abstractions and customizable event matching. Join variants can be considered as cartesian product computations with ”degenerate” control flow, such that unnecessary tuples are not materialized a priori. Based on this computational interpretation, we decompose joins into a generic, naive enumeration procedure of the cartesian product, plus variant-specific extensions, represented in terms of user-supplied effect handlers. Our microbenchmarks validate that this extensible design avoids needless materialization. Alongside a formal semantics for joining and prototypes in Koka and multicore OCaml, we contribute a systematic comparison of the covered domains and features.

References

[1]

Jagrati Agrawal, Yanlei Diao, Daniel Gyllstrom, and Neil Immerman. 2008. Efficient Pattern Matching over Event Streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[2]

Tyler Akidau, Robert Bradshaw, Craig Chambers, Slava Chernyak, Rafael J. Fernández-Moctezuma, Reuven Lax, Sam McVeety, Daniel Mills, Frances Perry, Eric Schmidt, and Sam Whittle. 2015. The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-scale, Unbounded, Out-of-order Data Processing. Proceedings of the VLDB Endowment 12 (2015), 1792–1803.

Digital Library

[3]

Arvind Arasu, Shivnath Babu, and Jennifer Widom. 2004. CQL: A Language for Continuous Queries over Streams and Relations. In Database Programming Languages. Springer Berlin Heidelberg.

[4]

Arvind Arasu, Shivnath Babu, and Jennifer Widom. 2006. The CQL Continuous Query Language: Semantic Foundations and Query Execution. The VLDB Journal (2006).

Digital Library

[5]

Arvind Arasu and Jennifer Widom. 2004. A Denotational Semantics for Continuous Queries over Streams and Relations. SIGMOD Record (2004).

Digital Library

[6]

Engineer Bainomugisha, Andoni Lombide Carreton, Tom Van Cutsem, Stijn Mostinckx, and Wolfgang De Meuter. 2013. A survey on reactive programming. Comput. Surveys 45, 4 (2013).

Digital Library

[7]

Andrej Bauer and Matija Pretnar. 2015. Programming with Algebraic Effects and Handlers. Journal of Logical and Algebraic Methods in Programming 84, 1 (2015), 108–123.

[8]

Nick Benton, Luca Cardelli, and Cédric Fournet. 2004. Modern Concurrency Abstractions for C#. Transactions on Programming Languages and Systems (TOPLAS) 26, 5 (2004), 769–804.

Digital Library

[9]

Aggelos Biboudis, Nick Palladinos, George Fourtounis, and Yannis Smaragdakis. 2015. Streams à la carte: Extensible Pipelines with Object Algebras. In Proceedings of European Conference on Object-Oriented Programming (ECOOP).

[10]

Gavin Bierman, Claudio Russo, Geoffrey Mainland, Erik Meijer, and Mads Torgersen. 2012. Pause ’n’ Play: Formalizing Asynchronous C♯. In Proceedings of European Conference on Object-Oriented Programming (ECOOP), James Noble (Ed.).

Digital Library

[11]

Dariusz Biernacki, Maciej Piróg, Piotr Polesiuk, and Filip Sieczkowski. 2018. Handle with care: relational interpretation of algebraic effects and handlers. PACMPL POPL (2018).

Digital Library

[12]

Irina Botan, Roozbeh Derakhshan, Nihal Dindar, Laura Haas, Renée J. Miller, and Nesime Tatbul. 2010. SECRET: A Model for Analysis of the Execution Semantics of Stream Processing Systems. Proceedings of the VLDB Endowment (2010).

Digital Library

[13]

Andrew Cave, Francisco Ferreira, Prakash Panangaden, and Brigitte Pientka. 2014. Fair Reactive Programming. In Proceedings of Symposium on Principles of Programming Languages (POPL) (POPL ’14). ACM, 361–372.

Digital Library

[14]

Sharma Chakravarthy, V. Krishnaprasad, Eman Anwar, and S.-K. Kim. 1994. Composite Events for Active Databases: Semantics, Contexts and Detection. In Proceedings of International Conference on Very Large Data Bases (VLDB).

Digital Library

[15]

S. Chakravarthy and D. Mishra. 1994. Snoop: An expressive event specification language for active databases. Data & Knowledge Engineering 14, 1 (1994), 1 – 26.

Digital Library

[16]

James Cheney, Sam Lindley, and Philip Wadler. 2013. A practical theory of language-integrated query. In Proceedings of International Conference on Functional Programming (ICFP).

Digital Library

[17]

Silvain Conchon and Fabrice Le Fessant. 1999. JoCaml: mobile agents for Objective-Caml. In First and Third International Symposium on Agent Systems Applications, and Mobile Agents (ASAMA).

Digital Library

[18]

Gregory H. Cooper and Shriram Krishnamurthi. 2006. Embedding Dynamic Dataflow in a Call-by-Value Language. In Proceedings of the European Conference on Programming Languages and Systems (ESOP).

Digital Library

[19]

Gianpaolo Cugola and Alessandro Margara. 2010. TESLA: A Formally Defined Event Specification Language. In Proceedings of the International Conference on Distributed Event-based Systems (DEBS).

Digital Library

[20]

Gianpaolo Cugola and Alessandro Margara. 2012. Processing Flows of Information: From Data Stream to Complex Event Processing. Comput. Surveys 44, 3 (2012), 15:1–15:62.

Digital Library

[21]

Evan Czaplicki and Stephen Chong. 2013. Asynchronous Functional Reactive Programming for GUIs. In Proceedings of Conference on Programming Language Design and Implementation (PLDI).

Digital Library

[22]

Ana Lúcia de Moura and Roberto Ierusalimschy. 2009. Revisiting coroutines. ACM Trans. Program. Lang. Syst. 31, 2 (2009).

Digital Library

[23]

Alan Demers, Johannes Gehrke, Mingsheng Hong, Mirek Riedewald, and Walker White. 2006. Towards Expressive Publish/Subscribe Systems. In Proceedings of the 10th International Conference on Advances in Database Technology (EDBT’06).

Digital Library

[24]

Yanlei Diao, Neil Immerman, and Daniel Gyllstrom. 2007. SASE+: An Agile Language for Kleene Closure Over Event Streams. Technical Report. UMass Technical Report 07.

[25]

Nihal Dindar, Nesime Tatbul, Renée J. Miller, Laura M. Haas, and Irina Botan. 2013. Modeling the execution semantics of stream processing engines with SECRET. The VLDB Journal (2013).

Digital Library

[26]

Stephen Dolan, Spiros Eliopoulos, Daniel Hillerström, Anil Madhavapeddy, KC Sivaramakrishnan, and Leo White. 2017. Concurrent System Programming with Effect Handlers. In Proceedings of the Symposium on Trends in Functional Programming.

[27]

Jonathan Edwards. 2009. Coherent Reaction. In Proceedings of Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA).

Digital Library

[28]

Conal M. Elliott. 2009. Push-pull Functional Reactive Programming. In Proceedings of the 2nd ACM SIGPLAN Symposium on Haskell (Haskell’09).

Digital Library

[29]

Esper. {n. d.}. Esper. http://www.espertech.com/esper/ .

[30]

Patrick Eugster and K.R. Jayaram. 2009. EventJava: An Extension of Java for Event Correlation. In Proceedings of European Conference on Object-Oriented Programming (ECOOP).

Digital Library

[31]

Matthias Felleisen and Robert Hieb. 1992. The Revised Report on the Syntactic Theories of Sequential Control and State. Theoretical Computer Science 103, 2 (1992), 235–271.

Digital Library

[32]

Matthew Fluet, Mike Rainey, John H. Reppy, and Adam Shaw. 2008. Implicitly-threaded parallelism in Manticore. In Proceedings of International Conference on Functional Programming (ICFP).

Digital Library

[33]

Yannick Forster, Ohad Kammar, Sam Lindley, and Matija Pretnar. 2017. On the Expressive Power of User-defined Effects: Effect Handlers, Monadic Reflection, Delimited Control. Proc. ACM Program. Lang. 1, ICFP (2017).

Digital Library

[34]

Cédric Fournet and Georges Gonthier. 1996. The reflexive CHAM and the Join-calculus. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[35]

Philipp Haller and Heather Miller. 2013. RAY: Integrating Rx and Async for Direct-Style Reactive Streams. (2013).

[36]

Martin Hirzel, Robert Soulé, Scott Schneider, Bugra Gedik, and Robert Grimm. 2013. A catalog of stream processing optimizations. Comput. Surveys (2013).

Digital Library

[37]

John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. 2006. Automata theory, languages, and computation. Pearson.

Digital Library

[38]

Ohad Kammar, Sam Lindley, and Nicolas Oury. 2013. Handlers in action. In Proceedings of International Conference on Functional Programming (ICFP).

Digital Library

[39]

Oleg Kiselyov, Aggelos Biboudis, Nick Palladinos, and Yannis Smaragdakis. 2017. Stream Fusion, to Completeness. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[40]

Oleg Kiselyov and Hiromi Ishii. 2015. Freer monads, more extensible effects. In Proceedings of Haskell Symposium.

Digital Library

[41]

Jürgen Krämer and Bernhard Seeger. 2009. Semantics and implementation of continuous sliding window queries over data streams. ACM Transactions on Database Systems 34, 1 (2009), 1–49.

Digital Library

[42]

Neelakantan R. Krishnaswami. 2013. Higher-order Functional Reactive Programming Without Spacetime Leaks. In Proceedings of International Conference on Functional Programming (ICFP).

Digital Library

[43]

Daan Leijen. 2017a. Structured Asynchrony with Algebraic Effects. In Proceedings of the International Workshop on TypeDriven Development (TyDe).

Digital Library

[44]

Daan Leijen. 2017b. Type directed compilation of row-typed algebraic effects. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[45]

Jeffrey R. Lewis, John Launchbury, Erik Meijer, and Mark B. Shields. 2000. Implicit Parameters: Dynamic Scoping with Static Types. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[46]

Sheng Liang, Paul Hudak, and Mark P. Jones. 1995. Monad Transformers and Modular Interpreters. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[47]

Sam Lindley. 2014. Algebraic effects and effect handlers for idioms and arrows. In Proceedings of the 10th ACM SIGPLAN workshop on Generic programming, WGP 2014, Gothenburg, Sweden, August 31, 2014.

Digital Library

[48]

Sam Lindley, Conor McBride, and Craig McLaughlin. 2017. Do Be Do Be Do. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[49]

Hai Liu and Paul Hudak. 2007. Plugging a Space Leak with an Arrow. (2007), 29 – 45. Festschrift honoring Gary Lindstrom on his retirement from the University of Utah after 30 years of service.

Digital Library

[50]

David C. Luckham. 2001. The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems. Addison-Wesley Longman Publishing Co., Inc.

Digital Library

[51]

D. C. Luckham, J. J. Kenney, L. M. Augustin, J. Vera, D. Bryan, and W. Mann. 1995. Specification and analysis of system architecture using Rapide. IEEE Transactions on Software Engineering 21, 4 (1995), 336–354.

Digital Library

[52]

Louis Mandel and Luc Maranget. 2014. The JoCaml language, Documentation and user’s manual, Chapter on Concurrent programming. http://jocaml.inria.fr/doc/concurrent.html .

[53]

Erik Meijer, Brian Beckman, and Gavin Bierman. 2006. LINQ: Reconciling Object, Relations and XML in the .NET Framework. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[54]

Leo A. Meyerovich, Arjun Guha, Jacob Baskin, Gregory H. Cooper, Michael Greenberg, Aleks Bromfield, and Shriram Krishnamurthi. 2009. Flapjax: A Programming Language for Ajax Applications. In Proceedings of Conference on ObjectOriented Programming, Systems, Languages, and Applications (OOPSLA).

Digital Library

[55]

Neil Mitchell. 2013. Leaking Space. ACM Queue 11, 9, Article 10 (Sept. 2013), 14 pages.

Digital Library

[56]

Eugenio Moggi. 1991. Notions of computation and monads. Information and computation 93, 1 (1991), 55–92.

Digital Library

[57]

Bruno C.d.S. Oliveira and William R. Cook. 2012. Extensibility for the Masses - Practical Extensibility with Object Algebras. In Proceedings of European Conference on Object-Oriented Programming (ECOOP).

Digital Library

[58]

Bruno C.d.S. Oliveira, Tijs van der Storm, Alex Loh, and William R. Cook. 2013. Feature-Oriented Programming with Object Algebras. In Proceedings of European Conference on Object-Oriented Programming (ECOOP).

Digital Library

[59]

Tomas Petricek, Alan Mycroft, and Don Syme. 2011. Extending monads with pattern matching. In Proceedings of Haskell Symposium.

Digital Library

[60]

Tomas Petricek, Dominic Orchard, and Alan Mycroft. 2014. Coeffects: A calculus of context-dependent computation. In Proceedings of International Conference on Functional Programming (ICFP).

Digital Library

[61]

Tomas Petricek and Don Syme. 2011. Joinads: A Retargetable Control-Flow Construct for Reactive, Parallel and Concurrent Programming. In Proceedings of the International Symposium on Practical Aspects of Declarative Languages (PADL).

Digital Library

[62]

Gordon D. Plotkin and John Power. 2003. Algebraic Operations and Generic Effects. Applied Categorical Structures (2003).

[63]

Gordon D. Plotkin and Matija Pretnar. 2009. Handlers of Algebraic Effects. In Proceedings of the European Conference on Programming Languages and Systems (ESOP).

Digital Library

[64]

ReactiveX. {n. d.}. ReactiveX. http://reactivex.io .

[65]

John H. Reppy. 1991. CML: A Higher-Order Concurrent Language. In Proceedings of Conference on Programming Language Design and Implementation (PLDI).

Digital Library

[66]

Rx.NET Example. 2013. Event Correlation. https://github.com/dotnet/reactive/blob/master/Rx.NET/Samples/ EventCorrelationSample/EventCorrelationSample/Program.cs#L55

[67]

Guido Salvaneschi, Gerold Hintz, and Mira Mezini. 2014. REScala: Bridging Between Object-oriented and Functional Style in Reactive Applications. In Proceedings of the International Conference on Modularity. ACM.

Digital Library

[68]

Robert Soulé, Martin Hirzel, Robert Grimm, Buğra Gedik, Henrique Andrade, Vibhore Kumar, and Kun-Lung Wu. 2010. A Universal Calculus for Stream Processing Languages. In Proceedings of the European Conference on Programming Languages and Systems (ESOP). Springer-Verlag.

Digital Library

[69]

Wouter Swierstra. 2008. Data types à la carte. Functional Programming (2008).

[70]

Don Syme, Tomas Petricek, and Dmitry Lomov. 2011. The F# Asynchronous Programming Model. In Proceedings of the International Symposium on Practical Aspects of Declarative Languages (PADL).

Digital Library

[71]

Philip Wadler. 1990a. Comprehending monads. In LISP and Functional Programming.

Digital Library

[72]

Philip Wadler. 1990b. Linear types can change the world. In Proceedings of the IFIP Working Group 2.2/2.3 Working Conference on Programming Concepts and Methods.

[73]

Philip Wadler. 1992. The Essence of Functional Programming. In Proceedings of Symposium on Principles of Programming Languages (POPL).

Digital Library

[74]

Walker White, Mirek Riedewald, Johannes Gehrke, and Alan Demers. 2007. What is "Next" in Event Processing?. In Proceedings of the Symposium on Principles of Database Systems (PODS).

Digital Library

[75]

Lukasz Ziarek, K. C. Sivaramakrishnan, and Suresh Jagannathan. 2011. Composable asynchronous events. In Proceedings of Conference on Programming Language Design and Implementation (PLDI).

Digital Library

Cited By

Rahman RTomar DKacharea GGawde MTsundue TKumar PKhalifa H(2024)Advanced Techniques for Digital Evidence Preservation: The Power of Blockchain and Machine LearningSustainable Security Practices Using Blockchain, Quantum and Post-Quantum Technologies for Real Time Applications10.1007/978-981-97-0088-2_6(99-124)Online publication date: 3-Apr-2024
https://doi.org/10.1007/978-981-97-0088-2_6
Kamina TUeno SDe Meuter WEugster PSalvaneschi GSant'Anna FZiarek LWeisenburger P(2022)Distributed Persistent Signals: Architecture and ImplementationProceedings of the 9th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems10.1145/3563837.3568341(13-23)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563837.3568341
Xie NCong YIkemori KLeijen D(2022)First-class names for effect handlersProceedings of the ACM on Programming Languages10.1145/35632896:OOPSLA2(30-59)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563289
Show More Cited By

Index Terms

Versatile event correlation with algebraic effects
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
      1. Semantics
    2. General programming languages
      1. Language features
        Control structures
        Coroutines
        Patterns

Recommendations

Structured asynchrony with algebraic effects
TyDe 2017: Proceedings of the 2nd ACM SIGPLAN International Workshop on Type-Driven Development

Algebraic effect handlers generalize many control-flow abstractions that are implemented specially in most languages, like exception handling, iterators, or backtracking. In this article, we show how we can implement full support for asynchronous ...
Temporal order optimizations of incremental joins for composite event detection
DEBS '07: Proceedings of the 2007 inaugural international conference on Distributed event-based systems

Queries for composite events typically involve the four complementary dimensions of event data, event composition, relationships between events (esp. temporal and causal), and accumulating events over time windows for negation and aggregation. We ...
Type directed compilation of row-typed algebraic effects
POPL '17

Algebraic effect handlers, introduced by Plotkin and Power in 2002,

are recently gaining in popularity as a purely functional approach to

modeling effects. In this article, we give a full overview of

practical algebraic effects in the context of ...

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 2, Issue ICFP

September 2018

1133 pages

EISSN:2475-1421

DOI:10.1145/3243631

Issue’s Table of Contents

Copyright © 2018 Owner/Author.

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 July 2018

Published in PACMPL Volume 2, Issue ICFP

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
1,270
Total Downloads

Downloads (Last 12 months)115
Downloads (Last 6 weeks)12

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rahman RTomar DKacharea GGawde MTsundue TKumar PKhalifa H(2024)Advanced Techniques for Digital Evidence Preservation: The Power of Blockchain and Machine LearningSustainable Security Practices Using Blockchain, Quantum and Post-Quantum Technologies for Real Time Applications10.1007/978-981-97-0088-2_6(99-124)Online publication date: 3-Apr-2024
https://doi.org/10.1007/978-981-97-0088-2_6
Kamina TUeno SDe Meuter WEugster PSalvaneschi GSant'Anna FZiarek LWeisenburger P(2022)Distributed Persistent Signals: Architecture and ImplementationProceedings of the 9th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems10.1145/3563837.3568341(13-23)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563837.3568341
Xie NCong YIkemori KLeijen D(2022)First-class names for effect handlersProceedings of the ACM on Programming Languages10.1145/35632896:OOPSLA2(30-59)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563289
Schuster PBrachthäuser JMüller MOstermann KJhala RDillig I(2022)A typed continuation-passing translation for lexical effect handlersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523710(566-579)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523710
Melicher DXu AZhao VPotanin AAldrich J(2022)Bounded Abstract EffectsACM Transactions on Programming Languages and Systems10.1145/349242744:1(1-48)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3492427
PERNA STANNEN VWONG L(2022)Iterating on multiple collections in synchronyJournal of Functional Programming10.1017/S095679682200004132Online publication date: 5-Jul-2022
https://doi.org/10.1017/S0956796822000041
Vielberth M(2021)Security Information and Event Management (SIEM)Encyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_1681-1(1-3)Online publication date: 2-Mar-2021
https://doi.org/10.1007/978-3-642-27739-9_1681-1
Wei GBračevac OTan SRompf T(2020)Compiling symbolic execution with staging and algebraic effectsProceedings of the ACM on Programming Languages10.1145/34282324:OOPSLA(1-33)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428232
Zhang YMyers A(2019)Abstraction-safe effect handlers via tunnelingProceedings of the ACM on Programming Languages10.1145/32903183:POPL(1-29)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290318

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