Modeling, Sharing, and Recursion for Weak Reduction Strategies using Explicit Substitution

We present the lambda sigma^a_w calculus, a formal synthesis of the concepts ofsharing and explicit substitution for weak reduction. We show howlambda sigma^a_w can be used as a foundation of implementations of functionalprogramming languages by modelling the essential ingredients of suchimplementations, namely weak reduction strategies, recursion, spaceleaks, recursive data structures, and parallel evaluation, in a uniform way.First, we give a precise account of the major reduction strategiesused in functional programming and the consequences of choosing lambda-graph-reduction vs. environment-based evaluation. Second, we showhow to add constructors and explicit recursion to give a precise accountof recursive functions and data structures even with respect tospace complexity. Third, we formalize the notion of space leaks in lambda sigma^a_wand use this to define a space leak free calculus; this suggests optimisationsfor call-by-need reduction that prevent space leaking and enablesus to prove that the "trimming" performed by the STG machine doesnot leak space.In summary we give a formal account of several implementationtechniques used by state of the art implementations of functional programminglanguages.Keywords. Implementation of functional programming, lambdacalculus, weak reduction, explicit substitution, sharing, recursion, spaceleaks