z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom