{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:47:46Z","timestamp":1770904066167,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,8,29]]},"abstract":"<jats:p>In many compilers, control flow is represented using an arbitrary  \ndirected graph. But in some interesting target languages, including  \nJavaScript and WebAssembly, intraprocedural control flow can be  \nexpressed only in structured ways, using loops, conditionals, and  \nmultilevel breaks or exits. As was shown by Peterson, Kasami, and  \nTokura in 1973, such structured control flow can be obtained by  \ntranslating arbitrary control flow. The translation uses two standard  \nanalyses, but as published, it takes three passes\u2014which may explain  \nwhy it was overlooked by Emscripten, a popular compiler from C to  \nJavaScript. By tweaking the analyses and by applying fundamental ideas  \nfrom functional programming (recursive functions and immutable  \nabstract-syntax trees), the translation, along with a couple of code  \nimprovements, can be implemented in a single pass. This new  \nimplementation is slated to be added to the Glasgow Haskell  \nCompiler. Its single-pass translation, its immutable representation,  \nand its use of dominator trees make it much easier to reason about  \nthan the original translation.<\/jats:p>","DOI":"10.1145\/3547621","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T19:39:26Z","timestamp":1661974766000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Beyond Relooper: recursive translation of unstructured control flow to structured control flow (functional pearl)"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5435-1135","authenticated-orcid":false,"given":"Norman","family":"Ramsey","sequence":"first","affiliation":[{"name":"Tweag, France \/ Tufts University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"2007","unstructured":"Alfred V. Aho , Monica S. Lam , Ravi Sethi , and Jeffrey D . Ullman . 2007 . Compilers : Principles, Techniques, and Tools. Pearson, Boston , 2 nd edition. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2007. Compilers: Principles, Techniques, and Tools. Pearson, Boston, 2nd edition.","edition":"2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808479"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321999"},{"key":"e_1_2_1_4_1","unstructured":"Bytecode Alliance. 2022. Cranelift code generator. URL https:\/\/github.com\/bytecodealliance\/wasmtime\/tree\/main\/cranelift. \t\t\t\t  Bytecode Alliance. 2022. Cranelift code generator. URL https:\/\/github.com\/bytecodealliance\/wasmtime\/tree\/main\/cranelift."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1780.1783"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004075"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the ACM SIGPLAN \u201917 Conference on Programming Language Design and Implementation, in SIGPLAN Notices, 52 (6): 185\u2013200","author":"Haas Andreas","year":"2017","unstructured":"Andreas Haas , Andreas Rossberg , Derek L. Schuff , Ben L. Titzer , Michael Holman , Dan Gohman , Luke Wagner , Alon Zakai , and JF Bastien . 2017 (June). Bringing the Web up to speed with WebAssembly . Proceedings of the ACM SIGPLAN \u201917 Conference on Programming Language Design and Implementation, in SIGPLAN Notices, 52 (6): 185\u2013200 . Andreas Haas, Andreas Rossberg, Derek L. Schuff, Ben L. Titzer, Michael Holman, Dan Gohman, Luke Wagner, Alon Zakai, and JF Bastien. 2017 (June). Bringing the Web up to speed with WebAssembly. Proceedings of the ACM SIGPLAN \u201917 Conference on Programming Language Design and Implementation, in SIGPLAN Notices, 52 (6): 185\u2013200."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201014"},{"key":"e_1_2_1_9_1","unstructured":"Yuri Iozzelli. 2019 (April). Solving the structured control flow problem once and for all. URL https:\/\/medium.com\/leaningtech\/solving-the-structured-control-flow-prob lem-once-and-for-all-5123117b1ee2. Blog post snapshotted in the Internet Archive on December 24 2021. \t\t\t\t  Yuri Iozzelli. 2019 (April). Solving the structured control flow problem once and for all. URL https:\/\/medium.com\/leaningtech\/solving-the-structured-control-flow-prob lem-once-and-for-all-5123117b1ee2. Blog post snapshotted in the Internet Archive on December 24 2021."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/267959.269971"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/355609.362337"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000319"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/10704567_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.6727752"},{"key":"e_1_2_1_16_1","first-page":"122","volume-title":"ACM SIGPLAN Workshop on ML","author":"Ramsey Norman","year":"2005","unstructured":"Norman Ramsey and Jo ao Dias . 2005 (September). An applicative control-flow graph based on Huet\u2019s zipper . In ACM SIGPLAN Workshop on ML , pages 101\u2013 122 . Norman Ramsey and Jo ao Dias. 2005 (September). An applicative control-flow graph based on Huet\u2019s zipper. In ACM SIGPLAN Workshop on ML, pages 101\u2013122."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2088456.1863539"},{"key":"e_1_2_1_18_1","unstructured":"Norman Ramsey Simon L. Peyton Jones and Christian Lindig. 2005 (February). The C\u2013 language specification Version 2.0 (CVS revision 1.128). See http:\/\/www.cs.tufts.edu\/~nr\/c\u2013\/code.html#spec. \t\t\t\t  Norman Ramsey Simon L. Peyton Jones and Christian Lindig. 2005 (February). The C\u2013 language specification Version 2.0 (CVS revision 1.128). See http:\/\/www.cs.tufts.edu\/~nr\/c\u2013\/code.html#spec."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48021"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190315.1190324"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Ben L. Titzer. 2022. A fast in-place interpreter for WebAssembly. PACMPL 6 (OOPSLA). To appear. \t\t\t\t  Ben L. Titzer. 2022. A fast in-place interpreter for WebAssembly. PACMPL 6 (OOPSLA). To appear.","DOI":"10.1145\/3563311"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048147.2048224"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547621","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:28Z","timestamp":1750272208000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,29]]},"references-count":22,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2022,8,29]]}},"alternative-id":["10.1145\/3547621"],"URL":"https:\/\/doi.org\/10.1145\/3547621","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,29]]},"assertion":[{"value":"2022-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}