Jason Dagit dagit at codersbase.com
Sat Oct 11 03:58:51 EDT 2008

Hello,

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'''
self.tail = tail
'''Unpack the cons cell'''
def uncons(self):

def htail(t):
'''This function works like Haskell's tail function.'''
l = t.value()
x, xs = l.uncons()
return xs

def plus(t1, t2):
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...