# Home

##### Clone this wiki locally

Example:

```
import Data.Supply
- The Untyped Lambda Calculus -———————————————————————-
type Name   = String
data E      = App E E | Var Name | Abs Name E
instance Show E where
showsPrec _ (Var x) xs      = x + xs
showsPrec n (Abs x e) xs
| n < 1                   = “\\” + x + ". " + showsPrec 0 e xs
showsPrec n (App e1 e2) xs
| n < 2                   = showsPrec 1 e1 (" " + showsPrec 2 e2 xs)
showsPrec _ e xs            = “(” + showsPrec 0 e (“)” ++ xs)
- Generating Names -—————————————————————————————
type NameS  = Supply (Char,Int)
newNameSupply :: IO NameS
newNameSupply = newSupply (‘a’,0) next
where
next (‘z’,n)  = (‘a’,n+1)
next (a,n)    = (toEnum (fromEnum a + 1), n)
newName :: NameS → Name
newName s = case supplyValue s of
(a,0) → [‘\$’,a]
(a,n) → ‘\$’ : a : show n
- A CPS Transformation -———————————————————————————
cps                  :: NameS → E → E
cps ns (Var x)      = Abs k \$ Var x
where k = newName ns
cps ns (App e1 e2)  = Abs k
\$ cps ns1 e2 `App` (Abs x \$
cps ns2 e1 `App` (Abs f \$
Var f `App` Var x `App` Var k))
— We split the name supply into four parts:
—  * two for the two recursive calls to “cps” (ns1 and ns2).
—  * two for the two local names that we need to generate.
where ns1:ns2:ns3:ns4:ns5:_ = split ns
f                 = newName ns3
k                 = newName ns4
x                 = newName ns5
cps ns (Abs x e)     = Abs k (Var k `App` (Abs x (cps ns2 e)))
where (ns1,ns2) = split2 ns
k         = newName ns1
- Testing -—————————————————————————————————-
test :: E > IO E
test e  = do ns < newNameSupply
return (cps ns e)
example :: IO E
example = test (Var “f” `App` (Var “g” `App` Var “x”))
- \\$a. (\\$b. (\\$c. x)
-            (\\$d. (\\$e. g)
-                  (\\$f. \$f \$d \$b)
-            )
-      )
-      (\\$g. (\\$h. f)
-            (\\$i. \$i \$g \$a)
-      )
```