How to translate Haskell to other languages?

11 Oct 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

Jason Dagit

Matthew Naylor

Derek Elkins

Jason Dagit

David Menendez

mail＠justinbogner.com

Matthew

tags

participants (6)