{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T09:02:12Z","timestamp":1776934932618,"version":"3.51.2"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N02706X\/1"],"award-info":[{"award-number":["EP\/N02706X\/1"]}],"id":[{"id":"10.13039\/501100000266","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":[[2019,1,2]]},"abstract":"<jats:p>Bidirectional typechecking, in which terms either synthesize a type or are checked against a known type, has become popular for its applicability to a variety of type systems, its error reporting, and its ease of implementation. Following principles from proof theory, bidirectional typing can be applied to many type constructs. The principles underlying a bidirectional approach to indexed types (generalized algebraic datatypes) are less clear. Building on proof-theoretic treatments of equality, we give a declarative specification of typing based on focalization. This approach permits declarative rules for coverage of pattern matching, as well as support for first-class existential types using a focalized subtyping judgment. We use refinement types to avoid explicitly passing equality proofs in our term syntax, making our calculus similar to languages such as Haskell and OCaml. We also extend the declarative specification with an explicit rules for deducing when a type is principal, permitting us to give a complete declarative specification for a rich type system with significant type inference. We also give a set of algorithmic typing rules, and prove that it is sound and complete with respect to the declarative system. The proof requires a number of technical innovations, including proving soundness and completeness in a mutually recursive fashion.<\/jats:p>","DOI":"10.1145\/3290322","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:33:51Z","timestamp":1546608831000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Sound and complete bidirectional typechecking for higher-rank polymorphism with existentials and indexed types"],"prefix":"10.1145","volume":"3","author":[{"given":"Jana","family":"Dunfield","sequence":"first","affiliation":[{"name":"Queen's University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neelakantan R.","family":"Krishnaswami","sequence":"additional","affiliation":[{"name":"University of Cambridge, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11783596_4"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70594-9_4"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273659"},{"key":"e_1_2_2_4_1","volume-title":"\u201cnatively\u201d. Electronic Notes in Theoretical Computer Science 59, 1","author":"Blume Matthias","year":"2001","unstructured":"Matthias Blume. 2001. No-Longer-Foreign: Teaching an ML compiler to speak C \u201cnatively\u201d. Electronic Notes in Theoretical Computer Science 59, 1 (2001)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645727.667363"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(95)00021-6"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582176"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351259"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","unstructured":"Stephen Dolan and Alan Mycroft. 2017. Polymorphism Subtyping and Type Inference in MLsub. In POPL. ACM Press 60\u201372. 10.1145\/3009837.3009882","DOI":"10.1145\/3009837.3009882"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292597.1292602"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500582"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1754809.1754827"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","unstructured":"Matthew Fluet and Riccardo Pucella. 2006. Phantom types and subtyping. (2006). arXiv: cs\/0403034 {cs.PL} .","DOI":"10.5555\/647319.721038"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings ML Family \/ OCaml Users and Developers workshops, ML Family\/OCaml 2015 (EPTCS). 23\u201335","author":"Garrigue Jacques","year":"2015","unstructured":"Jacques Garrigue and Jacques Le Normand. 2015. GADTs and Exhaustiveness: Looking for the Impossible. In Proceedings ML Family \/ OCaml Users and Developers workshops, ML Family\/OCaml 2015 (EPTCS). 23\u201335."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03542-0_19"},{"key":"e_1_2_2_18_1","unstructured":"Jean-Yves Girard. 1992. A Fixpoint Theorem in Linear Logic. (1992). Post to Linear Logic mailing list http:\/\/www.seas. upenn.edu\/~sweirich\/types\/archive\/1992\/msg00030.html ."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199475"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784748"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480927"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186031"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/331960.331977"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360207"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796806006034"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159803.1159811"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328483"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/509043"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345100"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111058"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375602"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/647887.736354"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180475.1180476"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/788018.788837"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1708016.1708023"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796811000098"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24849-1_23"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604150"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292560"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1481848.1481852"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290322","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3290322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:07Z","timestamp":1750208527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":38,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2019,1,2]]}},"alternative-id":["10.1145\/3290322"],"URL":"https:\/\/doi.org\/10.1145\/3290322","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2019-01-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}