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@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe