{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:54:50Z","timestamp":1750308890984,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T00:00:00Z","timestamp":1088640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>\n            Parallel functional languages often use meta-linguistic annotations to provide control over parallel evaluation. In this paper we explore a flexible mechanism to control when an expression is evaluated:\n            <jats:italic>first-class monadic schedules<\/jats:italic>\n            . We discuss the advantages of using such first-class values over traditional annotation-based systems. In particular, it is often desirable to make decisions about the operational behavior of parallel programs depending on the dynamic state of the system. For example, we may want to measure the system load before deciding to evaluate expressions in parallel. For this purpose, we show how\n            <jats:italic>monads<\/jats:italic>\n            can be used to access dynamic system parameters in a referentially transparent manner (up to termination).As a mechanism to reason about schedules, we present a set of\n            <jats:italic>algebraic properties<\/jats:italic>\n            that any implementation of schedules must satisfy. We also describe an implementation that translates schedules into a dialect of Scheme extended with\n            <jats:italic>futures<\/jats:italic>\n            . We prove that this implementation satisfies the given set of algebraic properties, and give performance results for a parallel solution to the\n            <jats:italic>n<\/jats:italic>\n            -body problem using the Barnes--Hut method.Although our ideas were developed specifically for nonstrict functional languages such as Haskell, we briefly discuss how they can be used with strict functional languages and imperative languages as well.\n          <\/jats:p>","DOI":"10.1145\/1011508.1011509","type":"journal-article","created":{"date-parts":[[2004,10,7]],"date-time":"2004-10-07T17:38:56Z","timestamp":1097170736000},"page":"609-651","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["First-class monadic schedules"],"prefix":"10.1145","volume":"26","author":[{"given":"Rajiv","family":"Mirani","sequence":"first","affiliation":[{"name":"Hewlett-Packard Company, Cupertino, CA"}]},{"given":"Paul","family":"Hudak","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, CT"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"volume-title":"Proceedings of the 3rd International Workshop on Parallel Implementation of Fuctional Languages. Tech. Rep. CSTR 91-07","year":"1991","author":"Achten P.","key":"e_1_2_1_1_1"},{"volume-title":"I-structures: Data structures for parallel computing","year":"1986","author":"Arvind","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Barnes J. and Hut P. 1986. A hierarchical O(n log n) force-calculation algorithm. Nature December.  Barnes J. and Hut P. 1986. A hierarchical O(n log n) force-calculation algorithm. Nature December.","DOI":"10.1038\/324446a0"},{"key":"e_1_2_1_4_1","first-page":"147","article-title":"Code optimization for lazy evaluation","volume":"1","author":"Bloss A.","year":"1988","journal-title":"LISP Symb. Comput."},{"volume-title":"Lecture Notes. International Summer School on Theoretical Foundations of Programming Methodology","year":"1981","author":"Broy M.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993.357241"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/31.3.243"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/107214.129259"},{"volume-title":"Proceedings of the 1982 ACM Symposium 94 LISP and Functional Programming. ACM","year":"1982","author":"Clinger W.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","unstructured":"Clinger W. et al. 1985. The Revised Report on Scheme or an UnCommon Lisp. AI Memo 848. Massachusetts Institute of Technology Cambridge Mass. (Aug.).  Clinger W. et al. 1985. The Revised Report on Scheme or an UnCommon Lisp. AI Memo 848. Massachusetts Institute of Technology Cambridge Mass. (Aug.)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800223.806764"},{"key":"e_1_2_1_13_1","unstructured":"Gordon D. A. 1993. Functional programming and input\/output. Ph.D. dissertation. Computer Laboratory University of Cambridge (Feb).  Gordon D. A. 1993. Functional programming and input\/output. Ph.D. dissertation. Computer Laboratory University of Cambridge (Feb)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_2_1_15_1","first-page":"177","volume-title":"Mass.","author":"Henderson P.","year":"1982"},{"volume":"201","volume-title":"Proceedings, Functional Programming Languages and Computer Architecture","author":"Hudak P.","key":"e_1_2_1_16_1"},{"first-page":"243","volume-title":"Proceedings of the 12th ACM Symposium on Principles of Programming Languages, (Jan.). ACM","author":"Hudak P.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","first-page":"312","volume-title":"Proceedings of the Santa Fe Graph Reduction Workshop, (Los Alamos\/MCC)","author":"Hudak P."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01414441"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1986.1663309"},{"volume-title":"Series in Supercomputing and Parallel Processing. McGraw-Hill","year":"1990","author":"Hudak P.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 1992 Conference on Programming Language Design and Implementation, (June). 10","author":"Jagannathan S.","key":"e_1_2_1_22_1"},{"volume-title":"Research Monographs in Parallel and Distributed Computing. Pitman.","author":"Kelly P.","key":"e_1_2_1_23_1"},{"first-page":"329","volume-title":"Workshops in Computing (Aug.). Springer-Verlag, New York","author":"Kewley J. M.","key":"e_1_2_1_24_1"},{"first-page":"78","volume-title":"ACM","author":"Mirani R.","key":"e_1_2_1_25_1"},{"volume-title":"Department of Computer Science","year":"1996","author":"Mirani R.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_28_1","unstructured":"Nikhil R. S. Arvind Hicks J. Aditya S. Augustsson L. Maessen J.-W. and Zhou Y. 1995. pH language reference manual version 1.0---preliminary. CSG Memo 369 Laboratory for Computer Science MIT Cambridge Mass.  Nikhil R. S. Arvind Hicks J. Aditya S. Augustsson L. Maessen J.-W. and Zhou Y. 1995. pH language reference manual version 1.0---preliminary. CSG Memo 369 Laboratory for Computer Science MIT Cambridge Mass."},{"key":"e_1_2_1_29_1","unstructured":"Nikhil R. S. 1991. Id (version 90.1) language reference manual. CSG Memo 284-2 Laboratory for Computer Science MIT Cambridge Mass.  Nikhil R. S. 1991. Id (version 90.1) language reference manual. CSG Memo 284-2 Laboratory for Computer Science MIT Cambridge Mass."},{"key":"e_1_2_1_30_1","unstructured":"Papadopoulos G. M. 1988. Implementation of a General Purpose Dataflow Multiprocessor. Ph.D. dissertation Laboratory for Computer Science MIT Cambridge Mass.  Papadopoulos G. M. 1988. Implementation of a General Purpose Dataflow Multiprocessor. Ph.D. dissertation Laboratory for Computer Science MIT Cambridge Mass."},{"key":"e_1_2_1_31_1","unstructured":"Peyton Jones S. L. Ed. 2003. Haskell 98 Language and Libraries---The Revised Report. Cambridge University Press Cambridge England.  Peyton Jones S. L. Ed. 2003. Haskell 98 Language and Libraries---The Revised Report. Cambridge University Press Cambridge England."},{"first-page":"71","volume-title":"Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, (Charleston, S. Ca., Jan. 10--13)","author":"Peyton Jones S. L.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","first-page":"98","volume-title":"Lecture Notes in Computer Science","volume":"274","author":"Peyton Jones S. L."},{"key":"e_1_2_1_34_1","unstructured":"Philbin J. F. 1993. The design of an operating system for modern programming languages. Ph.D. dissertation. YALEU\/DCS\/RR-997 Yale University.   Philbin J. F. 1993. The design of an operating system for modern programming languages. Ph.D. dissertation. YALEU\/DCS\/RR-997 Yale University."},{"key":"e_1_2_1_35_1","first-page":"296","volume-title":"Workshops in Computing. Springer-Verlag","author":"Robertson I. B.","year":"1989"},{"volume-title":"Tech. Rep. 88\/18, Department of Computer Science","year":"1988","author":"Sondergaard H.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Treleaven P. C. Brownbridge D. R. and Hopkins R. P. 1982. Data-driven and demand-driven computer architectures. ACM Comput. Surv. 14 1 (Mar.) 93--143. 10.1145\/356869.356873   Treleaven P. C. Brownbridge D. R. and Hopkins R. P. 1982. Data-driven and demand-driven computer architectures. ACM Comput. Surv. 14 1 (Mar.) 93--143. 10.1145\/356869.356873","DOI":"10.1145\/356869.356873"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002967"},{"key":"e_1_2_1_40_1","first-page":"54","volume-title":"Lecture Notes in Computer Science","volume":"259","author":"Turner D.","year":"1987"},{"key":"e_1_2_1_41_1","unstructured":"Wadler P. 1989. Theorems for free! In Proceedings of the 4th Symposium on Functional Programming Languages and Computer Architecture. ACM New York. 10.1145\/99370.99404   Wadler P. 1989. Theorems for free! In Proceedings of the 4th Symposium on Functional Programming Languages and Computer Architecture. ACM New York. 10.1145\/99370.99404"},{"key":"e_1_2_1_42_1","first-page":"1","volume-title":"Conference Record of the 19th Annual ACM Symposium on Principles of Programming Languages","author":"Wadler P.","year":"1992"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Walicki M. and Meldal S. 1997. Algebraic approaches to nondeterminism an overview. ACM Comput. Surv. 29 1 (Mar.) 30--81. 10.1145\/248621.248623   Walicki M. and Meldal S. 1997. Algebraic approaches to nondeterminism an overview. ACM Comput. Surv. 29 1 (Mar.) 30--81. 10.1145\/248621.248623","DOI":"10.1145\/248621.248623"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1011508.1011509","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1011508.1011509","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:25:42Z","timestamp":1750281942000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1011508.1011509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1011508.1011509"],"URL":"https:\/\/doi.org\/10.1145\/1011508.1011509","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}