ML module system (vs Haskell type classes) -long- 
Author Message
 ML module system (vs Haskell type classes) -long-

This brief note compares the capabilities of Haskell's type classes
with those of the Standard ML module system, in response to John
Peterson's query in comp.lang.functional.  It is addressed to those
who have at least a rudimentary acquaintance with SML modules and
Haskell type classes.

Parametric modules in SML (functors) and Haskell type classes were
both devised to deal with a need not met by classical parametric
polymorphism: to wit, the need to parameterize not only with respect to
a type, but with respect to a type accompanied by a set of associated
functions to operate on, or "interpret" that type.  In SML, types and
functions can be combined in a "structure" or basic module, while in
Haskell this is done by defining a class instance.  Haskell classes
in their most elementary form correspond roughly to SML signatures.

Haskell's type classes handle parameterization and instantiation
implicitly as an extension of the classic Hindley-Milner polymorphic
type inference system.  SML expresses the parameterization explicitly
through the definition and application of functors.  Technically, the
module system represents an enrichment of the basic polymorphic type
system with dependent sums and products obeying a phase distinction
(see various POPL papers (86,88,89)).

These two approaches to enriching parameterization are not equivalent,
and some of the differences are discussed in the following points.

(1) n-ary type constructors

One limitation of Haskell's type classes is that parameterization is
only allowed over simple types (i.e. 0-ary type constructors like
int).  Generalizations to n-ary type constructors (n>0) like list
have been proposed by Paul Hudak and Mark Jones, but they further
complicate the type class system.  SML functors handle n-ary type
constructors for any n in a uniform manor.

(2) multiple type constructors

Type classes do not allow one to parameterize with respect to a set of
several related type constructors and their interpreting functions
(e.g. vector spaces with scalars and vectors, abstract syntax with
declaration and expression types, graphs with nodes and edges).
Functors handle this with no difficulty.

(3) single instance per type

Type classes key instances to the instance type, so one can have only
one instance of a class for a given type (e.g. int as an ordered
type).  In the SML module system, you can have as many structures
as you like of a given signature with the same type(s) (e.g. several
different ORDER structures interpreting int as an ordered type with
different orderings).

(4) visibility of type parameter

Implicit instantiation of type classes requires that the type variable
ranging over the type class appear explicitly in the type of any
function parameterized with respect to the class.  This is not the
case for SML functors.  In fact, in many of the most important uses of
functors the parameter structure is used only internally to implement
the result structure, and none of its types are inherited by the
result.  This kind of parameterization is of great utility but cannot
be expressed naturally by type classes.

(5) Granularity of parameterization

There is a basic methodological or stylistic difference between SML
modules and Haskell type classes relating to the "granularity" of
parameterization.  Experience with Standard ML has shown that is it is
natural and useful to express parameterization at the module level,
where an entire complex of types and functions can be expressed
relative to a parameter structure.  The "burden" of explicit
instantiation through functor application is minimal because it is
amortized over a whole family of definitions.  This approach also
supports a natural functional style for composing program components
(see the example below).

Haskell, on the other hand, parameterizes individual functions, and
depends on type inference to perform instantiation.  This seems like
an elegant solution, but the cost in generality is illustrated above.
The type class construct clearly does not provide all the
functionality of a parametric module system, but if one were to add a
parametric module system to Haskell there would be a good deal of
overlap between the type class feature and parametric modules.  The
interaction between type classes and parametric modules would also
have to be dealt with (e.g. how would one write a specification for a
type class in a module signature).

I'll briefly mention some other features of the module system that go
beyond the capabilities of type classes.

* nesting: structures (and functors) can be nested within one
  another, providing a rudimentary form of inheritance.

* subtyping: coercive signature matching provides a simple but very
  important form of subtyping at the module level.

* higher-order modules: functors can be passed as parameters and
  returned by functors, giving useful additional functionality.

