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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
