Ad-hoc polymorphism

[Pauan]

The ability to have multiple functions with the same name and different types is very nice, but there are still situations where ad-hoc polymorphism is useful.

An example is a function which calls map, it would be nice if it worked with any type which implements map

There are many ways of implementing ad-hoc polymorphism: Haskell typeclasses, ML modules, and creating multiple copies of each function (used by Rust and others).

I propose a simplified typeclass mechanism for Koka.

Any variable can be marked as implicit:

implicit val foo: int = 1

implicit fun bar(): int { 2 }

Function parameters can also be marked as implicit:

fun qux(a: implicit int): int { a }

When a function has implicit arguments and it is called, it will search for implicit variables which are in scope, and if there is an implicit variable which matches the type, it will then automatically pass it in:

// This will be compiled into qux(foo)
qux()

It's also possible to pass in implicit arguments explicitly:

qux(implicit foo)

It's also possible to convert from implicit variables to regular variables, and from regular variables to implicit variables:

implicit val foo: int = 1

val bar: int = foo

implicit val qux: int = bar

And that's it. That's the entire system. With this, it's possible to create Haskell typeclasses by combining type with implicit:

type map<t> {
  Map(map: forall<a, b>(t<a>, (a) -> b) -> t<b>)
}

fun map(i: implicit map<t>, l: t<a>, f: (a) -> b): t<b> { (i.map)(l, f) }

implicit val map-list: map<list> = Map(
  map = fun(a, f) { ... }
)

// This is the same as map(implicit map-list, [1, 2, 3], fun(x) { x + 1 })
map([1, 2, 3], fun(x) { x + 1 })

The above code is equivalent to this Haskell program:

class Map t where
  map :: t a -> (a -> b) -> t b

instance Map [] where
  map a f = ...

map [1, 2, 3] \x -> x + 1

The Koka code is quite heavy-weight on the syntax. This can potentially be solved with the following trick:

rectype map<t> {
  Map(map: forall<a, b>(implicit map<t>, t<a>, (a) -> b) -> t<b>)
}

implicit val map-list: map<list> = Map(
  map = fun(_, a, f) { ... }
)

map([1, 2, 3], fun(x) { x + 1 })

The benefits of this light-weight typeclass system is that it is easy to implement and it's easy for the user to understand. It's the same as regular function arguments... except automatically passed in by the compiler.

It also gives a lot of the same power of ML modules, because it's possible to pass in implicit arguments explicitly, create implicit variables dynamically, and use locally scoped implicit variables.

One downside is that it's not possible to define union for maps or sets, because they assume that there is only a single typeclass instance per type.

Instead, you need to store the Ord instance in the data structure itself and use unionLeft or unionRight (which might be slower than union). This is possible because implicits can be converted into regular values and then stored in data structures.

Another downside is that I'm not sure how to define advanced features like functional dependencies or type families. But maybe the simplicity of implicit is more important than advanced type features.

[Pauan]

Implementation-wise, each compile-time scope would have a list of implicit variables.

When an implicit is looked up, it will check in the current scope.

If there is exactly one implicit variable in the current scope which matches the type, it will use that.

If there is more than one implicit variable which matches the type, it will error.

If there is zero implicit variables, it will then recursively check the outer scope.

This allows an inner implicit to shadow an outer implicit:

implicit val foo: int = 1

fun bar(a: implicit int): int { a }

fun qux() {
  // This shadows the `foo` implicit
  implicit val corge: int = 2
  bar()
}

fun main() {
  println(bar()) // prints 1
  printfn(qux()) // prints 2
}

This enables a form of "dynamically scoped variables" ala Common Lisp. Except unlike dynamically scoped variables (which use mutation), this is safe, because it gets compiled into function argument passing.

---

Also, there is an additional complexity when a function which has implicit arguments is used as a value. For example, when using a higher-order function:

implicit val foo: int = 1

fun bar(a: implicit int, b: int): int { a + b }

map([1, 2, 3], bar)

In this case, the Koka compiler has to create a lambda and resolve the implicit within the lambda:

map([1, 2, 3], fun(a) { bar(implicit foo, a) })

The same is true when storing bar in a data structure.

For performance, it would be useful to do common subexpression removal, so that way the lambda fun(a) { bar(implicit foo, a) } will be hoisted to the top level and reused:

fun bar_(a) { bar(implicit foo, a) }

map([1, 2, 3], bar_)
map([1, 2, 3], bar_)

---

There's some open questions:

• implicit is being used for three things:

  1. Marking a variable as implicit

  2. Marking function arguments as implicit

  3. Explicitly passing in an implicit to a function

  I don't like this interweaving of purposes. I feel like it should be possible to split these into separate orthogonal concepts.

• I'm not sure whether the syntax should be fun foo(implicit a: int) {} or fun foo(a: implicit int) {}

  • implicit a: int is better because it implies that the function argument itself has special behavior (which is correct)

    It also is more consistent with implicit val foo: int = 1

  • a: implicit int is better because it allows you to specify implicit in types:

    val foo: (implicit int, int) -> int
    

    It also has a better intuition when using higher-order functions: when an (implicit a) -> b is used in a context which expects a () -> b it will coerce the function into a lambda and resolve the implicit

