On 28 Jan 2010, at 10:54, Dušan Kolář wrote:
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
Dear Dušan,
You can also find an algorithm in everyone's favourite book in
combinatorial logic "To Mock a Mockingbird"
(http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird).
Cheers,
Matthias.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://
>
> Why is it difficult?
>
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))
On Thu, Jan 28, 2010 at 09:23:23AM -0500, Job Vranish wrote:
> -- 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.
Why is it difficult?
--
Felipe.
___
Ha
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 Exp
Hi Dušan
The Ester shell written in Clean compiles via the SKI combinators. It
is describe in the paper - 'A Functional Shell that Operates on Typed
and Compiled Applications' by Arjen van Weelden and Rinus Plasmeijer
which is available here:
http://www.st.cs.ru.nl/papers/2004/plar2004-Esther_AFP
Also see http://www.haskell.org/haskellwiki/Super_combinator Wiki page.
Fixed set of combinators gives you complexity of translation that is
more than linear of the length of lambda expression.
The length of output string is O(3^length(lambdaExpression)) for SK
combinator pair.
2010/1/28 Dušan K
See, for example, slide 119 and onwards in the slides at
http://www.cl.cam.ac.uk/teaching/0809/FFuncProg/FoFP_2009_slides.pdf
The slides covers SKI and BCSKI.
Cheers,
Max
2010/1/28 Dušan Kolář :
> Dear cafe,
>
> Could anyone provide a link to some paper/book (electronic version of both
> prefer
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