In addition, I would argue that the semantics of SML modules is
probably simpler than that of type classes, and it is easier to
implement them efficiently.  In terms of complexity of static
elaboration, they are probably roughly comparable.

Example:  The following module in the SML/NJ compiler hints at the
capabilities of the module system (src/sparc/sparcglue.sml).  It defines
one of several "instantiations" of the compiler for different
target architectures.

(* sparcglue.sml
 *
 * Copyright 1989 by AT&T Bell Laboratories
 *
 * AUTHOR:  John Reppy
 *          Cornell University
 *          Ithaca, NY 14853

 *)

structure SparcMC : CODEGENERATOR =
struct
    structure SparcC = Coder(structure M = SparcInstr and E = SparcMCEmit)
    structure MachGen = CPScomp(SparcCM(structure C = SparcC))
    fun generate lexp = (
          MachGen.compile lexp;
          SparcC.finish();
          SparcMCode.getCodeString())
end

structure SparcAC : ASSEMBLER =
struct
    structure SparcC = Coder(structure M = SparcInstr and E = SparcAsEmit)
    structure AssemGen = CPScomp(SparcCM(structure C = SparcC))
    fun generate (lexp, stream) = (
          SparcAsCode.outfile := stream;
          AssemGen.compile lexp;
          SparcC.finish())
end

structure IntSparc = IntShare(structure Machm = SparcMC
                              val fileExtension = ".sparc"
                              functor De{*filter*} = BogusDe{*filter*}
                                  )

structure IntSparcD = IntShare(structure Machm = SparcMC
                               val fileExtension = ".sparc"
                               functor De{*filter*} = RealDe{*filter*}
                                   )

structure CompSparc = Batch(structure M=SparcMC and A=SparcAC)

--
Dave MacQueen

Room 2A-431, AT&T Bell Labs, 600 Mountain Ave, Murray Hill, NJ 07974



Sun, 20 Aug 1995 23:01:40 GMT  
 ML module system (vs Haskell type classes) -long-

Quote:
MacQueen) writes:

| This brief note compares the capabilities of Haskell's type classes
| with those of the Standard ML module system

I'm glad that this topic has been brought up here; I'm sure the
discussion is long overdue and recent messages on comp.lang.functional
confirm this.

I'm sorry that this is so long, but there is a lot to reply to...

Before I get into the real issues, let me start with some examples to
illustrate why so many people have been tempted to make comparisons
between Standard ML modules and Haskell type classes.  As you'll see
a little later, I think you have to be very careful to compare the
right things ...

SOME EXAMPLES:
--------------
Looking at the following examples, it's easy to see some kind of
underlying correspondence between the two systems.  These definitions
might be used to describe equality.  I will write the Haskell code
on the right and the `corresponding' SML on the left.  To start with,
the similarity between Haskell class declarations and SML signature
declarations is quite striking:

 signature EQ =
  sig
   type t                               class EQ t where
   val  eq : t * t -> bool               eq :: (t,t) -> Bool
  end;

In addition, Haskell instance declarations look rather like SML
structure definitions:

 structure EqInt : EQ =
  struct
   type t  = int                        instance EQ Int where
   val  eq = (op =):int*int->bool        eq (x,y) = primEqInt x y
  end;

or, more generally, when a context is required for a Haskell instance
declaration, an SML functor definition:

 functor EqList(Eq : EQ) : EQ =
  struct
   type t  =  Eq.t list                 instance EQ a => EQ [a] where
   fun  eq ([],[]) = true                eq ([],[])  = True
   |    eq ((x::xs),(y::ys))             eq (x:xs,y:ys)
             = Eq.eq (x,y)                          = eq (x,y)
               andalso eq (xs,ys)                     && eq (xs,ys)
   |    eq _ = false;                    eq _        = False
  end;

I don't think there is any need to go into examples to show how
much more can be done with ML modules which go beyond the power of
Haskell type classes.  Standard textbooks (e.g. ML for the working
programmer) and the source for well-known programs including SML/NJ
(such as the excerpt that Dave MacQueen included in his posting)
give many examples which illustrate this better than I can here.

I will briefly describe one example in which the facilities of the
Haskell type class system seem (IMHO) to be more convenient.  Suppose
that we want to define a function to test for membership in a list
based on the equality test `eq' described above.  In Haskell, this
can be implemented using a top-level definition, in SML a functor
definition is needed to capture the dependency on the equality that
is used:

 functor Member(Eq : EQ) =
   struct
    fun member (x,[])  = false          member (x,[])   = False
    |   member (x,y::ys)                member (x,y:ys)
          = Eq.eq (x,y)                           = eq (x,y)
            orelse member (x,ys)                    || member (x,ys)
   end;

