Home > Archive > Functional > January 2007 > looking for a compiler
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
looking for a compiler
|
|
| J.ProPasserby@googlemail.com 2007-01-06, 7:20 pm |
| i need a compiler from any functional language to SKI, if who had one,
let me know,THX.
| |
|
| J.ProPasserby@googlemail.com ha scritto:
> i need a compiler from any functional language to SKI, if who had one,
> let me know,THX.
>
Sorry but ... what is SKI?
Thanks in advance.
| |
| Neelakantan Krishnaswami 2007-01-06, 7:20 pm |
| In article <459bcb85$0$20812$5fc30a8@news.tiscali.it>, Raff wrote:
> J.ProPasserby@googlemail.com ha scritto:
>
> Sorry but ... what is SKI?
S, K, and I are combinators (ie, closed lambda terms), which have the
property they are sufficient to compute the same function as any other
lambda term, by composing them in the appropriate ways. I is the
identity, K is a curried two-argument function that returns its first
argument, and S is a substitution operation:
I x -> x
K x y -> x
S x y z -> (x z) (y z)
In terms of logic, the K and S combinators correspond to the axioms:
K : A -> B -> A
S : (A -> B -> C) -> ((A -> B) -> (B -> C))
Function application corresponds to modus ponens.
Since combinators don't have free variables, it used to be popular to
generate machine code by compiling into a combinator calculus first.
--
Neel R. Krishnaswami
neelk@cs.cmu.edu
| |
|
| Neelakantan Krishnaswami wrote:
> In article <459bcb85$0$20812$5fc30a8@news.tiscali.it>, Raff wrote:
I wrote an optimizing compiler from lambda expressions to SK
expressions in Haskell,
available from http://www.cwi.nl/~tromp/cl/cl.html
Here's an example use:
-bash-3.00$ ghci Lambda.lhs
....
*Lambda> let pair = read"^x^y^z z x y" :: Lexp
*Lambda> pair
^x ^y ^z z x y
*Lambda> size pair
19
*Lambda> let skpair = toc pair
*Lambda> :t skpair
skpair :: Cexp
*Lambda> skpair
S (K (S (K (S (K (S (K (S S (K K))) K)) S)) (S (S K K)))) K
*Lambda> size skpair
56
(Sizes are measured as length of binary encodings)
regards,
-John
| |
| Ivan Jager 2007-01-06, 7:20 pm |
| On Wed, 3 Jan 2007, J.ProPasserby@googlemail.com wrote:
> i need a compiler from any functional language to SKI, if who had one,
> let me know,THX.
How about the Lazy K compiler?
http://homepages.cwi.nl/~tromp/cl/lazy-k.html
Ivan
| |
| J.ProPasserby@googlemail.com 2007-01-06, 7:20 pm |
|
"tromp =D0=B4=B5=C0=A3=BA
"
> Neelakantan Krishnaswami wrote:
>
> I wrote an optimizing compiler from lambda expressions to SK
> expressions in Haskell,
> available from http://www.cwi.nl/~tromp/cl/cl.html
i had this one before.it's a nice one,but i also need another one from
one kind of functional language to SK.
also have some Q about this compiler.
which rules are u followed for this compiler from lambda expressions to
SK?
i mean ????? =3D S
????? =3D K
????? =3D I
i'm a beginner of this area.
thanks.
about lazy K read it before~THX.
| |
| J.ProPasserby@googlemail.com 2007-01-06, 7:20 pm |
| > Neelakantan Krishnaswami wrote:
[color=darkred]
> I wrote an optimizing compiler from lambda expressions to SK
> expressions in Haskell,
> available from http://www.cwi.nl/~tromp/cl/cl.html
i had this one before.it's a nice one,but i also need another one from
one kind of functional language to SK.
also have some Q about this compiler.
which rules are u followed for this compiler from lambda expressions to
SK?
i mean ????? = S
????? = K
????? = I
i'm a beginner of this area.
thanks.
about lazy K read it before~THX.
| |
| Holger Siegel 2007-01-06, 7:20 pm |
| J.ProPasserby@googlemail.com <J.ProPasserby@googlemail.com> schrieb:
> i need a compiler from any functional language to SKI, if who had one,
> let me know,THX.
I have written this one some time ago. It is based on the rules given by
S. Peyton Jones in his book "The implementation of functional
programming languages". You can turn off the use of the B and C
combinators by changing 'useBC = True' to 'useBC = False'.
---------
module Ski(Expr(..), compile) where
-- a small functional language
data Expr
= App Expr Expr
| Lambda String Expr
| Var String
| S | K | I
| B -- B x y = (x . y)
| C -- C x y = flip x y
deriving(Show)
-- replace lambda terms with SKI terms
compile :: Expr -> Expr
compile (App e1 e2) = App (compile e1) (compile e2)
compile (Lambda x e) = abstract x (compile e)
compile x = x
abstract x (App f1 f2) = opt (abstract x f1) (abstract x f2)
abstract x (Var x')
| x==x' = I
abstract x y = App K y
useBC = True
opt (App K p) (App K q)
= App K (App p q)
opt (App K p) I
= p
opt (App K p) q
| useBC = App (App B p) q
opt p (App K q)
| useBC = App (App C p) q
opt p q = App (App S p) q
-- an example
y = Lambda "f" (App (Lambda "x" (App x x)) (Lambda "x" (App x x)))
where x = Var "x"
------
Try "compile y" in hugs or ghci.
| |
|
|
J.ProPasserby@googlemail.com wrote:
[color=darkred]
> also have some Q about this compiler.
> which rules are u followed for this compiler from lambda expressions to
>
> SK?
> i mean ????? = S
> ????? = K
> ????? = I
> i'm a beginner of this area.
> thanks.
The 9 rules are listed on page 9 of the accompanying paper
http://www.cwi.nl/~tromp/cl/LC.pdf
I reproduce them here, where [x]M denote bracket abstraction of
variable x from term M:
1. [x](S K M) = S K (for all M)
2. [x]M = K M (x not free in M)
3. [x]x = I
4. [x](M x) = M (x not free in M)
5. [x](x M x) = [x](S S K x M)
6. [x](M (N L)) = [x](S ([x]M) N L) (M,N variable free*)
7. [x]((M N) L) = [x](S M ([x]L) N) (M,L variable free*)
8. [x]((M L) (N L)) = [x](S M N L) (M,N variable free*)
9. [x](M N) = S ([x]M) ([x]N)
*This includes all I-equivalent terms as dealt with in rule 1.
regards,
-John
|
|
|
|
|