[Haskell-cafe] Re: OT: Literature on translation of lambda calculus to combinators
Dear all, Dušan Kolář kolar at fit.vutbr.cz writes: [...] 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... 13 years ago (ugh...) I've posted a tutorial-style treatment of the compilation of Dave Turner's SASL to SKI. Also addresses reduction and simple optimizations of the resulting SKI programs. http://www-db.informatik.uni-tuebingen.de/files/publications/sasl.ps.gz Cheers, —Torsten ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: OT: Literature on translation of lambda calculus to combinators
Job Vranish jvran...@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
Re: [Haskell-cafe] Re: OT: Literature on translation of lambda calculus to combinators
Cool, Thanks :D also quickcheck says the two algorithms are equivalent :) On Fri, Jan 29, 2010 at 4:33 AM, Nick Smallbone nick.smallb...@gmail.comwrote: Job Vranish jvran...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
