Dictionaries are sometimes not necessary

[E.Ireland@massey.ac.nz]

Original-Via: uk.ac.nsf; Fri, 1 Mar 91 04:49:27 GMT
Date: Fri, 1 Mar 91 10:48:57 NZD
From: E.Ireland@massey.ac.nz
To: haskell@edu.yale.cs
Subject: Dictionaries are sometimes not necessary
Sender: haskell-request@cs.glasgow.ac.uk

Hi,

In "A New Approach to the Implementation of Type Classes" , Mark Jones appears
to assume that dictionary-style transformation of Haskell programs is required
in order to implement Haskell type classes.  I thought I should point out that
this is not necessarily so.

I have written a not-yet-full-Haskell compiler which compiles to C through an
intermediate code similar to Luca Cardelli's FAM (Functional Abstract Machine),
but with additional support for lazy evaluation.  My compiler does not
currently implement type classes at all, or even have a type-checker.

The Lazy FAM is a closure based machine, and without transforming the Haskell
program, I can compile each Haskell function (and some suspended expressions)
into a C function.  However, at run-time, functions are always represented by
closures, each closure containing a function pointer and a set of bindings for
that function's free variables.  Anyway, as an example, consider compiling:

    f :: Num a => a -> a -> a
    f x y = (x + y) * (x - y)

We could decide to generate multiple versions of f, one for each member of
class Num.  I imagine that some Haskell compilers will do this for improved
speed in certain cases (such as when a = Int).  However, in general, this
approach will lead to a code generation explosion.

With the Lazy FAM, f will be compiled into a function with three free
variables, namely (+), (*), and (-).  The Lazy FAM startup code will build (at
run-time) closures for all functions at the outermost lexical level, and this
includes a closure for f.  However, we require several versions of f, each with
the appropriate free variables.

My intended approach for compiling type classes is to build a number of
distinct closures for f, all sharing the same compiled function.  The number of
closures will depend on the static structure of the entire Haskell program.
For example, if a program makes use of the (overloaded) equality function on
[Int], [[Char]], and [Integer], I would envisage generating three closures for
the list equality function.

Thus instead of a code generation explosion, I will have a closure building
explosion.  However this seems feasible, since:

(1) The size of a closure is proportional to the number of free variables it
    contains, not the complexity of the function definition.

(2) The explosion occurs once, at the beginning of program execution, and the
    closures are subsequently available for garbage collection (when they are
    no longer referenced, of course).

(3) I don't need to build any dictionaries.

(4) I don't need to do any program transformation - the compiler is simple,
    and a non-transformed program is much easier to debug.

However, please note:

(5) I have not implemented this yet.

If you believe this approach to be unworkable, I would like to know before I
spend months attempting to implement it!

Anyway, I hope that someone finds this useful or interesting.

-------------------------------------------------------------------------------
E.Ireland@massey.ac.nz          Evan Ireland, School of Information Sciences,
  (063) 69-099 x8541          Massey University, Palmerston North, New Zealand.