There is a nice simple algorithm on wikipedia:<br><a href="http://en.wikipedia.org/wiki/Combinatory_logic">http://en.wikipedia.org/wiki/Combinatory_logic</a><br>(for both SKI and BCKW)<br><br>translated to haskell:<br><br>
-- The anoying thing about the algorithm is that it is difficult to separate the SKI and LC expression types<br>-- it's easiest to just combine them.<br>data Expr = Apply Expr Expr<br> | Lambda String Expr<br>
| Id String<br> | S <br> | K<br> | I <br> deriving (Show)<br><br>convert (Apply a b) = Apply (convert a) (convert b)<br>convert (Lambda x e) | not $ occursFree x e = Apply K (convert e)<br>
convert (Lambda x (Id s)) | x == s = I<br>convert (Lambda x (Lambda y e)) | occursFree x e = convert (Lambda x (convert (Lambda y e)))<br>convert (Lambda x (Apply e1 e2)) = Apply (Apply S (convert $ Lambda x e1)) (convert $ Lambda x e2)<br>
convert x = x<br><br>occursFree var (Apply a b) = (occursFree var a) || (occursFree var b)<br>occursFree var (Lambda a b) = if a == var then False else (occursFree var b)<br>occursFree var (Id a) = if a == var then True else False<br>
occursFree var _ = False<br> <br>testExpr = Lambda "x" $ Lambda "y" $ Apply (Id "y") (Id "x")<br><br>test = convert testExpr<br><br><br>Hope that helps,<br><br>- Job<br><br>
<div class="gmail_quote">2010/1/28 Dušan Koláø <span dir="ltr"><<a href="mailto:kolar@fit.vutbr.cz">kolar@fit.vutbr.cz</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Dear cafe,<br>
<br>
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...<br>
<br>
Thanks,<br>
<br>
Dušan<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>