Polymorphic Regular Tree Types and Patterns

International audienceWe propose a type system based on regular tree grammars, where algebraic datatypes are interpreted in a structural way. Thus, the same constructors can be reused for different types and a flexible subtyping relation can be defined between types, corresponding to the inclusion of their semantics. For instance, one can define a type for lists and a subtype of this type corresponding to lists of even length. Patterns are simply types annotated with binders. This provides a generalization of algebraic patterns with the ability of matching arbitrarily deep in a value. We put the emphasize on simplicity and try to keep the specification and the algorithms as straightforward as possible. Our main contribution, compared to languages such as XDuce and CDuce, is that we are able to deal with both polymorphism and function types