{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T22:32:04Z","timestamp":1784845924698,"version":"3.55.0"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>\n            We propose a rich foundational theory of typed data streams and stream transformers, motivated by two high-level goals. First, the type of a stream should be able to express complex\n            <jats:italic toggle=\"yes\">sequential patterns<\/jats:italic>\n            of events over time. And second, it should describe the internal\n            <jats:italic toggle=\"yes\">parallel structure<\/jats:italic>\n            of the stream, to support deterministic stream processing on parallel and distributed systems. To these ends, we introduce\n            <jats:italic toggle=\"yes\">stream types<\/jats:italic>\n            , with operators capturing sequential composition, parallel composition, and iteration, plus a core calculus\n            <jats:italic toggle=\"yes\">\n              \u03bb\n              <jats:sup>ST<\/jats:sup>\n            <\/jats:italic>\n            of\n            <jats:italic toggle=\"yes\">transformers<\/jats:italic>\n            over typed streams that naturally supports a number of common streaming idioms, including punctuation, windowing, and parallel partitioning, as first-class constructions.\n            <jats:italic toggle=\"yes\">\n              \u03bb\n              <jats:sup>ST<\/jats:sup>\n            <\/jats:italic>\n            exploits a Curry-Howardlike correspondence with an ordered variant of the Logic of Bunched Implication to program with streams compositionally and uses Brzozowski-style derivatives to enable an incremental, prefix-based operational semantics. To illustrate the programming style supported by the rich types of\n            <jats:italic toggle=\"yes\">\n              \u03bb\n              <jats:sup>ST<\/jats:sup>\n            <\/jats:italic>\n            , we present a number of examples written in Delta, a prototype high-level language design based on\n            <jats:italic toggle=\"yes\">\n              \u03bb\n              <jats:sup>ST<\/jats:sup>\n            <\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3656434","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"1412-1436","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Stream Types"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9399-9308","authenticated-orcid":false,"given":"Joseph W.","family":"Cutler","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3716-516X","authenticated-orcid":false,"given":"Christopher","family":"Watson","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4124-8598","authenticated-orcid":false,"given":"Emeka","family":"Nkurumeh","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0599-9224","authenticated-orcid":false,"given":"Phillip","family":"Hilliard","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9631-1169","authenticated-orcid":false,"given":"Harrison","family":"Goldstein","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8428-7736","authenticated-orcid":false,"given":"Caleb","family":"Stanford","sequence":"additional","affiliation":[{"name":"University of California at Davis, Davis, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7839-1636","authenticated-orcid":false,"given":"Benjamin C.","family":"Pierce","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_1","volume-title":"Second Biennial Conference on Innovative Data Systems Research (CIDR)","author":"Abadi Daniel J","year":"2005","unstructured":"Abadi Daniel J, Ahmad Yanif, Balazinska Magdalena, \u00c7etintemel U\u011fur, Cherniack Mitch, Hwang Jeong-Hyon, Lindner Wolfgang, Maskey Anurag, Rasin Alex, Ryvkina Esther, Tatbul Nesime, Xing Ying, Zdonik Stanley. 2005. The Design of the Borealis Stream Processing Engine. Second Biennial Conference on Innovative Data Systems Research (CIDR)"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_3_1_4_1","doi-asserted-by":"crossref","unstructured":"Alur Rajeev Hilliard Phillip G Ives Zachary Kallas Konstantinos Mamouras Konstantinos Niksic Filip Stanford Caleb V Talonen Anton. 2021. Synchronization Schemas. Invited contribution Principles of Database Systems","DOI":"10.1145\/3452021.3458317"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578855.2535862"},{"key":"e_1_3_1_6_1","unstructured":"Arasu Arvind Babcock Brian Babu Shivnath Cieslewicz John Dar Mayur Etc Keith Ito Motwani Rajeev Srivastava Utkarsh Widom Jennifer. 2004. STREAM: The Stanford Data Stream Management System. Technical Report 2004-20. Stanford InfoLab"},{"key":"e_1_3_1_7_1","volume-title":"International Workshop on Database Programming Languages","author":"Arasu Arvind","year":"2003","unstructured":"Arasu Arvind, Babu Shivnath, Widom Jennifer. 2003. CQL: A language for continuous queries over streams and relations. International Workshop on Database Programming Languages. Springer"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341713"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434283"},{"key":"e_1_3_1_11_1","unstructured":"Bahr Patrick M\u00f8gelberg Rasmus Ejlers. 2023. Asynchronous Modal RFP. arXiv:2303.03710. https:\/\/arxiv.org\/abs\/2303.03710"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314040"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","unstructured":"Benneviste Albert Caspi Paul Edwards Stephen A Halbwachs Nicolas Guernic Paul Le Simone Robert De. 2003. The synchronous languages 12 years later. Proc. IEEE 91 1. https:\/\/doi.org\/10.1109\/JPROC.2002.805816 10.1109\/JPROC.2002.805816","DOI":"10.1109\/JPROC.2002.805816"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/944705.944711"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(92)90005-V"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11554554_8"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.191.0012"},{"issue":"4","key":"e_1_3_1_19_1","article-title":"Apache Flink: Stream and Batch Processing in a Single Engine","volume":"36","author":"Carbone Paris","year":"2015","unstructured":"Carbone Paris, Ewen Stephan, Markl Volker, Haridi Seif, Tzoumas Kostas. 2015. Apache Flink: Stream and Batch Processing in a Single Engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 36, 4","journal-title":"Bulletin of the IEEE Computer Society Technical Committee on Data Engineering"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535881"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64437-6_2"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872857"},{"key":"e_1_3_1_23_1","doi-asserted-by":"crossref","unstructured":"Cutler Joseph W. Watson Christopher Hilliard Phillip Goldstein Harrison Stanford Caleb Pierce Benjamin C.. 2023. Stream Types. arXiv:2307.09553 [cs.PL]","DOI":"10.1145\/3656434"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2005.26"},{"key":"e_1_3_1_25_1","unstructured":"Derakhshan Farzaneh. 2021. Session-Typed Recursive Processes and Circular Proofs. Ph.D. Dissertation. Carnegie Mellon University. https:\/\/www.andrew.cmu.edu\/user\/fderakhs\/publications\/Dissertation_Farzaneh.pdf"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563320"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1142\/2563"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/258948.258973"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25540-4_24"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2013.248"},{"key":"e_1_3_1_31_1","unstructured":"Apache Software Foundation. 2019. Apache Flink. https:\/\/flink.apache.org\/ (Accessed July 2022)."},{"key":"e_1_3_1_32_1","unstructured":"Apache Software Foundation. 2019. Apache Heron (originally Twitter Heron). https:\/\/heron.incubator.apache.org\/ (Accessed July 2022)."},{"key":"e_1_3_1_33_1","unstructured":"Apache Software Foundation. 2019. Apache Samza. https:\/\/samza.apache.org\/ (Accessed July 2022)."},{"key":"e_1_3_1_34_1","unstructured":"Apache Software Foundation. 2019. Apache Spark Streaming. https:\/\/spark.apache.org\/streaming\/ (Accessed July 2022)."},{"key":"e_1_3_1_35_1","unstructured":"Apache Software Foundation. 2019. Apache Storm. https:\/\/storm.apache.org\/ (Accessed July 2022)."},{"key":"e_1_3_1_36_1","unstructured":"Apache Software Foundation. 2021. Apache Beam. https:\/\/beam.apache.org\/ (Accessed July 2022)."},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029823"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563318"},{"key":"e_1_3_1_39_1","unstructured":"Gonzalez Gabriella. 2022. Pipes. https:\/\/hackage.haskell.org\/package\/pipes"},{"key":"e_1_3_1_40_1","unstructured":"Gonzalez Gabriella. 2024. FoldL. https:\/\/hackage.haskell.org\/package\/foldl"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90870-6_30"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-021-00605-3"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528412"},{"key":"e_1_3_1_44_1","doi-asserted-by":"crossref","unstructured":"Hoare C. A. R. (Tony) M\u00f6ller Bernhard Struth Georg & Wehrman Ian. Concurrent Kleene Algebra. 2009. In CONCUR 2009-Concurrency Theory: 20th International Conference CONCUR 2009 Bologna Italy September 1-4 2009. Proceedings. Springer 399\u2013414.","DOI":"10.1007\/978-3-642-04081-8_27"},{"key":"e_1_3_1_45_1","doi-asserted-by":"crossref","unstructured":"Honda Kohei Yoshida Nobuko & Carbone Marco. Multiparty asynchronous session types. 2008. In Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages 273\u2013284.","DOI":"10.1145\/1328438.1328472"},{"key":"e_1_3_1_46_1","doi-asserted-by":"crossref","unstructured":"Hosoya Haruo Vouillon J\u00e9r\u00f4me & Pierce Benjamin C.. Regular Expression Types for XML. 2005. ACM Transactions on Programming Languages and Systems (TOPLAS) 27 1 46\u201390. Preliminary version in ICFP 2000.","DOI":"10.1145\/1053468.1053470"},{"key":"e_1_3_1_47_1","doi-asserted-by":"crossref","unstructured":"Jain Namit Mishra Shailendra Srinivasan Anand Gehrke Johannes Widom Jennifer Balakrishnan Hari \u00c7etintemel U\u011fur Cherniack Mitch Tibbetts Richard & Zdonik Stan. Towards a streaming SQL standard. 2008. Proceedings of the VLDB Endowment 1 2.","DOI":"10.14778\/1454159.1454179"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","unstructured":"Jeffrey Alan. LTL Types FRP: Linear-Time Temporal Logic Propositions as Types Proofs as Functional Reactive Programs. 2012. In Proceedings of the Sixth Workshop on Programming Languages Meets Program Verification (Philadelphia Pennsylvania USA) (PLPV \u203212). Association for Computing Machinery New York NY USA 49\u201360. DOI:https:\/\/doi.org\/10.1145\/2103776.210378310.1145\/2103776.2103783.","DOI":"10.1145\/2103776.2103783"},{"key":"e_1_3_1_49_1","unstructured":"Johnson Theodore Muthukrishnan Shanmugavelayutham Shkapenyuk Vladislav & Spatscheck Oliver. A heartbeat mechanism and its application in Gigascope. 2005. In 31st International Conference on Very Large Data Bases (VLDB). VLDB Endowment."},{"key":"e_1_3_1_50_1","unstructured":"Kahn Gilles. The semantics of a simple language for parallel programming. 1974. Information Processing 74."},{"key":"e_1_3_1_51_1","doi-asserted-by":"crossref","unstructured":"Kallas Konstantinos Niksic Filip Stanford Caleb & Alur Rajeev. DiffStream: differential output testing for stream processing programs. 2020. Proceedings of the ACM on Programming Languages 4 OOPSLA.","DOI":"10.1145\/3428221"},{"key":"e_1_3_1_52_1","doi-asserted-by":"crossref","unstructured":"Kallas Konstantinos Niksic Filip Stanford Caleb & Alur Rajeev. Stream Processing With Dependency-Guided Synchronization. 2022. In Principles and Practice of Parallel Programming (PPoPP).","DOI":"10.1145\/3503221.3508413"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","unstructured":"Kapp\u00e9 Tobias Brunet Paul Luttik Bas Silva Alexandra & Zanasi Fabio. On series-parallel pomset languages: Rationality context-freeness and automata. 2019. Journal of Logical and Algebraic Methods in Programming 103 130\u2013153. DOI: https:\/\/doi.org\/10.1016\/j.jlamp.2018.12.00110.1016\/j.jlamp.2018.12.001.","DOI":"10.1016\/j.jlamp.2018.12.001"},{"key":"e_1_3_1_54_1","doi-asserted-by":"crossref","unstructured":"Kiselyov Oleg. Iteratees. 2012. In Functional and Logic Programming Tom Schrijvers and Peter Thiemann (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 166\u2013181.","DOI":"10.1007\/978-3-642-29822-6_15"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500588"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3315507.3330199"},{"key":"e_1_3_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564698"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_15"},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314580"},{"key":"e_1_3_1_61_1","article-title":"Trace theory","author":"Mazurkiewicz Antoni","year":"1986","unstructured":"Mazurkiewicz Antoni. 1986. Trace theory. In Advanced course on Petri nets. Springer","journal-title":"In Advanced course on Petri nets"},{"key":"e_1_3_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90014-4"},{"key":"e_1_3_1_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137770"},{"key":"e_1_3_1_64_1","doi-asserted-by":"publisher","DOI":"10.2307\/421090"},{"key":"e_1_3_1_65_1","unstructured":"Paykin JenniferKrishnaswami Neelakantan RZdancewic Steve. 2016. The Essence of Event-Driven Programming."},{"key":"e_1_3_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_3_1_67_1","first-page":"55","article-title":"Separation logic: A logic for shared mutable data structures","author":"Reynolds John C","year":"2002","unstructured":"Reynolds John C. 2002. Separation logic: A logic for shared mutable data structures. In Proceedings 17th Annual IEEE Symposium on Logic in Computer Science. IEEE, 55\u201374","journal-title":"In Proceedings 17th Annual IEEE Symposium on Logic in Computer Science"},{"key":"e_1_3_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.221"},{"key":"e_1_3_1_69_1","unstructured":"Snoyman Michael. 2023. Conduit. https:\/\/hackage.haskell.org\/package\/conduit"},{"key":"e_1_3_1_70_1","article-title":"A universal calculus for stream processing languages","author":"Soul\u00e9 Robert","year":"2010","unstructured":"Soul\u00e9 RobertHirzel MartinGrimm RobertGedik Bu\u011fraAndrade HenriqueKumar VibhoreWu Kun-Lung. 2010. A universal calculus for stream processing languages. In European Symposium on Programming (ESOP). Springer","journal-title":"In European Symposium on Programming (ESOP)"},{"key":"e_1_3_1_71_1","article-title":"Safe Programming over Distributed Streams","author":"Stanford Caleb","year":"2022","unstructured":"Stanford Caleb. 2022. Safe Programming over Distributed Streams. Ph. D. Dissertation. University of Pennsylvania","journal-title":"Ph. D. Dissertation"},{"key":"e_1_3_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050095"},{"key":"e_1_3_1_73_1","unstructured":"Composewell Technologies. 2023. Streamly. https:\/\/hackage.haskell.org\/package\/streamly-core"},{"key":"e_1_3_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45937-5_14"},{"key":"e_1_3_1_75_1","unstructured":"Trilla Jose Manuel Calderon. 2024. personal communication"},{"key":"e_1_3_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_3_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_3_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99336-8_21"},{"key":"e_1_3_1_79_1","article-title":"Discretized Streams:Fault-tolerant Streaming Computation at Scale","author":"Zaharia Matei","year":"2013","unstructured":"Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, and Ion Stoica. 2013. Discretized Streams:Fault-tolerant Streaming Computation at Scale. In 24th Symposium on Operating Systems Principles (SOSP). ACM.https:\/\/doi.org\/10.1145\/2517349.2522737","journal-title":"24th Symposium on Operating Systems Principles (SOSP)"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656434","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656434","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:39:07Z","timestamp":1751661547000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656434"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":78,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656434"],"URL":"https:\/\/doi.org\/10.1145\/3656434","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}