Implement abilities

[ayazhafiz]

Richard wrote up a design for abilities (Roc's take on typeclasses) here: https://docs.google.com/document/d/1kUh53p1Du3fWP_jZp-sdqwb5C9DuS43YJwXHg1NzETY/edit

As this is an important feature for the language's evolution, I'd like to see if we can begin making traction on implementing it in the near future. As a first step, we need to decide on some implementation decisions, at least for the "first iteration" of abilities. Some things to consider:

• How should functions associated with abilities be passed around? That is, dictionary passing, pure monomorphization, the trick Swift does, or something else?
• Abilities will need to have their own set of resolution rules. What will that resolver look like? Can we get away with path-walking and union-find-like optimizations like we do with the unifier, or do we need a more sophisticated constraint solver like chalk? (My inclination is that the answer is "no", or at least "I hope not" :) )
• Can abilities inherit other abilities?
• What is the concrete set of built-in abilities Roc will support? How will those be derived for user-space types?
• Abilities depend on newtypes; we will need good error message reporting mechanisms for when someone uses a type that looks really similar to a newtype that has a certain ability, but is not actually that newtype. The behavior of this mechanism needs to be sketched out.
• Other things I'm missing, please edit this comment and add them here :)

Status:

• [x] Parsing

  • https://github.com/rtfeldman/roc/pull/2714
  • https://github.com/rtfeldman/roc/pull/2802

• Stage 1 (basic support for abilities):

  • [x] Can
    • https://github.com/rtfeldman/roc/pull/2804
    • https://github.com/rtfeldman/roc/pull/2805
  • [x] Infer/check
    • https://github.com/rtfeldman/roc/pull/2838
    • https://github.com/rtfeldman/roc/pull/2842
    • https://github.com/rtfeldman/roc/pull/2853
  • [x] Codegen
    • #2857

• Stage 2 (expanding where abilities can be used):

  • [x] #2879
  • [x] #2881
  • [x] #2880

• Stage 3 (Encode/Decode, and derived abilities):

  • We want to support Encode/Decode
  • [x] Solve ability specializations at the front
  • [x] Resolve monomorphic specializations during solving
  • [x] Deal with resolution of specializations behind let-bindings (https://github.com/rtfeldman/roc/pull/2910#issuecomment-1120503734)
  • [x] Typechecking types that derive builtin abilities
  • [x] Codegen for builtin abilities on structural types
    • Note: we must operate on layout here, not on the surface type!

• Stage 4 (ability hierarchies):

  • [ ] Add the syntax for an ability hierarchy chain
  • [ ] Typechecking of ability hierarchy chains
  • [ ] Mono/codegen of ability hierarchy chains

• Maybe:

  • [ ] Admit type arguments in abilities
  • [ ] Typechecking abilities with type arguments

• Papercuts:

  • [x] #2878

[rtfeldman]

How should functions associated with abilities be passed around? That is, dictionary passing, pure monomorphization, the trick Swift does, or something else?

I always had monomorphization in mind for this. 🚀

[ayazhafiz]

Yeah, that's where my heart is too. Anything else would actually be harder, since we monomorphize all types today!

[rtfeldman]

What is the concrete set of built-in abilities Roc will support? How will those be derived for user-space types?

The ones I'm confident we'll want: Eq, Sort (aka Ord), Hash, Encode, and Decode.

As far as how they'll be derived, here's one idea for how to infer if something is eligible for all 5 of these. (If the type doesn't contain a function, we can derive all 5 of them similarly to how we currently automatically generate the implementation for Bool.isEq)

[rtfeldman]

Can abilities inherit other abilities?

Kinda? An important relationship is that if I have something with the Int ability, that must imply that it has the Num ability.

So if I write an 0x1 literal, it should have the type * has Int, and I should be able to pass it to Num.add : a, a -> a | a has Num

I dunno if "inherit" is the right word for that, but "having Int implies having Num" is important!

[rtfeldman]

Abilities will need to have their own set of resolution rules. What will that resolver look like? Can we get away with path-walking and union-find-like optimizations like we do with the unifier?

I think so. Elm's compiler has a concept of "constrained type variables" (which is basically what these are) except that there's a hardcoded set of them in the language instead of being user-extensible like abilities. In Elm's compiler they're implemented completely using the same machinery we already have today - e.g. Comparable, Appendable, etc.

[ayazhafiz]

Can abilities inherit other abilities?

I dunno if "inherit" is the right word for that, but "having Int implies having Num" is important!

Nevermind, I see this is in the document today:

Int has Num, { ... }

[ayazhafiz]

Can I implement an ability for another ability? That is something like

Shaable has {sha256} has Eq

isEq : v, v -> Bool where v has Shaable
isEq = \v1, v2 -> sha256 v1 = sha256 v2
isNotEq : ...

Note this is different from the semantics of Int has Num, { ... } presented above - that says that any type implementing Int must also implement Num

[rtfeldman]

So like "if you have Shaable you automatically have Eq too, with this default implementation, but you can override it if you want?"

[ayazhafiz]

Yes. Similar to how you can define traits for traits in Rust.

[rtfeldman]

That seems like a plausible feature, but I doubt it's something where we'd get a ton of benefit for designing for it up front (as opposed to adding it later if we decide it's a good idea), so I'd default to leaving it out for now, while being open to adding it later if compelling use cases come up!