Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments

[Thomas Fischbacher <tf@functionality.de>]

Jon Harrop wrote:

> This seems to be something that Lisp uses to allocate data structures on the 
> stack rather than the heap. Why would you want that?

In order to avoid dynamic memory management and get dynamically scoped
pre-allocated "implicit context" buffers to which I can refer as if they
were ordinary variables.

> 
>>let float_factorial =
>>   let _known_factorials = ref [|1.0;1.0;2.0;6.0;24.0;120.0;720.0|] in
>>   (fun n ->
>>     let known_factorials = !_known_factorials in
>>     let nr_known = Array.length known_factorials in
>>     if n < nr_known
>>     then
>>       known_factorials.(n)
>>     else
>>       let new_known_factorials = Array.make (n+1) 0.0 in
>>       begin
>>	for i=0 to nr_known-1 do
>>	  new_known_factorials.(i) <- known_factorials.(i)
>>	done;
>>	(let rec fill f_pos pos =
>>	  if pos > n then ()
>>	  else
>>	    let () = new_known_factorials.(pos) <- f_pos in
>>	    fill (f_pos *. (float_of_int (pos+1))) (pos+1)
>>	in
>>	fill (known_factorials.(nr_known-1)*.(float_of_int nr_known)) nr_known);
>>	_known_factorials := new_known_factorials;
>>	new_known_factorials.(n)
>>       end)
> 
> 
> I can't quite follow that. Is it doing something cleverer than this:
> 
> let float_factorial =
>   let m = ref [||] in
>   fun n ->
>     try (!m).(n) with _ ->
>     let m' = Array.make (n + 1) 1. in
>     for i=1 to n do
>       m'.(i) <- float i *. m'.(i - 1)
>     done;
>     m := m';
>     m'.(n);;

Well, it avoids some of the computations in your example, which re-does
all the array whenever it has to be extended.

>>Other advanced optimization techniques that can be used for benefit
>>in very specialized situations include (explicit) continuation coding:
>>rather than returning a value (e.g. a tuple), you take as an argument
>>a function to which you then pass on your return value(s). This is quite
>>useful whenever "execution flow branches out into multiple paths that
>>have to be taken",
> 
> Are you referring to CPS?

Yes, but not the call/cc implicit CPS, but explicitly passing around
continuations.

>>and may sometimes (though rarely) also be used for 
>>good as a poor man's VALUES/MULTIPLE-VALUE-BIND substitute.
> 
> Weren't values and multiple-value-bind completely superceded by pattern 
> matching?

No. :-) Pattern matching requires constructors, which cons. I am talking
about dynamical memory management avoidance techniques. There are a lot.

-- 
best regards,
Thomas Fischbacher
tf@functionality.de