Re: reference initialization

Pierre Weis
 Hongwei Xi
 John Max Skaller
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20000514 (21:20) 
From:  John Max Skaller <skaller@m...> 
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 higherorder > 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 n1 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 nontrivial. For example, the naive functional solution to fibonacci: let rec fib i = match i with  0  1 > 1  _ > fib (i1) + fib (i2) 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: 61296600850 checkout Vyper http://Vyper.sourceforge.net download Interscript http://Interscript.sourceforge.net