#8370 closed feature request (invalid)
Ranked Instances
Reported by: | wvv | Owned by: | |
---|---|---|---|
Priority: | normal | Milestone: | |
Component: | Compiler | Version: | 7.6.3 |
Keywords: | Cc: | ||
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | None/Unknown | Test Case: | |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
This is a first part of 3 depended extensions: Ranked Instances => Inherit Instances => Newclasses
This is very easy to implement. And it gives big advantages. And further developing. I suggest to add "rank" to instance.
Now the system of instances is flat, and compiler takes all of instances and check if only 1 match. If it is not(less or more than 1) - compiler trow an error.
With rankings compiler
- set N=0
- took all N-ranked instances and
- => try to find only one match instance.
- -> If it found only 1 - this is RESULT: needed instance,
- -> If it found many instances - throw an error
- -> If compiler found NO instances, compiler set N=N+1 and repeat
- If N=MaxRank and still no matches compiler throw an error
We use RankedInstances before OverlappingInstances (which must include RankedInstances), and in many cases instead of.
Proposed grammar
We add "rank N" between "instance" word and ".", where N is a number
{-# LANGUAGE RankedInstances #-} instance rank 1. C a => D a where ...
Default Rank
If instance has no rank, this means it has 0 rank
instance C a => D a where ... ~ instance rank 0. C a => D a where ...
This is a backward compatibility.
Examples
1)
instance rank 1. C Int a where ... -- (A) instance C a Bool where ... -- (B) rank 0
1+)
instance rank 1. C Int a where ... -- (A) instance rank 1. C a Bool where ... -- (B) instance C Int Bool where ... -- (C) rank 0
2)
instance rank 1. C Int [a] where ... -- (C) instance C Int [Int] where ... -- (D)
As we see, all instances are unambiguous!
Backward Compatibility
Without -XRankedInstances all instances with hight rank n, where n >0 - are not exported
More information (about all 3 extensions) is here http://haskell.1045720.n5.nabble.com/Proposal-RankedInstances-tt5737152.html
Change History (6)
comment:1 Changed 3 years ago by carter
- Resolution set to invalid
- Status changed from new to closed
comment:2 Changed 3 years ago by wvv
I'm really deeply appreciated !
And I'm really sorry if my examples are not understandable and my explanation isn't clearly enough ((
Here is a background: the main power of Haskell is type-classes and their implementation: instances. So, Haskell is interested to have as much instances as it can for any cases.
Unfortunately we can't have a lot of instances - they became to overlap each other. In many cases Overlapping Instances doesn't solve our problems. GHC add "default" instances. But it is a partially solved problem.
For now we are capable to write next:
instance Monad m => Functor m where fmap = liftM instance Applicative m => Functor m where fmap f x = pure f <*> x
But we cannot add them of overlapping reason. Both of them not only overlap with any concrete instance but each other. "Defaulting" and overlapping won't help us to solve this. All (except hidden with "defaulting") superclass' instances like:
instance Child a => Parent a where ..
are forbidden
(1)
Ranked Instances allow us to create and use all Child a => Parent a superclass' instances
class Applicative f where ... --without "Functor f=>", it is a misfeature instance rank 15. Monad m => Functor m where fmap = liftM instance rank 16. Applicative m => Functor m where fmap f x = pure f <*> x
Compiler try use all 0-ranked instances, then all 1-ranked, then ..., then all 14-ranked, then all 15-ranked.
If instances overlap in any rank-layer, it is an error. Our 2 instances are in different layers, so we have no overlapping.
All user's instances by default are 0-ranked. So if user create data, add 2 instances: Monad and Applicative,
data D a ... instance Monad D where ... class Applicative f where ... --without "Functor f=>" instance Applicative D where ...and not Functor, but try to use fmap
foo = (+) `fmap` D 1compiler use (Monad m => Functor m) instance, reason - lower rank, than (Applicative m => Functor m). If user define his own instance Functor data,
instance {- ranked 0. -} Functor D where ..it will be 0-ranked instance, so compiler use his instance, not superclass' instance (with much higher rank).
A lot of Child2Parent superclass' instances are the unique feature of this extension!
(2)
Ranked Instances allow us to get rid of default instances, but save all capabilities of it. Even more - with Ranked Instances is allowed to use several default-like instances (outside of class)
class ToJSON a where toJSON :: a -> Value default instance (Generic a, GToJSON (Rep a)) => ToJSON a where toJSON = genericToJSON defaultOptions
is the same as
class ToJSON a where toJSON :: a -> Value instance rank 10. (Generic a, GToJSON (Rep a)) => ToJSON a where toJSON = genericToJSON defaultOptions instance rank 11. (Data a) => ToJSON a where ...Here we have 2 default-like instances! If we wish to add third, I dunno, "Typeable a=> ToJson a" we still could add it (with higher rank).
We'll have with Ranked Instances much more, then with default instances!
(3)
Ranked Instances are powerful enough to use them instead of both Overlapping Instances and Incoherent Instances.
instance rank 3. C a Int Bool where ... instance rank 2. C Int Int a where ... instance rank 1. C a Bool a where ... instance rank 0. C Bool a Bool where ...
Neither Overlapping Instances, nor Incoherent Instances can't help us in this situation.
With Ranked Instances, Compiler try to
1) 0-rank: look if first and third args are Bool
2) if no, 1-rank: look if second arg is Bool
3) if no, 2-rank: look if first and second args are Int
4) if no, 3-rank: look if second argument is Int and third is Bool
5) if no, throw an error
We'll have with Ranked Instances much more, then Overlapping Instances and Incoherent Instances together!
(S)
If we summarize, Ranked Instances is a very powerful extension!
It is easy to implement, easy to use and easy to read the code.
It is compatible with all old code and other extensions.
It is a step forward, not aside.
It allows to write more generic code.
It helps to get rid of boilerplate.
I suppose, for now my proposal looks much more clearly. If it is something unclear, I give more explanation.
comment:3 Changed 3 years ago by carter
wvv, seems you're actually pointing a problem folks agree on (would be nice to be able to define a child type class and have it instantiate its parents), but I think your proposed approach is a bit confusing and overly complex.
likewise, its very very important to clearly explain the problem statement / goal, before jumping into made up notation that no one but you can decipher easily.
likewise, "its easy to implement " is hard to validate, or you'd already have a patched ghc with the ideas locally to test it out for usability! since you dont, by default you should assume its actually more subtle than you claim! if you want a feature for GHC, and you want a specific design that no one else is excited about, you need to cook up the patch yourself, and then demonstrate with working code that can actually run, that your ideas are good.
the burden of proof here lies with you. If you can cookup a patch that validates your claims, great. failing that, please read the book i suggested, an all the relevant papers in http://ghc.haskell.org/trac/ghc/wiki/ReadingList CAREFULLY.
I repeat, please don't post any new proposals until you have worked through the book i have suggested http://www.cs.cmu.edu/~rwh/plbook/book.pdf and the relevant parts of the reading list.
Please do that and I look forward to your subsequent involvement in ghc.
If you have any questions or troubles with those readings, then direct your questions to the haskell-cafe mailing list and/or the #haskell IRC channel on freenode.
Please refrain from posting any new proposals/ideas to GHC trac until after you have worked through the above reading list, which I anticipate will be late February 2014 at the earliest.
this ticket is closed.
comment:4 Changed 3 years ago by wvv
Wow! Great book! Thank you very much!
Contribution
I have Windows without VM. And even compile GHC from 0 (even without any contribution) will be a big challenge )) So, maybe this is not an option right now.
Easy Implemetation
I'm not familiar with low-Haskell code, but yes, it is easy!
We can divide changes to support code and significant code.
Support code
This is a dev's routine, I a newbie with these techniques. It is needed to
- add extension name to extension
- add parsing extension pragma
- add line "use -XRankedInstances or -XOverlappingInstances" in error message if both RankedInstances and OverlappingInstances are off
- I recommend deny to use both RankedInstances and OverlappingInstances in one module
- add data Ranked-Instances, absolutely similar as data Overlapping-Instances
- add parsing pattern to parser/Parser.y.pp, something like | "instance" "rank" digits "." <rest> . But forbid to parse without extension
- extract number
- and add "rank" field to all data Instance<Smth> and copy-paste this field everywhere it is needed.
Significant code
Fortunately, almost all code is already written by guys, who added Overlapping instances to GHC!
The reason - Ranked Instances are "user control overlapping".
http://ghc.haskell.org/trac/ghc/browser/ghc/compiler/types/InstEnv.lhs#L564
lookupInstEnv ... = pruned_matches = foldr insert_overlapping [] all_matches (safe_matches, safe_fail) = if length pruned_matches == 1 then check_safe (head pruned_matches) all_matches else (pruned_matches, False)
We need to change 2 functions - insert_overlapping and check_safe.
insert_overlapping
Let's look to insert_overlapping : http://ghc.haskell.org/trac/ghc/browser/ghc/compiler/types/InstEnv.lhs#L618
This function is fully satisfied, exept for beats sub-function. http://ghc.haskell.org/trac/ghc/browser/ghc/compiler/types/InstEnv.lhs#L641
(instA, _) `beats` (instB, _) = overlap_ok && isJust (tcMatchTys (mkVarSet (is_tvs instB)) (is_tys instB) (is_tys instA)) -- A beats B if A is more specific than B, -- (ie. if B can be instantiated to match A) -- and overlap is permitted
We cahange it to
(instA, _) `beats` (instB, _) = (fromRank instA < fromRank instB) || {- We don't need to check if extension is on, all non-extension instances have a privilege - the lowest 0 rank -} overlap_ok && ...
We add (!) just 1 line of significant code.
check_safe
This a bit complicated. Devs, who add Overlapping instances add a guard : "We restrict code compiled in 'Safe' mode from overriding code compiled in any other mode."
But we wish to allow over-rank instances through the modules. The simplest way - to forbid use Overlapped-Instances together with Ranked-Instances in one module. And add such lines from: http://ghc.haskell.org/trac/ghc/browser/ghc/compiler/types/InstEnv.lhs#L609
inSameMod b = let na = getName $ getName inst la = isInternalName na nb = getName $ getName b lb = isInternalName nb in (la && lb) || (nameModule na == nameModule nb)
into (this is not effective code, looks a bit hacky, but it works):
inSameMod b = let na = getName $ getName inst la' = isInternalName na la = isRankedExtension || la' -- allowing Rank nb = getName $ getName b lb' = isInternalName nb lb = isRankedExtension || lb' -- allowing Rank in (la && lb) || (nameModule na == nameModule nb)
Conclusion
Yes, Ranked Instances is very powerful extension! And yes, it is easy to implement!
Yes, I'm confused, no one even reply at my proposal. I don't even speak about serious discussions.
And yes, I regret, I have no one advocate through developers, who could add this extension less than a day in a test branch.
I've showed, how to add 3 lines of significant code (sure, it is needed some routine code for support this extension.)
I hope, it's become clearer.
Am I missing something? Is it still overly complex in implementation?
comment:5 Changed 3 years ago by carter
Please actually talk with the community via the cafe mailing list and #haskell mailing list. And explicitly ask for feedback there.
Your current expositions are not understandable by others.
Please go on the #haskell irc channel on freenode and ask for feed back of your type system ideas there.
You really need to have your ideas exposited off trac, as a starting point for feedback.
Please: take the next few months to dig into learning more type theory and how to critically evaluate when a type system is not just valid, but also good.
That no one else is excited about your proposal (or even critiquing)means either no one but you understands the proposal, and the parts that are understandable seem over complicated and unusually . Trac is not the right fora for learning how to communicate on this matter.
This ticket is closed. Please stop posting to trac while taking the next few months to learn. If you want to get feedback please use #haskell irc on freenode.
Even then, type system extensions to ghc are only seriously considered after you have given a formal exposition (because otherwise what does it mean) and perhaps even a candidate patch (or at least a willingness to subsequently write such a patch). Everyone is held to this standard for any nontrivial changes.
This ticket is closed. Stop posting to trac for a while and go learn. This is your last polite warning.
comment:6 Changed 3 years ago by carter
point being: you have many interesting ideas, but you need to work on having some conversations about the ideas and how they work with code OFF trac first to get feedback and refine them. :)
Hey wvv. Emailing cafe and getting no feedback is not sufficient reason to add a type system feature to ghc.
As a rule, lack of feedback on an idea is a red flag rather than a go ahead.
Remember the criterion I laid out for what most type system extensions need to satisfy to be suitable for consideration for ghc? It has to allow more valid programs and or prevent more bugs.
You have given lots of syntactic examples without any clear explanation of the type system ideas or why anyone should care.
Perhaps most importantly, your examples are hard to understand. Adding type system features that are hard to understand for ghc devs, that requires even more care!
Please, read some text books on type systems and programming languages, eg the one by Robert Harper is excellent, opinionated, and free online.
We all really appreciate your enthusiasm, but please take the time to learn a solid type theory foundation first! It's a lot of work, but it's also incredibly rewarding and you'll find it will really help force you to better clarify your ideas.
Nb: working through even that one book will take a few months of work. So any new proposals from you till after February 2014, at the earliest, I will probably be forced to close. And I will not explain as clearly as I have this time and the previous. This is your last polite warning.
If you wish to have any future seed of credibility with ghc devs, please take the time to learn and develop a more robust pl background wrt type systems before you post another such proposal.
Additionally: every serious type system proposal tends to be implemented by their advocate. You currently glaringly lack a clear picture of how type classes and constraint solving interact with inference work. I strongly recommend you read the "outside in" paper to learn more of what's going on there
Best of luck in your learning adventure!
All the reading suggestions I mention are easy to google for, you should be able to find them on your own