Re: reference initialization

From: Pierre Weis (Pierre.Weis@inria.fr)
Date: Mon May 22 2000 - 18:10:59 MET DST

  • Next message: Adnan Agbaria: "Starfish's alpha release"
  • Next message: Richard Samuels: "Exception is not caught by callback3_exn()"

    > 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/



    This archive was generated by hypermail 2b29 : Mon May 22 2000 - 18:18:46 MET DST