Repository navigation
Typeclass objects #27
Description
Typeclass objects offer dynamic (i.e. run-time and open modularity1) polymorphism by binding the typeclass bound to the static (compile-time) type of the reference and tagging the data type instances that the reference can contain, so that the correct dictionary can be dispatched dynamically at run-time.
They are named "trait objects" in Rust and "existential quantification" (e.g. forall a) or "existential typeclass" in Haskell.
1 Means we can't compile the universe, so we can't know all the data types required in dependency injection scenarios. Dynamic polymorphism is not just a run-time artifact, but it is also the fact of the real-world where total orders can't exist (i.e. the Second Law of Thermodynamics, Halting Problem, Incompleteness Theorem, Russell's Paradox, Byzantine Generals Problem, Byzantine fault-tolerance with CAP theorem, impossibility of existence without a quantified speed-of-light, etc). As well, there are no total orders of trustless, decentralization either.
Expression Problem
They have the benefit w.r.t. to Wadler's Expression Problem of delaying the binding of interface to data on construction of the typeclass object as opposed to OOP subclassing (and Scheme/JavaScript prototype2) which binds the interface to all instances of the subclassed type (on instantiation of the data). So they solve the Expression Problem up the point of instantiation of the typeclass object, but beyond that point while they allow adding new data types (via the aforementioned dynamic dispatch) they don't allow extending new operations after the instantation of the typeclass object which binds the allowed typeclass interface(s). Typeclass objects enable heterogeneous collections with dynamic extension of the collection of data types without requiring an invariant collections data structure (i.e. they can be the element type of an array). Whereas, typeclass bounds on function definitions delay binding the interface until the function call site and thus solve the Expression Problem up to that point, but they don't enable heterogeneous collections with dynamic extension of the collection of data types except via unions. Unions can both enable heterogeneous collections with dynamic extension of the collection of data types and delay binding of the interface until the function call site, but they require an invariant collections data structure such as a list.
2 Note that prototype programming can add new operations (but forces all instances of a prototype to take those new interfaces) and add new data types, but it can't add different interfaces to instances of the same prototype. Whereas, type classing can differentiate. (Edit: correction)
Syntax and Pecularities
Well obviously that is useless and not what I was referring to. I mean for example, I have a collection of typeclass objects and I want to sort or find them, so I need a relation.
A relation only applies to two objects of the same type.
Exactly. So thus
Eq<A, A>is useless for what I wrote above.One answer is to provide a mapping from each object type to a partial order (or total order).
So akin to subsumption to a subclass, except open to delayed definition. That might work for
sort.Or another alternative is
Eq<A, B>accepts any typeB, but always returnsfalseifBis notA. Sofindwill work.Okay I see how maybe typeclass objects are still useful. Thanks.
@keean wrote:
data Variant = for<A, B> Variant(A) requires A : Eq<B>
data Variant = Variant(A | Any) where A: Eq<Any>
That seems to be a general solution and I like it very much, unless someone can point out flaws.
So typeclass objects are always conceptually with | Any, e.g.:
let x: A where Show<A | Any> = MyType(1, 2)
let y: A where Eq<A | Any, Any> = MyType(1, 2)
Or in my (and Rust's) preferred OOPish style:
let x: A where (A | Any): Show = MyType(1, 2)
let y: A where (A | Any): Eq<Any> = MyType(1, 2)
But I prefer we can write that shorthand (and so we only need where clauses on function types and definitions):
let x: Show = MyType(1, 2)
let y: Eq<Any> = MyType(1, 2)
Hope you are also starting to see another reason why I favored an OOPish style because it is also more consistent with typeclass objects (and I actually did intuitively anticipate/expect this but not with complete solution worked out).
P.S. my understanding is that any function defined for a typeclass bound would also accept typeclass objects with that bound. The compiler would create a dynamic dispatch version of the said function on demand to be used when ever a reference to it is passed around. Seems to me that only functions called nominally can be monomorphized.
Activity
shelby3 commentedon Oct 8, 2016
@keean wrote:
I am instead proposing that be written the same as any typeclass bounded function without any
for<B>:f(callback: (B) => ()) where B: ShowI wrote in the OP:
keean commentedon Oct 8, 2016
This:
Doesn't work because you are not specifying the scope for 'B' you could mean:
Or you could mean:
shelby3 commentedon Oct 8, 2016
@keean wrote:
I don't understand why that is important. Please explain.
keean commentedon Oct 8, 2016
for<B>in the outer scope the callback is monomorphic with respect tofso the callback can only be called on one type, that is fixed at the timefis called.Bshelby3 commentedon Oct 8, 2016
@keean wrote:
Okay what you mean is that when
fis called, then at the call site the types of the callback are monomorphized. This meansfis only calling the callback with the said typeclass bounded instances and not with concrete data instances.I don't think the
for<B>is necessary. The scope can be determined by whether thewhereclause appears at the top-level scope or not! So non-top-level indicates a typeclass object; whereas, top-level indicates monomorphization at the call-site off. So now, you provided another more important reason that we need non-top-levelwhereclauses. I hate that ugly/noisyfor<B>.Right that is what I wrote else where, that it doesn't make any sense for
fto request a typeclass bounded callback (which isn't monomorphized at the call site forf) unless it is for dynamic dispatch typeclass object(s).keean commentedon Oct 8, 2016
Yes but I would rather make the programmer declare a datatype for a polymorphic callback function. This keeps the function syntax simpler, and is called first-class-polymorphism.
shelby3 commentedon Oct 9, 2016
@keean wrote in other thread:
I am pleased you raised this point.
First re-read my prior comment and click the link in it to remember what you pointed out to me about the scoping of the callback.
If the callback is scoped by the call site to function
f, then the caller chooses the typeclass bound(s), which satisfies your point.And if the callback is scoped by the function
f, thenfdecides the typeclass bound(s) of the typeclass object(s) of the callback.If you are not referring to augmentation of type-class bounds, that would only be in the case when the callback is scoped by the call-site of
f, except it is generally impossible. Let's clarify what kind of inference we are taking about.The function
fmay call some operations on the callback and/or it may storefin a data structure imperatively and thus we have no way of knowing which future operations on the callback will be allowed iffdoes not declare them. The compiler will forcefto declare them. You could I suppose infer the operations thatfinternally requires in its function body using principal typings, but we don't know yet to what extent we can support principal typings, as generally they are undecidable in an open system.So
fprobably must declare its typeclass bound(s) requirements (at least we decided at a minimum, it must be explicit at module boundaries).But you are making a different point. You are talking about the caller of
fbeing able to augment (not remove the typeclass boundsfrequires) the available typeclass bounds that the callback requires in the case where the callback is scoped at the call-site off. In this case, I agree with you, since you want to delay unification of the type variables until the call-site.So what you are saying is that
fcan require operations on the type variables of the callback and the caller can add some more required operations.The caller can add more
whererequirements (either inferred or explicit) at the call site off. The way the explicit will be done at call site is with a cast either top-level:f(callback): (MyCallback) => () [B: Print+Show]Or non-top-level:
f(callback: (B) => () [B: Print+Show])Note above that either will apply to the typeclass object or monomorphization cases, because per my proposal,
f's scoping of itswhereclause determines which case it is.shelby3 commentedon Oct 9, 2016
@keean wrote:
But that forces structural typing otherwise we can't reuse functions which have the same signature but different
datatype names. That is why I had suggestedtypealiases instead.And
typealiases must be expandable to any general types, so we won't be able to force (make) the programmer usetypealiases for non-top-levelwhereclauses (as they can use the general types any where a type signature is required).Edit: more discussion.
shelby3 commentedon Oct 9, 2016
@keean wrote:
Okay so the research paper you cited is all about achieving type inference.
So as I wrote in my prior comment in this thread, you are advocating abandoning the ability to reuse functions (which contain a type variable) based on their structural type and instead forcing said functions to be instantiated nominally (thus making equivalent structural function types non-composable because they have different nominal constructors), all because you want to be able use principal typings on these said functions. I've already warned and feared that you are going to making your principal typings goal into a weapon to defeat degrees-of-freedom of expression. @skaller has also warned similarly that type inference is the enemy of expressiveness.
I don't think it is often going to be the case that we want to have a function taking a callback, where both said function and the callback function are both not annotated with quantified (aka concrete) types. And for those cases where might have wanted to do that, we won't. We will have to annotate. For myself and also for readers, please provide me a convincing example showing this annotation overhead (in this specific case of type variables we are discussing) is a significant burden justifying abandoning the ability to compose functions generally?
Edit: also nothing stops you from using the method you prefer in your code and achieving type infererence. I am asking why we must force everyone to abandon function composition generality in all code, when they can choose to annotate.
I don't think I like complex code without type annotations. Raises cognitive load due to lack of explicit local reasoning. Type inference is useful where the reader can easily figure out in their head what the type annotations would have been. This is one of my big complaints that makes Haskell code so obtuse to read IMO.
keean commentedon Oct 9, 2016
There is no loss in expressive power (it even says so in the paper), and it will make the type signatures shorter and more readable.
There is no loss in composition, and I am not sure why you would suggest there is? Function type signatures don't compose, unless you are talking about copy-and-paste composition? Copy-and-paste just leads to stupid errors. Why bother with named functions at all, why not just copy and paste the raw-code? The same argument applies to types, it is better to have a named type you can re-use (like you call functions) rather than have people copy-and-paste huge complex and unintelligible type signatures.
keean commentedon Oct 9, 2016
I disagree, it is all about avoiding having to have higher ranked type annotations. In Haskell (and all other languages I know of except those that use FCP) you must annotate higher ranked types because they cannot be inferred. Haskell cannot infer them, no language I know of can infer them. So this is not about inference. This is about how you achieve the annotation. We already need first-class-polymorphism to correctly handle type-class dictionaries, so we already will have the mechanism for it.
We can keep the language simpler and keep the full expressive power, how could anyone not want that?
shelby3 commentedon Oct 9, 2016
@keean wrote:
I guess that is correct. I think I also used the term 'composition' and so it is really boilerplate that is the issue.
At the cost of causing other boilerplate...
I can't reuse a
MyCallbackevery where I can use aMyCallback2(and vice versa) even if the signature of the functions are otherwise identical.Granted I can destructure those constructors and re-construct a compatible instance, but this is boilerplate and additionally afaics if I have these in a typeclass object, then I will have need a different implementation for each one. Afaics, FCP is increasing boilerplate of composition in exchange for the hope of not having to write type annotations for higher-ranked types (and I say hope because I don't know if FCP inference will integrate with our unions and other features and I don't know if we won't end up needing higher-ranked types any way).
Which is precisely all about achieving (a similar level of expressiveness with) type inference. But the entire point of type inference is to not have boilerplate. I hope you didn't really expect that FCP is some Holy Grail without trade-offs.
It is about how we support type variables with minimal annotation and boilerplate, with the goal of enabling type inference with a boilerplate wrapping versus losing type inference with no boilerplate wrapping.
How is it simpler? You trade off one thing for another.
The difference is we don't normally expect structurally equivalent types to be equivalent (excluding our planned unions and intersections). But functions we normally do expect them to be composable on structurally equivalence (which is why we allow anonymous functions).
Note you did not address my comment here:
@shelby3 wrote:
keean commentedon Oct 9, 2016
You avoid nested where clauses in the syntax. The grammar will be simpler, (and this will be visible in the simple EBNF for the language).
We dont normally expect any equivalence operator to work on functions, so I am not sure this is important. Remember top-level functions can be fully polymorphic, so you only need to wrap the argument in the datatype at the call site. Like this:
skaller commentedon Oct 9, 2016
What is wrong with type annotations?
They’re great! They add to the ability to reason about code in principle.
They allow error messages to make sense.
The downside of annotation is verbosity which makes code harder to read.
The programmer should have flexibility chosing the tradeoff.
—
john skaller
skaller@users.sourceforge.net
http://felix-lang.org
shelby3 commentedon Oct 9, 2016
@keean wrote:
Disagree. We expect assignment of functions to work on structural equivalence.
And so you are right back to type annotations again.
We avoid that but add the boilerplate back in other places. So isn't necessarily a net gain in brevity. It also loses some local reasoning.
The nested
whereclauses can be avoided without forcing FCP, by offering atypealias as I mentioned twice before.And you didn't address my comment:
@shelby3 wrote:
Generally wrapping interacts badly because it becomes deeply nested!!!
Which is why we want a first-class anonymous union instead of massive case-tree logic to destructure
Either. OTOH, first-class without wrapping makes inference undecidable.272 remaining items
shelby3 commentedon May 25, 2017
You mean only if the code is compiled by the sandbox and not the untrusted party.
keean commentedon May 26, 2017
Compiling by the sandbox can work, but compilers are big and complex things to distribute. Nobody really does this, probably because of platform differences between windows/macos/Linux and compilation time for big applications can be really long.
JavaScript is interpreted / JIT compiled, so is possibly the closest, but it's not really compiled, and WebAssembly will be a target you compile to.
Java compiled to a byte code, and the byte code has to be verified before you can run it, which is prone to problems.
Remote code execution has so far proved to be a major security hole, and is generally to be avoided if you don't want your machine compromised. Browser exploits that allow machine compromise exist in the wild.
Maybe when the web browsers are written in Rust they will have a lower bug rate (where the bugs allow security to be compromised).
So in theory it can work, but in practice it's not a good idea.
shelby3 commentedon May 26, 2017
And C++ has a 1500 page manual. <joke>Maybe you and @skaller are the only humans on the planet who understand every nuance of C++.</joke>
And thus I am here trying to find an 80/20 rule sweet spot between Lucid™ simplicity and priorities on performance.
Complexity is not good. We should apply the K.I.S.S. principle.
JavaScript is not Joe-E, i.e. it was not designed well for security. For example, the bug I identified in these issue threads wherein all programming languages that do not have a set of brackets (which the user will never type!) for delimiting strings that can contain executable code, thus enable script injection attacks. (And the people in charge of browser security, including the guy Ian in charge of HTML5 (also), would rather do security theater, i.e. Almost Better Than Nothing™ security, than actual security)
Yeah many things suck in the real world of available programming languages and sandbox systems.
That is one of the many reasons I am working on Lucid.
We may not get it perfect the first iteration, but we can hopefully experiment on ideas for improvements.
Operating system and hardware security are also not impervious. Security will never be an absolute.
EDIT: security discussion continued in 2018 in a different thread.
shelby3 commentedon Jul 5, 2018
Although we noted up-thread that it’s possible to request a typeclass interface with factory for a parametrised
CONTAINER(and even request an iterator or an iterator factory typeclass interface for thatCONTAINER), the problem which @keean correctly pointed out is that there’s no type safety checked by the compiler for the implementation of the typeclass interface instance assuring that it operates onELEMents of theCONTAINER. The only type checking comes from the contextual use of the said typeclass interface, but it’s not assured that such contextual usage would be correct. One could imagine different scenarios (perhaps not the specific iterator example considered here) in which type safety would be violated and not caught by the compiler because of the lack of HKT.Analogously without HKT, there’s no way to express a functor
maptypeclass interface that is typesafe because there’s no way to express that the map functionA → Boperates on the element of theCONTAINERsuch thatAandBare both elements ofCONTAINER. We can create a map operation that type checks and works, but the necessary invariants have not been enforced by the compiler in the typeclass interface instance implementation.For this reason, I conclude we must support HKT.
Any objections?
keean commentedon Jul 6, 2018
HKT tend to be associated with partial-evaluation/currying so may not be the best fit for our language. We should consider alternatives, like type-families (type level functions).
shelby3 commentedon Jul 6, 2018
Could you please elaborate with an example that illustrates why you think this is the case?
And why would you assume our PL will not be using partial-evaluation/currying?
Could you show by example how this is an alternative?
I am thinking that iteration with typeclasses and even for your past
sortexample are not really typesafe without HKT. Please show me how they are type safe with type families? I thought about associated types and AFAICT they do not solve the following quoted problem:AFAICS, we end up assuming that the implementation of the typeclass does not violate that invariant but the compiler is unable to check it.
Also note that for Zer0, I’m proposing to forsake decidable global type inference, so HKT don’t present a hindrance in that respect.
sighoya commentedon Aug 29, 2018
@shelby3 wrote:
What about this:
keean commentedon Aug 29, 2018
@sighoya I suggested allowing typeclass constraints on the associated type like this:
would require that
IntisPrintable. In this way an associated type becomes an existential.shelby3 commentedon Aug 29, 2018
@keean that is premature specialization. Put the
requires Printable(Collection[A].Element)on thefuninstead.keean commentedon Aug 30, 2018
@shelby3
That does not solve the runtime type dependency though. We don't want to have the type of element determined by which implementation of Collection is used, because the Collection could be different at runtime. By constraining element to
Printablewe know that no matter what type it is we can print it.This takes us back to the same general problem. This type naturally wants to be an existential. We could make it a closed union, but then we would have to edit the typeclass every time we add an instance.
An alternative solution would be an open-union that is closed at link-time.
shelby3 commentedon Aug 30, 2018
@keean wrote:
I have told you this before and I will repeat it again. The compiler can generate the typeclass instance automatically for a closed union type (the non-disjoint, structural unions proposed for Zer0, not Haskell’s sum types which not even isomorphic to unions and thus are not unions) if every type in the closed union has a
Printableinstance.keean commentedon Aug 30, 2018
@shelby3
Yes it can, I even said this:
We would have to write:
The problem now is if we want to add an instance for a collection with a Float element type we cannot do so without editing the typeclass definition, which may be in a different module.
shelby3 commentedon Aug 30, 2018
@keean
Elementis an output type of the instance, so do not hardcode it on the typeclass definition as you have shown. The instance can set the type when it ever it changes to a different closed union. Thus the compiler can generate it.No need to edit the typeclass definition.
keean commentedon Aug 30, 2018
@shelby3
Not if we don't know the type that is selecting the instance. Consider
This does not work. If
xis existential then T must be existential too. However ifxis a closed union, then type T can be a closed union too. Ifxis an open union thenTwould need to be an open union as well.Personally I think it is more flexible to allow open unions, but I think you only want to allow closed ones?
For me an open union (resolved at link time) would offer all the functionality of a close union and an existential, with none of the complexities of the existential.
The good news is we can keep the same syntax and associated type mechanics for both, or even existentials if they are allowed, they type checking rule is straightforward, and we require associated types to be either open/closed unions or existentials dependent on the type that is selecting the instance.
shelby3 commentedon Aug 30, 2018
@keean wrote:
And you’re premature specialization “solution” is an oxymoron. It isn’t a solution. It just aids and abets the clusterfuck of open union bounds. Rather I prefer to use my list-of-lists “chunking” solution in the Subtyping issues thread #8 that I need to explicate better soon so we always have closed union bounds for chunks, but open union bounds effectively without incurring that clusterfuck of non-solutions you’re advocating.
Premature specialization is not flexibility. It is an anti-pattern. Yeah I want my solution, not non-solutions.
Please don’t ask me to explain all this now in great detail. We will just get into an argument.
When the time is right I will. This isn’t my priority right now to explain it. I know what is best and I am moving forward.
Because I don’t have time to write another 100 posts to explain something which is obvious for me, but apparently impossible to explain easily to others in my current state-of-mind and haste.
You still don’t seem to grok the anti-modularity of your total orders linking proposal even I have written dozens of posts in the Subtyping thread about it.