Overriding traits

[osa1]

One of the things traits don't make easy is overriding an instance used as a part of another instance.

This commonly comes up in traits like Debug or Display (or Show in Haskell) where we have complicated nested types (e.g. lists of sets of AST nodes), and we want to print the thing differently in different use sites.

For example, in one call site I may want to abbreviate some AST nodes, in other I may want to print them in detail.

This can be done with implicits. Example in Koka:

import std/data/rb-set

fun main()
  val set1: rbset<int> = empty().add(123).add(456)
  val set2: rbset<int> = empty().add(789).add(901)
  val list = [set1, set2]

  // Print using the defaults.
  println(list.show)

  // Print with custom element printer.
  println(list.show(?show = fn(set: rbset<int>) {
    set.show(?k/show = int/show-hex)
  }))

fun int/show-hex(i: int): string
  "0x123" // doesn't matter

But this has an issue: if an intermediate type (rbset) between the top-level type (list) and the type we want to override a method of (int) is not accessible (maybe it's a private type) then we can't call its show method and can't override what it calls on its elements.

The good part is, because it's not type directed, if the type has multiple ints (e.g. a pair of list<int>s), we can override some of them but not the others.

I suspect if we had a way of saying "override ToStr instances for I32 in this type" that would probably be good enough.

[osa1]

Scala's givens seems like another solution to this problem: https://langdev.stackexchange.com/a/2183/264

[osa1]

Alternatively we implement implicits (probably resolve based on names, not types, similar to Koka) and use implicits in these kind of use cases.

Implicits may be useful in other contexts too. For example, in PL implementation you may want to pass around some kind of "context" type that you basically never change (only update its fields). It may be convenient to pass these around as implicits.

[osa1]

It would be good if we could implement this without implicits to not add a feature that overlaps with an existing feature (traits) quite a bit in terms of use cases, and without new syntax.

I wonder if we could expose the traits as constant records of functions and give the user to construct their own constant records of functions, to override some of the methods.

For example, we have this Ord trait:

trait Ord[t]:
    cmp(self, other: t): Ordering
    __lt(self, other: t): Bool
    __le(self, other: t): Bool
    __gt(self, other: t): Bool
    __ge(self, other: t): Bool

An implementation of this for U32 would look like:

(
    cmp = fn(self: U32, other: U32): Ordering { ... }
    __lt = fn(self: U32, other: U32): Bool { ... }
    ...
)

or Iterator with an associated type:

trait Iterator[t]:
    type Item
    next(self): Option[Item]

would be implemented as

(
    next = fn(self: VecIter[t]): Option[t] = ...
)

Then we implement:

• A way to update records (which we should do anyway, it would be useful even without this feature).
• A way to pass trait arguments, as records.
• A way to refer to trait records implemented using the impl Foo for X syntax.

This would allow expressing something like: "call ToStr.toStr on this type, using this record for ToStr for U32".

---

Another idea:

with impl ToStr for U32:
    toStr(self): Str = ...      # show the number in hex
do:
    v.toStr()                   # v : Vec[U32]

If we go down this route we should also allow named alternative impl blocks and just referring to them instead:

impl ToStr for U32 as U32ToHexStr:
    toStr(self): Str = ...      # show the number in hex


# In expression context:
with U32ToHexStr do:
    v.toStr()

or maybe with inline syntax as well:

with U32ToHexStr v.toStr()

or perhaps

v.toStr() using U32ToHexStr     # `using` is parsed as a binary operator

[osa1]

This requires quite a bit of refactoring in the current implementation before we can start experimenting.

First, we currently implement runtime polymorphism by indexing a global dispatch table (conceptually, in the implementation we have a bunch of maps and vectors).

This assumes single-parameter traits, which is fine for now.

But it also indexes the dispatch table using the trait method's self argument's type id, which we obtain from the object header.

Since we can't change object header or the dispatch table in x using MyImpl, I don't think we can implement the plan above right now.

Tentative plan:

• Represent traits as constant record passing, as described above.
• Monomorphise generic functions for all types, not just for integers. (currently other types are monomorhpised as "pointers")
• Allow runtime polymorphism only for single-parameter typeclasses.

After this, x using MyImpl will effectively override the constant record for the type of MyImpl in x. The interpreter won't be seeing the using syntax.