Some comments on Interfaces after briefly reading

The "interfaces" thing is Haskell type classes. This is independent of parametric polymorphism. The way this works (in Felix at least) is that initially in phase 1 binding, you bind to a parametrically polymorphic interface. The constraints are not checked. During phase 2 binding as you're doing monomorphisation (elimination of type variables), you find and chose an instance, or barf if you can't find one. I can give more details on the resolution algorithms.

Now, interfaces are not properties of a single types. So given

interface Convertible(T1, T2) { .. }

how do you specify an instance? Can you write:

(int, real) implements Convertible?

This looks messy. The constraint spec is OK like:

where (U1, U2) implements Convertible

but it would be cleaner to just do

where Convertible(U1, U2)

The shorthand:


is problematic if you also have kinding constraints. In fact, using ?t inside a formula to introduce type variables is probably not so good either, it gets way too messy. What do you do if the type variable is not used in the formula? How do you introduce it?

In addition, when an interface has multiple functions in it, and you allow default implementations as Haskell and Felix do, you then must distinguish between a default implementation of an implementable function, and a helper function which cannot be overridden. In Felix I use the keyword virtual to specify an implementable function. Since this concern also applies to associated types, I also use the keyword virtual for associated types.

Finding of implementations from the general scope look very bad. You have to explicitly specify that a function is an implementation and what the types are like this:

implementation[K1] Convertible(K1, K1 * int) { ... }

Implementations can be polymorphic, and they can be specialised.

When you are calling a function, you need to be able to add a qualifier to specify which interface it comes from, along with type arguments. This is because, for example, the types are not used in the function domain and so cannot be deduced. It is important implementing the lookup that you find the interface and resolve the type arguments first before looking for an implementation. This makes the lookup a little bit different to ordinary lookup.

On interaction with ordinary generics. There are a couple of messy options here. In Felix there are three ways (more or less) to use an interface.

  1. Explicit qualification:


Here the interface is named, and the type argument is specified. The :: is from C++ notation. Uggh. Note, you STILL need to do overloading inside the interface to choose less, if you were stupid enough to provide two functions called less in the interface. Probably this should be banned.

  1. By injection into a function scope, using where clause.

where Convertible(T1, T2)

When you do this, the functions in the interface are local to the function and therefore by the usual scoping rules hide functions from an outer scope. Which functions, if any, from the outer scope that you find depend on your normal hiding rules. In C++, the hiding is absolute which I consider a design bug, so in Felix, outer functions with the same name are still visible to an overload resolution if no function in the current scope matches. But Chapel should just use what rules it normally does for name hiding.

  1. By exposure with an open clause.

open[K] Convertible(K, K*int);

This puts the functions of interface Convertible into the current scope, with their domains constrained. In the common case

open[K1, K2] Convertible[K1,K2];

the constraints can be dropped:

open Convertible;

which opens the whole interface in the current scope. Here's an example from Felix:

class Str[T] { virtual fun str: T -> string; }
open Str;
instance Str[int] { fun str(x:int):string { .... }}

where class is Chapel interface, instance is Chapel implements. When the user introduces a new type, they can add an instance of Str::str for that type.

There are more things you can do in Felix. For example you can "inherit" an interface into another interface to compose them. FYI here are some Felix interfaces for basic algebra stuff:

