On Sat, Oct 11, 2008 at 8:55 AM, Matthew Naylor <mfn-haskell-cafe@cs.york.ac.uk> 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?

I don't recall if I mentioned this in my original email. My goal is to do automatic translations. So, no you can't partially apply zipWith, but then that's because Python doesn't support partial application. On the other hand, you can easily use a lambda to get around this. So in an automatic translation I would replace partial application with lambdas. This shouldn't be a problem right?

My rule was to put a thunk around any "Haskell value". So I put cons cells in thunks and I even wrapped functions in thunks. The exception was that there were quite a few places where I could tell by inspection that a particular value would already be in a thunk. For example, since I require in my translation that putting a value in a cons requires the value to be a thunk then when I pull values out of a cons I already know they are thunks so no need to rewrap them.

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. :-)

I plan to exploit this in my translations as well. I will assume type checked Haskell programs as input to the translator.

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.

If nil() corresponds to [] in Haskell, then how did you arrive at this definition? As Derek Elkins points out your transformation is a CPS based. So I'm going to guess that c is the continuation and n represents the nil?

def nil() : return (lambda n: lambda c: n)

This one makes a little bit of sense to me. I see the components of the list, the x and xs, and you apply the continuation to them. What's going on with n?

def cons() : return (lambda x: lambda xs: lambda n: lambda c: c(x)(xs))

Now, now this is a getting a bit hard to read :)

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)))

I'm glad I don't have to maintain code that looks like this :)

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]

Cool!

So, supposing I went with a translation scheme like what you gave. I think I would end up with deeply nested function calls, this is probably very bad for the python run-time. Also, how do I allow Python to then access the Haskell values? I guess your definition of list above is an example of that, but I'm not sure how I'd pull that off in general.

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".

Interesting.

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.

Right, not so bad. My translation was doing the same thing actually. A common thing to see in my code is, x = thunk(lambda: y).

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!

Okay, I get that.

NOTE 2: "i" could be replaced with anything above --- it is never
actually inspected.

What "i" are you referring to?

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.

Could you explain this a bit more. I don't know ML, so the code is a bit hard for me to read, but also I was wondering why you introduced a side-effecting reference? Is that basically the same as my thunk type?

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.

Thanks!

Jason