Pure patterns type systems
Author(s) -
Gilles Barthe,
Horatiu Cirstea,
Claude Kirchner,
Luigi Liquori
Publication year - 2003
Publication title -
acm sigplan notices
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.31
H-Index - 99
eISSN - 1558-1160
pISSN - 0362-1340
ISBN - 1-58113-628-5
DOI - 10.1145/640128.604152
Subject(s) - computer science , rewriting , type theory , confluence , programming language , normalization (sociology) , lambda calculus , type (biology) , functional programming , pattern matching , typed lambda calculus , theoretical computer science , ecology , sociology , anthropology , biology
We introduce a new framework of algebraic pure type systems in which we consider rewrite rules as lambda terms with patterns and rewrite rule application as abstraction application with built-in matching facilities. This framework, that we call "Pure Pattern Type Systems", is particularly well-suited for the foundations of programming (meta)languages and proof assistants since it provides in a fully unified setting higher-order capabilities and pattern matching ability together with powerful type systems. We prove some standard properties like confluence and subject reduction for the case of a syntactic theory and under a syntactical restriction over the shape of patterns. We also conjecture the strong normalization of typable terms. This work should be seen as a contribution to a formal connection between logics and rewriting, and a step towards new proof engines based on the Curry-Howard isomorphism.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom