Re: Compiler translation of array indexing

From: Pierre Weis (Pierre.Weis@inria.fr)
Date: Wed Jan 19 2000 - 23:50:49 MET

  • Next message: Simao Desousa: "Applied Semantics Summer School APPSEM'2000"

    > It's perhaps worth mentioning that one way of achieving
    > this effect is to use type-driven overloading, as Haskell
    > does. One could say
    >
    > class Array a where
    > (.) :: a elt -> Int -> elt
    > ... more operations...
    >
    > (Here 'a' is a type variable ranging over type constructors
    > of kind *->*.)

    Thank you for the interesting information about Haskell.

    As you suggested by your sketch program, the Haskell type classes are
    undoubtedly a powerful and complex mechanism.
    However, it has some strange limitations that always seems extremely
    ``bizarre'' to me: for instance you may think you have a polymorphic
    equality but this polymorphic equality cannot compare two polymorphic
    objects (e.g. [] == [] is ill-typed). Strange, isn't it ?

    For the example we are examining, I'm afraid that once more this
    cannot be handled as desired by the Haskell type classes. In effect,
    what we want in the first place (at least in Caml) is to get rid of
    the two different syntactic notations for string and array accesses
    (When we can do so, we can start to dream to an extension of the
    mechanism to arbitrary vectors like data types).

    Unfortunately, to the best of my knowledge, even if Haskell classes
    can afford a zillion of instances of (.) for fancy vectors data types,
    they just fail to handle the overloading of v.(0) and s.[0]: you
    cannot declare string to belong to the class ``Array'' (since as you
    carefully told us 'a' must have kind *->*, which is not the kind of
    the string data type).

    In the same vein, the next overloading I would want for .() would
    certainly be for associative arrays (or hash tables in the Caml and
    usual terminology). In this case, I want to declare that the (binary)
    data type constructor ('a, 'b) hash_table as a member of the ``Array''
    class. I don't think this is well-kinded.

    Then, the following step would be to use the notation to access in lists.

    To summerize, I really would like to write
     v.(1) instead of Array.get v 1
     s.(1) instead of String.get s 1

    I would consider as an additional benefit of the new type system, if I
    could use:
     t.("ok") instead of Hashtbl.find t "ok",
     l.("ok") instead of List.assoc "ok" l.

    Unfortunately, I don't think that Haskell classes can handle the first
    group, neither the second one; it just allows a strange mixture of the
    two, since only the first and the last example can be declared as
    member of the same class (and this would define list as a member of
    ``Array''!). Strange, isn't it ?

    However, I just read the inference rules of the Haskell class system,
    to figure out how overloading was resolved (tricky isn't it?). So I
    never got an intuition of the class abstraction. So please, correct me
    if I made false inferences about the class system.

    In addition, since you are a true specialist of Haskell type classes,
    may be you could tell us if there is some secret feature that you know
    of in the Haskell type classes system that could elegantly deal with
    these simple, useful, and natural examples ?

    Sincerely,

    Pierre Weis

    INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/



    This archive was generated by hypermail 2b29 : Wed Jan 19 2000 - 23:54:30 MET