## Type classes in a dynamic language

Hello,
I wanted to discuss my take on a "type class" concept in a dynamically typed language. The language is called Ela (http://elalang.net) and for now it lacks any way to provide a function overloading. The language itself has Haskell/ML style syntax (layout based), is strict by default (lazy by demand), it is also pure and dynamically typed. I was playing with an idea of overloading for quite some time but didn't actually come to a good solution.

So another attempt.

First of all it is quite different from regular type classes as soon as it relies on a dynamic, not static dispatch. Also it is just single dispatch for now (which somewhat logical as soon as all functions are curried).

The preview version (link below) contains three new entities. The first is a 'type' entity that creates a user type:

type user x = User x


This declaration is basically a function (and is first class therefore). The right hand can contain any expression. Here a variant (aka polymorphic variant) tag is used which simply "wraps" a given value. Variant is helpful as soon as it can be used to "unwrap" the value like so:

let (User x) = ...


The second is a 'class' entity, which is defined like so:

class Foo
foo bar


(This syntax is probably a bit clumsy).
Ela requires that all "class members" are functions, signature is not required as soon as they are untyped. Basically a declaration like the one above creates two global functions 'foo' and 'bar' (classes are mostly ignored by the run-time). These two functions are quite different from regular functions as soon as they are organized as "vocabularies", type-indexed functions.

Having a class and a type one can create an instance of a class for a type like so:

instance Foo user
where foo (User x) = "Foo:" ++ show x
et bar (User x) = "Bar:" ++ show x


An instance adds these functions to the previously defined vocabularies.

These vocabularies are basically mutable objects however all instances are always executed before any user code. When implementing an instance it is required to provide an implementation for all functions in a class. It is not possible to override an existing instance (it is not a problem technically however I am not sure that this is a good feature). And of course it is possible to define instances for built-in types (such as int, double, string, list, etc.). "Class functions" also can't be shadowed by other bindings (Ela does support shadowing for regular bindings).

What do you think about such an approach?

There is a preview for this implementation. It only comes with prelude that defines several classes/instances for built-ins and other basic functions (such as composition, application operators, etc.) and REPL. Requires Mono 2.6+/.NET 2.0+, 1MB:
http://elalang.googlecode.com/files/ela-0.11-preview.zip

BTW. There's a short language reference and a side-by-side comparison with Haskell if you're interested:
http://code.google.com/p/elalang/w/list

## Comment viewing options

### Not seeing much motive...

Type classes in Haskell offer several advantages that you probably cannot pursue in a dynamic language:

1. Ability to select a method based on the result type (by inference or annotation).
2. Ability to treat typeclasses much like types, i.e. generic programming or existentials.
3. Ability to statically guard against ambiguous instances.

Ela at least avoids some of the dynamic-typing problems you might otherwise face (implicit coercion, inheritance).

But it seems to me that you don't really benefit much from the typeclass packaging (unless your goal is to ... statically ... ensure certain functions are defined together?) I'd suggest just overloading functions with pattern matching (like your let example) at arbitrary points in the toplevel. The idea is "open functions", not typeclasses.

### Actually Ela has open

Actually Ela has open functions defined like so:

let extends (Foo x) + (Foo y) = x+y


There are a couple of problems with them. First each definition like the one above rebinds a new function to the same name. This is obviously a problem because if you reference two modules and each of these modules extends a prelude function you will only see the function from the last referenced module.
Even if we solve this problem - there is another. Match clauses are processed in order. So if somebody would define another "extends" like so:

let extends x + (Foo y) = x+y


a previous definition would never be called.
And finally this is an uncontrolled way of overloading. For example somebody may decide to overload just division operator and give it a completely different meaning. Having a class Num controls this to some extent.

And when you actually try to think how to resolve all these issues you come to ... well, type classes.

The main benefit of type classes is closely related to user defined types. Basically they allow you to write polymorphic code - e.g. you can implement your own container and all functions like fold, map, flter, etc. would be able to work with it if you provide a specific instance. Without it you cant even compare non-standard type using standard equality operator.

Or another example - chars in Ela cannot be used in ranges. However this can be "fixed" by providing an instance of Num and Ord for a char.

It seems like quite a serious benefit. Without it if I define a user type - say datetime - i wouldn't be able to use merely all previously defined functions, e.g. no show, no read, filtering wouldn't work for a list of datetime's, etc.

In fact I *didn't* want to add type classes - at least because they do complicate the language which is not my intent - but i don't really see any other way to achieve the same result at the moment.

### Typeclass Issues

if you reference two modules and each of these modules extends a prelude function you will only see the function from the last referenced module

But you'll have this same problem with typeclasses - i.e. two different modules M1 and M2 independently decide they need a Foo class for a given type Bar, and a client inherits both M1 and M2 so now you have two Foo Bar instances in scope.

In Haskell this is a known concern with what Haskellers call "orphan instances". The usual answer is "don't do that." And, most of the time, that's a fine answer.

if somebody would define another "extends" like so:

let extends x + (Foo y) = x+y 

a previous definition would never be called.

Maybe, but you'll face similar issues with typeclasses. In this case there are two related issues - multi-parameter type classes, and overlapping instances. MPTCs are pretty much indispensable - I find it hard to work without them. Overlapping instances mostly indicate design error.

Without it if I define a user type - say datetime - i wouldn't be able to use merely all previously defined functions, e.g. no show, no read, filtering wouldn't work for a list of datetime's, etc.

It isn't as though typeclasses save you from defining things. Perhaps you want to automatically derive most functions? (cf. GeneralizedNewtypeDeriving extension for Haskell.)

### But you'll have this same

But you'll have this same problem with typeclasses - i.e. two different modules M1 and M2 independently decide they need a Foo class for a given type Bar, and a client inherits both M1 and M2 so now you have two Foo Bar instances in scope.

No, that is a different problem. I can easily have two modules that define different instances of the same class - and that was impossible to achieve with "extends". If we have two instances for the same class the current approach is to reject such a program.

Maybe, but you'll face similar issues with typeclasses. In this case there are two related issues - multi-parameter type classes, and overlapping instances. MPTCs are pretty much indispensable - I find it hard to work without them. Overlapping instances mostly indicate design error.

I will face a similar issue only if I add a support for multi dispatch. With the current approach it is not a problem. Previously I tried a more classical approach to overloading - there is even a post somewhere here - and it was powerful, but... i wasn't always sure by myself which function is going to be called.
However you are right and it is a serious limitation. I would probably need to decide if it is worth to add multi dispath again. But with the current approach I do process classes and instances in compile time and the most straightfroward solution might be just to reject a program with overlapping instances.

It isn't as though typeclasses save you from defining things. Perhaps you want to automatically derive most functions? (cf. GeneralizedNewtypeDeriving extension for Haskell.)

That is a "nice to have" thing but this is not what I am talking about. Yes, you will still have to implement all the equality functions, ord functions, etc. for your type - but now you can write polymorphic code that can compare any types, fold any container, etc.
Previously it was only possible by explicitly providing a comparison, etc. function as a parameter which is not very convinient.

Let's say that I have 50+ functions that work with a container. I can write my own container type and use all of these functions with my container. That was the goal actually - to simplify writing polymorphic code.

### Scope of definitions

I see - it's because your let extends structure is constrained by lexical scope that you feel you need a typeclass notion that is more globally accessible so functions can accept types that aren't visible in lexical scope.

Fixing your let extends into a more useful open functions model would solve the same problems as your proposed typeclasses.

### Yes. Actually this approach

Yes. Actually this approach to a type class is a result of thinking how to "fix" "let extends" functions.

A naive take on globally accessible "let extends" == multi methods. And as a result you have a global state that is mutating as long as your program runs. Which is not a good thing I believe.

It can be solved with static resolution through.

So "let extends" + globally accessible + static resolution + avoid overlapping + organize functions in meaningful groups (e.g. Eq, Ord, Num, etc.) == what I have at the moment.

### I've just realized that I

I've just realized that I have completely overlooked Clojure. It provides a support for so called protocols which are completely equal to my prototype implementation - including single first argument dispatch, dispatch only by type tags, no inheritance, etc.

The funny thing that it was introduced in a language as a sort of a replacement for multi methods.

### Associating Values with Types

Oleg Kiselyov describes in Implicit Configurations a more dynamically scoped approach to associating values with types - essentially creating "local" typeclasses.

I've also pursued a solution to configurations, precise resource acquisition, and dependency injection for complex Haskell values - leveraging Haskell's own dynamic types. The idea is injection of values and volatile resources (like threads, connections, or GLUT contexts) based on which types are used in a computation. The result is much more declarative than interleaving construction of resources in an IO monad with defining values.

My work on this is tabled for the moment, since I found a subset that solves my immediate needs - a way of associating resources with types in an infinite abstract space of resources. (I plan to tackle the greater configurations problem and the plugins problem together, since I'd really like adaptive reconfiguration based on changes in plugins).

Anyhow, all these approaches associate values with types. Perhaps that's all you need? Maybe typeclasses aren't the right way to approach this, but rather some form of context object that can associate values with types.

### I have a feeling that your

I have a feeling that your are proposing something very close to what I have implemented :) Can you expland this "associate values with types" strategy a bit?

Dynamic dispatch basically works because values (functions) are associated with types (by placing a "type tag" on a function). So you have, say, a set of (+) functions each with a unique type tag.

May be I am actually abusing the notion of "type class" here (which is most likely anyway). But I am just trying to understand how your approach will be different from what I have now.

Maybe typeclasses aren't the right way to approach this, but rather some form of context object that can associate values with types.

Do you mean that this context object should be explicitly set by a client code so that a single (+) function might have a different meaning depending on a context? Or this context should be inferred somehow?

### Configurations

My design is to solve a configurations problem - rich configuration, possibly multiple or changing configurations. The client can provide high priority rules to override defaults, and a simple constraint model can allow other rules to adapt.

My basic design reduces to:

• There is a set of rules of the form (Typeable a, Typeable b) => a -> b.
• This rule is a function from requirements to provisions.
• Sets of requirements or provisions can be modeled by tuples.
• An empty set of requirements can be modeled by unit.
• The client can ask for a value of a single type.
• The system will analyze the rules to find a path to implement the type, if one exists.
• However, there is a constraint: only one value of each type may be built. If two rules overlap in provisions, they conflict.
• If no valid path exists, will return a description of what it is missing (probably DNF [[TypeRep]]).

Then I wrap this in an Applicative, so I can interleave providing rules with defining the final value. Mostly, this makes it easy to provide defaults (which the client may later override). I have an idea on how to extend this with soft constraints (i.e. preferences, weighted logic) richer than simple ordering to provide a sort of hill-climbing optimization of large applications. I also plan to make this work well with plugins (which should not be difficult; GHC has one of the cleanest plugins models I've seen).

Basically, I'm linking based on types, constraints, and preferences rather than names. Stone soup programming.

### Open type classes ~= Interface types with semantic extensions

I have something useful to say here about open type classes and interfaces, but it's hard to formulate exactly. I'm going to thrash around here and hope people can see what I'm trying to point at.

Consider an "Interface" as defined in Java. It defines a set of methods that a particular object responds to. It may not be the only such set; some objects have a lot of different interfaces. You may be used to thinking of interface types as "Mixins." You can consider an interface to be something analogous to a type. An object that has many interfaces may be treated by polymorphic code as having many types.

But some objects implement the same interface in ways that are semantically different (are not Liskov-substitutable for other things having that interface). Consider a "Queue" interface that has "insert" and "fetch" and "count" methods. A FIFO queue and a LIFO queue both implement the interface but are not Liskov-Substitutable for each other. Clearly neither is properly a subtype of the other, but just as clearly the "Queue" interface is a (virtual) type that they are both subclasses of.

So how are the subclasses derived or specified, in terms of interfaces? The answer is that the idea of an "interface" has to be extended to include some semantics. The virtual class/interface for "Queue" would include statements like (Every "Queue" A isa "Collection") (FORALL A, FORALL datum: A.count() + 1 == (A.insert(datum)).count()) and (FORALL A: if A.count() >= 1 (A.fetch(@datum)).count() == A.count() - 1), which define a relationship of these three methods with reference to each other that is true for all Queues.

Then for the LIFO queue, you'd add more semantics definitions: something like (every "Lifo" L isa "Queue");(FORALL L, FORALL datum: (L.insert(datum)).fetch(@datum2) == L && datum == datum2).

For the FIFO queue, more semantics again and this time you'll have to do it by induction. Other subclasses of the same generic "Queue" will include things like a Priority Queue. So why are we writing math that *describes* code, instead of writing code?

Because we're still describing interfaces ("open classes") rather than implementations ("object types"). You may have a bunch of different things that all implement FIFO queues in different ways; with a linked list, with an array of fixed-width objects, with an array of pointers to variable width objects, etc. But all of them are described by the "Fifo" interface and all of them are described by the "Queue" interface and none of them are described by the "Lifo" interface. This means you can define routines that take "Queues" (if they don't rely on any semantics not guaranteed by the "Queue" interface) or you can define routines that take "Fifos" (if they don't rely on any semantics not guaranteed by the union of the "Queue" and "Fifo" interfaces).

Just as a note, I want to point out that the "Fifo" and "Lifo" interfaces do not specify any additional methods. The only difference between them is the specification of their semantics, and all the semantics that apply to "Queues" apply equally to them.

When you want to instantiate an object, its "type" is basically the set of all the different interfaces it's supposed to respond to, including the inherited interfaces of the parents of any of those interfaces that are derived. You can implement that functionality however you want. Now, it may be that your programming language can check your code against your stated interface properties and tell you if you've made a mistake. This is a resolution devoutly to be wished in language design, but "tricky" to code in a general case.

And now we get to polymorphism. Consider another routine definition. Suppose I have a generic function that takes a "Queue" as one of its six arguments. It can take a Fifo or a Lifo or some other kind of Queue, and it doesn't rely on any properties or methods other than those guaranteed by the Queue interface. But it doesn't need to be defined as part of that interface. It could be defined as part of a different interface. Indeed, it doesn't need to be defined as part of *any* interface if it isn't appropriate for it to be. And aside from being automatically specialized by calling the specialized methods of whatever arguments it gets, it may have thirty or forty completely different overloaded implementations depending on all kinds of different combinations of the types of its arguments. These implementations may be scattered around the code, wherever the definitions seem to make the most sense, with lots of "see also" clickable links in the comments (and lots of "this guy must have been crazy" muttered by the people who have to maintain the code, if it really gets that baroque).

So this is a way of thinking about "open type classes" -- as Interfaces with some added semantic constraints. Class inheritance and specialization can be inheritance and specialization in terms of interfaces, and then when you define an actual object type (what you're used to thinking of as a "class") you don't derive it from the interfaces; instead you write code to meet the set of interfaces it's committed to.

And generic functions with many implementations and complex type dispatch can coexist with specialized methods that are properties of a type. And while you *can* shoehorn one model into the other, it's usually not a good fit IMO to force them to be the same thing.

So anyway... I feel like I've talked all the way around my point now but somehow can't quite hit it on the head. There's something about generic functions, type dispatch, method inheritance, and the importance of semantics in defining "open type classes" that is there in the examples but I can't quite name it.

Ray

### Impossible

Type classes -- at least in the sense the word is commonly understood -- have no untyped semantics. Type classes dispatch on types independent from values. This cannot possibly work in an untyped (aka dynamically typed) language.

The closest you can get is something akin to CLOS multi methods, but it won't achieve all the expressive power of type classes (which, again, is fundamentally dependent on types).

### Of course it is different -

Of course it is different - as I mentioned. I do dispatch on types, not on values but it happens at run-time rather than compile time.

### Not so sure

I do dispatch on types, not on values

From my understanding of your description, I don't think that's true. You're doing dispatch on (the types of) concrete values. You can't do dispatch without having a value, which is what type classes can do.

but it happens at run-time rather than compile time.

It's a common misconception to think that type class dispatch is static. It is not. It can often be optimized away statically, but not in the general case -- e.g. not in the presence of existential types or polymorphic recursion.

### The problem here is that the

The problem here is that the whole notion of type is different in static and dynamic languages. From the standpoint of a dynamic language I do dispatch on types, as soon as functions are associated with type tags, not with values. From the standpoint of a statically typed language there are no types here at all.

As for existentials... You can surely do dynamic dispatch in Haskell but isn't it pretty close to what we have in OOP languages, e.g. dispatch against values?

### Type class instance selection is static

In support of this viewpoint, consider what happens when you enable overlapping instances and let Haskell attempt to find a best matching instance - the dispatch will only ever take into account the apparent type and not the actual ground type. For example, in a context of a polymorphic function where a variable has type [a], an instance matching [a] will be selected over [Int], and will be used uniformly, even if the polymorphic function is eventually instantiated at a=Int.

But of course you said "dispatch", not "instance selection", so I'm not saying you're wrong, but I prefer to look at it like this: the map from apparent type to instance is static, but if you have first class types (existential types) or infinitely many types (as is possible with polymorphic recursion), then you're going to need a some kind of run-time representation of types that can compute the mapping.

### Right.I'm no Haskell

Right (@Andreas, and for the OP)

I'm no Haskell specialist but I am skeptical as well whether the OP needs to borrow Haskell's type classes for his language, seemingly fairly dynamic-flavored (contradictory with type classes' design motivation AFAIK).

I don't know Haskell well, though I can read it, but I did get especially interested in type classes introduction in the language some while ago, after realizing I was devising something along similar lines independently (before noticing Haskell's type classes).

In my understanding, they are a clever way to enable Haskell make its concrete syntax more flexible upon the programmer's inventivity, and embed DSLs much more easily than without them.

They for sure are no types, but they feed themselves on static types as they range over type kinds, and I said clever because they have been designed to reside, and be used, at the most suitable level for their purpose : that is, at the intersection of the static type system and the concrete syntax of type kinds, precisely, prior existing in 98, to enforce the former's rules.

Thus, they allow Haskell and its users to cheat a lot, and often fruitfully, on other languages' built in features, where those languages' syntax design decisions are more involved and coupled with their type system. Hence, Haskell plus type classes capabilities that allow to "just" well... emulate/borrow those other languages' features (e.g., OO-related) within sometimes several DSLs used all at once, dissimulating themselves (to the untrained eye) in the same few lines of code.

Or even more crudely: type classes in Haskell == one of the rare evidences by the example in language design, of a clean, powerful meta programming facility without a text replacement-based preprocessor (often, much less clean, as we know)

Needless to say, but just to be clear, I welcome the Haskell experts correcting me on what I got wrong about type classes, of course.

EDIT
Btw, I suspect them to be strictly more expressive (in any interesting sense) than generics a la Java, or even, .NET. I also welcome any pointers about maybe a formal proof of this claim, if already done somewhere, that I have missed(?)

EDIT2
IMO, independently of other paradigmatic considerations, the ongoing designs of other languages, those that aim to provide static type checking, have a great opportunity to learn (and borrow) from Haskell type classes, oft-overlooked by them it seems (AFAIC, I see type classes orthogonal to the rest of Haskell strengths and weaknesses).

My (still vaporware) Y# is one of them. :) I can't think of any meaningful correspondence of type classes in a language that dispatches on values' (of a dynamic type setting) runtime types, though. It's a noble wish, but I'm afraid for dynamic languages it's as contradictory as, say, a precise rationals representation based on a mantissa+exponent (unfeasible) vs. numerator + denominator.

The latter takes into account what actually defines a rational : the ambient division operation of two integers, while the former completely ignores it.

### I think you are confusing

I think you are confusing type classes with something else. They are not directly related to generics and/or static typing. Generics in Haskell are indeed much more expressive than in .NET and even in Java. But they are simply the tool to implement type classes in a statically typed Haskell and clearly do not have any meaning or application in a dynamically typed environment.

Types classes are classes of types, an abstraction over types. This abstraction is feasible in a system with any typing.

The initial objection is more against the "type" part here, not the "class" part. Dynamically typed languages clearly do not have types in the same meaning as static languages, therefore "dispatch on types" appears to be a different type of dispatch in a statically and dynamically typed language.

But dynamic languages clearly do not prohibit abstractions at any level. This is just plain wrong.

### I think you are confusing

I think you are confusing type classes with something else.

Maybe. I did write I'm no specialist there, but as far as my own understanding of Haskell's type classes go vs. (statically checked) types in OO languages, the closest I could find is what's explained here : http://www.haskell.org/haskellwiki/OOP_vs_type_classes.

They are not directly related to generics and/or static typing. Generics in Haskell are indeed much more expressive than in .NET and even in Java.

Sorry for the confusion. I was just alluding to the fact that in order to implement, say, GADTs, with static type checking in .NET or Java, the closest you can find for this purpose is their generics, but it's much, much more painful (i.e., tedious) in their case than in Haskell (I tried, in several occasions, in C# that I know quite well, and it's a real pain. The syntax outcome you get is systematically too hairy.)

[...]therefore "dispatch on types" appears to be a different type of dispatch in a statically and dynamically typed language.

Of course. But since it's (in part) about talking of Haskell's type classes, and as Andreas pointed out, I was trying to make the point that even though the dispatch may or may not be performed (or optimized) statically, the type checking constraints/contexts that type classes introduce over types in the first place, still, are honored statically. Otherwise, that would not allow, by definition, to maintain a (statically) type-safe usage of type classes by the programmer.

But dynamic languages clearly do not prohibit abstractions at any level. This is just plain wrong.

I didn't write such an over-general (and indeed, untrue) claim anywhere, and I never would.

### Of course. But since it's

Of course. But since it's (in part) about talking of Haskell's type classes, and as Andreas pointed out, I was trying to make the point that even though the dispatch may or may not be performed (or optimized) statically, the type checking constraints/contexts that type classes introduce over types in the first place, still, are honored statically.

The main disconnection between static and dynamic languages here is that a notion of type is used in *completely* different meaning in static and dynamic world. This might be more of a terminology problem (or one might say that the term type is simply abused by those who find it applicable to dynamic languages).
The problem is that in a static language when you can a expression like so:

x = 2

You read it as: A name x of type integer.

But this is not valid in a dynamic language. In dynamic language you would read it as: A name x which has a value of type integer.

Types are bound to values and basically don't exist without values. Compiler do not reason about types at all, instead run-time environment inspects types of values as type tags.

The concept of a class is in the first place a concept of "class of operations" that can be used as an abstraction over types. Such an abstraction is perfectly valid (and I believe useful) in both static and dynamic languages. But it is naturally different as soon as you are abstracting over a different thing.

Whether it is valid (or not) to speak about type classes in dynamic environment depends whether it is valid to speak about presence of types in a dynamic language at all. I personally prefer to think that there are simply two ways to define "type" - in dynamic and in static world.

BTW. I am actually not the first one who is trying to abuse the "type class" in such a manner. For example, there is "Type classes without types" (http://repository.readscheme.org/ftp/papers/sw2005/garcia.pdf) paper where a Scheme implementation is discussed.

### Whether it is valid (or not)

Whether it is valid (or not) to speak about type classes in dynamic environment depends whether it is valid to speak about presence of types in a dynamic language at all. I personally prefer to think that there are simply two ways to define "type" - in dynamic and in static world.

Well, I hear you. (I skimmed thru your Ela language's source repository, and I find it interesting in fact.)

Just to be clear, though I happen to use a mainstream statically typed language (C#) if only to make a living, I hold absolutely nothing that'd be negatively dogmatic against dynamic languages. I actually enjoy using them, in some specific contexts I'm confident enough to put them at work. And that doesn't date from yesterday either, btw.

I was trying to say: you may not want, for the problem you're trying to solve to enhance Ela, to distract yourself with borrowing a feature of Haskell which has (just IMO*) already made design choices more involved than what you really need.

EDIT
*But, hell, I may be wrong. Right.

### The initial idea is not to

The initial idea is not to implement type classes in Ela. In fact my initial take was completely different.
The idea is to do the following. Having a function defined like so:

let sum (+) x y = x+y

to be able to write it just as:

let sum x y = x+y

so that a particular implementation of (+) can be somehow "inferred". I would also like a solution to be "safe" - which might mean to provide it with some static behavior, e.g. to deal with overlapping statically, etc. I would like to "group" functions as well.

For example, we have functions 'head', 'tail' and 'nil'. I want all these function to belong to a single function group so that if you want to overload 'head' you will have to overload the rest as well (as soon as overloading just 'head' without 'tail' and 'nil' seems quite meaningless for me).

### BTW. I am actually not the

BTW. I am actually not the first one who is trying to abuse the "type class" in such a manner. For example, there is "Type classes without types"

Interesting. So, looks like you've already found the most relevant paper for your concerns, anyway. Too bad my reading Scheme is even less confident than re: Haskell itself. ;)

Then, just be aware of what the paper's authors have been wise enough not to omit in their conclusion, at least:

In the case of multiple parameter classes, operations need not
be dependent upon all the class predicates. Despite interest in and
known uses for multiple parameter type classes for Haskell, as
well as support for them in several implementations, type checking
of programs that make use of them is undecidable in the general
case. Nonetheless they are considered useful, and various means
have been proposed to make them tractable [Jon00, PJM97, DO02,
CKPM05]. In the Scheme system, lack of dispatch information can
also be problematic, especially if multiple instances of the class
have overlapping predicates. A call to an operation with this sort
of ambiguity results in the most recent instanceâ€™s operation being
called. An implementation of this system could recognize such
ambiguities and report them as warnings at compile-time and as
errors at runtime, but the system we describe here does not.

It's one thing you won't want to miss to address if that applies to your plans for Ela as well, I suppose.

### I am aware of this problem.

I am aware of this problem. For now my answer is - no multiple dispatch at all (no "multi parameter type classes"). The version I am currently working on will provide a more civilized (yet still single parameter based) way of dispatch. A class will be defined like so:

class Show a
where showf:: _->a


So that you don't have to do dispatch based on the first argument only, but an instance is still done for one specific type, e.g. 'instance Show int'.

In fact the current version of Ela (2012.5) has an experimental "let extends" feature that implements "open functions". Besides some scoping issues, it does have a problem with overlapping which renders it (almost) useless.

Actually one of my ideas (probably even the main idea) with this new approach is to simplify the resolution and to deal with overlapping strictly statically (by rejecting overlapping instances in compile time).

### By the way the paper "Type

By the way the paper "Type classes without types" is more of a theoretical research, when in reality there is an existing implementation of something pretty similar in another Lisp-like language - I mean protocols in Clojure (which I myself discovered just recently). And interesting thing is that Clojure protocols are awfully a lot like my prototype implementation and are intended as a sort of a replacement for multi methods.

### I remember discussion about

I remember discussion about edit-time "type classes", where the implicit values/dictionaries are determined at edit-time rather than compile time. Does somebody remember the thread where this discussion took place?

### What is "edit-time"?

What is "edit-time"?

### The phase where the

The phase when the programmer is writing the program (as opposed to compile-time: the phase when the compiler is compiling the program, or in your case run-time: the phase when the program is run).

### But in order to resolve type

But in order to resolve type classes in a typeful language a program should be typed. So it simply looks like that your program compiles (at least partially) as you type code in your code editor. What difference does it make in comparison with regular static resolution?

### I think I vaguely remember

I think I vaguely remember that in some or all cases the programmer has to select which instance to use. But this is the reason I'm asking whether somebody remembers the thread :) Google was not helping.

### We had an exchange along those lines

Here

Is that what you're thinking of?

### Yes, that was was I was

Yes, that was was I was thinking of. In my memory the concept was more fleshed out in the thread than it seems to be...

Can you explain why you think that type classes should be resolved at edit time, and what kind of UI for doing this you had in mind?

### One rationale for doing

One rationale for doing instance selection at edit time is that instance selection/overload resolution is ad hoc and complicated to reason about. Rather than even trying to reason about overload resolution, it seems better that we just inspect the result of the resolution to verify that it picked the symbol we wanted in each instance.

Another thing is that for me, this is the same mechanism as module disambiguation. So if you type 'x * y', it needs to resolve which '*' you mean, and looks at types to figure that out. So in some sense I have truly ad hoc overloading, which Haskell doesn't (and doesn't want), but because it's at edit time, and you get to see which symbol you picked.

The UI for this right now is to show the ascii as typed, and then to replace symbols with more descriptive symbols when the instance/ambiguity can be resolved (more descriptive symbols possibly being a different unicode symbol maybe with a subscript, so < might turn into < with a Z subscript when the integer version is selected, indicating a namespace tag). Sean warned me that this might be annoyingly jarring, and I think he's right. Particularly jarring is when the horizontal size of the replacement changes, as that shifts everything else on the line. I'm going to try smoothing animations to see if I can minimize the annoyance. It's also annoying if you have to go back when you realize you aren't going to end up removing an ambiguity, so I'm going to add key strokes that let you edit/resolve the previous ambiguity without moving the cursor there.

I've posted about some of this elsewhere on LtU not too long ago, but I don't find it.

### My intuition is that any

My intuition is that any width change are unacceptable even if smoothly animated. You could try padding the width so they all are same size instead. Is there a demo I can mess around with?

### I have some other ideas and

I have some other ideas and think I can find something that works. Adding extra padding ahead of time is an idea I could try. I could also only have it do replacements in response to certain events, like when you hit tab or reach the end of a line, and before that just indicate in a generic way that a symbol is no longer ambigous (e.g. underline ambiguity in red).

For the UI, I have a C++ / OpenGL prototype to render everything, but I'm not ready to release it yet. I probably will release something before I finish bootstrapping the language & IDE, but I want to get a little further than I am now.

### Interesting!

So essentially you have code completion and instead of selecting 1 candidate, you can select a whole set of candidates? Instead of selecting int.multiply, you can select the whole set multiply which means anything.multiply, and later select the exact one or have the exact one inferred?

You could show the same short identifier even after disambiguation, and only show the full disambiguation and extra information when you put your cursor on that identifier or when you go into a "show all inferred types" mode.

Type classes allow you to hide the parameter to a function to keep the function generic, for example:

mult3 a b c = a*b*c

Written out this becomes:

mult3 (*) a b c = a*b*c

How do you plan to deal with this? Is this done automatically behind the scenes? How do you decide whether an identifier needs to be disambiguated further vs whether to add it as a hidden parameter? Would inferring that automatically involve a global process? That would probably be less problematic than usual because it happens at edit time.

Do you keep track of which selections were made by a human and which were inferred? For example if you have x*y and due to other code it is inferred that this is an integer multiplication, but later that other code gets edited and now it's a vector multiplication. What happens with the x*y? What if the integer multiplication was selected by the programmer? Is that a type error, or fixed up automatically?

### More information

Right now I only do one resolution at a time, but that can result in cascading resolutions. I use tags rather than a namespace hierarchy so that I can produce minimal disambiguations of symbols in scope (<_Z vs. Integer.<).

You're right, I didn't mention the definition side of type classes. I have a system of theories that's kind of like ML modules that underlies all of this. Also, I'm not pushing the bag of constraints style typing that happens in Haskell when you have type classes. Typically (caveats apply), what matters when you write something like mult3 is whether you're working in a context in which Num, *, etc. are concrete or abstract, which is this mechanism I have...

I started to write more the first time around to answer your last paragraph's questions, but yes, when a disambiguation is deduced from types, that can currently be undone by a changes to the code around. There are some somewhat thorny issues about when things need to be firmed up and what things do when you're passing through error states.