Subtyping

[Marcin 'Qrczak' Kowalczyk]

Sat, 18 Aug 2001 01:05:17 -0700, Ashley Yakeley <ashley@semantic.org> pisze:

> One possible solution would be to extend Haskell with "open"
> algebraic data types.

> This seems to me straightforward, but perhaps not very useful unless
> there's a way of declaring "generic" functions on these types that
> can be extended somehow later:

Indeed.

Later additions to the function would have to be restricted to match
at least one constructor defined in the current module, to make the
combined definition independent of the order of additions - modules
are by nature unordered. And something more - this is not enough for
unambiguous definition:
    -- Base definition
    foo :: SomeObject -> SomeObject -> Int
    foo _ _ = 0
    -- Module 1
    foo (SomeInt a) _ = 1
    -- Module 2
    foo _ (SomeString a) = 2
    -- Which argument is evaluated as the first?
    -- What is called for foo (SomeInt 0) (SomeString "")?

> But would this sort of thing solve your problem?

Yes, although now I think that this use would be equivalent to using
Dynamic, only with a prettier syntax.

There is a particular case which could make use of extensible
functions and can't be simulated with Dynamic, but I would use a
different solution anyway (the same as I would use now with Dynamic)
- for speed. The situation is as follows:

The interpreted language (BTW, designed and implemented purely for
fun, no serious external reason) introduces the concept of type
in the standard library. A type is represented as a symbol (term
without arguments).

Unique symbols are born by calling a builtin function, and obtaining
bindings is generally associated with executing some code (like value
bindings in ML).

How a type is determined:
    - Function is called with a distinguished argument (Type)
      and is supposed to return its type.
    - Terms have types depending on their symbol, looked up in
      a dictionary.
    - Integers and strings have types Integer_t, String_t.

Type are used to look up definitions of generic functions in
dictionaries, usually depending on the first argument. There is
also a dictionary of supertypes, so e.g. equality on Bool_t uses the
implementation of equality on Term_t if not defined directly.

Suppose that arbitrary foreign Haskell objects would be included
in values, wrapped as Dynamic. How to determine the type of such an
object? It's trivial to return a generic Haskell_t, but there is no
way to make further classification otherwise than invoking foreign
functions checking for particular Haskell types in sequence (the
functions would have to be registered somehow).

With open algebraic types it can be done. Just define a generic
function for returning the type, and populate its definition in
modules providing particular foreign object types.

Fortunately it can be done better than both solutions and it's
compatible with Dynamic. Just include a representation of type in
the value, along with Dynamic holding the actual object. Since most
actions on such object would begin with determining its type, it's
good to have it ready instead of looking it up in a dictionary. It
requires foresight that checking types of foreign objects will be
needed, but well, I indeed know now that it's needed.

And it's enough. Since type is used for classification to the
granularity equivalent to Haskell types sitting inside the Dynamic,
further dispatching can be done in the language proper, looking up
the type in dictionaries, as for all its generic functions, and they
will usually assume a concrete Haskell type inside the Dynamic.

It happens that the language uses open algebraic types itself,
only without static typechecking. All algebraic types are open: one
can always register more symbols for a particular type, or produce
functions which return such type for a Type request (it can be
considered lying about their types). But expect that registering
something non-standard as a Bool_t and passing it to functions
expecting a Bool_t will usually surprise these functions and many of
them will refuse to work.

There is a continuum between making new types and using open algebraic
types. Constructors for exceptions are born as other terms with unique
symbols. You can either register them under a generic Exception_t type
or give them new types; it doesn't matter for how they are caught if
all these types use the same generic pattern matching implementation
for Term_t. Either way you can implement patterns which perform
matching in any fancy way (e.g. look up in a hierarchy of exception
symbols they maintain).

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK