[Haskell-cafe] How to translate Haskell to other languages?

[Matthew Naylor]

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.