Now suppose you want to test for membership of a given list in a list
of lists of integers.  In Haskell we can write:

  member ([1,2], [[1], [2,3], [3,4,5]])

In SML we have to build the appropriate structures and then extract
the equality function from that:

  structure eqListInt = EqList(EqInt);
  structure memberListInt = Member(eqListInt);
  memberListInt.member ([1,2], [[1], [2,3], [3,4,5]]);

The first two lines here are the equivalent of building dictionaries
which happens automatically in the Haskell version.  The fact that
the Haskell system is not as sophisticated as the ML module system
makes this possible.

WHY MIGHT YOU MIGHT WANT TO ADD HASKELL STYLE TYPE CLASSES TO SML?
------------------------------------------------------------------
The treatment of polymorphic equality has long been acknowledged as
one of the weaker aspects of SML.  Haskell's system of type classes
provide a solution to this, something that many Haskell users have
come to appreciate.  Furthermore, type classes also provide a more
general treatment for the overloading of numeric operations.  The
fact that this all supported within the same framework, controlled
by the programmer, is certainly attractive.  As the original paper
claimed, type classes are a way of making ad-hoc polymorphism
less ad-hoc.

The fact that Haskell type classes (without any of the extensions
that have been proposed (and often implemented) since their
introduction) do not support:

   (1) n-ary type constructors
   (2) multiple type constructors
   (3) multiple instances per type
   (4) visibility of type parameter
   (5) Certain granularities of parameterization
   (6) Nesting
   (7) Coercive subtyping
   (8) Higher order modules

