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

[Stephen Tetley]

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.pdf

Ester is part of the Clean 2.2 distribution, but I've had a quick look
at it now and I suspect it has diverged a bit from the version
described in the paper.

The paper references Antoni Diller's 'Compiling Functional Languages'
(Wiley - ISBN 0 471 92027 4) as the source of the algorithms they use.
This book is long out of print but it is good and comprehensive. I got
my copy second-hand from an affiliate on Amazon UK a few years ago
after reading the Ester paper. Amazon UK currently has quite a few
copies available - the £8+postage price is pretty cheap, the sellers
will post internationally (caveat - I've no experience with any of the
affiliates listed). There is a full implementation (in Pascal) in the
appendix.

Diller references David Turner's paper "A New Implementation Technique
for Applicative Languages" (1979 "Software - Practice and Experience",
vol 9, pp 31-49). If you have a university affiliation you should be
able to source this, I haven't seen it myself.

Best wishes

Stephen