A System F accounting for scalars
Pablo Arrighi, Alejandro Díaz-Caro · 2009
The algebraic λ-calculus [40] and the linear-algebraic λ-calculus [3] extend the λ-calculus with the possibility of making arbitrary linear combinations of λ-calculus terms (preserving ∑ αi.ti). In this paper we provide a fine-grained, System F-like type system for the linear-algebraic λ-calculus (Lineal). We show that this scalar type system enjoys both the subject-reduction property and the strong-normalisationproperty, which constitute our main technical results. The latter yields a significant simplification of the linear-algebraic λ-calculus itself, by removing the need for some restrictions in its reduction rules – and thus leaving it more intuitive. But the more important, original feature of this scalar type system is that it keeps track of ‘the amount of a type’ that this present in each term. As an example, we show how to use this type system in order to guarantee the well-definiteness of probabilistic functions ( ∑ αi = 1) – thereby specializing Lineal into a probabilistic, higher-order λ-calculus. Finally we begin to investigate the logic induced by the scalar type system, and prove a no-cloning theorem expressed solely in terms of the possible proof methods in this logic. We discuss the potential connections with Linear Logic and Quantum Computation.