11 Oct 09:55
How to translate Haskell to other languages?
From: Jason Dagit <dagit <at> codersbase.com>
Subject: How to translate Haskell to other languages?
Newsgroups: gmane.comp.lang.haskell.cafe
Date: 2008-10-11 07:58:51 GMT
Subject: How to translate Haskell to other languages?
Newsgroups: gmane.comp.lang.haskell.cafe
Date: 2008-10-11 07:58:51 GMT
Hello,
I was thinking about translating Haskell to other languages, python being the main one at the moment.
Here is my attempt at manually encoding Haskell in Python:
\begin{code}
import types
class thunk:
'''Thunks allow us to delay a computation and they also store their
value inside themselves once they have been accessed.'''
def __init__(self, v):
self.v = v
def value(self):
'''Force the thunk to be calculated by referencing it.'''
while self.isReducible():
self.reduce()
return self.v
def reduce(self):
'''Reduces the thunk, by either calling the represented function
or reducing the layers of thunk.'''
if (type(self.v) == types.FunctionType):
self.v = self.v()
else:
self.v = self.v.value()
return self.v
def isReducible(self):
'''Returns True when the thunk is still callable.'''
return isinstance(self.v, thunk) or \
type(self.v) == types.FunctionType
class nil:
'''Empty list element'''
def __init__(self):
pass
class cons:
'''Non-empty lists'''
def __init__(self, head, tail):
self.head = head
self.tail = tail
'''Unpack the cons cell'''
def uncons(self):
return self.head, self.tail
def htail(t):
'''This function works like Haskell's tail function.'''
l = t.value()
x, xs = l.uncons()
return xs
def plus(t1, t2):
'''Adds numbers'''
i1 = t1.value()
i2 = t2.value()
return thunk(i1+i2)
def zipWith(f, t1, t2):
'''This is like Haskell's zipWith function.'''
l1 = t1.value()
if isinstance(l1, nil): return thunk(nil())
l2 = t2.value()
if isinstance(l2, nil): return thunk(nil())
x, xs = l1.uncons()
y, ys = l2.uncons()
zw = thunk(lambda: zipWith(f, xs, ys))
fxy = thunk(lambda: f(x,y))
return thunk(cons(fxy, zw))
def fibs():
'''This is the classic fibs:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)'''
f1 = thunk(1)
f2 = thunk(1)
fn = thunk(fibs)
rest = thunk(lambda: zipWith(plus, fn, htail(fn)))
restlist = thunk(cons(f2, rest))
fiblist = thunk(cons(f1, restlist))
return fiblist
def hmap(f, t):
'''map _ [] = []
map f (x:xs) = f x : map f xs'''
l = t.value()
if isinstance(l, nil): return thunk(nil())
x, xs = l.uncons()
fx = thunk(lambda: f(x))
mapfxs = thunk(lambda: hmap(f, xs))
return thunk(cons(fx, mapfxs))
def show(t):
'''show :: a -> String'''
v = t.value()
return thunk(str(v))
def printList(t):
'''This just gives us a way to debug lists.'''
v = t.value()
print "[",
while True:
h,t = v.uncons()
print "%s" % h.value(),
if isinstance(t.value(), nil): break
else: print ", ",
v = t.value()
print "]"
def take(tn, tl):
'''take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs'''
n = tn.value()
if n <= 0: return thunk(nil())
l = tl.value()
if isinstance(l, nil): return thunk(nil())
x,xs = l.uncons()
nminusone = thunk(lambda: plus(tn, thunk(-1)))
takerec = thunk(lambda: take(nminusone, xs))
return thunk(cons(x, takerec))
\end{code}
You can try this out in python with:
tenfibs = take(thunk(10), fibs())
printList(tenfibs)
This will print the first 10 fibs.
Questions:
I think the examples above are correctly lazy. Have I missed something?
I noticed my thunks can get wrapped in each other, is this to be expected, or am I doing it wrong?
Is there an easier encoding using generators? When I started I was using generators instead of thunk, but I found it was complicating my design so I removed it. And yet, since generators are python's version of thunks, it seems like there should be a more natural encoding there.
I'm not explicitly using a graph reduction algorithm to reach WHNF, does this mean my translation is wrong?
Are there some well known test cases I should try? Anyone know of a paper that discusses making this translation?
I am trying to avoid writing an interpreter in Python for Haskell. My goal is to translate Haskell functions into the equivalent Python. I'm also hoping to avoid needing a G-machine.
Thanks!
Jason
I was thinking about translating Haskell to other languages, python being the main one at the moment.
Here is my attempt at manually encoding Haskell in Python:
\begin{code}
import types
class thunk:
'''Thunks allow us to delay a computation and they also store their
value inside themselves once they have been accessed.'''
def __init__(self, v):
self.v = v
def value(self):
'''Force the thunk to be calculated by referencing it.'''
while self.isReducible():
self.reduce()
return self.v
def reduce(self):
'''Reduces the thunk, by either calling the represented function
or reducing the layers of thunk.'''
if (type(self.v) == types.FunctionType):
self.v = self.v()
else:
self.v = self.v.value()
return self.v
def isReducible(self):
'''Returns True when the thunk is still callable.'''
return isinstance(self.v, thunk) or \
type(self.v) == types.FunctionType
class nil:
'''Empty list element'''
def __init__(self):
pass
class cons:
'''Non-empty lists'''
def __init__(self, head, tail):
self.head = head
self.tail = tail
'''Unpack the cons cell'''
def uncons(self):
return self.head, self.tail
def htail(t):
'''This function works like Haskell's tail function.'''
l = t.value()
x, xs = l.uncons()
return xs
def plus(t1, t2):
'''Adds numbers'''
i1 = t1.value()
i2 = t2.value()
return thunk(i1+i2)
def zipWith(f, t1, t2):
'''This is like Haskell's zipWith function.'''
l1 = t1.value()
if isinstance(l1, nil): return thunk(nil())
l2 = t2.value()
if isinstance(l2, nil): return thunk(nil())
x, xs = l1.uncons()
y, ys = l2.uncons()
zw = thunk(lambda: zipWith(f, xs, ys))
fxy = thunk(lambda: f(x,y))
return thunk(cons(fxy, zw))
def fibs():
'''This is the classic fibs:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)'''
f1 = thunk(1)
f2 = thunk(1)
fn = thunk(fibs)
rest = thunk(lambda: zipWith(plus, fn, htail(fn)))
restlist = thunk(cons(f2, rest))
fiblist = thunk(cons(f1, restlist))
return fiblist
def hmap(f, t):
'''map _ [] = []
map f (x:xs) = f x : map f xs'''
l = t.value()
if isinstance(l, nil): return thunk(nil())
x, xs = l.uncons()
fx = thunk(lambda: f(x))
mapfxs = thunk(lambda: hmap(f, xs))
return thunk(cons(fx, mapfxs))
def show(t):
'''show :: a -> String'''
v = t.value()
return thunk(str(v))
def printList(t):
'''This just gives us a way to debug lists.'''
v = t.value()
print "[",
while True:
h,t = v.uncons()
print "%s" % h.value(),
if isinstance(t.value(), nil): break
else: print ", ",
v = t.value()
print "]"
def take(tn, tl):
'''take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs'''
n = tn.value()
if n <= 0: return thunk(nil())
l = tl.value()
if isinstance(l, nil): return thunk(nil())
x,xs = l.uncons()
nminusone = thunk(lambda: plus(tn, thunk(-1)))
takerec = thunk(lambda: take(nminusone, xs))
return thunk(cons(x, takerec))
\end{code}
You can try this out in python with:
tenfibs = take(thunk(10), fibs())
printList(tenfibs)
This will print the first 10 fibs.
Questions:
I think the examples above are correctly lazy. Have I missed something?
I noticed my thunks can get wrapped in each other, is this to be expected, or am I doing it wrong?
Is there an easier encoding using generators? When I started I was using generators instead of thunk, but I found it was complicating my design so I removed it. And yet, since generators are python's version of thunks, it seems like there should be a more natural encoding there.
I'm not explicitly using a graph reduction algorithm to reach WHNF, does this mean my translation is wrong?
Are there some well known test cases I should try? Anyone know of a paper that discusses making this translation?
I am trying to avoid writing an interpreter in Python for Haskell. My goal is to translate Haskell functions into the equivalent Python. I'm also hoping to avoid needing a G-machine.
Thanks!
Jason
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
A translation scheme, D[], from a combinator definition to a Python
definition might look as follows.
D[c v* = e] = def c() : return (lambda v1: ... lambda vn: E[e])
E[e0 e1] = E[e0] (E[e1])
E[v] = v
E[c] = c()
Here is the result of (manually) applying D to the list-reversing program.
def nil() : return (lambda n: lambda c: n)
def cons() : return (lambda x: lambda xs: lambda n: lambda c: c(x)(xs))
def rev2() : return (lambda acc: lambda x: lambda xs:
rev()(xs)(cons()(x)(acc)))
def rev() : return (lambda v: lambda acc: v(acc)(rev2()(acc)))
def main() : return (rev() (cons()(0)(
cons()(1)(
cons()(2)(
nil()))))(nil()))
The result of main() is a partially-applied function, which python
won't display. But using the helper
def list(f) : return (f([])(lambda x: lambda xs: [x] + list(xs)))
we can see the result of main():
>>> list(main())
[2, 1, 0]
Of course, Python is a strict language, so we have lost Haskell's
non-strictness during the translation. However, there exists a
transformation which, no matter how a combinator program is evaluated
(strictly, non-strictly, or lazily), the result will be just as if it
had been evaluated non-strictly. Let's call it N, for "Non-strict" or
"call-by-Name".
N[e0 e1] = N[e0] (\x. N[e1])
N[v] = v (\x. x)
N[f] = f
I've cheekily introduced lambdas on the RHS here --- they are not
valid combinator expressions! But since Python supports lambdas, this
is not a big worry.
NOTE 1: We can't remove the lambdas above by introducing combinators
because the arguments to the combinator would be evaluated and that
would defeat the purpose of the transformation!
NOTE 2: "i" could be replaced with anything above --- it is never
actually inspected.
For the sake of interest, there is also a "dual" transformation which
gives a program that enforces strict evaluation, no matter how it is
evaluated. Let's call it S for "Strict".
S[e0 e1] = \k. S[e0] (\f. S[e1] (\x. k (f x)))
S[v] = \k. k v
S[f] = \k. k f
I believe this is commonly referred to as the CPS
(continuation-passing style) transformation.
Now, non-strict evaluation is all very well, but what we really want
is lazy evaluation. Let's take the N transformation, rename it to L
for "Lazy", and indulge in a side-effecting reference, ML style.
L[e0 e1] = L[e0] (let r = ref None in
\x. match !r with
None -> let b = L[e1] in r := Some b ; b
| Some b -> b)
L[v] = v (\x. x)
L[f] = f
I don't know enough to define L w.r.t Python.
I haven't tried too hard to fully understand your translation, and
likewise, you may not try to fully understand mine! But I thought I'd
share my view, and hope that it might be useful (and correct!) in some
way.
Matthew.
RSS Feed