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