Ad-hoc polymorphism in the type system

[resolritter]

Re #171 (comment)

Gleam does not currently have type classes, though may have something similar in future.

I kept wondering what that "something" was but could not find any hints, thus I'll start this discussion assuming there's no strong decision made yet, otherwise feel free to close this.

For starters, I like Edward Kmett's "Type Classes vs. the World" not only because it's a good talk but also has some comparisons throughout (specially at the start); of course it's biased towards Haskell's type classes.

Rust's trait system is cool as well.

I have a positive impression of given/using from Scala 3's type classes. I found a video comparing how it has improved from Scala 2 which is quite entertaining. I'm not a Scala developer myself so can't really criticize how it has changed over the years, but it seems that Scala 3's polymorphism has better ergonomics and is saner.

I've also heard about OCaml's upcoming "modular implicits" being an improvement over ML modules but have never really studied what it is myself.

Overall I'm not educated enough to advocate for one or the other so this whole post is just trying to showcase different "typeclass-ish" approaches from other languages which saw some real adoption. Feel free to discuss any other kinds systems which fit functional languages.

[lpil]

Hello! You've guessed right, there is no firm ideas of what this might look like at present. While these ad-hoc polymorphism features are powerful it is easy to open the door to code that is very difficult to understand and modify, which is something we wish to avoid in Gleam.

I have a positive impression of given/using from Scala 3's type classes

Huh! This is the first time I'm hearing about the given/using of Scala 3. That looks very nice in a bunch of ways and I'm quite curious about it now. This looks a lot closer to the kind of system we might have in Gleam one day.

