An optimisation of lambda type assignments via resource control

Abstract

The size of a lambda term’s type assignment is traditionally interpreted as the number of involved typing rules, since that interpretation corresponds to the complexity of underlying logical proof. However, it can be also assessed using some finer-grained measures such as the number of involved type declarations, or even as the sum of the sizes of all types in involved type declarations. These quantitative properties of type assignments are relevant for implementation issues, e.g. for compiler construction. We propose a type assignment method that relies on the translation of a typeable lambda term to the corresponding term of the resource control lambda calculus. This calculus, introduced by Ghilezan et al. in [1], contains operators for variable duplication and erasing, and linear substitution, whereas its typed version corresponds to intuitionistic logic with explicit structural rules of contraction and thinning. We prove that the translation preserves the type of a term, and that all output resource control lambda terms are in theirγω-normal forms, meaning that resource control operators are put in optimal positions considering the size of type assignments. The translation output of a given lambda term is often syntactically more complex and therefore more rules need to be used for its type assignment in the target resource control calculus. However, we show that two finer grained measures decrease when types are assigned to terms satisfying a certain minimal level of complexity.