{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T04:12:37Z","timestamp":1751688757531,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2107289, CCF-2007784, CNS-2314323"],"award-info":[{"award-number":["CCF-2107289, CCF-2007784, CNS-2314323"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            Parallel programs are frequently modeled as\n            <jats:italic toggle=\"yes\">dependency<\/jats:italic>\n            or\n            <jats:italic toggle=\"yes\">cost<\/jats:italic>\n            graphs, which can be used to detect various bugs, or simply to visualize the parallel structure of the code. However, such graphs reflect just one particular execution and are typically constructed in a\n            <jats:italic toggle=\"yes\">post-hoc<\/jats:italic>\n            manner.\n            <jats:italic toggle=\"yes\">Graph types<\/jats:italic>\n            , which were introduced recently to mitigate this problem, can be assigned statically to a program by a type system and compactly represent the family of all graphs that could result from the program.\n          <\/jats:p>\n          <jats:p>\n            Unfortunately, prior work is restricted in its treatment of\n            <jats:italic toggle=\"yes\">futures<\/jats:italic>\n            , an increasingly common and especially dynamic form of parallelism. In short, each instance of a future must be statically paired with a vertex name. Previously, this led to the restriction that futures could not be placed in collections or be used to construct data structures. Doing so is not a niche exercise: such structures form the basis of numerous algorithms that use forms of pipelining to achieve performance not attainable without futures. All but the most limited of these examples are out of reach of prior graph type systems.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we propose a graph type system that allows for almost arbitrary combinations of futures and recursive data types. We do so by indexing datatypes with a type-level\n            <jats:italic toggle=\"yes\">vertex structure<\/jats:italic>\n            , a codata structure that supplies unique vertex names to the futures in a data structure. We prove the soundness of the system in a parallel core calculus annotated with vertex structures and associated operations. Although the calculus is annotated, this is merely for convenience in defining the type system. We prove that it is possible to annotate arbitrary recursive types with vertex structures, and show using a prototype inference engine that these annotations can be inferred from OCaml-like source code for several complex parallel algorithms.\n          <\/jats:p>","DOI":"10.1145\/3632859","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"482-511","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Pipelines and Beyond: Graph Types for ADTs with Futures"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-0007-0898","authenticated-orcid":false,"given":"Francis","family":"Rinaldi","sequence":"first","affiliation":[{"name":"Illinois Institute of Technology, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3280-9731","authenticated-orcid":false,"given":"june","family":"wunder","sequence":"additional","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9916-6614","authenticated-orcid":false,"given":"Arthur","family":"Azevedo de Amorim","sequence":"additional","affiliation":[{"name":"Rochester Institute of Technology, Rochester, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3210-9727","authenticated-orcid":false,"given":"Stefan K.","family":"Muller","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"[n.d.]. The Rust language. https:\/\/www.rust-lang.org. Accessed: 2023-07-07."},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01088832"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147403.1147416"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498698"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/224164.224210"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232650"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258517"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48046-3_17"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","unstructured":"Jingde Cheng. 1993. Process dependence net of distributed programs and its applications in development of distributed systems. In Proceedings of 1993 IEEE 17th International Computer Software and Applications Conference COMPSAC \u201993. 231\u2013240. https:\/\/doi.org\/10.1109\/CMPSAC.1993.404187 10.1109\/CMPSAC.1993.404187","DOI":"10.1109\/CMPSAC.1993.404187"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3229060"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11693024_2"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N"},{"key":"e_1_3_1_14_1","first-page":"87","volume-title":"Advanced Topics in Types and Programming Languages","author":"Henglein Fritz","year":"2005","unstructured":"Fritz Henglein, Henning Makholm, and Henning Niss. 2005. Effect Types and Region-Based Memory Management. In Advanced Topics in Types and Programming Languages, Benjamin C. Pierce (Ed.). MIT Press, Cambridge, Massachusetts, Chapter 3, 87\u2013135."},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808098.2808100"},{"key":"e_1_3_1_16_1","first-page":"275","volume-title":"Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference (ATEC \u201902)","author":"Jim Trevor","year":"2002","unstructured":"Trevor Jim, J. Greg Morrisett, Dan Grossman, Michael W. Hicks, James Cheney, and Yanling Wang. 2002. Cyclone: A Safe Dialect of C. In Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference (ATEC \u201902). USENIX Association, USA, 275\u2013288."},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114108"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","unstructured":"Y. Kasahara Y. Nomura M. Kamachi J. Cheng and K. Ushijima. 1995. An integrated support environment for distributed software development based on unified program representations. In Proceedings 1995 Asia Pacific Software Engineering Conference. 254\u2013263. https:\/\/doi.org\/10.1109\/APSEC.1995.496974 10.1109\/APSEC.1995.496974","DOI":"10.1109\/APSEC.1995.496974"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","unstructured":"Oleg Kiselyov Ralf L\u00e4mmel and Keean Schupke. 2004. Strongly typed heterogeneous collections. Proceedings of the ACM SIGPLAN 2004 Haskell Workshop Haskell\u201904 (2004) 96\u2013107. https:\/\/doi.org\/10.1145\/1017472.1017488 10.1145\/1017472.1017488","DOI":"10.1145\/1017472.1017488"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90102-5"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50029-0_8"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523443"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498708"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679682100023X"},{"key":"e_1_3_1_25_1","unstructured":"Francis Rinaldi june wunder Arthur Aevedo De Amorim and Stefan K. Muller. 2023. Pipelines and Beyond: Graph Types for ADTs with Futures. arXiv: 2311.06984 [cs.PL]"},{"key":"e_1_3_1_26_1","volume-title":"A Graph Model for Parallel Computations","author":"Bezos Jorge E Rodriguez","year":"1969","unstructured":"Jorge E Rodriguez Bezos. 1969. A Graph Model for Parallel Computations. Ph. D. Dissertation. Massachusetts Institute of Technology, Cambridge, Massachusetts."},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408995"},{"key":"e_1_3_1_28_1","volume-title":"Scheduling Deterministic Parallel Programs","author":"Spoonhower Daniel","year":"2009","unstructured":"Daniel Spoonhower. 2009. Scheduling Deterministic Parallel Programs. Ph. D. Dissertation. Carnegie Mellon University, Pittsburgh, PA, USA."},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951929"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2613"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1984.5010248"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292560"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103786.2103795"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00062-5"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632859","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632859","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:03:45Z","timestamp":1751659425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":33,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632859"],"URL":"https:\/\/doi.org\/10.1145\/3632859","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}