I was approaching something like this in my head for an implicits system (tiny not very useful code snippet https://github.com/gleam-experiments/experiments/blob/master/implicit.gleam) but I hadn't got very far. I will have to look into Scala's approach more.

[lpil]

I generally have the opinion that people should work on anything they personally find interesting, so it doesn't matter so much.

On the other hand I am trying to focus on things that will bring the most immediate value. Right now that means the issues in the v0.17 milestone and then after that working on the Gleam build tool and package manager. The big task there is incorporating pubgrub into the hex library

https://github.com/gleam-lang/hexpm-rust

https://github.com/pubgrub-rs/pubgrub

pubgrub-rs/pubgrub#80

[resolritter]

since you seemed particularly interested in implicits, I'll also link a talk from Scala's creator about Scala implicit's designs and how they changed over time: https://www.youtube.com/watch?v=LwacEp_VjCM

[timjs]

This subjects intrigues me, and I keep thinking about multiple possible solutions.

@lpil Could you list the problems you'd like to solve, which properties you're looking for, and what features you absolutely like to avoid?

[lpil]

The main constraint is that I wish for gleam code to always be easy to modify, comparatively speaking. I think that systems such as type classes make it very easy to write code which is conceptually challenging or intimidating, which doesn't align very well with this goal.

The next constraint is that Gleam should be easy to use from the host language. Creating a thick runtime in order to support some interface type system on top of Erlang would make it much more difficult to use Glean code from Erlang, Elixir, etc. I would like the generated interface is to be understandable and for the generated code to be readable.

I think not having interfaces of any kind in the language works very well towards the school but it comes at the cost of verbosity in many places. I am interested in exploring additions to the language which offer some of the convenience found in other languages without sacrificing interop or simplicity.

Exactly which verbosity is to be tackled is not yet clear. I think we will know more as more Gleam code is written, and different solutions will be better for different situations, at which point we can compare them against their respective drawbacks. I think it is very likely that we will not be going for the most powerful system, instead we would prefer a more constrained one that is easier to work with.

Overall it's a very early exploratory stage.

[lpil]

This other issue is worth looking at here #1272

[timjs]

Warning 1: Very long post!
Warning 2: Probably contains typos, so please let me know if you find some!

As we're discussing implicits as a possible solution to ad-hoc polymorphism, I'd like to describe some alternative design choices to aid a well founded decision. Implicits solve both ad-hoc polymorphism and configuration contexts, but as this topic is about ad-hoc polymorphism only, I'll only take that into account.

Which problems could we solve?

1. Writing functions over any type that supports addition:

   fn addmul(x, y) {
     x + x * y + y
   } 

   Currently this is restricted to fn(Int, Int) -> Int, as the + and * operators only works on integers, and we have separate +. and *. operators for floats. However, addmul could be inferred as a function taking any type of number supporting addition.
2. Writing functions over any type that supports equality or ordering:

   fn unique(xs: List(a)) -> List(a) { .. }

   Currently works on any type, because Gleam has polymorphic equality (inherited from Erlang). However, this can give strange results when comparing queues, as equivalent queues can have different underlying value representations.
3. Write functions over any collection:

   fn sum(xs: List(a)) -> Result(a, Nil) {
     reduce(over: xs, with: (+))
   )

   Currently only works on lists, because reduce is defined on lists. However, this could be defined as a general function over any collection type. (For example as done by Elixir with Enum.)
4. Write functions over record fields:

   fn hello(x) {
     print(x.name)
   }

   Currently this Gleam code doesn't compile. There can be multiple records in scope which define a .name field and we cannot decide upfront which type to pick for x. However, this could be inferred as a function taking any record which has a .name field.

Which solutions do exist?

I'll list some solutions ordered from least powerful to most powerful. The structure is as show in below graph. Abbreviations refer to each possible solution presented below. I use trait to describe these solutions, but you can equally well read type class everywhere. All solutions can be implemented in the same way, by passing dictionaries as additional arguments.

Overloaded function names (O)

Based on Odersky, Wadler, Wehr (1995).

One would declare some function names as overloaded. Instances are defined separately. When using such a name in a function body, the compiler infers a type based on the first parameter only. At the call site, the compiler searches for an instance fitting the function constraints.

// Declare `+` and `*` as an overloaded name
// Note that we do not give a type signature for how plus should look like
trait +
trait *

// Instantiate for Int and Float
impl +(x, y) { prim_int_add(x, y) }
impl *(x, y) { prim_int_mul(x, y) }
impl +(x, y) { prim_float_add(x, y) }
impl *(x, y) { prim_float_mul(x, y) }

// Use in function 
fn addmul(x, y) {
  x + x * y + y
} 
// The inferred type for `addmul` is
fn(a, a) -> a where + : fn(a, a) -> a, * : fn(a, a) -> a

Pros:

• Full type inference
• No hierarchy
• No grouping of functionality
• Solves problems 1 and 2 and 4

Cons:

• Type signatures of functions can get big
• No hierarchy
• No grouping of functionality
• Does not allow us to abstract over collections

Single parameter traits (ST)

Based on Wadler & Blot (1989)

These are the type classes implemented in basic Haskell.

// Declare `Calcs` as a trait for numeric calculations
// Note that we do give type signatures here
trait Calcs(a) {
  fn +(a, a) -> a
  fn *(a, a) -> a
}

// Instantiate for Int and Float
impl Calcs(Int) {
  fn +(x, y) { prim_int_add(x, y) }
  fn *(x, y) { prim_int_mul(x, y) }
}
impl Calcs(Float) {
  fn +(x, y) { prim_float_add(x, y) }
  fn *(x, y) { prim_float_mul(x, y) }
}

// Use in function 
fn addmul(x, y) {
  x + x * y + y
} 
// The inferred type for `addmul` is
fn(a, a) -> a where Calcs(a)

Pros:

• Full type inference
• Hierarchies
• Grouping of functionality
• Can have default implementations
• Solves problems 1 and 2

Cons:

• Does not allow us to abstract over collections

Multi-parameter traits (MT)

This is a simple extension on single parameter traits: allow more parameters. Implicits as discussed in #1272 are as powerful as this option and share the same benefits and problems. Differences are that, they ask developers to manually bring instances into scope and allow for contextual abstraction.

// Declare a trait which collects elements `e` into a collection `c`
trait Collects(e, c) {
  fn reduce(over collection: c, with fun: fn(a, e) -> a) -> Result(a, Nil)
  fn insert(into collection: c, element x: e) -> c
  ..
}

// Implement for lists
impl Collects(e, List(e)) {
  fn reduce(..) {..}
  fn insert(..) { .. }
  ..
}

// Use in function
fn sum(xs)  {
  reduce(over: xs, with: (+))
)
// The inferred type for `sum` is 
fn(c) -> Result(e, Nil) where Collects(e, c), Calcs(e)

However, note that there is no relation between the collection type c and its element type e. Which means that we get ambiguous types:

fn insert_both(x, y, collection) {
  collection |> insert(x) |> insert(y)
}
fn bad(collection) {
  collection |> insert2(True, 24) // This is OK
}
fn main() {
  bad([]) // Error will be here, could be in another module or even different package!
}

Because insert_both has type fn(a, b, c) -> c where Collects(a, c), Collects(b, c) and bad has type fn(c) -> c where Collects(Bool, c), Collects(Char, c), all will be fine up until the moment someone uses bad on a homogenous collection type.

Pros:

• Full type inference
• Hierarchies
• Grouping of functionality
• Can have default implementations
• Solves problems 1 and 2

Cons:

• Not a real solution for problems 3 and 4

Parametric traits (PT)

Based on Chen, Hudak, Odersky (1992)

This is a mixture of single- and multi-parameter traits, but the additional parameters are uniquely determined by the first one. It is similar but not entirely as powerful as Swift protocols and Rust traits, where the single type parameter is the Self type, and the type arguments are associated types.

// Declare a trait where collection `c` collects elements `e`
trait c : Collects(e) {
  fn reduce(over collection: c, with fun: fn(a, e) -> a) -> Result(a, Nil)
  fn insert(into collection: c, element x: e) -> c
  ..
}

// Implement for lists
impl List(e) : Collects(e) {
  fn reduce(..) {..}
  fn insert(..) { .. }
  ..
}

// Use in function
fn sum(xs) {
  reduce(over: xs, with: (+))
)
// The inferred type for `sum` is
fn(c) -> Result(e, Nil) where c : Collects(e), e : Calcs

Pros:

• Full type inference
• Hierarchies
• Grouping of functionality
• Can have default implementations
• Solves problems 1 and 2 and 3 and 4

Cons:

• Introduces type level computations (eg Succ and Pred on Peano numbers)

Multi-parameter traits with functional dependencies (MTD)

Based on Jones, 2000.

This is a more general addition to multi-parameter traits to solve the problems mentioned before. In short, parametrised traits specify a dependency of type variables in one direction. One can generalise this idea to multiple variables in multiple directions. This is what PureScript uses and Haskell with the FunctionDependencies extension.

// Declare a trait where collection `c` collects elements `e` and `e` is uniquely determined by `c`
trait Collects(e, c) | c ~> e {
  fn reduce(over collection: c, with fun: fn(a, e) -> a) -> Result(a, Nil)
  fn insert(into collection: c, element x: e) -> c
  ..
}

// Implement for lists
impl Collects(e, List(e)) {
  fn reduce(..) {..}
  fn insert(..) { .. }
  ..
}

// Use in function
fn sum(xs) {
  reduce(over: xs, with: (+))
)
// The inferred type for `sum` is
fn(c) -> Result(e, Nil) where Collects(c, e), Calcs(e)

Pros:

• Full type inference
• Hierarchies
• Grouping of functionality
• Can have default implementations
• Solves problems 1 and 2 and 3 and 4 and even more

Cons:

• Introduces type level computations (eg Succ and Pred on Peano numbers)

Multi-parameter type constructor traits (MCT)

Based on Jones (1995).

This are traits or type classes on higher-kinded types, which allows us to declare Functor, Applicative, Monad, and Traversable from Haskell/PureScript.

// Declare a trait where collection `c` collects elements `e`
// Note that `c` is used as a _type constructor_ taking `e` as an argument in the signatures below
trait Collects(e, c) {
  fn reduce(over collection: c(e), with fun: fn(a, e) -> a) -> Result(a, Nil)
  fn insert(into collection: c(e), element x: e) -> c(e)
  ..
}

// Implement for lists
// Note that `List` is used as a _type constructor_ without arguments
impl Collects(e, List) {
  fn reduce(..) {..}
  fn insert(..) { .. }
  ..
}

// Use in function
fn sum(xs) ->  {
  reduce(over: xs, with: (+))
)
// The inferred type for `sum` is
fn(c(e)) -> Result(e, Nil) where Collects(e, c(e)), Calcs(e)

Note that with this extension, one can crate instances for List, Set, Queue, etc, but not for String or Binary as both are concrete types and not type constructors.

Pros:

• Full type inference
• Hierarchies
• Grouping of functionality
• Can have default implementations
• Solves problems 1 and 2 and 4 and even more

Cons:

• Partially solves problem 3
• Needs higher-kinded types and a kind checker

Multi-parameter type constructor traits with functional dependencies (MCTD)

Obviously, we can combine above solution with functional dependencies, which is exactly what Haskell and PureScript do. (Concrete examples left as exercises to the reader ;-))

[timjs]

Opened #1284.

[saolof]

Just wondering about what prevents you from abstracting over collections with O if you do it like in Haskell's lens library? I.e. work with traversals instead of with traversables. Pretty much every collection function can take a:

type LensLike f s t a b = (a -> f b) -> s -> f t

with minor variations on what f is allowed to be, which could be made less polymorphic by specializing f to various weakenings of the continuation monad for different optics and by allowing interfaces where functions return existential types. Go went for a concrete variation on that with range over function, though of course that is in the context of an imperative language where closures have side effects.

[timjs]

Hmm, interesting thought. I don't see immediate similarities between Go's new generics and Haskell's lenses. Can you explain that more? Also, note that Gleam also isn't a pure language, and closures in Gleam can have side effects.

[jrstrunk]

What side effects can gleam closures have?

[lpil]

There's no restrictions on side effects in Gleam.