This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Re: reference initialization
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2000-05-14 (21:20) From: John Max Skaller Subject: Re: reference initialization
```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

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

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