[Haskell-cafe] decoupling type classes

[Yin Wang]

Hi all,

I have an idea about type classes that I have been experimenting. It
appears to be a generalization to Haskell’s type classes and seems to
be doable. It seems to related the three ideas: type classes, implicit
parameters, and (typed) dynamic scoping. But I don't know whether it
is good or not. I hope to get some opinions before going further.

Basically, Haskell’s type classes passes dictionaries around. Each
dictionary contains one or more “methods”. When “names” which belong
to a dictionary are called, we invoke functions that match its
principle type in the call site's scope.

I have an experimental system which “decouples” the dictionary.
Instead of passing on a dictionary, it passes individual “implicit
parameters" around. Those implicit parameters are type inferenced and
they can contain type parameters just as methods in a type class.
Similarly, they are resolved by their types in the call site's scope.

The convenience of this approach compared to Haskell’s type classes is
that we no longer require a user of a type class to define ALL the
methods in a type class. For example, a user could just define a
method + without defining other methods in the Num class: -, *, … He
can use the method + independently. For example, if + is defined on
the String type to be concatenation, we can use + in another function:

weirdConcat x y = x + y + y

This has a utility, because the methods in the Num class don’t “make
sense” for Strings except +, but the current type class design
requires us to define them. Note here that weirdConcat will not have
the type (Num a) => a -> a -> a, since we no longer have the Num
class, it is decoupled into separate methods.

There is another benefit of this decoupling: it can subsume the
functionality of MPTC. Because the methods are no longer grouped,
there is no “common” type parameter to the methods. Thus we can easily
have more than one parameter in the individual methods and
conveniently use them as MPTC methods.



SOME IMPLEMENTATION DETAILS

Here is how it can be implemented. When we see an “undefined” variable
in a function definition which has been declared as “overloaded
function”, we store the function name, and the type variables that are
associated with it. For example,

overload g — (explicitly declare g as an overloaded function)

f x y (String s) = …
…
let z = g x s y in
…
…

We don’t know what x and y are, but we know from the body of f that
their types satisfy this pattern: g ’a String ’b. Thus we store this
pattern constraint as an extra (implicit) argument in the type of f:

f :: a → b → String (exist g: g a String b)

We may have multiple such arguments.

At the call sites of f, we look for a function g in the scope that
satisfies the pattern g ‘a String ’b, but we don’t pass on the
substitution, so they remain polymorphic. Once found, the function is
passed as an extra parameter to f. This is essentially dictionary
passing, but without grouping. It can be also more efficient because
the parameters may be stored in registers.

Here g is explicitly declared as “overloaded”, although my
experimental system doesn’t need this. Any undefined variable inside
function body automatically becomes overloaded. This may cause
unintended overloading and it catches bugs late. That’s why we need
the “overload” declarations.

But the automatic overloading of the undefined may be useful in
certain situations. For example, if we are going to use Haskell as a
shell language. Every “command” must be evaluated when we type them.
If we have mutually recursive definitions, the shell will report
“undefined variables” either way we order the functions. The automatic
overloading may solve this problem. The undefined variables will
temporarily exist as automatic overloaded functions. Once we actually
define a function with the same name AND satisfies the type
constraints, they become implicit parameters to the function we
defined before. If we call a function whose implicit parameters are
not associated, the shell reports error very similar to Haskell’s
“type a is not of class Num …”


RELATIONSHIP TO DYNAMIC SCOPING

It seems to be helpful to think of the “method calls” as referencing
dynamically scoped variables. They are dispatched depending on the
bindings we have in the call site's scope (and not the scope where the
method is defined!). So it is very much similar to the much-hated
dynamic scoping. But the dispatching is more disciplined — it doesn't
just match the name. It must match both the name and the inferred
principle type.

This intuition also explains why local instances shouldn't be allowed,
because if we capture the variables at the definition site, the method
call becomes "statically scoped".



-- yin