Re: reference initialization

From: John Max Skaller (skaller@maxtal.com.au)
Date: Sun May 14 2000 - 16:37:48 MET DST

  • Next message: John Max Skaller: "Re: Suggestion: Print more error messages?"

    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
    



    This archive was generated by hypermail 2b29 : Sun May 14 2000 - 23:23:54 MET DST