[Pauan]

Also, I would really like to use special syntax for implicit int, such as @int, because implicit is really verbose. But it seems like Koka already uses all of the special symbols, so there isn't any symbols available.

[Pauan]

I thought about it some more, and I wonder if it would be better to keep implicit and non-implicit variables completely separate. In other words, it wouldn't automatically convert implicit to non-implicit.

Essentially, implicit and explicit variables would have separate types, and therefore cannot be mixed.

It is still possible to manually convert from implicit to non-implicit by using this function:

fun explicit(a: implicit a): a { a }

Now it's possible to convert from an implicit variable to an explicit value:

implicit val foo: int = 1

// The same as `val bar: int = foo`
val bar: int = explicit()

If there are many implicits in scope, you can select the one you want:

val bar: int = explicit(implicit foo)

[Pauan]

Thinking about it further, perhaps we don't need functional dependencies. I'm not an expert on it, but it seems to me that functional dependencies were added to Haskell to prevent ambiguous type inference and to move errors to the place where the function is defined, rather than the place where the function is used.

But with my proposed implicit arguments, ambiguities are already possible (and are resolved by manually passing in an instance), and there is no implicit type inference: implicit arguments must always be manually marked as implicit.

In addition, Haskell allows for values which contain typeclass constraints, such as foo :: (Foo a) => a, but that would not be allowed with my proposal: only implicit function arguments can be polymorphic. In other words, variables are always monomorphic. Therefore the monomorphism restriction is not needed.

This creates a simpler mental model for the programmer, and it is also closer to the implementation: polymorphic values in Haskell are actually functions, because they can be instantiated with different typeclass instances.

With my proposal, they would actually be functions, rather than something which looks like a value but is actually a function. This preserves the mental model that using a variable is cheap, and doesn't involve arbitrary computation.

So in practice functional dependencies might not offer any advantages, and therefore we don't need to clutter up the simplicity of my proposal.

[Pauan]

It's also interesting to note that algebraic effect handlers provide a lot of the same functionality as typeclasses.

For example, consider this Haskell typeclass:

class Add a where
  add :: a -> a -> a

instance Add Int where
  add left right = left + right

genericAdd :: Add a => a -> a -> a
genericAdd left right = add (add (add left right) right) right

main :: IO ()
main = print (genericAdd 1 2)

We can define that in Koka like this:

effect add<a> {
  add(left: a, right: a): a
}

val add-int = handler {
  add(a: int, b: int) -> resume(a + b)
}

fun generic-add(left: a, right: a): add<a> a {
  add(add(add(left, right), right), right)
}

fun main(): console () {
  println(add-int({ generic-add(1, 2) }))
}

However, I suspect this doesn't provide quite as much flexibility as typeclasses do, and it's a bit conceptually weird to use a "side effect" system for non-side effect polymorphism.

It's also rather clunky to use, because we have to explicitly call add-int. But we generally only need to call add-int at the top level of our program, because the effects will propagate downward automatically.

I also have some concerns about the efficiency of using effect handlers for this: typeclasses are quite efficient, since it simply involves the compiler automatically adding an extra argument to functions.

This means that programmers can freely use typeclasses all the time, without worrying about performance. This leads to more abstract libraries, which in turn helps reduce code duplication. I am a huge fan of Rust's motto of "zero-cost abstractions", which is one of the reasons I'm a huge fan of typeclasses.

However, despite those concerns, it may be worthwhile to explore whether it's possible to avoid adding typeclasses, and instead rely solely upon effect handlers.

[Pauan]

As an alternative to my proposal, we could instead have "implicit effect handlers", which are the same as regular effect handlers except that they are automatically applied based upon the type context:

val add-int = implicit-handler {
  add(a: int, b: int) -> resume(a + b)
}

fun main(): console () {
  println(generic-add(1, 2))
}

When an effect needs to be discharged, it will search the current and parent scopes for an implicit handler and will then automatically call it. So the above code would be equivalent to this:

fun main(): console () {
  println(add-int({ generic-add(1, 2) }))
}

This also answers the question of "how does Koka know to automatically apply the async-handle handler when calling main with an async effect?"

I haven't thought this through, so I'm still hazy on the details, but it's an alternative to consider.

[Pauan]

Something else I thought of: is it possible to implement the effect system using implicit parameter passing? That should offer a significant performance boost.

If it's possible, I think that would make it viable to use the effect system to implement ad-hoc polymorphism. Then the only thing missing is implicit effect handlers.

[Pauan]

If we decide to use the effect system instead of typeclasses, I think it would be useful to rename it. It's very weird to use the word "effect", because we're not really using it for side effects, we're just using it solely for polymorphism.

I think a good suggestion is to use protocol to create an effect, and implement to create a handler:

protocol add<a> {
  add(left: a, right: a): a
}

val add-int = implement {
  add(a: int, b: int) -> resume(a + b)
}

fun generic-add(left: a, right: a): add<a> a {
  add(add(add(left, right), right), right)
}

fun main(): console () {
  println(add-int({ generic-add(1, 2) }))
}

This naming still works for side effects (like exn, async, etc.), because the purpose of the effect system is to add new effects to the language, and these new effects describe a protocol which must be implemented by handlers.

Some other good suggestions: interface / implement, require / provide, contract / fulfill

[Pauan]

Another option is to use standard OOP interfaces:

interface add<a> {
  add(left: a, right: a): a
}

fun generic-add<a implement add<a>>(left: a, right: a): a {
  add(add(add(left, right), right), right)
}


implement add<int> {
  add(a, b) -> a + b
}


struct my-int(value: int)

implement add<my-int> {
  add(a, b) -> my-int(add(a.value, b.value))
}


generic-add(1, 2) // -> 7
generic-add(my-int(1), my-int(2)) // -> my-int(7)

In C# this would be compiled down to regular C# interfaces.

In JavaScript this can be implemented in a variety of ways, but here is one possibility:

Number.prototype._type = "std/core/int";


var add_vtable = {};

function add(left, right) {
  return add_vtable[left._type].add(left, right);
}

function generic_add(left, right) {
  return add(add(add(left, right), right), right);
}


function add_int_add(left, right) {
  return left + right;
}

add_vtable["std/core/int"] = {
  add: add_int_add
};


function my_int(value) {
  return { _type: "path/to/my-int", value: value };
}

function add_my_int_add(a, b) {
  return my_int(add_int_add(a.value, b.value));
}

add_vtable["path/to/my-int"] = {
  add: add_my_int_add
};


generic_add(1, 2); // -> 7
generic_add(my_int(1), my_int(2)); // -> my_int(7)

A few things to note:

• Interfaces get turned into functions + a vtable.

• This is slower than typeclasses, and it's also less powerful (typeclasses can dispatch on multiple arguments, and typeclasses can dispatch on the return type).

• Because the implementation is (indirectly) attached to the type rather than passed in implicit arguments, it's easy to pass a type deep down the call stack without any problems, whereas typeclasses require the implicit arguments to be threaded through the entire call stack.

  This gives a bit more runtime flexibility at the cost of reduced performance and increased memory usage.

  One major benefit of having the implementations attached to the type is that it's easy to create things like list<add<a>>, which is a list where every element implements the add interface. This lets you combine multiple types into a single list, as long as every type implements the appropriate interfaces. This kind of polymorphism is trickier with typeclasses (but still possible).

• All types need to have a _type property, which must be unique per type. In this case I'm just using the fully qualified name of the type.

• Built-in JavaScript types can be given a _type by abusing the prototype (e.g. Number.prototype, String.prototype, etc.)

• It's very tricky to create implementations for functions (e.g. implement add<(a) -> a>), whereas it's trivial with typeclasses.

• When the type is known, it doesn't need to call the add function, instead it can call the implementation directly. Therefore the add_my_int_add function can just call add_int_add rather than calling add.

  This is true with typeclasses as well.

[b-studios]

@Pauan I don't know whether you are still interested, but ...

Something else I thought of: is it possible to implement the effect system using implicit parameter passing?

Actually, this is what I do in Scala Effekt. This works really great in particular with Dotty's new implicit function types.

Also you might be interested in #68 and #69 where I started to implement implicits in Koka. There are still some barriers to use the implicits as implemented there for ad-hoc polymorphism, but it is a first step.

[Pauan]

Actually, this is what I do in Scala Effekt.

I get a 404 for this page, but I took a look at the code, it's very cool!

Also you might be interested in #68 and #69 where I started to implement implicits in Koka

Yeah, I saw those. Nowadays I use Rust (and I'm quite happy with it), but I'm glad to see things progressing with Koka. I still like its clean, minimal design.

[b-studios]

Thanks for letting me know about the breakage of my page! Sad to hear you moved to Rust, I would have been interested how migrating the large code base to Koka went.

[TimWhiting]

@Pauan

Interestingly I separately came up with a similar system in #336, which has now been implemented in Koka by Daan. However, my approach proposed using names instead of types and explicit implicit declarations. Your approach seems more similar to what Scala has implemented for implicits. There seems to be a wide range of approaches and ways a compiler could determine what to automatically pass in as an implicit parameter, and these two approaches are just a few points on that spectrum.

When I talked with Daan, implicit effect handlers seemed like a bad idea after thinking it through more thoroughly. Effect handlers are dynamically scoped and can easily be intercepted, which is not really something desirable for ad-hoc polymorphism. Interestingly, sometime after your comment #16 (comment) effect handlers in Koka were altered to work by passing evidence down (implicitly in the runtime), and it is very performant like you predicted https://www.microsoft.com/en-us/research/publication/generalized-evidence-passing-for-effect-handlers/.

Hope you give Koka a try again sometime soon, and leave some feedback on more issues or discussion topics! I'm also a fan of Koka's clean minimal design.

Instead of closing this issue, I'm just going to convert it to a discussion topic since I feel like there is definitely interesting (non-issue) ideas that others visiting Koka might be interested in.