{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:49Z","timestamp":1750221289805,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"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":["1219240"],"award-info":[{"award-number":["1219240"]}],"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":[[2018,1]]},"abstract":"<jats:p>We present partial evaluation by specialization-safe normalization, a novel partial evaluation technique that is Jones-optimal, that can be self-applied to achieve the Futamura projections and that can be type-checked to ensure it always generates code with the correct type. Jones-optimality is the gold-standard for nontrivial partial evaluation and guarantees that a specializer can remove an entire layer of interpretation. We achieve Jones-optimality by using a novel affine-variable static analysis that directs specialization-safe normalization to always decrease a program\u2019s runtime.<\/jats:p>\n          <jats:p>We demonstrate the robustness of our approach by showing Jones-optimality in a variety of settings. We have formally proved that our partial evaluator is Jones-optimal for call-by-value reduction, and we have experimentally shown that it is Jones-optimal for call-by-value, normal-order, and memoized normal-order. Each of our experiments tests Jones-optimality with three different self-interpreters.<\/jats:p>\n          <jats:p>\n            We implemented our partial evaluator in F\n            <jats:sub>\u03c9<\/jats:sub>\n            <jats:sup>\n              \u00b5\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sup>\n            , a recent language for typed self-applicable meta-programming. It is the first Jones-optimal and self-applicable partial evaluator whose type guarantees that it always generates type-correct code.\n          <\/jats:p>","DOI":"10.1145\/3158102","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Jones-optimal partial evaluation by specialization-safe normalization"],"prefix":"10.1145","volume":"2","author":[{"given":"Matt","family":"Brown","sequence":"first","affiliation":[{"name":"University of California at Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[{"name":"University of California at Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"volume-title":"Proceedings of PEPM\u201992","year":"1992","author":"Andersen Lars Ole","key":"e_1_2_2_1_1"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2643135.2643146"},{"key":"e_1_2_2_3_1","first-page":"35","volume-title":"Higher-Order and Symbolic Computation","author":"Barker Steve","year":"2007"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58402-1_15"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90002-F"},{"key":"e_1_2_2_6_1","first-page":"10","volume-title":"Proceedings of ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation","author":"Bondorf Anders","year":"1994"},{"volume-title":"Proceedings of ICFP\u201910","year":"2010","author":"Edwin","key":"e_1_2_2_7_1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676988"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837623"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009853"},{"volume-title":"Webpage accompanying this paper. The webpage accompanying this paper is","year":"2018","author":"Brown Matt","key":"e_1_2_2_11_1"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007205"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411226"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/154630.154645"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237784"},{"volume-title":"Proceedings of ESOP\u201903","year":"2003","author":"Danvy Olivier","key":"e_1_2_2_16_1"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328408.1328433"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010095604496"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11924661_25"},{"volume-title":"Proceedings of PEPM\u201999","year":"1999","author":"Gl\u00fcck Robert","key":"e_1_2_2_20_1"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/568173.568175"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-008-9033-5"},{"key":"e_1_2_2_23_1","first-page":"150","volume-title":"Ershov Memorial Conference","author":"Gl\u00fcck Robert","year":"2009"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480945.1480954"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000058"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541568.2541572"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034808"},{"first-page":"282","volume-title":"Proceedings of Rewriting Techniques and Applications","author":"Jones Neil D.","key":"e_1_2_2_28_1"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/153676"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32202-0_3"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3540543961_8"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45350-4_11"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000423"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/215465.215469"},{"volume-title":"Lambda calculus. https:\/\/www21.in.tum.de\/teaching\/logik\/SS13\/lambda-en.pdf , (accessed","year":"2017","author":"Nipkow Tobias","key":"e_1_2_2_35_1"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90109-U"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542509"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048098"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32033-3_17"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44978-7_15"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232647"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/944705.944728"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158102","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":42,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158102"],"URL":"https:\/\/doi.org\/10.1145\/3158102","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}