{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T01:48:28Z","timestamp":1784166508818,"version":"3.55.0"},"reference-count":30,"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\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["621-2014-4864"],"award-info":[{"award-number":["621-2014-4864"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"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>\n            In a dependently typed language, we can guarantee correctness of our programs by providing formal proofs. To check them, the typechecker elaborates these programs and proofs into a low level core language. However, this core language is by nature hard to understand by mere humans, so how can we know we proved the right thing? This question occurs in particular for dependent copattern matching, a powerful language construct for writing programs and proofs by dependent case analysis and mixed induction\/coinduction. A definition by copattern matching consists of a list of\n            <jats:italic>clauses<\/jats:italic>\n            that are elaborated to a\n            <jats:italic>case tree<\/jats:italic>\n            , which can be further translated to primitive\n            <jats:italic>eliminators<\/jats:italic>\n            . In previous work this second step has received a lot of attention, but the first step has been mostly ignored so far.\n          <\/jats:p>\n          <jats:p>We present an algorithm elaborating definitions by dependent copattern matching to a core language with inductive datatypes, coinductive record types, an identity type, and constants defined by well-typed case trees. To ensure correctness, we prove that elaboration preserves the first-match semantics of the user clauses. Based on this theoretical work, we reimplement the algorithm used by Agda to check left-hand sides of definitions by pattern matching. The new implementation is at the same time more general and less complex, and fixes a number of bugs and usability issues with the old version. Thus we take another step towards the formally verified implementation of a practical dependently typed language.<\/jats:p>","DOI":"10.1145\/3236770","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":13,"title":["Elaborating dependent (co)pattern matching"],"prefix":"10.1145","volume":"2","author":[{"given":"Jesper","family":"Cockx","sequence":"first","affiliation":[{"name":"Chalmers University of Technology, Sweden \/ University of Gothenburg, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Abel","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Sweden \/ University of Gothenburg, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500591"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429075"},{"key":"e_1_2_2_3_1","unstructured":"Agda development team. 2017. Agda 2.5.3 documentation. http:\/\/agda.readthedocs.io\/en\/v2.5.3\/  Agda development team. 2017. Agda 2.5.3 documentation. http:\/\/agda.readthedocs.io\/en\/v2.5.3\/"},{"key":"e_1_2_2_4_1","unstructured":"Agda issue. 2017a. Disambiguation of type based on pattern leads to non-unique meta solution. (2017). https:\/\/github. com\/agda\/agda\/issues\/2834 (on the Agda bug tracker).  Agda issue. 2017a. Disambiguation of type based on pattern leads to non-unique meta solution. (2017). https:\/\/github. com\/agda\/agda\/issues\/2834 (on the Agda bug tracker)."},{"key":"e_1_2_2_5_1","unstructured":"Agda issue. 2017b. Internal error in src\/full\/Agda\/TypeChecking\/Coverage\/Match.hs:312. (2017). https:\/\/github.com\/agda\/ agda\/issues\/2874 (on the Agda bug tracker).  Agda issue. 2017b. Internal error in src\/full\/Agda\/TypeChecking\/Coverage\/Match.hs:312. (2017). https:\/\/github.com\/agda\/ agda\/issues\/2874 (on the Agda bug tracker)."},{"key":"e_1_2_2_6_1","unstructured":"Agda issue. 2017c. Panic: unbound variable. (2017). https:\/\/github.com\/agda\/agda\/issues\/2856 (on the Agda bug tracker).  Agda issue. 2017c. Panic: unbound variable. (2017). https:\/\/github.com\/agda\/agda\/issues\/2856 (on the Agda bug tracker)."},{"key":"e_1_2_2_7_1","unstructured":"Agda issue. 2017d. Record constructor is accepted record pattern is not. (2017). https:\/\/github.com\/agda\/agda\/issues\/2850 (on the Agda bug tracker).  Agda issue. 2017d. Record constructor is accepted record pattern is not. (2017). https:\/\/github.com\/agda\/agda\/issues\/2850 (on the Agda bug tracker)."},{"key":"e_1_2_2_8_1","volume-title":"Mismatch between order of matching in clauses and case tree","author":"Agda","year":"2018","unstructured":"Agda issue. 2018a. Mismatch between order of matching in clauses and case tree ; subject reduction broken. ( 2018 ). https: \/\/github.com\/agda\/agda\/issues\/2964 (on the Agda bug tracker). Agda issue. 2018a. Mismatch between order of matching in clauses and case tree; subject reduction broken. (2018). https: \/\/github.com\/agda\/agda\/issues\/2964 (on the Agda bug tracker)."},{"key":"e_1_2_2_9_1","unstructured":"Agda issue. 2018b. Unifier throws away pattern. (2018). https:\/\/github.com\/agda\/agda\/issues\/2896 (on the Agda bug tracker).  Agda issue. 2018b. Unifier throws away pattern. (2018). https:\/\/github.com\/agda\/agda\/issues\/2896 (on the Agda bug tracker)."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.3.297"},{"key":"e_1_2_2_11_1","volume-title":"FPCA 1985, Nancy, France, September 16-19, 1985, Proceedings (Lecture Notes in Computer Science), Jean-Pierre Jouannaud (Ed.)","volume":"201","author":"Augustsson Lennart","year":"1985","unstructured":"Lennart Augustsson . 1985 . Compiling Pattern Matching. In Functional Programming Languages and Computer Architecture , FPCA 1985, Nancy, France, September 16-19, 1985, Proceedings (Lecture Notes in Computer Science), Jean-Pierre Jouannaud (Ed.) , Vol. 201 . Springer, 368\u2013381. Lennart Augustsson. 1985. Compiling Pattern Matching. In Functional Programming Languages and Computer Architecture, FPCA 1985, Nancy, France, September 16-19, 1985, Proceedings (Lecture Notes in Computer Science), Jean-Pierre Jouannaud (Ed.), Vol. 201. Springer, 368\u2013381."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_5"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679681300018X"},{"key":"e_1_2_2_14_1","volume-title":"Types for Proofs and Programs","author":"Brady Edwin","year":"2003","unstructured":"Edwin Brady , Conor McBride , and James McKinna . 2003. Inductive Families Need Not Store Their Indices . In Types for Proofs and Programs , International Workshop, TYPES 2003 , Torino, Italy, April 30 - May 4, 2003, Revised Selected Papers (Lecture Notes in Computer Science), Stefano Berardi, Mario Coppo, and Ferruccio Damiani (Eds.), Vol. 3085 . Springer , 115\u2013129. Edwin Brady, Conor McBride, and James McKinna. 2003. Inductive Families Need Not Store Their Indices. In Types for Proofs and Programs, International Workshop, TYPES 2003, Torino, Italy, April 30 - May 4, 2003, Revised Selected Papers (Lecture Notes in Computer Science), Stefano Berardi, Mario Coppo, and Ferruccio Damiani (Eds.), Vol. 3085. Springer, 115\u2013129."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800055.802037"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951917"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the 1992 Workshop on Types for Proofs and Programs","author":"Coquand Thierry","year":"1992","unstructured":"Thierry Coquand . 1992 . Pattern Matching with Dependent Types . In Proceedings of the 1992 Workshop on Types for Proofs and Programs , B\u00e5stad, Sweden , June 1992, Bengt Nordstr\u00f6m, Kent Pettersson, and Gordon Plotkin (Eds.). 71\u201383. http: \/\/www.cse.chalmers.se\/~coquand\/pattern.ps Thierry Coquand. 1992. Pattern Matching with Dependent Types. In Proceedings of the 1992 Workshop on Types for Proofs and Programs, B\u00e5stad, Sweden, June 1992, Bengt Nordstr\u00f6m, Kent Pettersson, and Gordon Plotkin (Eds.). 71\u201383. http: \/\/www.cse.chalmers.se\/~coquand\/pattern.ps"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21401-6_26"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Healfdene Goguen Conor McBride and James McKinna. 2006. Eliminating Dependent Pattern Matching. In Algebra Meaning and Computation Essays Dedicated to Joseph A. Goguen on the Occasion of His 65th Birthday (Lecture Notes in Computer Science) Kokichi Futatsugi Jean-Pierre Jouannaud and Jos\u00e9 Meseguer (Eds.) Vol. 4060. Springer 521\u2013540.  Healfdene Goguen Conor McBride and James McKinna. 2006. Eliminating Dependent Pattern Matching. In Algebra Meaning and Computation Essays Dedicated to Joseph A. Goguen on the Occasion of His 65th Birthday (Lecture Notes in Computer Science) Kokichi Futatsugi Jean-Pierre Jouannaud and Jos\u00e9 Meseguer (Eds.) Vol. 4060. Springer 521\u2013540.","DOI":"10.1007\/11780274_27"},{"key":"e_1_2_2_22_1","unstructured":"INRIA. 2017. The Coq Proof Assistant Reference Manual (version 8.7 ed.). INRIA. http:\/\/coq.inria.fr\/  INRIA. 2017. The Coq Proof Assistant Reference Manual (version 8.7 ed.). INRIA. http:\/\/coq.inria.fr\/"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480927"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.48"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/141471.141499"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292597.1292606"},{"key":"e_1_2_2_29_1","volume-title":"Twenty Five Years of Constructive Type Theory","author":"Pollack Robert","unstructured":"Robert Pollack . 1998. How to Believe a Machine-Checked Proof . In Twenty Five Years of Constructive Type Theory , Giovanni Sambin and Jan Smith (Eds.). Oxford University Press . http:\/\/www.brics.dk\/RS\/97\/18\/BRICS-RS-97-18.pdf Robert Pollack. 1998. How to Believe a Machine-Checked Proof. In Twenty Five Years of Constructive Type Theory, Giovanni Sambin and Jan Smith (Eds.). Oxford University Press. http:\/\/www.brics.dk\/RS\/97\/18\/BRICS-RS-97-18.pdf"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08918-8_3"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14052-5_29"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951929"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328482"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236770","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236770","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\/3236770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":30,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236770"],"URL":"https:\/\/doi.org\/10.1145\/3236770","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"}}]}}