Semantics of Typed Lambda-Calculus with Constructors

Abstract

We present a Curry-style second-order type system with union and intersection types for the lambda-calculus with constructors of Arbiser, Miquel and Rios, an extension of lambda-calculus with a pattern matching mechanism for variadic constructors. We then prove the strong normalisation and the absence of match failure for a restriction of this system, by adapting the standard reducibility method.

Keywords

• computer science - logic in computer science
• f.3.2, f.4.3