[Haskell-cafe] How to translate Haskell to other languages?
Jason Dagit
dagit at codersbase.com
Sat Oct 11 03:58:51 EDT 2008
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081011/4270aa8f/attachment.htm
More information about the Haskell-Cafe
mailing list