Difference between revisions of "Lam2Combi"
(Created page with "'''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 simpl...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
'''This article is a stub, and is currently a work in progress''' | '''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 | + | In this tutorial we will show how to translate [[lambda terms]] into [[Structured Combinators | structured combinators]], by building a simple compiler for [[Wu]] - a Haskell-like purely-functional programming language. |
== Data Structures == | == Data Structures == | ||
| Line 12: | Line 12: | ||
=== Build Instructions === | === Build Instructions === | ||
| − | Run: | + | Run: |
| + | cabal configure | ||
cabal build | cabal build | ||
The executable file should be generated at ./dist/iwu | The executable file should be generated at ./dist/iwu | ||
| Line 18: | Line 19: | ||
=== Usage Instructions === | === Usage Instructions === | ||
| − | After loading the iwu executable file, try a few examples in Wu: | + | After loading the iwu executable file, try a few examples in [[Wu]]: |
wu> succ x = + 1 x | wu> succ x = + 1 x | ||
The REPL should reply with a compiled expression: | The REPL should reply with a compiled expression: | ||
| Line 26: | Line 27: | ||
The REPL should reply with | The REPL should reply with | ||
flip = C3T2[0,2,1] | 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. | + | C3T2[0,2,1] is a [[Structured Combinators | 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, [[Pattern Types | type]] 2. |
Now, a more complex function: | Now, a more complex function: | ||
| Line 32: | Line 33: | ||
foldr = C4T14[3,2,0,1,2](foldr_r) | foldr = C4T14[3,2,0,1,2](foldr_r) | ||
foldr_r = C5T40[1,3,0,1,2,4](foldr) | 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- | + | 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 | + | Type :env to check the list of functions defined in the current session. |
wu> :env | 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) ] | [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 | To quit, type :q | ||
Latest revision as of 09:08, 21 July 2022
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.
Data Structures
The Backend
REPL
The source code for the iWu REPL is available on github
Build Instructions
Run:
cabal configure 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