On Sat, 2008-10-11 at 16:55 +0100, Matthew Naylor wrote:
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.
This is indeed a CPS transform. Specifically, a call-by-value CPS transform. There is also a call-by-name one. N[e0 e1] = \k. N[e0] (\f. f N[e1] k) N[v] = v N[c] = \k. k c