Cálculos de substituições explícitas à La Bruijn com sistemas de tipos com interseção

AUTOR(ES)
DATA DE PUBLICAÇÃO

2010

RESUMO

The ג-calculus is a well known theoretical computation model as old as the concept of computable functions. Due to the substitution definition as a meta-operator there exists a great quantity of variations of this computational system in which the operation of substitution is treated explicitly. In this work we investigate intersection type systems for two explicit substitution calculi, the גσ and the גse, both with de Bruijn indices. Type assignment systems allow one to have a static code analysis through implicit typing inference, where no type declaration is required. Intersection types present a machine friendly way to add polymorphism to type systems with features such as the principal typing property, allowing e.g. a separate compilation and the smartest recompilation. We study the גcalculus with de Bruijn indices with two diferente type systems, in a preliminary step for adding intersection types for both explicit substitution calculi. A characterisation for principal typíngs of irreducibe terms is a given in on of the systems, wich the intersection type systems for each גσ and גse are basead on. We analyse the subject reduction property, which guarantees that all terms of the system preserve their types during any possible computation, in some variations for the proposed type systems. Another analysed property is the relevance, in which only necessary suppositions are allowed in a typing inference, turning a weakening rule inadmissible in the type system.

ASSUNTO(S)

lambda calculus substituições explícitas lambda calculus explicit substitutions type theory matematica aplicada teoria de tipos

ACESSO AO ARTIGO

Documentos Relacionados