Re: Caml wish list

From: Pierre Weis (Pierre.Weis@inria.fr)
Date: Tue Apr 25 2000 - 20:16:24 MET DST

  • Next message: Brian Rogoff: "Polymorphic variants question"

    > Well, I can't remember offhand how SMJ/NJ handles overloading, but it
    > seems to work reasonably well. On the other hand, I am nowadays a
    > convert to ocaml's hard line on overloading---it's an absolute curse
    > of many, many C++ programs by coders whose enthusiasm outruns their
    > judgement.

    We think many Caml users feel that using different addition function
    (+) and (+.) for integers and floats is a safe way of programming, but
    really frustrating at the same time.

    So do we. Therefore we are currently in the effort of adding some kind
    of limited overloading to Caml. This is not a trivial problem, if you
    want something really good both at the expressiveness and the
    efficiency levels.

          * * *

    As you mentioned, SML provides a set of overloaded functions such as
    (+), but it is quite limited. In addition, for the sake of efficiency
    and simplicity of the typing and compilation schemes, the overloaded
    functions in SML have a restricted ``functional'' status: you cannot
    abstract pieces of code containing overloaded operators. Hence, you
    cannot define derived overloaded functions using already existing
    overloaded functions.

    A simple example that novice SML users often encounter is the double
    function using overloaded (+):

    # let double = fun x -> x + x;;

    In SML, this double function is not an overloaded function for
    integers and floats, because the type of (+) must always be statically
    deduced from the context, which is impossible here. This definition is
    just either rejected (SML '90), or resolved using a default type
    assignment for overloaded symbols (SML '97): then (+) is typed as its
    default type int -> int -> int, and consequently double gets type int
    -> int.

    This way, the compiler always has the precise type of use for each
    occurrence of (+). Therefore occurrences of (+) can be replaced by
    the corresponding primitives, for example:

            # 1 + 2 ====> add_int 1 2
            # 1.0 + 2.0 ====> add_float 1.0 2.0
            # fun x -> x + x ====> fun x -> add_int x x

    Therefore overloaded functions are just "typeful macros" in SML.

    We think this is one reasonable solution, since the users will feel
    much less frustration than using the separated functions (+) and (+.),
    and the compilation for these overloaded functions is straightforward
    and has no run time overhead.

          * * *

    However, we are not promoting this simple overloading facility,
    because we think the ``abstraction restriction'' to be unnatural in a
    functional setting: even if the definition of new overloaded symbols
    is prohibited, the abstraction over overloaded operators (as in double
    above) should be possible in higher-order functional languages like
    SML or Caml!

    Our "extensional polymorphism" framework is a bit more complicated
    than the ``default assigment'' static scheme, but it provides
    abstraction and "real" overloaded functions. (By the way, we call
    those "generic" functions.) Using extensional polymorphism, the double
    function is polymorphic, being defined for ``any argument whose type
    is suitable for (+)''. Thus, you can use it for integers and floats!

    # let double = fun x -> x + x;;
    val double : $a -> $a = <fun>

    # double 1;;
    - : int = 2

    # double 3.14;;
    - : float = 6.28

    We use special type variables $a, $b, ..., called dynamic type
    variables, to denote type parameters abstracted into type schemes for
    polymorphic generic functions. In the definition of double, the
    context of (+) is left unresolved, and double becomes polymorphic. The
    compilation of double abstracts the type context for the internal (+),
    and dynamically passes it to (+) to select the appropriate addition
    primitive.

    You may worry about efficient compilation of this feature, since, as
    examplify by the double generic function, some information from the
    typing context has to be passed at run time, and hence double involves
    an extra argument (a type) to be provided to (+) at run time, and also
    an additional pattern matching selection to apply the proper addition
    primitive; undoubtedly, the generic double function is a bit slower
    than its direct non-overloaded counterpart definitions for integers
    and floats, like

    # let double_int x = x + x;;
    # let double_float x = x +. x;;

    However, writing those two definitions means twice more code, hence
    twice more possibilities of bugs, twice more maintenance, and twice
    more identifiers to remember. This simplification is worth a slight
    efficiency loss ...

    Note also that usual simple overloading of operators is still as
    efficient as it can be, since static type annotations allow the
    inlining of the corresponding primitives, at least for the predefined
    set of usual arithmetic operators (+, -, *, ...).

    Polymorphic uses of overloaded operators in generic functions need an
    extra type book keeping for dynamic resolution, but there is no
    possible efficiency comparison with other compilation schemes, since
    these functions are completely new in ML and cannot be expressed
    neither in SML nor in Caml.

    As a side effect of the extensional polymorphism discipline, we
    manipulate types at run time, and this provides various benefits and
    new features to the lasnguage:

            * safe value I/O (persistent value I/O between different
              programs, or safe usage of input_value/output_value),
            * dynamic values,
            * some limited polymorphic print facility,
            * a new kind of computation mixing types and values ...

    The current prototype is an extension of the 2.04 version of Objective
    Caml; we are planning to release it when it will be fully stable, like
    the label extension in 2.99. We don't know yet which version of
    Objective Caml it will be 3.0, 3.x or 3.99...

    Hope this helps,

    Jun Furuse & Pierre Weis



    This archive was generated by hypermail 2b29 : Tue Apr 25 2000 - 20:23:05 MET DST