Interfaces

Some comments on Interfaces after briefly reading https://chapel-lang.org/releaseNotes/1.24/04-ongoing.pdf

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:

?t:TotalOrder

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:

TotalOrder[int]::less(1,2)

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 { .... }}
println(24.str);

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:

http://felix-lang.org/share/src/packages/algebra.fdoc

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

-Brad

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?

-Vass

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:

https://chapel-lang.org/contributing.html

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