{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:19Z","timestamp":1750220779970,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["15K15965"],"award-info":[{"award-number":["15K15965"]}],"id":[{"id":"10.13039\/501100000646","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":[[2019,7,26]]},"abstract":"<jats:p>\n            Parallel reduction is a major component of parallel programming and widely used for summarization and aggregation. It is not well understood, however, what sorts of nontrivial summarizations can be implemented as parallel reductions. This paper develops a calculus named \u03bb\n            <jats:italic>as<\/jats:italic>\n            , a simply typed lambda calculus with algebraic simplification. This calculus provides a foundation for studying parallelization of complex reductions by equational reasoning. Its key feature is \u03b4 abstraction. A \u03b4 abstraction is observationally equivalent to the standard \u03bb abstraction, but its body is simplified before the arrival of its arguments by using algebraic properties such as associativity and commutativity. In addition, the type system of \u03bb\n            <jats:italic>as<\/jats:italic>\n            guarantees that simplifications due to \u03b4 abstractions do not lead to serious overheads. The usefulness of \u03bb\n            <jats:italic>as<\/jats:italic>\n            is demonstrated on examples of developing complex parallel reductions, including those containing more than one reduction operator, loops with jumps, prefix-sum patterns, and even tree manipulations.\n          <\/jats:p>","DOI":"10.1145\/3341644","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T20:55:51Z","timestamp":1564433751000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Lambda calculus with algebraic simplification for reduction parallelization by equational reasoning"],"prefix":"10.1145","volume":"3","author":[{"given":"Akimasa","family":"Morihata","sequence":"first","affiliation":[{"name":"University of Tokyo, Japan"}]}],"member":"320","published-online":{"date-parts":[[2019,7,26]]},"reference":[{"volume-title":"Synthesis of Parallel Algorithms, John H","author":"Blelloch Guy E.","key":"e_1_2_2_1_1"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164147"},{"key":"e_1_2_2_3_1","volume-title":"Fourth International Workshop","volume":"589","author":"Callahan David","year":"1992"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951920"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2017.04.035"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25318-8_9"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/857172.857251"},{"volume-title":"Algorithmic Skeletons: Structural Management of Parallel Computation","year":"1989","author":"Cole Murray I.","key":"e_1_2_2_8_1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247537"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389251"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01806309"},{"volume-title":"MapReduce: Simplified Data Processing on Large Clusters. In 6th Symposium on Operating System Design and Implementation (OSDI 2004)","year":"2004","author":"Dean Jeffrey","key":"e_1_2_2_12_1"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122971.1122980"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-012-0241-8"},{"key":"e_1_2_2_15_1","volume-title":"16th International Euro-Par Conference, Ischia, Italy, August 31 - September 3, 2010, Proceedings, Part II (Lecture Notes in Computer Science)","volume":"6272","author":"Emoto Kento","year":"2010"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062355"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062382"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178255"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796806006046"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411203.1411224"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(97)00014-2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062354"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256201"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268972"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243176.3243204"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/243439.243447"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863582"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-013-9093-z"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158618"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90009-8"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863523.1863535"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626405002246"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148116"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268953"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12251-4_23"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034791"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480905"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250752"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003457"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815418"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993554"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/237578.237581"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1988.5103"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90037-3"},{"key":"e_1_2_2_46_1","volume-title":"Intersection Types and Complexity of Simply Typed Lambda Calculus. In 23rd International Conference on Rewriting Techniques and Applications (RTA\u201912)","volume":"15","author":"Terui Kazushige","year":"2012"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30477-7_14"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341644","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341644","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:29Z","timestamp":1750200089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341644"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":47,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2019,7,26]]}},"alternative-id":["10.1145\/3341644"],"URL":"https:\/\/doi.org\/10.1145\/3341644","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"2019-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}