Lam2Combi

This article is a stub, and is currently a work in progress

In this tutorial we will show how to translate lambda terms into structured combinators, by building a simple compiler for Wu - a Haskell-like purely-functional programming language.

REPL

The source code for the iWu REPL is available on github

Build Instructions

Run:

  cabal build

The executable file should be generated at ./dist/iwu

Usage Instructions

After loading the iwu executable file, try a few examples in Wu:

  wu> succ x = + 1 x

The REPL should reply with a compiled expression:

  succ = +1

Try another example:

  wu> flip x f g = x g f 

The REPL should reply with

  flip = C3T2[0,2,1]

C3T2[0,2,1] is a structured combinator, a lifted higher-order function defined in terms of graph transformations. In this case, the function flip compiles to a combinator of arity 3, type 2.

Now, a more complex function:

  wu> foldr f z ls = ls (z) (\h t -> f h (foldr f z t))
  foldr = C4T14[3,2,0,1,2](foldr_r)
  foldr_r = C5T40[1,3,0,1,2,4](foldr)

In this case, the compiler has lifted the internal lambda abstraction (\h t -> f h (foldr f z t)) to an auxiliary function foldr_r. Nested lambdas are useful on programs at a high-level language, but complicate the compilation process (especially when using a variable abstraction algorithm). Lambda-lifting solves this problem, separating nested lambdas into standalone functions.

Type :env to check the list of functions defined in the current session.

   wu> :env
   [succ = +1 , flip = C3T2[0,2,1], foldr = C4T14[3,2,0,1,2](foldr_r), foldr_r = C5T40[1,3,0,1,2,4](foldr) ]  

To quit, type :q