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

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