English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
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-22 (16:16)
From: Pierre Weis <Pierre.Weis@i...>
Subject: Re: reference initialization
> 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/