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

[Matthew]

Hi Jason,

> So in an automatic translation I would replace partial application
> with lambdas.  This shouldn't be a problem right?

suppose f is a 3-argument function, and you encounter the application
f x.  One possible translation would be to replace f x with

  (\y. \z. f (x,y,z))

I don't know if this is what you mean.  Anyway, the problem is that f
might not be a function name; it could be the argument of a
higher-order function, in which case we don't know how many
lambda-bound variables to introduce.  It's easiest just to define f
as f() = \x. \y. \z. e rather than f (x,y,z) = e, I think.

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

Regarding terminology: be careful not to confuse the CPS
transformation with the transformation that encodes data as functions.
I've made this mistake in the past.  To my knowledge, the "CPS
transformation" refers to the transformation that enforces strict
evaluation in a program.  Encoding data as functions removes data
constructors and case expressions from a program (albeit using
continuations).  I think the latter is known by at least two names:
Scott's encoding, and Berarducci and Bohm's encoding.  It is not the
same as the Church encoding.  I first read about it in a paper by Jan
Martin Jansen.

  Jan Martin Jansen, Pieter Koopman and Rinus Plasmeijer. Efficient
  Interpretation by Transforming Data Types and Patterns to Functions.
  Trends in Functional Programming, Volume 7, Intellect, 2007.

(Googling the title should reveal a PDF.)

But since then, I've noticed the transformation used (anonamously) in
several old texts about compiling functional languages.

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

Converting data to function-encoded data: this can be done with a
fold, e.g. "foldr cons nil" should do the trick for lists.

Converting function-encoded data back to data: it should be possible
to generate a function like my "list(xs)" (which returns a Python
represention of a function-encoded Haskell list xs) for any given data
type.

Alternatively, you could just add constructors and case expressions to
the syntax I gave for "combinator programs", and deal with them
explicitly in the translation.

> >  N[e0 e1]   =   N[e0] (\x. N[e1])
> >  N[v]       =   v (\x. x)
> >  N[f]       =   f
>
> What "i" are you referring to?

Woops, "i" refers to the combinator representing the function \x. x.
(I wrote NOTE 2 before realising NOTE 1!)  Basically, the (\x. x)
above can be replaced with any expression that terminates, but
preferrably one that will be cheap to evaluate.

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

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

Generally: a reference is created for every argument in a
function-call.  The first time that argument is evaluated, the
reference is updated to store the result of the evaluation, so that it
is never performed again.

More specifically:

  * "ref" creates a mutable reference.  In ML, bindings of a let are
    evaluated before the body of the let.

  * !r gets the value at a reference r, and "r := e" updates the
    value at reference r.

  * None and Some are the ML equivalents to Nothing and Just.

  * e0 ; e1 evaluates e0 before e1 and then returns the value of e1.


> Is that basically the same as my thunk type?

I imagine it is very similar to your thunk type, but I don't know
enough Python to say for sure.

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

There are some optimisations to the translation.  For example, if a
function is applied to an argument, and that argument is not
referenced more than once in the body of f, then there is no need to
create a reference for said argument.

Matthew.