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.