Hi Jason, I don't know Python, but let me share some thoughts that you might find useful. First, a few questions about your manual translations. Are your functions curried? For example, can I partially apply zipWith? Also, you put a "thunk" around things like "cons(...)" --- should it not be the arguments to "cons" that are thunked? Now, on to an automatic translation. As you may know already, Haskell programs can be transformed to "combinator programs" which are quite simple and easy to work with. Here is what I mean by a "combinator program": p ::= d* (a program is a list of combinator definitions) d ::= c v* = e (combinator definition) e ::= e e (application) | v (variable/argument) | c (constant: integer literal, combinator name, etc.) As an example of a combinator program, here is one that reverses the list [0,1,2]. rev v acc = v acc (rev2 acc) rev2 acc x xs = rev xs (cons x acc) cons x xs n c = c x xs nil n c = n main = rev (cons 0 (cons 1 (cons 2 nil))) nil This program does not type-check in Haskell! But Python, being dynamically typed, doesn't suffer from this problem. :-) 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.