Interfaces

[Aloso]

It would be nice if Gleam supported interfaces, which could work similar to Java or Go interfaces, Rust traits or Haskell typeclasses. I think Rust traits would be the ideal solution, but they could prove to be difficult, perhaps even impossible to implement in a dynamic language, so it might be more realistic to adopt something more similar to Java or Go interfaces.

This is not a finished proposal, just some ideas to get feedback.

Motivation

Generics

When passing a value to a function, it's often unimportant of what type this value is, as long as it has a certain capability. Example in Rust:

fn print(value: impl ToString) { // any value that can be converted to a string
    println!("{}", value.to_string());
}

And a more complex example:

fn contains<C, N>(collection: C, needle: N) -> bool
where C: IntoIterator<Item = N>,
      N: PartialEq,
{
    collection
        .into_iter()
        .any(|n| n == needle)
}

The function can be called for any collection that can be iterated over. The iterator generates values of type N, which must implement PartialEq (so it can be compared for equality).

Operator overloading

In Rust, traits are used for operator overloading. For example, the PartialEq trait overloads the == and != operators, PartialOrd overloads the <, >, <= and >= operators, Add overloads the binary + operator, Drop overloads destructors, Fn overloads function calls, Try overloads the ? operator (equivalent to the try keyword in Gleam) etc.

Traits like Add, Sub, Mul and Div are useful when creating types such as complex numbers, vectors, big integers or date/time primitives that support arithmetic operations. PartialOrd is useful when a type should be sortable, like numbers, strings, dates/times, IP addresses, etc. Drop is useful when a type allocates memory, opens a file, locks a Mutex or acquires any other kind of resource, and should release the resource when it is destructed.

I guess not all of these can be applied to Gleam, since Gleam is dynamic and garbage collected.

Of course, traits aren't strictly necessary for operator overloading. Instead, we could use the same approach as e.g. C++, C#, Scala and Kotlin, by adding special methods:

// overloading `+` in Kotlin:
data class Counter(val index: Int) {
    operator fun plus(increment: Int): Counter =
        Counter(index + increment)
}

Designs

Java

Rust, Go and Java have very different approaches to interfaces/traits: In Java, each type must specify which interfaces it implements:

public interface Geometry {
    double area();
}

public class Rect implements Geometry {
    double width;
    double height;

    public double area() {
        return width * height;
    }
}

Go

In Go, interfaces are implemented implicitly for all types that have a certain set of functions:

type Geometry interface {
    area() float64
}

type Rect struct {
    width, height float64
}

func (r Rect) area() float64 {
    return r.width * r.height
}
// now Rect implements Geometry!

Rust

Rust traits are similar to Haskell typeclasses. In Rust, the implementation is explicit like in Java, however, traits can be implemented for types from a different package:

trait Geometry {
    fn area(&self) -> f64;
}

impl Geometry for Rect {
    fn area(&self) -> f64 {
        self.width * self.height
    }
}

// this type could be defined in a different package:
pub struct Rect {
    pub width: f64,
    pub height: f64,
}

Rust traits can be implemented generically, e.g.

trait Foo {}

impl Foo for bool {}
impl<T: Foo> Foo for Vec<T> {}
impl<T: Clone + Default> Foo for T {}

A Rust trait can have associated types, and can refer to itself with the Self type. For example, Add is defined as:

pub trait Add<Rhs = Self> {
    /// The resulting type after applying the `+` operator.
    type Output;

    /// Performs the `+` operation.
    fn add(self, rhs: Rhs) -> Self::Output;
}

This makes Rust traits much more powerful than Java/Go interfaces. There is a limitation however: Some traits aren't object safe and therefore can't be used with dynamic dispatch. For example:

trait Foo {
    fn foo(self, rhs: Self);
}

If Foo is used with dynamic dispatch, we don't know what the Self type is, we only know that it is some type that implements Foo. But the foo() method requires that both arguments have the same type, which can't be enforced, so the above trait can't be used with dynamic dispatch.

[lpil]

Gleam isn't a dynamic language, so we should not have any problems there implementing traits/interfaces.

Whether this kind of metaprogramming is the right fit for Gleam is not yet clear. It is powerful and enables very concise APIs, but it adds conceptual complexity and does not make the language more capable.

Here's some previous thoughts:

• https://github.com/gleam-lang/suggestions/issues/67
• https://github.com/gleam-experiments/experiments/blob/master/traits.gleam

[Aloso]

P.S. Gleam is "dynamic" in the same sense as TypeScript, because it compiles to a dynamic language, and uses dynamic dispatch everywhere by default, instead of monomorphizing generic functions, if I'm not mistaken.

This makes it difficult to implement functions that are generic over their return type, like collect or parse. If you look into the source, you'll see something like T::call_function(), where T is a trait or a generic argument.

I guess this could be solved somehow, but I doubt that it will be easy. Rusts type system is Turing complete, after all.

[lpil]

The solution there is to pass around a implicit argument that's a dictionary containing the implementing functions for that data type. This is how OCaml does it (though explicitly), and how Haskell's type classes work (though they may be monomorphised during optimisation).

We could also perform some amount of monomorphising to improve performance.

Codegen for one such system can be seen here https://github.com/gleam-experiments/experiments/blob/master/traits.gleam

[jalberto-ghub]

A probably interesting alternative would be to associate interfaces to Gleam modules. After all core in Gleam, like in Erlang lives in modules. That would allow having generic implementations that could be passed as first class objects.

As long as the module implements the same interface, they can be passed similar to a function around.

[lpil]

Modules could be a good foundation for runtime representation, though the inability to compose modules means that generic or composable interfaces becomes largely impossible. For us it is a shame that tuple calls were removed

[jalberto-ghub]

I was thinking more in the sense of modules implementing interfaces:

A.gleam:
implements Collection // uses lists as the representation

B.gleam
implements Colection // uses some super data-structure for very large collections

Now you can have an Agent that requires a collection to represent and manipulate its state. You can now initialize the Agent which whatever of the two implementations that best fit the use case. In other words the message-handler function for this agent can receive the collection implementation to use.

[lpil]

Oh I see, we're talking more language design than runtime implementation.

What would be the advantage of using a module here over records? Records can be constructed and composed at runtime, which is a big advantage.

[jalberto-ghub]

I am very new to Gleam but as opposed to types, it seems to me behaviours are defined by modules and not by types.

It may make sense for a module defining a Type to implement comparable. But do we really want to straightjacked the sort algorithm that we should use when trying to order elements of that Type? No, that would be a responsibility of the module using the type in some data-structure. But should we forced a priory a module that requires doing some sorting to actually pick whether to use insert/bubble/merge/quick-sort?

Why can't we allow the developer to be able to indicate what to use (or to change the default used by the module) without needing to rewrite the rest of the module functionality just because the need to use a different sorting.

Maybe I am thinking more in the sense of Clojure's Protocols: A module provides one or more protocols (set of "function signatures") and any other module needing such functionality can use it. But not only use it, but being instantiated (composed) to use a particular implementation of the protocol.

MyModule.gleam

import mergesort
import fooModule(sorting: mergesort.SortingProtocol)

pub fn doStuff(x, y) {
   fooModule.doFoo(x, y) // doFoo calls functions in the SortingProtocol
}

pub fn doStuff2(w) {
  fooModule.doFoo2(w) // doFoo2 may not make any calls to the SortingProtocol, but I do not need to know
}

I mean this is not necessarily the syntax, but I think you get my drift.

[lpil]

That works, but I think we want to also consider generics and interface composability

Generics

Imagine these two interfaces

interface Add {
  fn add(self, self) -> self
}

interface Fold(element) {
  fn fold(self, acc, fn(element, acc) -> acc) -> acc
}

With modules both can be implemented, but we are not able to implement this sum function because it requires a specialisation of Fold, which isn't something we can do with modules because there's no way to inject the Add implementation into the Fold implementation.

fn sum(items: Fold(n)) -> n
  where n: Add

The only thing we can do is generate additional modules at compile time, but this means we need to make a full copy of the two modules for every combination of types for every package they are used in. This would generate a lot of code, slowing compile times and making the app size grow a lot.

Composability

It would also be desirable to have functions take arguments that implement multiple interfaces:

fn play(dog: Animal + Friend) -> Nil

This is not possible with modules again, we would need some form of container data structure for them like a record. If records are used to combine modules it begs the question why not always use records in place of modules?

[jalberto-ghub]

These are interesting issues. I really do not like the name interfaces, it is too OOP for a FP language. For example the use of self makes me think that these are functions intrinsic to a value type. Their implementation is part of the Type which brings the language too close to OO for me. So I will describe it as behaviours, implemented in some code (module) which is closer to the terminology used by Erlang.

I can understand having add as a behaviour because you obviously can have multiple implementations for modules implementing different Types, but also as stand-alone algorithms implementing different strategies to achieve a goal. I am not sure about having multiple implementations of fold as to requiring it to be a behaviour but for the sake of argument, let's say we want that.

adder.gleam

pub behaviour Adder(x) { 
   fn add(x, x) -> x  // This function only can combine things of the same type, by definition
   fn zero() -> x
}

reducer.gleam

pub behaviour Reducer(iter(e), y) { // Here iter(e) is some parameterized type, like a gleam/Iterator
  fn fold(iter(e), y, fn(e, y) -> y) -> y
}

folder.gleam

import gleam/iterator
import adder.{Adder}
import reducer.{Reducer}
provides Reducer(Iterator(y), y)
requires(adds: Adder(y))  // adds is a variable representing the module to use you have one for every behaviour required

pub fn fold(
  iter: Iterator(y),
  initial: y
) -> y {
  iterator.fold(over: iter, from: initial, with adds.add)
}

numerics.gleam

import adder.{Adder}
   provides Adder(Int)

pub  fn add(x: Int, y: Int) { x + y }

pub fn zero() { 0 }

myModule.gleam

//// Concrete implementation of sum
import gleam/iterator.{Iterator}
import numerics
import folder(numerics.Adder)

pub fn sum(over iter: Iterator(Int) {
  folder.fold(iter, 0)
}

myModule2.gleam

//// Generic implementation of sum
import adder.{Adder}
import reducer.{Reducer}
requires(adds: Adder, red: Reducer)
provides Totaler(x)

pub behaviour Totaler(x) {
   fn sum(iter(x)) -> x
}

pub fn sum(iter) {
   red.fold(iter, adds.zero())
}

[lpil]

For this behaviour and implementations of it what Erlang code would be generated? I don't see how this could be implemented using modules.

pub behaviour Reducer(iter(e), y) { // Here iter(e) is some parameterized type, like a gleam/Iterator
  fn fold(iter(e), y, fn(e, y) -> y) -> y
}

What code does provides and requires generate?

[jalberto-ghub]

That is a good question, how to implement it on a language like Erlang. By the way, remember these are just ideas. I am not hooked on any specific syntax. I am just trying to not conflate the world of Types (sets of possible values) with the world of the generic operations that may apply to any set of values.

If one had free hand on designing the scoping rules of a language, I would say behaviour defines a Type whose values are the set of name/signature functions. So provides should generate an instance of such type. But the main role of provide is so that at compilation time we can verify: (a) that the module actually provides the functions of the behaviour in a type consistent manner (i.e. add & zero are type consistent) ; and (b) when the module is imported the types the compiler can check what it is provided.

Similar for requires. Notice in my example I use the same definition of Adder & Folder coming from the same module all throughout. Should that ne a requirement? Or should two behaviours in different modules with the same name and function signatures be treated as the same? I do not know. I leave that yo you. If we thing of them as a type, maybe there is no difference of which file they were defined. I guess they should behave like any other type in gleam.

Now, about implementation (this is absolutely bonkers stuff coming from the top of my head):

If behaviour defines a type, then provides defines a value for that type. The important thing here is that the value is always a constant with respect to its requires so you can recreate it cheaply at any time.

Ideally you would want the behaviours to be available as part of the execution context, we do not want to macro expand the whole module like a template. But I do not know how doable that is on the BEAM.

But what we could do is to say that module providing behaviours A, B & C defines a function(s) that given the behaviour returns the behaviour's instantiated value. So

numerics.provides_Adder() -> 
    #Adder{ add =  fn (x, y) {numerics.add(x,y)}, zero = fn() {numerics.zero()} } // encapsulation may not be needed

Having this, makes the behaviour instantiated functions available at any point.

Probably a more complicated question is how to implement require. I see two alternatives: (a) pass the behaviours as an extra parameter to all functions in the module; (b) this is a parameterized module, therefore you have two levels of functions, that would keep the arity of the actual implementation intact.

For (b) it would be something like:

folder.gleam

provides( Reducer(Iterator(y), y) )
requires(adds: Adder(y))

pub fn fold(
  iter: Iterator(y),
  initial: y
) -> y {
  iterator.fold(over: iter, from: initial, with adds.add)
}

becomes:

fn meta_fold(adds: Adder(y)) {
  fn (
    iter: Iterator(y),
    initial: y
  ) -> y {
    iterator.fold(over: iter, from: initial, with adds.add)
  }
}

pub fn provides_Reducer(adds: Adder(y)) {
  fold = meta_fold(adds)
  #Reducer{fold = fn(iter, initial) { fold(iter, initial) }} // fold on the behaviour is a flat function signature.
}

And myModule.gleam

import folder(numerics.Adder)

pub fn sum(over iter: Iterator(Int) {
  folder.fold(iter, 0)
}

becomes

import folder

pub fn sum(over iter: Iterator(Int) {
  adder = numeric.provides_Adder()
  folder = folder.provides_Reducer(adder)
  folder.fold(iter, 0)
}

There may be all kinds of issues here, but I think you can see where I am going with it.

[lpil]

The question is how the parameterised module you've mentioned would work. This functionality was removed from the BEAM so we would not be able to use modules as the basis of interfaces in this way.

[jalberto-ghub]

How does Erlang implements behaviours? There is nothing above that depends of module variables or anything like that. If is all functions

[lpil]

Erlang's behaviours are not composable or parameterisable, they are very limited compared to interfaces in most languages. Injecting the implementation is also always done manually by the programmer by providing it as an argument to the function that usees the behaviour, there's no language support for this. This can be done today in Gleam with records and we do so in Gleam OTP library