{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:56:39Z","timestamp":1750308999025,"version":"3.41.0"},"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>We develop a type-theoretical method for optimizing type directed compilation of polymorphic languages, implement the method in SML#, which is a full-scale compiler of Standard ML extended with several advanced features that require type-passing operational semantics, and report its effectiveness through performance evaluation. For this purpose, we first define a predicative second-order lambda calculus with finitary polymorphism, where each type abstraction is explicitly constrained to a finite type universe, and establishes the type soundness with respect to a type-passing operational semantics. Different from a calculus with stratified type universes, type universes of the calculus are terms that represent a finite set of instance types. We then develop a universe reconstruction algorithm that takes a term of the standard second-order lambda calculus, checks if the term is typable with finitary polymorphism, and, if typable, constructs a term in the calculus of finitary polymorphism. Based on these results, we present a type-based optimization method for polymorphic functions. Since our formalism is based on the second-order lambda calculus, it can be used to optimize various polymorphic languages. We implement the optimization method for native (tag-free) data representation and record polymorphism, and evaluate its effectiveness through benchmarks. The evaluation shows that 83.79% of type passing abstractions are eliminated, and achieves the average of 15.28% speed-up of compiled code.<\/jats:p>","DOI":"10.1145\/3236776","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Finitary polymorphism for optimizing type-directed compilation"],"prefix":"10.1145","volume":"2","author":[{"given":"Atsushi","family":"Ohori","sequence":"first","affiliation":[{"name":"Tohoku University, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsuhiro","family":"Ueno","sequence":"additional","affiliation":[{"name":"Tohoku University, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisayuki","family":"Mima","sequence":"additional","affiliation":[{"name":"Tohoku University, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1086"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzx018"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19810270205"},{"volume-title":"Types in Compilation","author":"Elsman Martin","key":"e_1_2_2_4_1","unstructured":"Martin Elsman . 1998. Polymorphic equality \u2014 No tags required . In Types in Compilation , Xavier Leroy and Atsushi Ohori (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 136\u2013155. Martin Elsman. 1998. Polymorphic equality \u2014 No tags required. In Types in Compilation, Xavier Leroy and Atsushi Ohori (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 136\u2013155."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/227699.227700"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199475"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(94)00005-0"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01019005"},{"key":"e_1_2_2_9_1","volume-title":"Peyton Jones and John Launchbury","author":"Simon","year":"1991","unstructured":"Simon L. Peyton Jones and John Launchbury . 1991 . Unboxed values as first class citizens in a non-strict functional language. In Functional Programming Languages and Computer Architecture, John Hughes (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg, 636\u2013666. Simon L. Peyton Jones and John Launchbury. 1991. Unboxed values as first class citizens in a non-strict functional language. In Functional Programming Languages and Computer Architecture, John Hughes (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 636\u2013666."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/77350.77355"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/77350.77355"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/143165.143205"},{"volume-title":"An Intuitionistic Theory of Types: Predicative Part","author":"L\u00f6f.","key":"e_1_2_2_13_1","unstructured":"Martin- L\u00f6f. 1975. An Intuitionistic Theory of Types: Predicative Part . In Logic Colloquium, H. E. Rose and J. C. Shepherdson (Eds.). Noth Holland , Amsterdam . Martin-L\u00f6f. 1975. An Intuitionistic Theory of Types: Predicative Part. In Logic Colloquium, H. E. Rose and J. C. Shepherdson (Eds.). Noth Holland, Amsterdam."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140335.1140364"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/143165.143200"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/218570.218572"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2831"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680100394X"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155112"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/2369948"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/258948.258958"},{"key":"e_1_2_2_24_1","unstructured":"SML#-Project-Team. 2005 \u2013 2018. SML# Project. http:\/\/www.riec.tohoku.ac.jp\/smlsharp\/  SML#-Project-Team. 2005 \u2013 2018. SML# Project. http:\/\/www.riec.tohoku.ac.jp\/smlsharp\/"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/231379.231414"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/182409.182411"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796898003086"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159877"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004245"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236776","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\/3236776"}},"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\/3236776"],"URL":"https:\/\/doi.org\/10.1145\/3236776","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"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"}}]}}