(i.e. the points mentioned in Dave MacQueen's message) are not really
important since these features are not needed to deal with the kinds
of applications for which type classes are intended.

WHY MIGHT YOU WANT TO ADD SML STYLE MODULES TO HASKELL?
-------------------------------------------------------
The module system in the current version of Haskell is one of the
weakest parts of the language.  I have a great admiration for the
SML module system and feel that Haskell could benefit substantially
from a similar system.  I am sure that there are many other people
in the Haskell community who would agree with this.
(`I come, not to criticise SML modules, but to praise them' :)

As the examples at the beginning of this message indicate and as
Dave MacQueen mentions in his posting, there is a definite overlap
between the two systems.  We need to get a better understanding of
this before we can hope to find a satisfactory solution which
combine both in a single language.  Reading Dave MacQueen's message,
I get the impression that he does not think that such a solution
can be found; for example we do not currently know how a type class
might be specified in a module signature.  For my part, I hope that
a good solution can be found.  I also do not know whether it is
possible, but the idea of a language which supports both type
classes and and parametric modules in an elegant and consistent
fashion is sufficiently appealing to warrant further investigation.
And even if we ultimately find that there is no solution, we will
have learnt a lot along the way.

TYPE CLASSES AS AN ALTERNATIVE TO ML MODULES?
ML MODULES AS AN ALTERNATIVE TO TYPE CLASSES?
---------------------------------------------
No, absolutely not.  It's true that there is something similar in the
motivation for two systems:

| Parametric modules in SML (functors) and Haskell type classes were
| both devised to deal with a need not met by classical parametric
| polymorphism: to wit, the need to parameterize not only with respect to
| a type, but with respect to a type accompanied by a set of associated
| functions to operate on, or "interpret" that type.

Both systems are intended to deal with a need not meet by parametric
polymorphism.  But the `need' is different in each case.  They are,
in effect, solutions to different problems.

Parameterization is certainly a common ground between the two, but
David goes on to explain where the difference lies:

| Haskell's type classes handle parameterization and instantiation
| implicitly as an extension of the classic Hindley-Milner polymorphic
| type inference system.  SML expresses the parameterization explicitly
| through the definition and application of functors.

Implicit versus explicit.  That is the key difference.  Pretty much
anything that can be done in an implicit manner can also be done
in an explicit manner.  After all, the implicit version is usually
just thought of as a convenient shorthand for the explicit version.
It is the degree of convenience provided that makes the implicit
version worth considering.

MISCELLANEOUS REMARKS:
----------------------
| One limitation of Haskell's type classes is that parameterization is
| only allowed over simple types (i.e. 0-ary type constructors like
| int).  Generalizations to n-ary type constructors (n>0) like list
| have been proposed by Paul Hudak and Mark Jones, but they further
| complicate the type class system.  SML functors handle n-ary type
| constructors for any n in a uniform manor.

One could argue that some of the extensions proposed actually reduce
complexity by eliminating special cases and ad-hoc restrictions.
You refer to some of my work here.  IMO, this is certainly true for
some of the extensions which I have investigated (and that you refer
to here), both from a theoretical and implementation standpoint.

| In addition, I would argue that the semantics of SML modules is
| probably simpler than that of type classes, and it is easier to
| implement them efficiently.  In terms of complexity of static
| elaboration, they are probably roughly comparable.

The examples that I started this message with illustrate a translation
from a language with type classes to a language with SML modules.
In my opinion, it should be possible to construct an implementation
of type classes in this way by automating the translation.  Although
I have not actually done this, it is actually very close to the way
that the current version of Gofer works, so this is more than just a
vague notion.  (Of course, I'm ignoring the strict/non-strict distinction
between the two languages.)  On that assumption, type classes can be
implemented just as efficiently as the `corresponding' SML version.
(On the other hand, since the target of the translation is not the
full SML module language, it may even be possible to get a more
efficient implementation because you don't have to support the full
generality which that requires.)

THE BOTTOM LINE:
----------------
Type classes are no substitute for parametric modules.  They're
not intended to be.  But they do offer a
...

read more »



Mon, 21 Aug 1995 06:46:58 GMT  
 ML module system (vs Haskell type classes) -long-
Zhong Shao asks:

|  (1) How hard it is for a normal programmer to get a clear understanding
|      of type classes, say, at least being able to understand type errors,
|      and knowing how to infer the type of a function by hand so that you
|      can write the module interfaces?

It would be interesting to ask that question to Haskell programmers at large.
Here, of course, is our opportunity!  My experience (with other people, not
myself) is that, if type classes are introduced as a standard part of the
type system, then most people don't have any more problems coming to grips
with them than they do with polymorphism.

[Once or twice I've talked to people that have had problems with the Text
class in Haskell ... but never because of the use of type classes.  Instead,
the problems have been caused by misunderstandings about the continuation
passing style used to define printing functions.  What I'm saying is that
if we're going to talk about problems people have had with `type classes',
let's make sure that really is what we are talking about.]

You can probably get some kind of feeling for your question my considering
how you would answer the same question about equality types in SML.  Except
that, a Haskell programmer may well be more familiar with type classes
because they are used on a more regular basis, not just when equality is
involved.

|  (2) Is it really worth adding the extra complexity of the type classes to
|      the ML type system? Besides from the polymorphic equality function
|      and those numerical overloading operators (+,-,*,/ etc.), (these are
|      precisely what's overloaded in SML now)   can any Haskell people show
|      us some very useful type classes that seems very awkward to be
|      implemented in the SML module system?

I guess the examples with the EQ class in my last posting didn't seem very
awkward to you?  Fair enough; judgements like that are subjective and
opinions will always differ.  I have some Gofer scripts that make quite
heavy use of overloading and I'd be happy to give you copies so that you can
do the translation and make comparisons yourself.  The translations are
certainly possible and you may decide that you prefer to program in that
style.  Lots of Haskell programmers would disagree but there's no right or
wrong here.

|      In other words, would "SML module system + polymorphic equality +
|      simple overloading numerical operators"  be enough to deal
|      successfully with most practical "type-class" based programs ?

I have here a fairly large Haskell program (13,000 lines or so).  It doesn't
really do anything fancy with type classes; no new classes are defined in
the program, it just uses what Haskell already provides.  In case it matters,
I didn't write the code.  It turns out that this program actually uses five
different Haskell classes:

    Eq     (equality)
    Ord    (ordering)
    Num    (simple arithmetic)
    Text   (textual display and formatting)
    Enum   (enumeration)

The program doesn't have anything to do with floating point so it doesn't use
any of the classes provided for more sophisticated numeric work.  It also
doesn't involve reading or writing from binary files so the Bin class isn't
involved and it doesn't use arrays so the Ix class isn't used.

You could add each of these to your proposed system as further special cases
but of course, that won't make it any prettier.  A single and general
extension which provides all of these as special cases seems more
attractive to me.  In addition, it has the advantage the user is also able
to add new classes as an application requires, rather than being restricted
to some fixed set.  If you're wondering whether there are ever any cases
where the ability to define a new class outside those provided by the
prelude is actually useful, you might like to take a look at my paper,
recently published in JFP, which does just this for a class of lattices.

|      ML functor differs from most other parametric modules (such as Ada  
|      generics) in that its implementation is shared by all of its
|      instances.

In most implementations of Haskell, the `implementation' of a parametric
module that you refer to corresponds to a `dictionary value'.  In Gofer,
any dictionary value is shared by all of its instances, the same
property that you have stated here.  In some particular implementations
of Haskell it may be true that there are physically distinct implementations
of the same dictionary, but they are always guaranteed to be semantically
equivalent, so I doubt that this would cause any significant problems.

|      This requires that the formal argument interface (signature) of the
|      functor has to have a unique meaning at compile time (called
|      "principal signatures", just like the "most general types" in ML
|      type system) so that the compiler can actually generate the correct
|      code for it.

There is a similar motivation in Haskell; you need to know what the
structure of a dictionary looks like if you are actually going to try and
take anything out of that dictionary.

|      It is very difficult to prove the existence of "principal signatures"
|      if type classes are added into the module interface.

First of all, the meaning of a class declaration is fixed; the uniqueness
property you require should hold for class declarations.  It is the meaning
of the member functions for different instances of a class that vary.

A second point to make is that I wouldn't want to suggest that you simply
bolt type classes on top of the module system in the way that talk about
including class declarations in interfaces suggests.  There is enough of
an overlap to make a less dramatic (and more elegant) extension seem
possible.

All the best,
Mark



Tue, 22 Aug 1995 07:17:46 GMT  
 ML module system (vs Haskell type classes) -long-

Quote:

> WHY MIGHT YOU MIGHT WANT TO ADD HASKELL STYLE TYPE CLASSES TO SML?
> ------------------------------------------------------------------
> The treatment of polymorphic equality has long been acknowledged as
> one of the weaker aspects of SML.  Haskell's system of type classes
> provide a solution to this, something that many Haskell users have
> come to appreciate.  Furthermore, type classes also provide a more
> general treatment for the overloading of numeric operations.  The
> fact that this all supported within the same framework, controlled
> by the programmer, is certainly attractive.  As the original paper
> claimed, type classes are a way of making ad-hoc polymorphism
> less ad-hoc.

(I am just adding one more well-known argument commonly used in the ML
 community on why one might NOT want to add type classes into SML)

I agree that the system of type classes provides a better solution to
polymorphic equality than "equality type variables" in SML. But as far
as I know, many ML programmers complain about ML "equality type variables"
not because they are too ad-hoc, but because they complicate the originally
quite simple Hindley-Milner type system (same for ML "weak type variables"
which Haskell people doesn't have to bother :-).

Adding the type classes into SML will complicate the core language type
system even further. And a more complicated type system seems not to be
very compatible with the usual philosophy of modular programming (thus
the SML module system). I cite the following paragraph from Xavier Leroy's
Ph.D thesis that is precisely made for this point:

       Programming in a typed language requires the programmer to have a
       good understanding of the type system: to write type declarations
       in the source code; to understand the type errors reported by the
       compiler; finally, to write type specifications in module
       interfaces. This argument favors type systems that are as simple
       as possible. .... (more on this on pages 146-147 of the thesis)

So naturally, one might like to ask the following questions:

(1) How hard it is for a normal programmer to get a clear understanding
    of type classes, say, at least being able to understand type errors,
    and knowing how to infer the type of a function by hand so that you
    can write the module interfaces?

(2) Is it really worth adding the extra complexity of the type classes to
    the ML type system? Besides from the polymorphic equality function
    and those numerical overloading operators (+,-,*,/ etc.), (these are
    precisely what's overloaded in SML now)   can any Haskell people show
    us some very useful type classes that seems very awkward to be
    implemented in the SML module system?

    In other words, would "SML module system + polymorphic equality +
    simple overloading numerical operators"  be enough to deal successfully
    with most practical "type-class" based programs ?

Quote:
> WHY MIGHT YOU WANT TO ADD SML STYLE MODULES TO HASKELL?
> -------------------------------------------------------

> .......................................................
> a good solution can be found.  I also do not know whether it is
> possible, but the idea of a language which supports both type
> classes and and parametric modules in an elegant and consistent
> fashion is sufficiently appealing to warrant further investigation.

As Dave MacQueen mentioned in his comments, adding ML modules to Haskell
with type classes will make many features (that both have) redundant. Also,
type classes poses great difficulties in making the ML kinds of parametrized
modules (functors) work:

    ML functor differs from most other parametric modules (such as Ada  
    generics) in that its implementation is shared by all of its instances.
    This requires that the formal argument interface (signature) of the
    functor has to have a unique meaning at compile time (called "principal
    signatures", just like the "most general types" in ML type system)
    so that the compiler can actually generate the correct code for it.
    It is very difficult to prove the existence of "principal signatures"
    if type classes are added into the module interface.
    (I am not saying it's impossible, but you can get an idea of this by
     taking a look at the proof for the existance of "principal signatures"
     for SML in Mads Tofte's Ph.D thesis, his recent paper on higher-order
     functors (in POPL92), or the book "Commentary of Standard ML".)  



Mon, 21 Aug 1995 14:10:56 GMT  
 ML module system (vs Haskell type classes) -long-
Zhong Shao:
  So naturally, one might like to ask the following questions:

  (1) How hard it is for a normal programmer to get a clear understanding
      of type classes, say, at least being able to understand type errors,
      and knowing how to infer the type of a function by hand so that you
      can write the module interfaces?

  (2) Is it really worth adding the extra complexity of the type classes to
      the ML type system? Besides from the polymorphic equality function
      and those numerical overloading operators (+,-,*,/ etc.), (these are
      precisely what's overloaded in SML now)   can any Haskell people show
      us some very useful type classes that seems very awkward to be
      implemented in the SML module system?

To many outside the ML community its type system seems complex and
hard to understand.  However, the ML type system can be explained in
very simple terms and once you get the hang of it everything seems
obvious.  Having implemented type classes, I would assert that type
classes are only a slight complication to the basic ML style type
system.  If type classes are properly presented and compilers provide
good error messages then understanding type classes is really no
harder than understanding the basic ML type system.  Remember that
type classes have not been around for long and mature implementations
of type classes have only recently become availble.  Very little
material has been written explaining type classes in a tutorial manner.

So to answer the questions:

(1) Probably not that hard.

(2) Possibly yes.  Exactly how type classes and modules would interact
    is still unknown.  However, it is interesting to note that the
    main uses of type classes in Haskell, numeric overloading,
    equality and comparison operations, and I/O operations all
    correspond to aspects of ML not normally addressed by the module
    system.  This seems to suggest that there is room to clean up ML
    using type classes.

I certainly would not suggest that type classes can replace the ML
module system.  However, type classes have a certain convenience that
is not provided by the module system.  The construction and
propagation of the dictionaries which implement the class system is
completely hidden from the user while the module system requires more
explicit user control.  This extra control may make modules much more
expressive but also harder to use.

I won't take this debate any further since I'm no expert on the ML
module system.  Maybe some others in the Haskell community can give
some good examples of things that are more natural using type classes
than the ML module system.

  John Peterson
  Yale Haskell Project



Tue, 22 Aug 1995 00:31:04 GMT  
 ML module system (vs Haskell type classes) -long-

An interesting reply to

Quote:

>| This brief note compares the capabilities of Haskell's type classes
>| with those of the Standard ML module system

In particular, I thought Mark P. Jones' point about implicit vs
explicit was worth making (and repeating :-)

Quote:
>Implicit versus explicit.  That is the key difference.  Pretty much
>anything that can be done in an implicit manner can also be done
>in an explicit manner.  After all, the implicit version is usually
>just thought of as a convenient shorthand for the explicit version.
>It is the degree of convenience provided that makes the implicit
>version worth considering.

I would disagree with Mark P. Jones' claim that:

Quote:
>The fact that Haskell type classes (without any of the extensions
>that have been proposed (and often implemented) since their
>introduction) do not support:
>   (1) n-ary type constructors
>   (2) multiple type constructors
>   (3) multiple instances per type
>   (4) visibility of type parameter
>   (5) Certain granularities of parameterization
>   (6) Nesting
>   (7) Coercive subtyping
>   (8) Higher order modules
>(i.e. the points mentioned in Dave MacQueen's message) are not really
>important since these features are not needed to deal with the kinds
>of applications for which type classes are intended.

I think handling (some of?) these is important since it makes programs
easier to write and I think we should explore what it is unreasonable/
impossible to extend type classes to handle so that we can judge what
making structures/ dictionaries explicit buys us.

In his posting, Dave MacQueen included an example which illustrates
the use of (I think) (3) and (4). I wasn't aware of any other features
and would be interested in seeing an example which demonstrated their
use.

My attempt at translating the Standard ML example into Haskell Type
Classes is given at the end of this message.

Problems encountered (first four not module related):

1) I've had to guess the signatures of Coder, CPScomp, SparcCM and
   SparcMCode and probably guessed incorrectly. (Subtext: the small
   amount of extra text is due to adding (the equivalent of)
   signatures and this would have been much simpler if the example
   included appropriate signatures.)

2) I've ignored the file-handling in SparcAC (and other things which look
   as though they involve side-effects) since, if I put that in, I'd use
   monads and I want to stick to discussing modules without getting onto
   monads.

3) I (unrealistically?) assumed the de{*filter*} to consist of a single
   function - again, more information about this module is required.

4) Coder seems to use two parameters - I wasn't clear what they were
   or whether they would always match so I simplified.

5) I had to explicitly type part of the definition of compileSparc to get
   round problem (4) (visibility of type parameter). This is quite
   straightforward.

6) I had to introduce two types (Sparc and SparcD) to get round
   problem (3) (single instance per type). This is a bit unpleasant
   but may be reasonable in the context (ie it might fit well with
   other bits of the compiler.)

7) I'm uncertain how the function "CODEGENERATOR.generate" can access
   the current instance of "fileExtension" - since fileExtension's
   type does not mention the type variable "machine" (ie problem (4)
   (visibility of type parameter)). This could be "fixed" by giving
   fileExtension a bogus parameter which did mention "machine" or
   (tidier?) by an extension that allowed explicit reference
   to the current instance.

