Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage

The lambda calculus since more than half a century is a model and foundation of functional programming languages. However, lambda expressions can be evaluated with different reduction strategies and thus, there is no fixed cost model nor one canonical implementation for all applications of the lambda calculus. This article is an introduction to a dissertation is composed of four conference papers where: we present a systematic survey of reduction strategies of the lambda ca...

In this paper we establish an automated amortised resource analysis for term rewrite systems. The method is presented in an annotated type system and gives rise to polynomial bounds on the innermost runtime complexity of the analysed term rewrite system. Our analysis does not restrict the input rewrite system in any way so that rewrite systems may serve as abstractions of first-order, eagerly evaluated functional programs over user-defined inductive data-types. This facilitat...

Substitution resolution supports the computational character of $\beta$-reduction, complementing its execution with a capture-avoiding exchange of terms for bound variables. Alas, the meta-level definition of substitution, masking a non-trivial computation, turns $\beta$-reduction into an atomic rewriting rule, despite its varying operational complexity. In the current paper we propose a somewhat indirect average-case analysis of substitution resolution in the classic $\lambd...

This paper introduces a new machine architecture for evaluating lambda expressions using the normal-order reduction, which guarantees that every lambda expression will be evaluated if the expression has its normal form and the system has enough memory. The architecture considered here operates using heap memory only. Lambda expressions are represented as graphs, and all algorithms used in the processing unit of this machine are non-recursive.

We introduce a new nameless representation of lambda terms inspired by ordered logic. At a lambda abstraction, number and relative position of all occurrences of the bound variable are stored, and application carries the additional information where to cut the variable context into function and argument part. This way, complete information about free variable occurrence is available at each subterm without requiring a traversal, and environments can be kept exact such that th...

Slot and van Emde Boas' weak invariance thesis states that reasonable machines can simulate each other within a polynomially overhead in time. Is lambda-calculus a reasonable machine? Is there a way to measure the computational complexity of a lambda-term? This paper presents the first complete positive answer to this long-standing problem. Moreover, our answer is completely machine-independent and based over a standard notion in the theory of lambda-calculus: the length of a...

In this paper we introduce a typed, concurrent $\lambda$-calculus with references featuring explicit substitutions for variables and references. Alongside usual safety properties, we recover strong normalization. The proof is based on a reducibility technique and an original interactive property reminiscent of the Game Semantics approach.

Slot and van Emde Boas' weak invariance thesis states that reasonable machines can simulate each other within a polynomially overhead in time. Is $\lambda$-calculus a reasonable machine? Is there a way to measure the computational complexity of a $\lambda$-term? This paper presents the first complete positive answer to this long-standing problem. Moreover, our answer is completely machine-independent and based over a standard notion in the theory of $\lambda$-calculus: the le...

We study the properties, in particular termination, of dependent types systems for lambda calculus and rewriting.

Mechanical proofs by logical relations often involve tedious reasoning about substitution. In this paper, we show that this is not necessarily the case, by developing, in Agda, a proof that all simply typed lambda calculus expressions evaluate to values. A formalization of the proof is remarkably short (~40 lines of code), making for an excellent introduction to the technique of proofs by logical relations not only on paper but also in a mechanized setting. We then show that ...