From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA01504 for caml-red; Mon, 22 May 2000 18:16:58 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA25635 for ; Mon, 22 May 2000 18:11:06 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e4MGAxD11240; Mon, 22 May 2000 18:10:59 +0200 (MET DST) Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA03408; Mon, 22 May 2000 18:10:59 +0200 (MET DST) From: Pierre Weis Message-Id: <200005221610.SAA03408@pauillac.inria.fr> Subject: Re: reference initialization To: simonpj@microsoft.com (Simon Peyton-Jones) Date: Mon, 22 May 2000 18:10:59 +0200 (MET DST) Cc: caml-list@inria.fr In-Reply-To: <9E6D5163D780C142B2B58107F4E605A9021C994B@red-msg-23.redmond.corp.microsoft.com> from "Simon Peyton-Jones" at mai 20, 2000 01:13:52 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: weis > So array takes an uppper and lower bound, and a list of (index,value) pairs; > it returns an array with each element filled in. The list should mention > each element just once, but that is not statically checked. > > In conjunction with list comprehensions, this gives rise to quite nice code. > For example, to tabulate a function we might write > > array (1,n) [(i, f i) | i <- [1..n]] > > Referring to existing elements is easy via recursion: > > fibs = arrray (1,n) ([(1,1),(2,1)] ++ > [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]]) > > Notice how easily the boundary cases are specified. > > Laziness means that the compiler does not need to figure out which > order to do the initialisation. In a strict language it would be a little > harder -- or perhaps one could say "it's done in the order the index,value > pairs are given". This would be perfectly reasonable. > You may wonder about the efficiency issue. After all, it doesn't seem > great to build an intermediate list just before constructing an array. > But a bit of short-cut deforestation does the trick, and eliminates the > intermediate list. I have to admit that a lot of things have to Work Right > in the compiler to really get the for-loop you intended, but that's what > compilers are for. Wao! You've got a really impressive compiler. > None of this is specific to Haskell or to a lazy language. Caml could > well use it. I mention it on this list becuase it's an aspect of the > Haskell design that I think has worked particularly well, and which > might be of use to Camlers. Oups. I frankly doubt that we can define in Caml something like your fibs: fibs = arrray (1,n) ([(1,1),(2,1)] ++ [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]]) Don't forget our evaluation regime that will try to completely evaluate the list ([(1,1),(2,1)] ++ [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]]) before calling the array creation function. What's the meaning of fibs! then, since fibs has no existance yet ? I think that in these examples, lazy evaluation is important: the list is lazyly evaluated, and the fibs array elements are assigned one at a time, as soon as the corresponding pair of the list has been computed. As far as I can imagine the way vectors are handled in a lazy language, the compiler must ``initialize'' vectors elements with a dummy ``undefined value'', and updates this dummy value as usual as soon as a value is provided for the dummy. This way you always have the ``not yet initialized'' test for free, since attempts to access such an element will raise some ``bottom'' or ``undefined'' exception. However, for the ``completely initialized test'' you also need to access all the elements of the new vector (once more accessing an undefined element will automatically raise an exception). And I suspect also that the ``initialized only once'' check will be tricky... (or similar to an ML solution). So, I don't know how to implement your elegant solution in a strict language (unless by adding some lazy evaluation regime for some functions, such as ... array!) > A lot of the benefit comes from the re-use (for arrays) of the > list comprehension notation. I forget whether Caml has such notation, > but again, it's nothing to do with laziness and it's a notation which > is really useful. Yes this is really a interesting notation. However, I studied it once, and as far as I remember I had the feeling that lazy evaluation was also mandatory to handle ``real'' cases other than the trivial ones (such as. [(i, f i) | i <- [1..n]] that can be easily done in Caml): complex mutually recursive lists, where f and the bounds where functions of other lists given in comprehension. Also, I remember my strange feeling at reading pieces of code like: [i | i <- [1..2**32]] which is not completely reasonable in a strict language. Anyway, you're right that we could may give it a try ... Thank you for your interesting remarks. Pierre Weis INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/