Re: reference initialization

[John Max Skaller <skaller@maxtal.com.au>]

Pierre Weis wrote:
 
> You should consider that there is a general initialisation function in
> the Array module, named Array.init, that allocates for you a fresh
> array then fill it with values obtained by calling an arbitrary
> supplied function:
> 
> # Array.init;;
> - : int -> f:(int -> 'a) -> 'a array = <fun>
> 
> Using it, you don't need to bother with any dummy initialization value:
> 
> let combine_arrays a b =
>   let alen = Array.length a in
>   let blen = Array.length b in
>   let init i = if i < alen then a.(i) else b.(i) in
>   Array.init (alen + blen) init
> 
> This code ensures the ``always initialized strategy'' of ML, and seems
> to me elegant and clear (but note that it uses higher-order
> functionality). Have I missed something ?

I think so: the init function is a callback; code which
'naturally' initialises an array by storing into it needs
to be 'control inverted': in general this is very hard,
if not impossible, to do by hand. The general case requires
the client to write an 'interpreter' for the initialisation
algorithm, maintaining state in the callback's closure.

If we consider a simple initialisation like:

	for i=0 to n-1 do x.(i) <- i done

the control inverse is

	fun i -> i

which is simple. However, for more complex algorithms,
such as a sort, this seems non-trivial. For example,
the naive functional solution to fibonacci:

	let rec fib i = match i with 
		| 0 | 1 -> 1 
		| _ -> fib (i-1) + fib (i-2)

works, but is unacceptably inefficient. The actual control
inverse of the usual procedural array initialisation algorithm,
which keeps track of the last two fibonacci numbers, requires
a wrapper function to create the storage in a closure:

	let fib_creator () =
		let a = ref 1 and b = ref 1 in
		let fib i = (* ignore the i *)
			let result = !a + !b in
			b := !a; a := result;
			result
		in fib

Here, fib_creator is a lazy data structure, and fib an iterator
over it. A 'purer' solution could be constructed
using streams I think.

I have written a tool which performs control inversion mechanically,
although in a different context (procedural code 'reading' messages
is control inverted to be event driven). There is some sort of
deep duality theorem here.

But I think the effect is: code which is easy to write procedurally
must be converted to use continuation passing, and that isn't
a trivial task.

[On the other hand, it is usually easy to write a dispatcher for
callback driven code, provided it is the control inverse of
a single thread of control]

So I think you are missing something: iter provides a reasonable
solution for only 'half' of those problems where the callback
driven style is 'natural'. In ocaml, the only way I'm aware of
to encode continuations 'naturally' requires using (hardware
or bytecode) threads.

[BTW: if we had this duality theorem, we would know how to
mix functional and stateful code in the same language seamlessly:
it would seem Charity offers some hints here]

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net