Lambda the Ultimate

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.

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 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.

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 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 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.

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?

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.

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.

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 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?

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 (@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 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 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 (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) 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 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 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. 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 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 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"?

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 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 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.

Here

Is that what you're thinking of?

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 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 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 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.

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?

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.