Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#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 Revisions:

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 2 years ago by carter

  • Resolution set to invalid
  • Status changed from new to closed

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

comment:2 Changed 2 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 1

compiler 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 2 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 2 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 2 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 2 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. :)

Note: See TracTickets for help on using tickets.