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

[Job Vranish]

Cool, Thanks :D

also quickcheck says the two algorithms are equivalent :)



On Fri, Jan 29, 2010 at 4:33 AM, Nick Smallbone <nick.smallbone at gmail.com>wrote:

> Job Vranish <jvranish at gmail.com> writes:
>
> > Ideally we'd like the type of convert to be something like:
> > convert :: LambdaExpr -> SKIExpr
> > but this breaks in several places, such as the nested converts in the RHS
> of the rule:
> > convert (Lambda x (Lambda y e)) | occursFree x e = convert (Lambda x
> (convert (Lambda y e)))
> >
> > A while ago I tried modifying the algorithm to be pure top-down so that
> it wouldn't have this problem, but I
> > didn't have much luck.
> >
> > Anybody know of a way to fix this?
>
> The way to do it is, when you see an expression Lambda x e, first
> convert e to a combinatory expression (which will have x as a free
> variable, and will obviously have no lambdas). Then you don't need
> nested converts at all.
>
> Not-really-tested code follows.
>
> Nick
>
> data Lambda = Var String
>            | Apply Lambda Lambda
>            | Lambda String Lambda deriving Show
>
> data Combinatory = VarC String
>                 | ApplyC Combinatory Combinatory
>                  | S
>                 | K
>                 | I deriving Show
>
> compile :: Lambda -> Combinatory
> compile (Var x) = VarC x
> compile (Apply t u) = ApplyC (compile t) (compile u)
> compile (Lambda x t) = lambda x (compile t)
>
> lambda :: String -> Combinatory -> Combinatory
> lambda x t | x `notElem` vars t = ApplyC K t
> lambda x (VarC y) | x == y = I
> lambda x (ApplyC t u) = ApplyC (ApplyC S (lambda x t)) (lambda x u)
>
> vars :: Combinatory -> [String]
> vars (VarC x) = [x]
> vars (ApplyC t u) = vars t ++ vars u
> vars _ = []
>
> _______________________________________________
> 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/20100129/1055e8d4/attachment.html