[Haskell-cafe] OT: Literature on translation of lambda calculus to combinators

[Job Vranish]

There is a nice simple algorithm on wikipedia:
http://en.wikipedia.org/wiki/Combinatory_logic
(for both SKI and BCKW)

translated to haskell:

-- The anoying thing about the algorithm is that it is difficult to separate
the SKI and LC expression types
--  it's easiest to just combine them.
data Expr = Apply Expr Expr
          | Lambda String Expr
          | Id String
          | S
          | K
          | I
      deriving (Show)

convert (Apply a b) = Apply (convert a) (convert b)
convert (Lambda x e) | not $ occursFree x e = Apply K (convert e)
convert (Lambda x (Id s)) | x == s = I
convert (Lambda x (Lambda y e)) | occursFree x e = convert (Lambda x
(convert (Lambda y e)))
convert (Lambda x (Apply e1 e2)) = Apply (Apply S (convert $ Lambda x e1))
(convert $ Lambda x e2)
convert x = x

occursFree var (Apply a b) = (occursFree var a) || (occursFree var b)
occursFree var (Lambda a b) = if a == var then False else (occursFree var b)
occursFree var (Id a) = if a == var then True else False
occursFree var _ = False

testExpr = Lambda "x" $ Lambda "y" $ Apply (Id "y") (Id "x")

test = convert testExpr


Hope that helps,

- Job

2010/1/28 Dušan Kolář <kolar at fit.vutbr.cz>

> Dear cafe,
>
>  Could anyone provide a link to some paper/book (electronic version of both
> preferred, even if not free) that describes an algorithm of translation of
> untyped lambda calculus expression to a set of combinators? Preferably SKI
> or BCKW. I'm either feeding google with wrong question or there is no link
> available now...
>
>  Thanks,
>
>    Dušan
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100128/0e06c2d8/attachment.html