{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:13:35Z","timestamp":1775873615961,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,7,30]]},"abstract":"<jats:p>Partially-static data structures are a well-known technique for improving binding times. However, they are often defined in an ad-hoc manner, without a unifying framework to ensure full use of the equations associated with each operation.<\/jats:p>\n          <jats:p>We present a foundational view of partially-static data structures as free extensions of algebras for suitable equational theories, i.e. the coproduct of an algebra and a free algebra in the category of algebras and their homomorphisms. By precalculating these free extensions, we construct a high-level library of partially-static data representations for common algebraic structures. We demonstrate our library with common use-cases from the literature: string and list manipulation, linear algebra, and numerical simplification.<\/jats:p>","DOI":"10.1145\/3236795","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Partially-static data as free extension of algebras"],"prefix":"10.1145","volume":"2","author":[{"given":"Jeremy","family":"Yallop","sequence":"first","affiliation":[{"name":"University of Cambridge, UK"}]},{"given":"Tamara","family":"von Glehn","sequence":"additional","affiliation":[{"name":"University of Cambridge, UK"}]},{"given":"Ohad","family":"Kammar","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2426890.2426917"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-009-9049-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2014.02.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561347_18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2008.09.008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2008.09.008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007205"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040306"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796898003104"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007763000430"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-34897-1_14"},{"key":"e_1_2_1_12_1","volume-title":"A Type Specialisation Tutorial","author":"Hughes John","unstructured":"John Hughes . 1999. A Type Specialisation Tutorial . Springer Berlin Heidelberg , Berlin, Heidelberg , 293\u2013325. John Hughes. 1999. A Type Specialisation Tutorial. Springer Berlin Heidelberg, Berlin, Heidelberg, 293\u2013325."},{"key":"e_1_2_1_13_1","volume-title":"Fourth International Valentin Turchin Workshop on Metacomputation.","author":"Inoue Jun","year":"2014","unstructured":"Jun Inoue . 2014 . Supercompilation via staging . In Fourth International Valentin Turchin Workshop on Metacomputation. Jun Inoue. 2014. Supercompilation via staging. In Fourth International Valentin Turchin Workshop on Metacomputation."},{"key":"e_1_2_1_14_1","volume-title":"Partial Evaluation and Automatic Program Generation","author":"Jones Neil D.","unstructured":"Neil D. Jones , Carsten K. Gomard , and Peter Sestoft . 1993. Partial Evaluation and Automatic Program Generation . Prentice-Hall, Inc. , Upper Saddle River, NJ, USA. Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. 1993. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Inc., Upper Saddle River, NJ, USA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976022.2976028"},{"key":"e_1_2_1_16_1","volume-title":"Functional and Logic Programming (Lecture Notes in Computer Science)","author":"Kiselyov Oleg","unstructured":"Oleg Kiselyov . 2014. The Design and Implementation of BER MetaOCaml . In Functional and Logic Programming (Lecture Notes in Computer Science) , Michael Codish and Eijiro Sumii (Eds.), Vol. 8475 . Springer International Publishing , 86\u2013102. Oleg Kiselyov. 2014. The Design and Implementation of BER MetaOCaml. In Functional and Logic Programming (Lecture Notes in Computer Science), Michael Codish and Eijiro Sumii (Eds.), Vol. 8475. Springer International Publishing, 86\u2013102."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017753.1017794"},{"key":"e_1_2_1_18_1","unstructured":"Torben \u00c6gidius Mogensen. 1988. Partially Static Structures in a Self-Applicable Partial Evaluator. In Partial Evaluation and Mixed Computation D. Bj\u00f8rner A.P. Ershov and N.D. Jones (Eds.).  Torben \u00c6gidius Mogensen. 1988. Partially Static Structures in a Self-Applicable Partial Evaluator. In Partial Evaluation and Mixed Computation D. Bj\u00f8rner A.P. Ershov and N.D. Jones (Eds.)."},{"key":"e_1_2_1_19_1","volume-title":"14 years on. Talk given at the International Summer School on Metaprogramming","author":"Jones Simon Peyton","year":"2016","unstructured":"Simon Peyton Jones . 2016. Template Haskell , 14 years on. Talk given at the International Summer School on Metaprogramming , Cambridge, UK . ( August 2016 ). https:\/\/www.cl.cam.ac.uk\/events\/metaprog2016\/Template-Haskell-Aug16.pptx . Simon Peyton Jones. 2016. Template Haskell, 14 years on. Talk given at the International Summer School on Metaprogramming, Cambridge, UK. (August 2016). https:\/\/www.cl.cam.ac.uk\/events\/metaprog2016\/Template-Haskell-Aug16.pptx ."},{"key":"e_1_2_1_20_1","volume-title":"The Essence of Multi-stage Evaluation in LMS","author":"Rompf Tiark","unstructured":"Tiark Rompf . 2016. The Essence of Multi-stage Evaluation in LMS . Springer International Publishing , Cham , 318\u2013335. Tiark Rompf. 2016. The Essence of Multi-stage Evaluation in LMS. Springer International Publishing, Cham, 318\u2013335."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429128"},{"key":"e_1_2_1_22_1","volume-title":"Diatchki","author":"Sheard Tim","year":"2002","unstructured":"Tim Sheard and Iavor S . Diatchki . 2002 . Staging Algebraic Datatypes. Unpublished manuscript. (2002). http:\/\/web.cecs.pdx.edu\/~sheard\/papers\/stagedData.ps . Tim Sheard and Iavor S. Diatchki. 2002. Staging Algebraic Datatypes. Unpublished manuscript. (2002). http:\/\/web.cecs.pdx.edu\/~sheard\/papers\/stagedData.ps ."},{"key":"e_1_2_1_23_1","volume-title":"Domain-Specific Program Generation (Lecture Notes in Computer Science), Christian Lengauer, Don S","author":"Taha Walid","unstructured":"Walid Taha . 2003. A Gentle Introduction to Multi-stage Programming .. In Domain-Specific Program Generation (Lecture Notes in Computer Science), Christian Lengauer, Don S . Batory, Charles Consel, and Martin Odersky (Eds.), Vol. 3016 . Springer , 30\u201350. Walid Taha. 2003. A Gentle Introduction to Multi-stage Programming.. In Domain-Specific Program Generation (Lecture Notes in Computer Science), Christian Lengauer, Don S. Batory, Charles Consel, and Martin Odersky (Eds.), Vol. 3016. Springer, 30\u201350."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/258993.259019"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2426890.2426906"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110273"},{"key":"e_1_2_1_27_1","volume-title":"OCaml Users and Developers Workshop","author":"Yallop Jeremy","year":"2015","unstructured":"Jeremy Yallop and Leo White . 2015 . Modular Macros. (September 2015) . OCaml Users and Developers Workshop 2015. Jeremy Yallop and Leo White. 2015. Modular Macros. (September 2015). OCaml Users and Developers Workshop 2015."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236795","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236795","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:28Z","timestamp":1750282888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236795"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":27,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236795"],"URL":"https:\/\/doi.org\/10.1145\/3236795","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}