Implementing a Functional Language with Graph Reduction

Implementing a Functional Language with Graph Reduction

Posted on December 27, 2021 by Thomas Mahler

Abstract

Implementing a small functional language with a classic combinator based graph-reduction machine in Haskell.

The implementation is structured into three parts:

A λ-calculus parser from A Combinatory Compiler which was extended to cover a tiny functional language based on the untyped λ-calculus. A compiler from λ-calculus to combinatory logic combinators (S,K,I,B,C and Y) which is based on bracket-abstraction and some optimization rules. A graph-reducer. Combinator terms are allocated into a graph data-structure. Which is then reduced by applying combinator graph-reduction. The destructive inplace reduction of the graph is made possible by using STRef mutable references.

Introduction

In my last blog post I presented two ways of transforming λ-terms into variable free representations: - bracket abstraction to combinatory logic terms (SKI) and - bracket abstraction to terms of closed cartesian categories (CCC).

... continue reading