From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: Resource control (was: Re: Why curry?)
Date: 14 Oct 92 23:59:41 GMT
	<TMB.92Oct12210548@arolla.idiap.ch> <1992Oct13.105748.29860@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 13 Oct 92 10:57:48 GMT

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

   |> What I'm saying is that most people who know SML reasonably well
   |> understand clearly how I want my computation to be carried out when I
   |> write something like:
   |> 
   |>    fun f(x) =
   |>        let
   |>    	   val z = g(x)
   |>        in
   |>            fn y => h(y,z)
   |>        end
   |>    
   |>    fun f'(x) = fn y => h(y,g(x))
   |> 
   |> In the first case, I don't want "g(x)" to be recomputed, in the second
   |> case I do want it recomputed. It seems that this is annotation enough.
   |> Why invent a new notation? 

   [...]

   Regarding the example itself, I suppose that the reason for you to 
   sometimes want to recompute "g(x)" is that it has some side effect
   that should occur? In a pure language, you don't need to care about
   how many times an expression is evaluated, at least not for program
   correctness. So the first version is always better in this case.

No, that's not the reason. I want that control even in a purely
functional language. My programs not only have to be correct, they
also have to fit into a real machine. There is some overhead that I am
willing to pay for the convenience of using a functional programming
language (like SML), and there is some overhead that I can't afford to
pay.

The reason why I may want to have "g(x)" recomputed is because its
result occupies memory. Now, if I happen to be tight on memory, I may
prefer the value to be recomputed rather than saved.

   Incidentally, here is how you'd write the first version in Haskell
   if your compiler implements fully lazy lambda lifting:

      f x y = h y (g x)

   The fully lazy lambda lifter would then transform this to something
   like the following:

      f x = f' (g x)

      f' z y = h y z

   Then if you wanted to compute "map (f 17) xs", the "(f 17)" application
   would be shared and as soon as it was used for the first time, it would
   be rewritten to "(f' (g 17))" where "g 17" would also be shared and
   therefore evaluated at most once.

Good for it. But I don't always want that to happen. If you try to
deal with 20M of data on a 64M machine, issues like what gets saved
and what gets recomputed become important.

You might say: "well, we only cache intermediate results like 'g(x)',
but if we run out of memory, we flush them". The problem is that that
will most likely also flush the few precious intermediate results that
I know I want to keep.

   Well, this was a bit of a sidetrack ... what I thought about was rather
   annotations that would express the desired order of evaluation, more 
   like writing "f (after (g x))" to indicate that "g x" should be
   completely evaluated before "f" was called. Now, in this case "after"
   is almost a hyperstrictness annotation, the difference being that it 
   forced the compiler to use this schedule, wheras a hyperstrictness
   annotation allowed the compiler to do as it thought best. Still other
   annotations could be used to indicate the order of evaluation of various
   subexpressions.

Well, if you come up with an efficient, lazy version of SML that has
such annotations, I'll be happy to give it a try. For the time being,
I don't find expressing my algorithms in an eager language to be a
significant bother, and in terms of performance (as a few experiments
with available lazy functional languages have convinced me), I don't
have any choice.

					Thomas.
Newsgroups: comp.lang.functional