<div dir="ltr"><br><br><div class="gmail_quote">On Sat, Oct 11, 2008 at 8:55 AM, Matthew Naylor <span dir="ltr"><<a href="mailto:mfn-haskell-cafe@cs.york.ac.uk" target="_blank">mfn-haskell-cafe@cs.york.ac.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi Jason,<br>
<br>
I don't know Python, but let me share some thoughts that you might<br>
find useful.<br>
<br>
First, a few questions about your manual translations. Are your<br>
functions curried? For example, can I partially apply zipWith? Also,<br>
you put a "thunk" around things like "cons(...)" --- should it not be<br>
the arguments to "cons" that are thunked?</blockquote><div><br>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?<br>
<br>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. <br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Now, on to an automatic translation. As you may know already, Haskell<br>
programs can be transformed to "combinator programs" which are quite<br>
simple and easy to work with. Here is what I mean by a "combinator<br>
program":<br>
<br>
p ::= d* (a program is a list of combinator definitions)<br>
d ::= c v* = e (combinator definition)<br>
e ::= e e (application)<br>
| v (variable/argument)<br>
| c (constant: integer literal, combinator name, etc.)<br>
<br>
As an example of a combinator program, here is one that reverses the<br>
list [0,1,2].<br>
<br>
rev v acc = v acc (rev2 acc)<br>
rev2 acc x xs = rev xs (cons x acc)<br>
cons x xs n c = c x xs<br>
nil n c = n<br>
<br>
main = rev (cons 0 (cons 1 (cons 2 nil))) nil<br>
<br>
This program does not type-check in Haskell! But Python, being<br>
dynamically typed, doesn't suffer from this problem. :-)</blockquote><div><br>I plan to exploit this in my translations as well. I will assume type checked Haskell programs as input to the translator.<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
<br>
A translation scheme, D[], from a combinator definition to a Python<br>
definition might look as follows.<br>
<br>
D[c v* = e] = def c() : return (lambda v1: ... lambda vn: E[e])<br>
E[e0 e1] = E[e0] (E[e1])<br>
E[v] = v<br>
E[c] = c()<br>
<br>
Here is the result of (manually) applying D to the list-reversing program.<br>
</blockquote><div><br>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?<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
def nil() : return (lambda n: lambda c: n)</blockquote><div><br>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?<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
def cons() : return (lambda x: lambda xs: lambda n: lambda c: c(x)(xs))</blockquote><div><br>Now, now this is a getting a bit hard to read :) <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
def rev2() : return (lambda acc: lambda x: lambda xs:<br>
rev()(xs)(cons()(x)(acc)))<br>
def rev() : return (lambda v: lambda acc: v(acc)(rev2()(acc)))<br>
</blockquote><div> <br>I'm glad I don't have to maintain code that looks like this :)<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
def main() : return (rev() (cons()(0)(<br>
cons()(1)(<br>
cons()(2)(<br>
nil()))))(nil()))<br>
<br>
The result of main() is a partially-applied function, which python<br>
won't display. But using the helper<br>
<br>
def list(f) : return (f([])(lambda x: lambda xs: [x] + list(xs)))<br>
<br>
we can see the result of main():<br>
<br>
>>> list(main())<br>
[2, 1, 0]</blockquote><div><br>Cool!<br><br>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.<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
Of course, Python is a strict language, so we have lost Haskell's<br>
non-strictness during the translation. However, there exists a<br>
transformation which, no matter how a combinator program is evaluated<br>
(strictly, non-strictly, or lazily), the result will be just as if it<br>
had been evaluated non-strictly. Let's call it N, for "Non-strict" or<br>
"call-by-Name".</blockquote><div><br>Interesting.<br> <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
<br>
N[e0 e1] = N[e0] (\x. N[e1])<br>
N[v] = v (\x. x)<br>
N[f] = f<br>
<br>
I've cheekily introduced lambdas on the RHS here --- they are not<br>
valid combinator expressions! But since Python supports lambdas, this<br>
is not a big worry.</blockquote><div><br>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).<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
NOTE 1: We can't remove the lambdas above by introducing combinators<br>
because the arguments to the combinator would be evaluated and that<br>
would defeat the purpose of the transformation!</blockquote><div><br>Okay, I get that.<br><br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
NOTE 2: "i" could be replaced with anything above --- it is never<br>
actually inspected.</blockquote><div><br>What "i" are you referring to?<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Now, non-strict evaluation is all very well, but what we really want<br>
is lazy evaluation. Let's take the N transformation, rename it to L<br>
for "Lazy", and indulge in a side-effecting reference, ML style.</blockquote><div><br>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?<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
<br>
L[e0 e1] = L[e0] (let r = ref None in<br>
\x. match !r with<br>
None -> let b = L[e1] in r := Some b ; b<br>
| Some b -> b)<br>
L[v] = v (\x. x)<br>
L[f] = f<br>
<br>
I don't know enough to define L w.r.t Python.<br>
<br>
I haven't tried too hard to fully understand your translation, and<br>
likewise, you may not try to fully understand mine! But I thought I'd<br>
share my view, and hope that it might be useful (and correct!) in some<br>
way.</blockquote><div><br>Thanks!<br><br>Jason<br></div></div><br></div>