Bounded polymorphism and typeclasses - ideas #502
Comments
|
This is a proposal for adding typeclasses to Unison, highlighting differences to the Haskell system. The basic concepts of classes, instances and (appropriately sugared) dictionary-passing are all there, with some variations. What do people think? What do people see as the main drawbacks? The basic gist is
All instances are named instancesWe want Unison code to live in an 'open universe', where (as Paul said here) "people can after the fact discover common structure and layer it onto existing data types". So it's a problem if we let one author define a canonical instance for a type - any instance someone else defines is now second-class. So let's not have any canonical instances. Let's say all instances are named, and the coder needs to choose which they want to use. So to define an instance you'd say something like and then your instance is named One upside of letting go of canonical instances, is we're no longer steered towards making unnatural choices: we don't have to choose whether the default And particularly for Unison, it's good not to have to deal with the environment data of 'which typeclass instance goes with which type': we don't have modules/files to put this information in, and we certainly don't want to have that information existing separately for every term. The user can see and control the dictionary-passing, when they need toThe choice and plumbing of dictionaries needs to be under the coder's control. So they can specify them explicitly, and sometimes this is mandatory: Unison will never silently assume that the coder means to use Explicitly visible dictionary argumentsSuppose we have a typeclass method like this... Now consider these definitions, and how they're explicitly passing and pattern-matching on dictionary arguments, using a The Elided dictionary argumentsTo make a given instance the default in some scope, you write a In the following case, a There's a nice parallel between
The pretty-printer will render the code clearly even in cases where there are several instances in play for the same type: Classes as recordsA class declaration is just a record declaration but where some of the accessors use So whereas produces (amongst other things) an accessor function if we instead make it a class then the generated accessor is: CoherenceThere isn't any 😄 Or rather, if your function consumes/produces data that includes a choice of instance amongst its invariants, you'd better say so in your API docs, like this: (Hopefully comments like that can be attached to the argument/result in question, and in a standard format.) Maybe it's because I'm not a true haskeller, but I don't see this as a problem. Of all the various invariants and assumptions we code into the data we work with, which we don't manage to capture in types, questions of which instance we're using are only a small minority. Maybe there's some future in which a dependently-typed Unison lets us reach greater perfection by encoding instance choice in types, but til then I don't think we need to sweat it. Subclasses?Ideally you'd only need to specify Maybe we should look into more general record subtyping / row polymorphism / extensible records stuff as an approach to this? So, one record type extending another when it has a superset of the fields. To me, record subtyping seems to be a general setting into which interface extension fits quite nicely, so I like this idea, but I am a bit scared off by what an ordeal it seems to be for haskell. This is a big question, but maybe for starters we should see how things shake out without doing anything special here? Background readingTerminologyIn the above, I've used 'class' and 'instance' to make it more familiar. But I'd actually propose using the Idris terminology of 'interface' and 'implementation' instead. It emphasises that it's fine to have multiple interfaces to a given type - rather than a type belonging irrevocably to a given class in just one way. Also we wouldn't actually talk about 'dictionaries', but probably 'interface arguments' or 'interface parameters'. Less important notes
syntax, but instead make it even clearer what's going on: we're just defining a term.
|
|
Interesting proposal! Will noodle on it. |
|
A few issues/embellishments on the proposal above... View preferenceI was pondering the following example, and doubting whether it's really OK to make the user type out all the instances they're using! Making the user spell out those two The notes above suggest one approach to making this less verbose: allow the user to specify their preferred default instances as part of some 'view preferences' - kind of their own personal lens through which they view the code. Given the usability worry, I'm now thinking this is a necessary part of this proposal, rather than just an add-on, so I'd just like to develop the idea a little bit further. Suppose you could configure Unison with a preference to automatically use (unique) instances from some parts of the branch, say everything underneath If someone else has different view preferences then they'd see the code pretty-printed with Wiring together instancesBack in the I'm not sure where it happens, but somewhere between saying that Unison can do that trick, and allowing the user to throw in Is there any world in which we side-step cases that make this hard, at least for now? Maybe by restricting what instances can be in play simultaneously? Or making the user wire up more challenging cases manually? Zero-parameter typeclassesZero-parameter typeclasses seem like they'd be useful, and I can't see why they shouldn't be allowed. It's useful to program to an interface, regardless of whether it's an interface to a specific type. This makes more sense once you're calling them 'interfaces' rather than 'typeclasses'. Example: |
|
What I find compelling about this proposal is how little it requires of the representation of typechecked Unison programs—just one flag on function parameters indicating whether the actual argument might be left to the compiler to figure out. The exact strategy for figuring out these implicit arguments can be left to the compiler front-end (and possibly differ by the particular Unison dialect). |
|
I want to list a few of the properties of the proposal sketched out above, partly because that helps think about it and assess it, and partly because I've got a proposal for how subclasses could work (further down this post), which threatens one of the properties. Properties of this proposal
Note that it's not obvious why you'd want or need properties 1 and 2.
I dwell on this because the subclassing proposal below is janky enough in how it represents class types, that you might want to hide that under the covers, so losing property (2). Subclasses againSo far this proposal has a gap around subclassing. (I should probably be calling it 'class extension'.) I said:
I'm pretty ignorant about the technicalities of extensible records, but I have a suspicion that they'd be a nice approach to this (and you could maintain property (2) nicely, if that was important to you). Also the fact that elm and purescript both have them (1 - last three screenshots, 2) makes me think they'd be worth looking into anyway. But maybe it's a bit drastic to demand we add them to Unison. The next section sketches out a way of getting subclassing without extensible records. An approach to subclasses via productsIt's a bit janky in a couple of respects, but we could get typeclass extension by making the witness types into products. Paul alluded to this in one of his comments under here. Suppose for starters we've got the basic And suppose we extend it as follows. Let's say that this desugars to a product type, something like... ...and generates the following accessors. Maybe to define an instance you'd say something like this: When actually using these classes, the interesting case is when you have an Even though we're using But in the following example we can't dodge the need for an The user would have to specify how to go from the Now, you could imagine putting a little bit of type-driven smarts into the compiler, for it to work this out itself, but I'm not assuming that in this sketch, since it's getting into dangerous 'implicit conversions' territory. Perhaps in the restricted case of populating a typeclass parameter it would be OK. Less important detail
|
|
For super/subclassing it may be sufficient to provide constraint aliases; then you can do something like this: This happens in Haskell from time to time when you have a ball of constraints that are typically all satisfied together. This means instances of |
|
One interesting situation is when there are two subclasses of a superclass in scope and the code calls a function from the superclass, as in class Eq a = { ... }
class Eq a => Ord a = { ... }
class Eq a => Hash a = { ... }
foo : Ord a, Hash a => a -> a -> Boolean
foo x y = x == y -- ambiguous ==, one from Ord, one from HashThis is not a problem when there is typeclass coherence. Without coherence, it would be worthwhile to consider how any given proposal would resolve this issue. |
|
Hey just a quick comment, I think this discussion is interesting and please continue (I'm reading everything) but just FYI we probably won't have time to do much with this in the short term, are focused on more basic stuff for M1. :) |
|
Another variation would be to make class extension only a matter of code generation. That is, class Eq a = {
(==) : a -> a -> Boolean
}
class Eq a => Ord a = {
compare : a -> a -> Ordering
}would desugar to class Eq a = {
(==) : a -> a -> Boolean
}
class Ord a = { -- note no more relation to Eq
(==) : a -> a -> Boolean
compare : a -> a -> Ordering
}Like extensible records, this retains property (2) classes are just record types, but otherwise needs explicit conversion from |
|
This paper may be interesting. It describes dynamic binding in Koka, using algebraic effects. |
|
On the topic of approaches to this via abilities/effects, see slack discussions starting with the idea from @runarorama here. |
|
This comment discusses @runarorama's idea of using abilities as Unison's take on typeclasses. This is my current favorite approach. I initially thought that the ability mechanism was too powerful to be used as a typeclass system, like trimming flowers with a chainsaw... but now I'm seeing abilities as a generalization of typeclasses, and have a feeling of 'oh, the answer was in front us all along'. My main worry is around performance of the generated code, thinking ahead to the day when that's the sort of thing we worry about! I think we'd need a path to being able to say that 'typeclass-style' abilities don't give you a performance penalty on account of using the ability mechanism. That line of thinking (which I'm not very confident in) has brought me round to saying that typeclass-style abilities should get their own syntax (maybe In a nutshell, the proposal is:
Abilities as typeclasses - what it could look likeLet's step through how we'd express a Ability declarationuse .base
use .base.io
ability Monoid a where
mempty : a
mappend : a -> a -> aWe use an ability as our class declaration. This feels nice. An ability declaration looks just like a Haskell class declaration. Using a methodNow let's use our typeclass: mconcat : [a] ->{Monoid a} a
mconcat xs = List.foldb id mappend Monoid.mempty xsWe've expressed Overall this also feels nice. Calling a polymorphic functionWe've got our function using bounded polymorphism, now let's try and call it at a specific known type. hi : [Text] -> Text
hi xs = handle monoidText in mconcat ("Hi " +: xs)This is less nice. To avoid having a Haskell doesn't make you do type anything at all here: when a typeclass constraint can be resolved to something with no type variables, it goes and finds/constructs an instance for you to satisfy the constraint, without you having to say anything. Would we want to be able to write the following? hi' : [Text] -> Text
hi' xs = mconcat ("Hi " +: xs)For that to work we'd need to have told Unison that
By same the argument as mentioned in 'All instances are named instances' further up this thread, I don't think we want a public canonical handler But we could have a personal one - say you tell I think it's too tricksy to sometimes elide the handler entirely, and sometimes not. Given that there's semantically meaningful information lurking in the program around the call to I'm proposing the least intrusive possible cue, a single character 'conversion' operator: hi'' : [Text] -> Text
hi'' xs = ~(mconcat ("Hi " +: xs))Note the The Defining a handlerHere's how that looks: monoidText : Request (Monoid Text) a -> a
monoidText r = case r of
{ Monoid.mempty -> k } -> handle monoidText in k ""
{ Monoid.mappend x y -> k} -> handle monoidText in k (x ++ y)
{ a } -> a(Note how it has a special form in which each case uses Plus throw in a bit of extra ceremony required by the tilde conversion mechanism (or I guess we could make Unison do this under the covers): .base.conversions.monoidTextConversion : '{Monoid Text, e} a -> '{e} a
.base.conversions.monoidTextConversion a = '(handle monoidText in !a)Yuk, seven (or five) lines of obscure stuff, just to say what Haskell says with instance Monoid Text where
mempty = ""
mappend = (++)I guess we could consider expanding the following... instance monoidText : Monoid Text where
mempty = ""
mappend = (++)into the full term of type Performance of the generated codeThis section ends up arguing towards the conclusion that the typeclass use case should get its own kind of ability (called 'interface' say). Let's take another look at this: mconcat : [a] ->{Monoid a} a
mconcat xs = List.foldb id mappend Monoid.mempty xsI think a key concern here is our prospects for compiling this to fast code. I believe today ability request calls are dispatched in the runtime by throwing exceptions. I'm sure this is something that could be attacked with optimization strategies at some point, but fundamentally in the general case an ability request dispatch is likely to be different to a regular method dispatch (e.g. consider the case where the continuation is used twice, and how that would interact with how optimizations are able to treat the stack frame.) But I think we need to get to the point where we can see a plausible future path to compiling typeclass-style request calls to regular method dispatches. Otherwise, by forcing people to go into the more general setting of abilities to get polymorphic function dispatch, we've forced them to take a performance hit, which is never going to go away. So what is a 'typeclass-style' handler? It's one of the form h : Request Foo a -> a
h = case r of
{ Foo.x p q … s-> k } -> handle h in k (x' p q … s)
…
{ a } -> a(A) Each case is linear in the continuation Would it help if Unison had linearity tracking in its type system? It would help for (A). Maybe we could say that h : 1 Request Foo a -> awas linear in the continuation (and request arguments), and we'd require that a linearly-used ability was handled by a linear handler. But even if that worked out, that doesn't give us conditions (B) or (C). So I suspect actually we'd need just a separate kind of ability ( That then strengthens the case for the The above line of reasoning would be bogus if we didn't actually need to compile method dispatches differently between the ability and interface cases - for example if the optimization for the interface case was handled as part of some later global optimization pass over the build. I don't know how that would work though. (Note here I'm assuming there is still, one day, a whole-codebase build step used in perf-critical cases.) Other issues{Monoid a, Monoid b}As Runar pointed out, we don't have good support for ability lists where multiple abilities share the same head type constructor. That would be a deal-breaker for effectively using abilities as a typeclass mechanism. Hopefully this could be fixed? I don't know enough to comment. I guess one issue would be resolving an SubclassesIs there a path to something like Haskell's Commentary
|
|
#499 raises the idea of pluggable syntax for Unison. It occurs to me that if the mechanism for that is sufficiently granular, then it may provide an elegant way forward on this issue without fear of committing to an approach that may turn out to be a poor fit for the language in the long run. Specifically, if existing language constructs (whether through the ability system or regular function parameters) are already sufficiently general to encode bounded polymorphism in a way that could be handled efficiently, then maybe more ergonomic syntactic sugar could be provided via the plugin mechanism so that different approaches could be explored in parallel (and could even co-exist in the long term, with developers opting for the sugarings / surface encodings that suite their own preferences). |
|
What about combining Rust's Trait (i.e. Typeclass) coherence rules (which it sounds like are the informal rules in Haskell) with a Unison-specific mechanism for patching dependencies with glue impls (i.e. instances)? Unison's design makes patching dependencies almost trivial. In particular, if a library that introduces a new type is missing an impl for a Trait you would like to use on that type, you can simply patch the library to introduce the impl. There could even be a dedicated class of "glue libraries" for providing these impls, that Unison could provide first-class support for. I suppose there's still the possibility that you could depend on one "glue library" in your code, and then later on try to add a dependency that depends on a conflicting "glue library". In those cases you might have to do a non-trivial patch to resolve the conflict. But I suspect the ecosystem would quickly coalesce on standard, compatible implementations. |
|
Sounds interesting @scottjmaddox but I didn't understand it yet! 😢 A few more lines spelling out the proposal, with free-standing text rather than by reference to other languages, would help me. |
|
@atacratic Sorry for the confusion, this is very much a half-baked idea. Unfortunately, I don't think I can really explain it without referring to other languages, since:
But let me see if I can better to communicate the concept (as ill formed as it might be): First, lets define some terms: I am going to use "Trait" and "impl", rather than "Typeclass" and "instance", because I'm more familiar with Rust than with Haskell. If you're more familiar with Haskell, then please substitute "Typeclass" for "Trait", and "instance" for "impl". Now, as far as I can tell, the primary complaint about Traits is that there is an inherent conflict with Modules. If you want both Traits and Modules in your language, then the issue of orphan impls arises. An orphan impl is an impl that is defined in a module other than the module in which either the Trait or the implementing Type is defined. Orphan impls are a problem because they can conflict. So allowing orphan impls in your language means you can end up with two modules that cannot be used in the same codebase (or at least, cannot be used without some approach for resolving the conflict, which could result in unintuitive behavior). In Rust, orphan impls are outlawed. So you can only impl a Trait either in the module that defines the trait, or in the module that defines the implementing Type. In practice, this works reasonably well, although it can cause frustrations at times, for example when you want to use the Serde crate to serialize/deserialize a type defined in another crate that does not implement Serde's Serialize/Deserialize traits. Typically, the way this is handled is by either providing a compile-time feature flag to add these impls, or by writing a wrapper Type with the desired impls. In Unison, it seems like it should be possible to completely bypass these complaints about Traits, by leveraging Unison's unique ability to patch modules. Unison could provide a tool for easily (perhaps even automatically) patching external dependencies with conflicting orphan impls. So rather than banning orphan impls, as in Rust, you could allow them and provide a tool for semi-automated or fully-automated merging of orphan impls. Going a step further, Unison could provide a sort of package manager for single-impl-packages, i.e. "glue packages". When you want to use an impl for a trait and type defined in two different external dependencies, you would attempt to import the appropriate glue package. If it doesn't exist in the ecosystem yet, you could write it and publish it. This would encourage the ecosystem to standardize on particular glue impls, and keep conflicts to a minimum. Does that make the idea any clearer? |
|
@scottjmaddox interesting! 🙂 The orphan impls situation sounds the same as in Haskell, where rules excluding orphans maintain 'coherence' (avoiding mixing the use of different instances). I don't know if I'd phrase it as 'bypass the constraint': plenty of people think that Haskell's enforcement of coherence is a good feature. There's a heading 'Coherence' above that touches on this, although it assumes knowledge of the haskell background. I wonder what it would mean to 'merge' two orphan impls? Maybe finding an example use case would be a good way to get clarity there. |
|
Looks relevant... Tom Schrijvers, Bruno C. d. S. Oliveira, Philip Wadler, and Koar Marntirosian. 2019. COCHIS: Stable and coherent implicits. J. Funct. Program. 29 (2019), e3. https://doi.org/10.1017/S0956796818000242 https://pdfs.semanticscholar.org/76ad/639df681bc1757e270245851b9d7dd7ab810.pdf abstract:
|
I wanted to throw in my tuppence on what Unison could do about typeclasses (see comment below) so I'm opening this issue as a place to put such things.
I'm aware that this is one of those topics that can generate endless discussion, so I propose that this issue just be for concrete proposals and observations, rather than opinions and preferences. Even so maybe Paul will just want to close it...
Quoting this post from the blog for starters:
[edit] As of 29 Aug '19 this issue contains two proposals:
The text was updated successfully, but these errors were encountered: