Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän

Elaborating dependent (co… - Göteborgs universitet Till startsida
Till innehåll Läs mer om hur kakor används på gu.se

Elaborating dependent (co)pattern matching

Artikel i vetenskaplig tidskrift
Författare Andreas Abel
Jesper Cockx
Publicerad i Proceedings of the ACM on Programming Languages
Volym 2
Nummer/häfte ICFP
Sidor 75:1-75:30
Publiceringsår 2018
Publicerad vid Institutionen för data- och informationsteknik (GU)
Institutionen för data- och informationsteknik, datavetenskap (GU)
Sidor 75:1-75:30
Språk en
Länkar https://dl.acm.org/citation.cfm?doi...
Ämneskategorier Programvaruteknik, Teoretisk datalogi


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 clauses that are elaborated to a case tree, which can be further translated to primitive eliminators. In previous work this second step has received a lot of attention, but the first step has been mostly ignored so far. 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.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?