With the possible exception of the last two points, I think this was
quite straightforward.

I'd welcome bug reports, corrections, improvements, discussion, etc.

I'd also be interested to see examples that demonstrated the other
differences between ML-modules and Type Classes and, in particular,
sharing!

Alastair Reid

class Coder machine where
    finish :: Assembler machine -> Assembler machine

class CM machine => CPScomp machine where
    compile :: Core -> Assembler machine
    compile = {- probably a default definition here? -}

class CodeStrings machine where
    getCodeString :: Assembler machine -> String

class (Coder machine,
       CodeStrings machine,
       CPScomp machine) => CODEGENERATOR machine where
    fileExtension :: String
    de{*filter*} :: ???
    generate :: Core -> Assembler machine
    generate = getCodeString . finish . compile

instance CODEGENERATOR Sparc where
    fileExtension = ".sparc"
    de{*filter*} = BogusDe{*filter*}

instance CODEGENERATOR SparcD where
    fileExtension = ".sparc"
    de{*filter*} = RealDe{*filter*}

class (Coder machine, CPScomp machine) =>  ASSEMBLER machine where
    generate :: Code machine -> String
    generate = finish . compile

compileSparc :: String -> String
compileSparc = (generate :: Code Sparc -> String) . generate

--
Alastair Reid, Computing Science Department, Glasgow University, rm G091,
17 Lilybank Gardens, Glasgow G12 8QQ, SCOTLAND. Work:no phone;home:041 334 3048



