From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: Why curry? (Re: Why functional languages?)
Date: 7 Oct 92 22:18:35 GMT
	<TMB.92Oct4181821@arolla.idiap.ch> <1992Oct6.141724.29356@kth.se>
Reply-To: tmb@idiap.ch
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
In-reply-to: kff@dentex.tds.kth.se's message of 6 Oct 92 14:17:24 GMT

In article <1992Oct6.141724.29356@kth.se> kff@dentex.tds.kth.se (Karl-Filip Faxen) writes:

   In article <TMB.92Oct4181821@arolla.idiap.ch>, tmb@arolla.idiap.ch (Thomas M. Br
   euel) writes:
   |> 
   |> Why _do_ people continue to use curried syntax when they just want a
   |> function with several arguments? It's difficult to optimize for the
   |> compiler, 

   That is not correct (and I should know, I'm writing a Haskell 
   compiler :-). First, it is not particularly difficult to generate
   good code for calls to curried functions (that is, functions with
   types like (a -> b -> c -> d -> e)). Every function is represented
   as a lambda-expression (e.g. (\x.\y.\z. e)), and in a compiled graph
   reduction implementation (e.g. the G machine and its derivates) the
   number of nested lambda bindings around the body of the function 
   (3 in this case) gives the precise number of arguments that the 
   compiled code for the function needs to in order to execute (partial
   applications are represented as a thunk (or closure) containing a 
   pointer to the code of the supercombinator and a list of the (still 
   to few) arguments it has been applied to).

(Please note that I said "difficult", not "impossible", and that I
gave a benchmark. Current compilers apparently have difficulties with
optimizing currying well, and here are the reasons...)

That doesn't seem to be an acceptable strategy for compiling code
for eager evaluation:

	fun f x = let val z = g(x) in fn y => h(x,z) end

Now, I certainly want computation of "z" to happen and complete before
all the arguments to "f" are available (in fact, not having this
control over evaluation and resources is precisely why I don't like
lazy evaluation).

To a degree, the same argument applies even if there is no overt
computation like "g". Consider:

	val make_opaque : ('a -> 'b) -> ('a,'b) opaque
	val apply_opaque : ('a,'b) opaque * 'a -> 'b

	fun p x y = ...
	fun q x = make_opaque(fn y => ...)

By your rules, you will generate entry points for "p" with two
arguments and for "q" with one argument. That means that calls with
the number of arguments you expect like "p 1 2" and "q 1" will be
faster than calls like "p 1" and "apply_opaque(q 1,2)".

   Now, if we have a simple, first order function application (where
   the applied function is a known supercombinator) we can look up the
   number of outermost lambdas, check if the function is applied with
   the right number of arguments and call an entrypoint that uses some
   efficient calling convention.

I see. So you are saying that several entrypoints need to be
generated. That was my point: you either pay space (plus a little
time), or you pay time.

   Thus the curried style of function definition carries no additional
   cost in itself; it is calling "unknown" functions that cost, and that
   cost is regardless of the syntax used when defining the function.

Note that, as far as I can tell, unless you duplicate the code for the
function completely for each possible entrypoint, even if you generate
different entrypoints for the same function, you still pay some
overhead in jumps and some register space for state. The reason is
that different entrypoints have different results.

   Second, the tupling style also needs to be optimized, or you have to
   allocate the tuples explicitly in the heap and then explicitly
   destructure them immediately afterwards. This can of course be done,
   but it is not any simpler than the above mentioned optimization for 
   curried functions (I think :-).

Of course. But the difference is that for tupled functions there is a
constant number (2) of possible entry points (one for a "tuple" arg,
and one for a "destructured tuple" arg (*)), and that the return value
does not depend on which of the two entry points you choose.

   |> it gives uninformative type signatures (is "'a -> 'a -> 'a"
   |> intended to be a function of one argument returning a function, or is
   |> it intended to be a function of two arguments returning a "'a"?),

   It is both.

Well, that's like saying that "lists" and "arrays" are the same.  Why
not use such a nice type system if you have it?

   You are free to apply it to two arguments to get a "'a" in 
   one place and apply it to one argument and get a function with type 
   "'a -> 'a" that you e.g. map over a "'a list" in another place. I do
   these things all the time.

Sure, I also do these things "all the time", but only with a very
small fraction of my functions. Those functions, I do curry (those
functions also tend to be local and hence inlinable). Note also that
those functions will not receive a complete set of arguments when they
are called.

				Thomas.

(*) Yes, arguments can be more complex than that and require more
destructuring. However, that is true for both curried and tupled
syntax. What we are comparing here is "f(a,b,c)" vs "f a b c".

Newsgroups: comp.lang.functional