The most interesting is worth showing here:

  class Monad [M: TYPE->TYPE] {
    virtual fun ret[a]: a -> M a;
    virtual fun bind[a,b]: M a * (a -> M b) -> M b;
    fun join[a] (n: M (M a)): M a => bind (n , (fun (x:M a):M a=>x));

Notice the interface parameter M is NOT a type but a type function! In Felix TYPE is the kind of ordinary types, and so TYPE->TYPE is a function from types to types. Also notice the join operator is not virtual, so it cannot be specified in an implementation. ret and bind are the traditional Haskell names for monad operators.

Whew. Sorry so long. I've implemented what you called interfaces so I know about the gotchas having been got by them. The biggest problem after you sort out the syntax is associated types. In languages like C++, Felix, and Chapel, it just doesn't play with ordinary overloading. In Haskell it's irrelevant, because there is no ordinary overloading, all overloading is inside a type class anyhow.

Also, I didn't explain fully, but you must specify the interface a function is providing an implementation for, otherwise polymorphic recursion won't work. Which opens up another issue: how are you going to terminate polymorphic recursions? Haskell knows how to check this. In Felix I just put a limit in the compiler because I couldn't figure out how to check it.

In case you don't know what polymorphic recursion is: it happens when, in an implementation of a function from an interface, you call the function from the interface again with a different type. So it isn't an ordinary recursive call.

@skaller โ€”

Thanks very much for sharing your experience with, and feedback on, interfaces with us. @vass is heading up this effort within our team, but is out of the office until the new year, so I've tagged him here in hopes that he can catch up on this and comment when he's back.

Beyond the general challenges in specifying and implementing interfaces, we also have the challenge that our compiler code is a bit crufty and was written without interfaces in mind. So Vass has been working on wrestling the feature in. Meanwhile, a second team is working on an incremental rewrite of our compiler, which is intended to be better structured (in general, and for implementing interfaces specifically). Unfortunately, the net effect is that in either version of the compiler, a complete implementation is still a ways off (which is regrettable because we'd like to be using interfaces more in our libraries today).


Well FYI I am considering applying for the job HPE is advertising as a compiler writer/language designer. Since my resume is a blank page I'm thinking to help out free to start hoping to get some recommendations from existing team members and users. I well understand the existence of crufty code in compilers for languages with a long history .. you would probably throw up if you read some of the Felix compiler code. In addition, C++ is a really bad language for implementing a compiler with only one real advantage: its commonly available. Felix uses Ocaml for the compiler which is vastly superior as a language but it causes no end of problems for Windows users trying to build the compiler. I really wish I could eliminate that dependency.

1 Like

Hi @skaller,

Indeed, thank you for sharing your thoughts on interfaces. You bring up a couple of interesting issues. I encourage you to post your proposals of features for Chapel interfaces as GitHub issues here: Sign in to GitHub ยท GitHub

BTW how does Haskell check polymorphic recursions?


There is an algorithm (obviously lol) to check polymorphic recursions converge. I don't know what it is, but I guess I could find a reference to some literature. I have a friend who knows the compiler and people, I could ask him to help. It's not clear to me (obviously again) whether the algorithm would work in a significantly different type system.

In Felix, I just put a limit of 50 iterations to stop explosions. However that's not really good enough. There are three cases I think:

  1. Finite convergence. In other words, the polymorphic recursion degenerates into an ordinary recursion and is terminated by the usual method. This would very often happen in a single step I think, because often some embellished version of a function is just delegating to a more basic one. In other cases, one is reducing a finite data structure one component at a time until complete: this happens in Felix, converting a tuple to a string. The tuple is split into a head and tail, the head is polymorphic-recursion converted, then the tail.

  2. Oscillation. This could also be checked with say a trail, so it would reduce into a set of mutually recursive functions the length of the recursion cycle. This is a bit harder to do that case 1.

  3. Infinite expansion. I guess this is detected by a failure to prove convergence, rather than a proof of divergence but I don't know.

I would note, like other recursions, it is not just self-recursion involved. We could actually recurse indirectly through a sequence of functions. I guess you could eliminate that by inlining until it because a self-recursion.

@vass I'm loath to post too many issues at the moment, i'm still feeling out the community. I also don't have a strong enough grasp on how Chapel type system works, and that also makes it hard to evaluate the interfaces proposal. Certainly the idea of the proposal, which is like Haskell type classes, Felix type classes, C++ concepts, stuff proposed for Go, Rust has type classes too and in Rust they're absolutely fundamental .. yes the idea is good.

But it will degenerate into a mess, as it has in C++, if the core type system is not solidly based on algebra. The way this machinery works in Felix is not quite the same as Haskell, but the Felix method is probably the closest to what you will have to do in Chapel. I will is tell you right now there is a serious issue. The use of "implicits" in Rust and Chapel and Go may help with this but I don't know without further study. Haskell and Felix both require explicit instantiation of specialisations.

Here's what happens in Felix.

  1. The type class interface has function interfaces in it which are parametrically polymorphic.
  2. Calls to the function are bound to this interface, each call with specialised the type variables of the interface.
  3. The instances for various types provided by the used are type checked fully, and they're matched against the type class interface function method, to make sure they conform. In Felix, if it doesn't match, its fine, it just isn't an instance of the interface function. That's a design bug in Felix. There's no way to say "this is supposed to be an override".
  4. Felix monomorphises the whole program the usual way, but starting at top level monomorphic functions, and creating monomorphic versions of every polymorphic function called. It does this recursively, and this propagates monomorphic types through the system, eliminating all type variables in the result.
  5. During monomorphicsation, if a type class interface function call is monomorphised, the system has to search for a matching instance implementation. This involves unification as well as overload resolution since implementations can overlap.
  6. If an suitable unambiguous implementation cannot be found, an instantiation error is issued. This is NOT a type error. It's a "you forgot to provide an implementation for this type" error. Same as a failed overload resolution is not a type error as such.

The key thing about the Felix implementation is the constraints are never checked. They do not have to be checked. The way this works is that, if a type variable is constrained to type class X, then the functions of X are added to the body of the function so they can be called. So rather than X being a constraint, it actually enables the use of functions that parametric polymorphism would otherwise disallow because they depend on the type parameter.

Haskell checks I believe. But Haskell also passes actual dictionaries of functions at run time. It has to do this because it has separate compilation AND because it supports second order polymorphism, and it CAN do this because of boxing. But Felix is much faster, because it completely eliminates all type classes and interfaces during monomorphisation, so it can actually inline and do other optimisations: the type class interface/implementation stuff has zero run time performance cost (same as C++ templates: the price is paid at compile time).

Now two things:

  1. Absolutely rigid parametric polymorphism is a prerequisitre. No generic crud. You'll never get it to work properly otherwise.
  2. Associated types, aka output types, or existential types can be made to work, but they do not play with ordinary overloading

The reason for this is simple enough: ordinary overloading is already done. The associated type stuff is available to functions of type class instances, but it is NOT available to functions outside type classes.

There may be a way to fix this, I don't know. It's not an issue in Haskell because of the type inference algorithm, and the fact Haskell does not do overloading outside type classes anyhow.

@skaller -- understood. One way to be involved with the community, assuming this is your goal, is to see which parts of these pages jibe with you:

The main push of the project right now is to solidify the design and the implementation that we already have, reduce backwards-incompatible changes, and to improve user experience. For example, it is unlikely that we will make significant changes to how Chapel generics work.

Interfaces are a bit different because their design is still in flux. A partial list of things that are on our mind at the moment is here:

The problem I have really is that stabilising the language and retaining compatibility are in direct conflict with progress towards a better system.

Interfaces are useless unless applied to polymorphic functions. There's no point having them if you have generics. The WHOLE point is to first have type checked polymorphism, and then add interface constraints to make them easier to use, whilst retaining most of the type safety.

In fact, with type classes/interfaces, you can get type errors AFTER type checking, but these all have the form "cannot find implementation of function" which is easy to grok (if you really meant to have one, go implement it!).

FYI there is a detailed description of the contribution process but the DCO link does not work and I cannot find any reference to it in the doc. Do you have a link?

The "sign every commit" seems onerous. I do lots of commits during development, Github knows who makes the commits. Often lots of loosely related (or even unrelated) things get committed at once. The reason is, I usually ensure a full build and test works before committing (which can be hundreds of changes). Afraid my "git fu" is low. I have too much trouble reverting to bother committing untested code.

OK one of the things that worries me with Interfaces is the implicit implementations. If I understand correctly, in some scope if you require an interface containing a function f, a suitable f is searched for at that point. Is that correct?

If so, this seems like a disaster because a different f might be found in different places. This means for some fixed monomorphic type, such as int, the behaviour can be different, depending on the point of call. This is exactly the incoherent behaviour we want to avoid, it's precisely the problem with the existing generics. But Rust does this too, and so does Go.

In Felix and Haskell, on the other hand, you have to explicitly construct an implementation containing the required functions. If two such implementations exist, an ambiguity error is reported. So if there's no error, there is exactly one function which can be called with a given name and signature via the interface.

A consequence of this is that if you already have an ordinary function f you have to use a forwarding function in the implementation. On the other hand, the functions in the implementation cannot be called directly, they can only be called via the interface.

However, this is merely an inconvenience. The real issue is how do you handle the problem when you actually do want two implementations??

As an example, consider a Comparable interface with one type T that provides a function less. Now thinking of sorting integers using this, we may want two definitions of less one which is less and one which is more, depending on whether we want to sort in ascending or descending order.

IMHO this is one of the limitations of the Haskel type class system compared to the Ocaml system of modular functors. Conceptually, you can only define one set of uniform canonical notation. The advantage is you don't have to be explicit about which one you mean, because there's only one. The disadvantage of the Ocaml system is every functor applied to a module to produce another module has to be explicitly named to use it.

Anyhow at the moment, I question the semantic soundness of the implicit implementation feature. In particular for any call to an interface function, the semantics can be hijacked (silently changed) by adding a new function that a particular call will invoke instead of the one it used to call. Hijacking is one of the features of dependent name lookup in C++ which is a universal problem with templates.

Hello @skaller - here is the DCO link:

Thanks, got it!

Hi @skaller, Also thank you for noticing the broken links. We fixed them by pointing the Contributing web page at Contributor Info โ€” Chapel Documentation 1.25 instead of in the github repository.