Pipelines and Beyond: Graph Types for ADTs with Futures (2024)

Skip Abstract Section

1. [n. d.]. The Rust language. https://www.rust-lang.org Accessed: 2023-07-07Google Scholar
2. Özalp Babaoğlu, Keith Marzullo, and Fred B. Schneider. 1993. A Formalization of Priority Inversion. Real-Time Systems, 5, 4 (1993), 285–303. https://doi.org/10.1007/BF01088832Google ScholarDigital Library
3. Utpal Banerjee, Brian Bliss, Zhiqiang Ma, and Paul Petersen. 2006. A Theory of Data Race Detection. In Proceedings of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging (PADTAD ’06). Association for Computing Machinery, New York, NY, USA. 69–78. isbn:1595934146 https://doi.org/10.1145/1147403.1147416Google ScholarDigital Library
4. Olivier Blanvillain, Jonathan Immanuel Brachthäuser, Maxime Kjaer, and Martin Odersky. 2022. Type-level programming with match types. Proceedings of the ACM on Programming Languages, 6 (2022), 1, issn:24751421 https://doi.org/10.1145/3498698Google ScholarDigital Library
5. Guy Blelloch and John Greiner. 1995. Parallelism in Sequential Functional Languages. In Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture (FPCA ’95). Association for Computing Machinery, New York, NY, USA. 226–237. isbn:0897917197 https://doi.org/10.1145/224164.224210Google ScholarDigital Library
6. Guy E. Blelloch and John Greiner. 1996. A Provable Time and Space Efficient Implementation of NESL. In Proceedings of the First ACM SIGPLAN International Conference on Functional Programming (ICFP ’96). Association for Computing Machinery, New York, NY, USA. 213–225. isbn:0897917707 https://doi.org/10.1145/232627.232650Google ScholarDigital Library
7. Guy E. Blelloch and Margaret Reid-Miller. 1997. Pipelining with Futures. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’97). Association for Computing Machinery, New York, NY, USA. 249–259. isbn:0897918908 https://doi.org/10.1145/258492.258517Google ScholarDigital Library
8. Zhenqiang Chen, Baowen Xu, Jianjun Zhao, and Hongji Yang. 2002. Static Dependency Analysis for Concurrent Ada 95 Programs. In Reliable Software Technologies — Ada-Europe 2002, Johann Blieberger and Alfred Strohmeier (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 219–230. isbn:978-3-540-48046-4 https://doi.org/10.1007/3-540-48046-3_17Google ScholarCross Ref
9. 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 ’93. 231–240. https://doi.org/10.1109/CMPSAC.1993.404187Google ScholarCross Ref
10. Tiago Cogumbreiro, Raymond Hu, Francisco Martins, and Nobuko Yoshida. 2018. Dynamic Deadlock Verification for General Barrier Synchronisation. ACM Trans. Program. Lang. Syst., 41, 1 (2018), Article 1, Dec., 38 pages. issn:0164-0925 https://doi.org/10.1145/3229060Google ScholarDigital Library
11. Matthew Fluet, Greg Morrisett, and Amal Ahmed. 2006. Linear Regions Are All You Need. In Proceedings of the 15th European Conference on Programming Languages and Systems (ESOP’06). Springer-Verlag, Berlin, Heidelberg. 7–21. isbn:354033095X https://doi.org/10.1007/11693024_2Google ScholarDigital Library
12. Emden R. Gansner and Stephen C. North. 2000. An Open Graph Visualization System and Its Applications to Software Engineering. Softw. Pract. Exper., 30, 11 (2000), Sept., 1203–1233. issn:0038-0644 https://doi.org/10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-NGoogle ScholarCross Ref
13. 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. 87–135.Google Scholar
14. Thomas Bracht Laumann Jespersen, Philip Munksgaard, and Ken Friis Larsen. 2015. Session Types for Rust. In Proceedings of the 11th ACM SIGPLAN Workshop on Generic Programming (WGP 2015). Association for Computing Machinery, New York, NY, USA. 13–22. isbn:9781450338103 https://doi.org/10.1145/2808098.2808100Google ScholarDigital Library
15. 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 ’02). USENIX Association, USA. 275–288. isbn:1880446006Google ScholarDigital Library
16. Richard M. Karp and Rayamond E. Miller. 1966. Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing. SIAM J. Appl. Math., 14, 6 (1966), 1390–1411. https://doi.org/10.1137/0114108Google ScholarDigital Library
17. 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–263. https://doi.org/10.1109/APSEC.1995.496974Google ScholarCross Ref
18. Oleg Kiselyov, Ralf Lämmel, and Keean Schupke. 2004. Strongly typed heterogeneous collections. Proceedings of the ACM SIGPLAN 2004 Haskell Workshop, Haskell’04, 96–107. isbn:1581138504 https://doi.org/10.1145/1017472.1017488Google ScholarDigital Library
19. Bogdan Korel. 1987. The program dependence graph in static program testing. Inform. Process. Lett., 24, 2 (1987), 103–108. issn:0020-0190 https://doi.org/10.1016/0020-0190(87)90102-5Google ScholarDigital Library
20. Nicolas Lagaillardie, Rumyana Neykova, and Nobuko Yoshida. 2020. Implementing Multiparty Session Types in Rust. In Coordination Models and Languages: 22nd IFIP WG 6.1 International Conference, COORDINATION 2020, Held as Part of the 15th International Federated Conference on Distributed Computing Techniques, DisCoTec 2020, Valletta, Malta, June 15–19, 2020, Proceedings. Springer-Verlag, Berlin, Heidelberg. 127–136. isbn:978-3-030-50028-3 https://doi.org/10.1007/978-3-030-50029-0_8Google ScholarDigital Library
21. Mae Milano, Joshua Turcotti, and Andrew C. Myers. 2022. A Flexible Type System for Fearless Concurrency. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA. 458–473. isbn:9781450392655 https://doi.org/10.1145/3519939.3523443Google ScholarDigital Library
22. Stefan K. Muller. 2022. Static Prediction of Parallel Computation Graphs. Proc. ACM Program. Lang., 6, POPL (2022), Article 46, Jan., 31 pages. https://doi.org/10.1145/3498708Google ScholarDigital Library
23. Liam O’Connor, Zilin Chen, Christine Rizkallah, Vincent Jackson, Sidney Amani, Gerwin Klein, Toby Murray, Thomas Sewell, and Gabriele Keller. 2021. Cogent: uniqueness types and certifying compilation. J. Funct. Program., 31 (2021), e25. https://doi.org/10.1017/S095679682100023XGoogle ScholarCross Ref
24. 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.Google Scholar
25. Jorge E Rodriguez Bezos. 1969. A Graph Model for Parallel Computations. Ph. D. Dissertation. Massachusetts Institute of Technology. Cambridge, Massachusetts.Google Scholar
26. K. C. Sivaramakrishnan, Stephen Dolan, Leo White, Sadiq Jaffer, Tom Kelly, Anmol Sahoo, Sudha Parimala, Atul Dhiman, and Anil Madhavapeddy. 2020. Retrofitting parallelism onto OCaml. Proc. ACM Program. Lang., 4, ICFP (2020), 113:1–113:30. https://doi.org/10.1145/3408995Google ScholarDigital Library
27. Daniel Spoonhower. 2009. Scheduling Deterministic Parallel Programs. Ph. D. Dissertation. Carnegie Mellon University. Pittsburgh, PA, USA.Google Scholar
28. David Thibodeau, Andrew Cave, and Brigitte Pientka. 2016. Indexed Codata Types. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). Association for Computing Machinery, New York, NY, USA. 351–363. isbn:9781450342193 https://doi.org/10.1145/2951913.2951929Google ScholarDigital Library
29. Mads Tofte and Jean-Pierre Talpin. 1997. Region-Based Memory Management. Information and Computation, 132, 2 (1997), 109–176. issn:0890-5401 https://doi.org/10.1006/inco.1996.2613Google ScholarDigital Library
30. Mark Weiser. 1984. Program Slicing. IEEE Transactions on Software Engineering, SE-10, 4 (1984), 352–357. https://doi.org/10.1109/TSE.1984.5010248Google ScholarDigital Library
31. Hongwei Xi and Frank Pfenning. 1999. Dependent Types in Practical Programming. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’99). Association for Computing Machinery, New York, NY, USA. 214–227. isbn:1581130953 https://doi.org/10.1145/292540.292560Google ScholarDigital Library
32. Brent A. Yorgey, Stephanie Weirich, Julien Cretin, Simon Peyton Jones, Dimitrios Vytiniotis, and José Pedro Magalhães. 2012. Giving Haskell a Promotion. In Proceedings of the 8th ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI ’12). Association for Computing Machinery, New York, NY, USA. 53–66. isbn:9781450311205 https://doi.org/10.1145/2103786.2103795Google ScholarDigital Library
33. Christoph Zenger. 1997. Indexed types. Theoretical Computer Science, 187, 1 (1997), 147–165. issn:0304-3975 https://doi.org/10.1016/S0304-3975(97)00062-5Google ScholarDigital Library

Index Terms

1. Pipelines and Beyond: Graph Types for ADTs with Futures

   1. Software and its engineering

      1. Software notations and tools

         1. General programming languages

            1. Language types

               1. Parallel programming languages

      2. Software organization and properties

         1. Software functional properties

            1. Formal methods

               1. Automated static analysis

   2. Theory of computation

      1. Logic

         1. Linear logic

• Static prediction of parallel computation graphs

  Many algorithms for analyzing parallel programs, for example to detect deadlocks or data races or to calculate the execution cost, are based on a model variously known as a cost graph, computation graph or dependency graph, which captures the parallel ...

  Read More

• Language-Agnostic Static Deadlock Detection for Futures

  PPoPP '24: Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming

  Deadlocks, in which threads wait on each other in a cyclic fashion and can't make progress, have plagued parallel programs for decades. In recent years, as the parallel programming mechanism known as futures has gained popularity, interest in preventing ...

  Read More

• Qualified types for MLF

  Proceedings of the tenth ACM SIGPLAN international conference on Functional programming

  MLF is a type system that extends a functional language with impredicative rank-n polymorphism. Type inference remains possible and only in some clearly defined situations, a local type annotation is required. Qualified types are a general concept that ...

  Read More