{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:55:08Z","timestamp":1790927708295,"version":"4.1.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T00:00:00Z","timestamp":1693353600000},"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":[[2023,8,30]]},"abstract":"<jats:p>\n                    Records are finite functions from keys to values. In this work we focus on two main distinct usages of records: structs and maps. The former associate different keys to values of different types, they are accessed by providing nominal keys, and trying to access a non-existent key yields an error. The latter associate all keys to values of the same type, they are accessed by providing expressions that compute a key, and trying to access a non-existent key usually yields some default value such as Null or nil. Here, we propose a type theory that covers both kinds of usage, where record\n                    <jats:italic>types<\/jats:italic>\n                    may associate to different types either single keys (as for structs) or sets of keys (as for maps) and where the same record\n                    <jats:italic>expression<\/jats:italic>\n                    can be accessed and used both in the struct-like style and in the map-like style we just described. Since we target dynamically-typed languages our type theory includes union and intersection types, characterized by a subtyping relation. We define the subtyping relation for our record types via a semantic interpretation and derive the decomposition rules to decide it, define a backtracking-free subtyping algorithm that we prove to be correct, and provide a canonical representation for record types that is used to define various type operators needed to type record operations such as selection, concatenation, and field deletion.\n                  <\/jats:p>","DOI":"10.1145\/3607838","type":"journal-article","created":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T13:40:31Z","timestamp":1693489231000},"page":"215-258","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Typing Records, Maps, and Structs"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0951-7535","authenticated-orcid":false,"given":"Giuseppe","family":"Castagna","sequence":"first","affiliation":[{"name":"CNRS, France \/ Universit\u00e9 Paris Cit\u00e9, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,8,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ballerina. Ballerina Language Specification. https:\/\/ballerina.io\/learn\/ballerina-specifications\/"},{"key":"e_1_2_1_2_1","volume-title":"8th ACM International Conference on Functional Programming. ACM Press","author":"Benzaken V\u00e9ronique","year":"2003","unstructured":"V\u00e9ronique Benzaken, Giuseppe Castagna, and Alain Frisch. 2003. CDuce: an XML-Centric General-Purpose Language. In ICFP \u201903, 8th ACM International Conference on Functional Programming. ACM Press, Uppsala, Sweden. 51\u201363."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49498-1_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1988.5099"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13346-1_2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0040253"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-16(1:15)2020"},{"key":"e_1_2_1_8_1","volume-title":"The French School of Programming","author":"Castagna Giuseppe","unstructured":"Giuseppe Castagna. 2023. Programming with union, intersection, and negation types. In The French School of Programming, Bertrand Meyer (Ed.). Springer. isbn:978-3-031-34517-3 ISBN 978-3-031-34517-3. Preprint at arxiv:2111.03354"},{"key":"e_1_2_1_9_1","volume-title":"The Design Principles of the Elixir Type System. The Art, Science, and Engineering of Programming, 8, 2","author":"Castagna Giuseppe","year":"2024","unstructured":"Giuseppe Castagna, Guillaume Duboc, and Jos\u00e9 Valim. 2024. The Design Principles of the Elixir Type System. The Art, Science, and Engineering of Programming, 8, 2 (2024), To appear. Preprint at arxiv:2306.06391"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1069774.1069793"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498674"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676991"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676991"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034788"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806612"},{"key":"e_1_2_1_16_1","unstructured":"Elixir. Elixir Typespecs. https:\/\/hexdocs.pm\/elixir\/typespecs.html"},{"key":"e_1_2_1_17_1","unstructured":"Erlang. Erlang Reference Manual User\u2019s Guide. https:\/\/www.erlang.org\/doc\/reference_manual\/users_guide.html"},{"key":"e_1_2_1_18_1","unstructured":"F'. F# documentation. https:\/\/learn.microsoft.com\/en-us\/dotnet\/fsharp\/"},{"key":"e_1_2_1_19_1","unstructured":"Alain Frisch. 2004. Th\u00e9orie conception et r\u00e9alisation d\u2019un langage de programmation adapt\u00e9 \u00e0 XML. Ph. D. Dissertation. Universit\u00e9 Paris Diderot. http:\/\/www.cduce.org\/papers\/frisch_phd.pdf"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029823"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391293"},{"key":"e_1_2_1_22_1","unstructured":"Go. The Go Programming Language Specification. https:\/\/go.dev\/ref\/spec"},{"key":"e_1_2_1_23_1","unstructured":"Hive. Apache Hive Language Manual. https:\/\/cwiki.apache.org\/confluence\/display\/Hive\/LanguageManual"},{"key":"e_1_2_1_24_1","unstructured":"C. A. R. Hoare. 1965. Record Handling. ALGOL Bull. nov 39\u201369. issn:0084-6198"},{"key":"e_1_2_1_25_1","unstructured":"C. A. R. Hoare. 1966. Further Thoughts on Record Handling. ALGOL Bull. mar 5\u201311. issn:0084-6198"},{"key":"e_1_2_1_26_1","unstructured":"C. A. R. Hoare. 1966. Record Handling. Lecture Notes NATO Summer School."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/62678.62702"},{"key":"e_1_2_1_28_1","volume-title":"Semantic Subtyping in Luau. Blog post. https:\/\/blog.roblox.com\/2022\/11\/semantic-subtyping-luau Accessed on May 6th 2023","author":"Jeffrey Alan","unstructured":"Alan Jeffrey. 2022. Semantic Subtyping in Luau. Blog post. https:\/\/blog.roblox.com\/2022\/11\/semantic-subtyping-luau Accessed on May 6th 2023"},{"key":"e_1_2_1_29_1","unstructured":"Julia. Julia Documentation. https:\/\/docs.julialang.org\/"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30477-7_7"},{"key":"e_1_2_1_31_1","unstructured":"Lua. Lua Reference Manual. https:\/\/www.lua.org\/manual"},{"key":"e_1_2_1_32_1","unstructured":"Luau. Luau. https:\/\/luau-lang.org\/"},{"key":"e_1_2_1_33_1","unstructured":"OCaml. Learn OCaml. https:\/\/ocaml.org\/docs"},{"key":"e_1_2_1_34_1","article-title":"A Versatile Constraint-Based Type Inference System","volume":"7","author":"Pottier Fran\u00e7ois","year":"2000","unstructured":"Fran\u00e7ois Pottier. 2000. A Versatile Constraint-Based Type Inference System. Nordic J. of Computing, 7, 4 (2000), dec, 312\u2013347. issn:1236-6064","journal-title":"Nordic J. of Computing"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75284"},{"key":"e_1_2_1_36_1","volume-title":"workshop on Advances in types for computer science at the Newton Institute","author":"R\u00e9my Didier","year":"1995","unstructured":"Didier R\u00e9my. 1995. A case study of typechecking with constrained types: Typing record concatenation. August, Presented at the workshop on Advances in types for computer science at the Newton Institute, Cambridge, UK"},{"key":"e_1_2_1_37_1","unstructured":"Ruby. What is Ruby? https:\/\/ruby-doc.org\/3.2.1"},{"key":"e_1_2_1_38_1","unstructured":"Rust. The Rust Reference. https:\/\/doc.rust-lang.org\/stable\/reference\/"},{"key":"e_1_2_1_39_1","unstructured":"Scala. The Scala Programming Language. https:\/\/docs.scala-lang.org\/"},{"key":"e_1_2_1_40_1","unstructured":"Swift. The Swift Programming Language Book. https:\/\/www.swift.org\/documentation\/"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the Symposium on Logic in Computer Science (LICS \u201987)","author":"Wand Mitchell","year":"1987","unstructured":"Mitchell Wand. 1987. Complete Type Inference for Simple Objects. In Proceedings of the Symposium on Logic in Computer Science (LICS \u201987), Ithaca, New York, USA, June 22-25, 1987. IEEE Computer Society, 37\u201344."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39162"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571224"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276483"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607838","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:37:06Z","timestamp":1750163826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,30]]},"references-count":44,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2023,8,30]]}},"alternative-id":["10.1145\/3607838"],"URL":"https:\/\/doi.org\/10.1145\/3607838","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,30]]},"assertion":[{"value":"2023-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}