Tue, 22 Aug 1995 19:31:55 GMT  
 ML module system (vs Haskell type classes) -long-

Quote:
> Zhong Shao asks:
> |  (1) How hard it is for a normal programmer to get a clear understanding
> |      of type classes, say, at least being able to understand type errors,
> |      and knowing how to infer the type of a function by hand so that you
> |      can write the module interfaces?

> It would be interesting to ask that question to Haskell programmers at large.
> Here, of course, is our opportunity!  My experience (with other people, not

Even with little experience writing in SML (i've only written a
2500 line compiler), the type system seems simple and obvious.  I
do not think that adding type classes would make the type system
significantly more difficult to understand.  On the contrary, while i
was learning the language, one of the most confusing aspects was the
inconsistancy in which functions were overloaded.  I knew the
arithmetic functions (+,-,* and /) somehow could handle multiple types
so i assumed this was done in a general way.  I was disappointed when
i found there was no general mechanism.

I have always wondered if and when SML would support Haskell style
type classes.  In fact, if SML had type classes, i would be even more
convinced that SML is the C of the future.  I would be tempted to
try to use it for all my work - hoping that someday garbage collection
would be an insignificant performance cost.  :)


                \(o/



Tue, 22 Aug 1995 23:49:48 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Haskell type classes vs Ocaml modules

2. Conflict Between Class-as-Module and Class-as-Type (long)

3. Standard ML modules and the Axiom type system

4. Haskell vs ML (or O'Caml)

5. ML Vs Haskell

6. Erlang vs ml, haskell

7. Haskell vs ML

8. Haskell classes and overloading (long)

9. OCaml module type repetition in mli and ml files

10. ML module system

11. Haskell - Question about multi-parameter type classes

12. Haskell type classes, adding extra constraints

 

 
Powered by phpBB® Forum Software