GitLab

---------------------
	Dealing with deriving
	---------------------

I spent a ridiculously long time peering at a bug report whereby
a 'deriving' clause sent GHC 5.02.1 into a loop.  It was all to
do with allowing instances like

	instance Foo a b => Baz (T a)

(Notice the 'b' on the left which does not appear on the right.)

I realised that it's hard for the deriving machinery to find a
fixpoint when these sort of instance decls are around.  So I
now constrain *derived* instance decls not to have this form;
all the tyvars on the left must appear on the right.

On the way I commoned up the previously-separate tcSimplify
machinery for 'deriving' and 'default' decls with that for
everything else.   As a result, quite a few files are touched.

I hope I havn't broken anything.

---------------------------------------------
	More type system extensions (for John Hughes)
	---------------------------------------------

1.  Added a brand-new extension that lets you derive ARBITRARY CLASSES
for newtypes.  Thus

	newtype Age = Age Int deriving( Eq, Ord, Shape, Ix )

The idea is that the dictionary for the user-defined class Shape Age
is *identical* to that for Shape Int, so there is really no deriving
work to do.   This saves you writing the very tiresome instance decl:

	instance Shape Age where
	   shape_op1 (Age x) = shape_op1 x
	   shape_op2 (Age x1) (Age x2) = shape_op2 x1 x2
	   ...etc...

It's more efficient, too, becuase the Shape Age dictionary really
will be identical to the Shape Int dictionary.

There's an exception for Read and Show, because the derived instance
*isn't* the same.

There is a complication where higher order stuff is involved.  Here is
the example John gave:

   class StateMonad s m | m -> s where ...

   newtype Parser tok m a = Parser (State [tok] (Failure m) a)
			  deriving( Monad, StateMonad )

Then we want the derived instance decls to be

   instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
   instance StateMonad [tok] (State [tok] (Failure m))
	 => StateMonad [tok] (Parser tok m)

John is writing up manual entry for all of this, but this commit
implements it.   I think.


2.  Added -fallow-incoherent-instances, and documented it.  The idea
is that sometimes GHC is over-protective about not committing to a
particular instance, and the programmer may want to say "commit anyway".
Here's the example:

    class Sat a where
      dict :: a

    data EqD a = EqD {eq :: a->a->Bool}

    instance Sat (EqD a) => Eq a where
      (==) = eq dict

    instance Sat (EqD Integer) where
      dict = EqD{eq=(==)}

    instance Eq a => Sat (EqD a) where
      dict = EqD{eq=(==)}

    class Collection c cxt | c -> cxt where
      empty :: Sat (cxt a) => c a
      single :: Sat (cxt a) => a -> c a
      union :: Sat (cxt a) => c a -> c a -> c a
      member :: Sat (cxt a) => a -> c a -> Bool

    instance Collection [] EqD where
      empty = []
      single x = [x]
      union = (++)
      member = elem

It's an updated attempt to model "Restricted Data Types", if you
remember my Haskell workshop paper. In the end, though, GHC rejects
the program (even with fallow-overlapping-instances and
fallow-undecideable-instances), because there's more than one way to
construct the Eq instance needed by elem.

Yet all the ways are equivalent! So GHC is being a bit over-protective
of me, really: I know what I'm doing and I would LIKE it to pick an
arbitrary one. Maybe a flag fallow-incoherent-instances would be a
useful thing to add?

------------------------------
	Add linear implicit parameters
	------------------------------

Linear implicit parameters are an idea developed by Koen Claessen,
Mark Shields, and Simon PJ, last week.  They address the long-standing
problem that monads seem over-kill for certain sorts of problem, notably:

	* distributing a supply of unique names
	* distributing a suppply of random numbers
	* distributing an oracle (as in QuickCheck)


Linear implicit parameters are just like ordinary implicit parameters,
except that they are "linear" -- that is, they cannot be copied, and
must be explicitly "split" instead.  Linear implicit parameters are
written '%x' instead of '?x'.  (The '/' in the '%' suggests the
split!)

For example:

    data NameSupply = ...

    splitNS :: NameSupply -> (NameSupply, NameSupply)
    newName :: NameSupply -> Name

    instance PrelSplit.Splittable NameSupply where
	split = splitNS


    f :: (%ns :: NameSupply) => Env -> Expr -> Expr
    f env (Lam x e) = Lam x' (f env e)
		    where
		      x'   = newName %ns
		      env' = extend env x x'
    ...more equations for f...

Notice that the implicit parameter %ns is consumed
	once by the call to newName
	once by the recursive call to f

So the translation done by the type checker makes
the parameter explicit:

    f :: NameSupply -> Env -> Expr -> Expr
    f ns env (Lam x e) = Lam x' (f ns1 env e)
		       where
	 		 (ns1,ns2) = splitNS ns
			 x' = newName ns2
			 env = extend env x x'

Notice the call to 'split' introduced by the type checker.
How did it know to use 'splitNS'?  Because what it really did
was to introduce a call to the overloaded function 'split',
ndefined by

	class Splittable a where
	  split :: a -> (a,a)

The instance for Splittable NameSupply tells GHC how to implement
split for name supplies.  But we can simply write

	g x = (x, %ns, %ns)

and GHC will infer

	g :: (Splittable a, %ns :: a) => b -> (b,a,a)

The Splittable class is built into GHC.  It's defined in PrelSplit,
and exported by GlaExts.

Other points:

* '?x' and '%x' are entirely distinct implicit parameters: you
  can use them together and they won't intefere with each other.

* You can bind linear implicit parameters in 'with' clauses.

* You cannot have implicit parameters (whether linear or not)
  in the context of a class or instance declaration.


Warnings
~~~~~~~~
The monomorphism restriction is even more important than usual.
Consider the example above:

    f :: (%ns :: NameSupply) => Env -> Expr -> Expr
    f env (Lam x e) = Lam x' (f env e)
		    where
		      x'   = newName %ns
		      env' = extend env x x'

If we replaced the two occurrences of x' by (newName %ns), which is
usually a harmless thing to do, we get:

    f :: (%ns :: NameSupply) => Env -> Expr -> Expr
    f env (Lam x e) = Lam (newName %ns) (f env e)
		    where
		      env' = extend env x (newName %ns)

But now the name supply is consumed in *three* places
(the two calls to newName,and the recursive call to f), so
the result is utterly different.  Urk!  We don't even have
the beta rule.

Well, this is an experimental change.  With implicit
parameters we have already lost beta reduction anyway, and
(as John Launchbury puts it) we can't sensibly reason about
Haskell programs without knowing their typing.

Of course, none of this is throughly tested, either.

----------------------
	Implement Rank-N types
	----------------------

This commit implements the full glory of Rank-N types, using
the Odersky/Laufer approach described in their paper
	"Putting type annotations to work"

In fact, I've had to adapt their approach to deal with the
full glory of Haskell (including pattern matching, and the
scoped-type-variable extension).  However, the result is:

* There is no restriction to rank-2 types.  You can nest forall's
  as deep as you like in a type.  For example, you can write a type
  like
	p :: ((forall a. Eq a => a->a) -> Int) -> Int
  This is a rank-3 type, illegal in GHC 5.02

* When matching types, GHC uses the cunning Odersky/Laufer coercion
  rules.  For example, suppose we have
	q :: (forall c. Ord c => c->c) -> Int
  Then, is this well typed?
	x :: Int
	x = p q
  Yes, it is, but GHC has to generate the right coercion.  Here's
  what it looks like with all the big lambdas and dictionaries put in:

	x = p (\ f :: (forall a. Eq a => a->a) ->
		 q (/\c \d::Ord c -> f c (eqFromOrd d)))

  where eqFromOrd selects the Eq superclass dictionary from the Ord
  dicationary:		eqFromOrd :: Ord a -> Eq a


* You can use polymorphic types in pattern type signatures.  For
  example:

	f (g :: forall a. a->a) = (g 'c', g True)

  (Previously, pattern type signatures had to be monotypes.)

* The basic rule for using rank-N types is that you must specify
  a type signature for every binder that you want to have a type
  scheme (as opposed to a plain monotype) as its type.

  However, you don't need to give the type signature on the
  binder (as I did above in the defn for f).  You can give it
  in a separate type signature, thus:

	f :: (forall a. a->a) -> (Char,Bool)
	f g = (g 'c', g True)

  GHC will push the external type signature inwards, and use
  that information to decorate the binders as it comes across them.
  I don't have a *precise* specification of this process, but I
  think it is obvious enough in practice.

* In a type synonym you can use rank-N types too.  For example,
  you can write

	type IdFun = forall a. a->a

	f :: IdFun -> (Char,Bool)
	f g = (g 'c', g True)

  As always, type synonyms must always occur saturated; GHC
  expands them before it does anything else.  (Still, GHC goes
  to some trouble to keep them unexpanded in error message.)


The main plan is as before.  The main typechecker for expressions,
tcExpr, takes an "expected type" as its argument.  This greatly
improves error messages.  The new feature is that when this
"expected type" (going down) meets an "actual type" (coming up)
we use the new subsumption function
	TcUnify.tcSub
which checks that the actual type can be coerced into the
expected type (and produces a coercion function to demonstrate).

The main new chunk of code is TcUnify.tcSub.  The unifier itself
is unchanged, but it has moved from TcMType into TcUnify.  Also
checkSigTyVars has moved from TcMonoType into TcUnify.
Result: the new module, TcUnify, contains all stuff relevant
to subsumption and unification.

Unfortunately, there is now an inevitable loop between TcUnify
and TcSimplify, but that's just too bad (a simple TcUnify.hi-boot
file).


All of this doesn't come entirely for free.  Here's the typechecker
line count (INCLUDING comments)
	Before	16,551
	After	17,116

------------------------------------------
	Improved handling of scoped type variables
	------------------------------------------

The main effect of this commit is to allow scoped type variables
in pattern bindings, thus

	(x::a, y::b) = e

This was illegal, but now it's ok.  a and b have the same scope
as x and y.


On the way I beefed up the info inside a type variable
(TcType.TyVarDetails; c.f. IdInfo.GlobalIdDetails) which
helps to improve error messages. Hence the wide ranging changes.
Pity about the extra loop from Var to TcType, but can't be helped.

-------------------------------------------------------
  Correct an error in the handling of implicit parameters
  -------------------------------------------------------

	MERGE WITH STABLE BRANCH UNLESS HARD TO DO

Mark Shields discovered a bug in the way that implicit parameters
are dealt with by the type checker.  It's all a bit subtle, and
is extensively documented in TcSimplify.lhs.

This commit makes the code both simpler and more correct.  It subtly
changes the way in which type signatures are treated, but not in a way
anyone would notice: see notes with "Question 2: type signatures"
in TcSimplify.lhs.

Cosmetica

Add comments

Add pprEquation

Improve error messages from the typechecker,
after a suggestion from Alastair Reid.

-----------------------------------------
	Fix a bug in the monomorphism restriction
	------------------------------------------

Thanks for Koen for reporting this bug.

In tcSimplifyRestricted, I wrongly called tcSimpifyToDicts,
whereas actually we have to simplfy further than simply to
a dictionary.

The test for this is in typecheck/should_compile/tc132.hs

Yet another newtype-squashing bug; this time TcType.unifyTyX

Typos in a comment. Whitespace at eols.

--------------------------------------------
	Fix another bug in the squash-newtypes story.
	--------------------------------------------

[This one was spotted by Marcin, and is now enshrined in test tc130.]

The desugarer straddles the boundary between the type checker and
Core, so it sometimes needs to look through newtypes/implicit parameters
and sometimes not.  This is really a bit painful, but I can't think of
a better way to do it.

The only simple way to fix things was to pass a bit more type
information in the HsExpr type, from the type checker to the desugarer.
That led to the non-local changes you can see.

On the way I fixed one other thing.  In various HsSyn constructors
there is a Type that is bogus (bottom) before the type checker, and
filled in with a real type by the type checker.  In one place it was
a (Maybe Type) which was Nothing before, and (Just ty) afterwards.
I've defined a type synonym HsTypes.PostTcType for this, and a named
bottom value HsTypes.placeHolderType to use when you want the bottom
value.

----------------------------------
	Fix a predicate-simplification bug
	----------------------------------

Fixes a bug pointed out by Marcin

    data R = R {f :: Int}
    foo:: (?x :: Int) => R -> R
    foo r = r {f = ?x}

    Test.hs:4:
	Could not deduce `?x :: Int' from the context ()
	arising from use of implicit parameter `?x' at Test.hs:4
	In the record update: r {f = ?x}
	In the definition of `foo': r {f = ?x}

The predicate simplifier was declining to 'inherit' an
implicit parameter.  This is right for a let-binding, but
wrong for an expression binding.  For example, a simple
expression type signature:

		(?x + 1) :: Int

This was rejected because the ?x constraint could not be
floated out -- but that's wrong for expressions.

****	MERGE WITH 5.00 BRANCH     ********

	--------------------------------
	Monomorphism restriction for implicit parameters
	--------------------------------

This commit tidies up the way in which monomorphic bindings
are dealt with, incidentally fixing a bug to do with implicit
parameters.

The tradeoffs concerning monomorphism and implicit paramters are
now documented in TcSimplify.lhs, and all the strategic choices
are made there (rather than in TcBinds where they were before).

I've continued with choice (B) -- which Jeff first implemented --
because that's what Hugs does, lacking any other consensus.

------------------------------------------------
	Dramatically improve the error messages arising
	from failed unifications triggered by 'improvement'
	------------------------------------------------

A bit more plumbing in FunDeps, and consequential wibbles elsewhere

Changes this:

    Couldn't match `Int' against `[(String, Int)]'
	Expected type: Int
	Inferred type: [(String, Int)]

to this:

    Foo.hs:8:
	Couldn't match `Int' against `[(String, Int)]'
	    Expected type: Int
	    Inferred type: [(String, Int)]
	When using functional dependencies to combine
	  ?env :: Int, arising from a type signature at Foo.hs:7
	  ?env :: [(String, Int)],
	    arising from use of implicit parameter `?env' at Foo.hs:8
	When generalising the types for ident

****	MERGE WITH 5.00 BRANCH     ********

	--------------------------------
	Fix a bad implicit parameter bug
	--------------------------------

TcSimplify.tcSimplifyIPs was just completely wrong; it wasn't
doing improvement properly nor binding values properly. Sigh.

To make this work nicely I added
	Inst.instName :: Inst -> Name

Add comments

Don't use the same simplify code for both restricted and unrestricted
bindings.  In particular, a restricted binding shouldn't try to capture
implicit params.

Improve error reporting

----------------
	Nuke ClassContext
	----------------

This commit tidies up a long-standing inconsistency in GHC.
The context of a class or instance decl used to be restricted
to predicates of the form
	C t1 .. tn
with
	type ClassContext = [(Class,[Type])]

but everywhere else in the compiler we used

	type ThetaType = [PredType]
where PredType can be any sort of constraint (= predicate).

The inconsistency actually led to a crash, when compiling
	class (?x::Int) => C a where {}

I've tidied all this up by nuking ClassContext altogether, and using
PredType throughout.  Lots of modified files, but all in
more-or-less trivial ways.

I've also added a check that the context of a class or instance
decl doesn't include a non-inheritable predicate like (?x::Int).

Other things

 * rename constructor 'Class' from type TypeRep.Pred to 'ClassP'
   (makes it easier to grep for)

 * rename constructor HsPClass  => HsClassP
		      HsPIParam => HsIParam

Improve rule matching

When doing constraint simplification on the LHS of a rule,
we *don't* want to do superclass commoning up.  Consider

	fromIntegral :: (Integral a, Num b) => a -> b
	{-# RULES "foo"  fromIntegral = id :: Int -> Int #-}

Here, a=b=Int, and Num Int is a superclass of Integral Int. But we *dont*
want to get

	forall dIntegralInt.
	fromIntegral Int Int dIntegralInt (scsel dIntegralInt) = id Int

because the scsel (super class selection) will mess up matching.
Instead we want

	forall dIntegralInt, dNumInt.
	fromIntegral Int Int dIntegralInt dNumInt = id Int


TcSimplify.tcSimplifyToDicts is the relevant function, but I had
to generalise the main simplification loop a little (adding the
type WantSCs).

Implement do-style bindings on the GHCi command line.

The syntax for a command-line is exactly that of a do statement, with
the following meanings:

  - `pat <- expr'
    performs expr, and binds each of the variables in pat.

  - `let pat = expr; ...'
    binds each of the variables in pat, doesn't do any evaluation

  - `expr'
    behaves as `it <- expr' if expr is IO-typed, or `let it = expr'
    followed by `print it' otherwise.

Typechecking [TcModule, TcBinds, TcHsSyn, TcInstDcls, TcSimplify]
~~~~~~~~~~~~
* Fix a bug in TcSimplify that broke functional dependencies.
  Interleaving unification and context reduction is trickier 
  than I thought.  Comments in the code amplify.  

* Fix a functional-dependency bug, that meant that this pgm:
	class C a b | a -> b where f :: a -> b
	
	g :: (C a b, Eq b) => a -> Bool
	g x = f x == f x
  gave an ambiguity error report.  I'm afraid I've forgotten
  what the problem was.


* Correct the implementation of the monomorphism restriction,
  in TcBinds.generalise.  This fixes Marcin's bug report:
	test1 :: Eq a => a -> b -> b
	test1 x y = y

	test2 = test1 (3::Int)
  Previously we were erroneously inferring test2 :: () -> ()

* Make the "unf_env" that is looped round in TcModule go round
  in a big loop, not just round tcImports.  This matters when
  we have mutually recursive modules, so that the Ids bound in
  the source code may appear in the imports.  Sigh.  But no big
  deal.

  It does mean that you have to be careful not to call isLocalId,
  isDataConId etc, because they consult the IdInfo of an Id, which 
  in turn may be determined by the loop-tied unf_env.

More on functional dependencies

My last commit allowed this:

	instance C a b => C [a] [b] where ...

if we have

	class C a b | a -> b

This commit completes the change, by making the 
improvement stages improve only the 'shape' of the second
argument of C.  

I also had to change the iteration in TcSimplify -- see
the comments in TcSimplify.inferLoop.

Fix superclass bug in context reduction (gave infinite loops before!)

Fix typos in comments.

------------------------------------
	   Mainly FunDeps (23 Jan 01)
	------------------------------------

This commit re-engineers the handling of functional dependencies.
A functional dependency is no longer an Inst; instead, the necessary
dependencies are snaffled out of their Class when necessary.

As part of this exercise I found that I had to re-work how to do generalisation
in a binding group.  There is rather exhaustive documentation on the new Plan
at the top of TcSimplify.

	******************
	WARNING: I have compiled all the libraries with this new compiler
		 and all looks well, but I have not run many programs.
		 Things may break.  Let me know if so.
	******************

The main changes are these:

1.  typecheck/TcBinds and TcSimplify have a lot of changes due to the
    new generalisation and context reduction story.  There are extensive
    comments at the start of TcSimplify

2.  typecheck/TcImprove is removed altogether.  Instead, improvement is
    interleaved with context reduction (until a fixpoint is reached).
    All this is done in TcSimplify.

3.  types/FunDeps has new exports
	* 'improve' does improvement, returning a list of equations
	* 'grow' and 'oclose' close a list of type variables wrt a set of
	  PredTypes, but in slightly different ways.  Comments in file.

4.  I improved the way in which we check that main::IO t.  It's tidier now.

In addition

*   typecheck/TcMatches:
	a) Tidy up, introducing a common function tcCheckExistentialPat

	b) Improve the typechecking of parallel list comprehensions,
	   which wasn't quite right before.  (see comments with tcStmts)

	WARNING: (b) is untested!  Jeff, you might want to check.

*   Numerous other incidental changes in the typechecker

*   Manuel found that rules don't fire well when you have partial applications
    from overloading.  For example, we may get

	f a (d::Ord a) = let m_g = g a d
			 in
			 \y :: a -> ...(m_g (h y))...

    The 'method' m_g doesn't get inlined because (g a d) might be a redex.
    Yet a rule that looks like
		g a d (h y) = ...
    won't fire because that doesn't show up.  One way out would be to make
    the rule matcher a bit less paranoid about duplicating work, but instead
    I've added a flag
			-fno-method-sharing
    which controls whether we generate things like m_g in the first place.
    It's not clear that they are a win in the first place.

    The flag is actually consulted in Inst.tcInstId

Remove bogus zonkInst

Compiles now

merge rev. 1.46.2.3 from ghc-4-07-branch (fix line numbers in
defaulting warnings).

1.	Outputable.PprStyle now carries a bit more information
	In particular, the printing style tells whether to print
	a name in unqualified form.  This used to be embedded in
	a Name, but since Names now outlive a single compilation unit,
	that's no longer appropriate.

	So now the print-unqualified predicate is passed in the printing
	style, not embedded in the Name.

   2.	I tidied up HscMain a little.  Many of the showPass messages
	have migraged into the repective pass drivers

Track renaming of typecheck/TcInstUtil to types/InstEnv.

Flags hacking:

   - `dopt_GlasgowExts'  is now written `dopt Opt_GlasgowExts'
   - convert all the warning options into DynFlags

Mostly typechecker stuff.

Simons work, mainly on the type checker

--------------------------------------
	Adding generics		SLPJ Oct 2000
	--------------------------------------

This big commit adds Hinze/PJ-style generic class definitions, based
on work by Andrei Serjantov.  For example:

  class Bin a where
    toBin   :: a -> [Int]
    fromBin :: [Int] -> (a, [Int])

    toBin {| Unit |}    Unit	  = []
    toBin {| a :+: b |} (Inl x)   = 0 : toBin x
    toBin {| a :+: b |} (Inr y)   = 1 : toBin y
    toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y


    fromBin {| Unit |}    bs      = (Unit, bs)
    fromBin {| a :+: b |} (0:bs)  = (Inl x, bs')    where (x,bs') = fromBin bs
    fromBin {| a :+: b |} (1:bs)  = (Inr y, bs')    where (y,bs') = fromBin bs
    fromBin {| a :*: b |} bs  	  = (x :*: y, bs'') where (x,bs' ) = fromBin bs
							  (y,bs'') = fromBin bs'

Now we can say simply

  instance Bin a => Bin [a]

and the compiler will derive the appropriate code automatically.

		(About 9k lines of diffs.  Ha!)


Generic related things
~~~~~~~~~~~~~~~~~~~~~~

* basicTypes/BasicTypes: The EP type (embedding-projection pairs)

* types/TyCon:
	An extra field in an algebraic tycon (genInfo)

* types/Class, and hsSyn/HsBinds:
	Each class op (or ClassOpSig) carries information about whether
	it  	a) has no default method
		b) has a polymorphic default method
		c) has a generic default method
	There's a new data type for this: Class.DefMeth

* types/Generics:
	A new module containing good chunk of the generic-related code
	It has a .hi-boot file (alas).

* typecheck/TcInstDcls, typecheck/TcClassDcl:
	Most of the rest of the generics-related code

* hsSyn/HsTypes:
	New infix type form to allow types of the form
		data a :+: b = Inl a | Inr b

* parser/Parser.y, Lex.lhs, rename/ParseIface.y:
	Deal with the new syntax

* prelude/TysPrim, TysWiredIn:
	Need to generate generic stuff for the wired-in TyCons

* rename/RnSource RnBinds:
	A rather gruesome hack to deal with scoping of type variables
	from a generic patterns.  Details commented in the ClassDecl
	case of RnSource.rnDecl.

	Of course, there are many minor renamer consequences of the
	other changes above.

* lib/std/PrelBase.lhs
	Data type declarations for Unit, :+:, :*:


Slightly unrelated housekeeping
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* hsSyn/HsDecls:
	ClassDecls now carry the Names for their implied declarations
	(superclass selectors, tycon, etc) in a list, rather than
	laid out one by one.  This simplifies code between the parser
	and the type checker.

* prelude/PrelNames, TysWiredIn:
	All the RdrNames are now together in PrelNames.

* utils/ListSetOps:
	Add finite mappings based on equality and association lists (Assoc a b)
	Move stuff from List.lhs that is related

--------------------------------------------------
	Tidying up HsLit, and making it possible to define
		your own numeric library

		Simon PJ 22 Sept 00
	--------------------------------------------------

** NOTE: I did these changes on the aeroplane.  They should compile,
	 and the Prelude still compiles OK, but it's entirely 
	 possible that I've broken something

The original reason for this many-file but rather shallow
commit is that it's impossible in Haskell to write your own
numeric library.  Why?  Because when you say '1' you get 
(Prelude.fromInteger 1), regardless of what you hide from the
Prelude, or import from other libraries you have written.  So the
idea is to extend the -fno-implicit-prelude flag so that 
in addition to no importing the Prelude, you can rebind 
	fromInteger	-- Applied to literal constants
	fromRational	-- Ditto
	negate		-- Invoked by the syntax (-x)
	the (-) used when desugaring n+k patterns

After toying with other designs, I eventually settled on a simple,
crude one: rather than adding a new flag, I just extended the
semantics of -fno-implicit-prelude so that uses of fromInteger,
fromRational and negate are all bound to "whatever is in scope" 
rather than "the fixed Prelude functions".  So if you say

	{-# OPTIONS -fno-implicit-prelude #-}
	module M where
 	import MyPrelude( fromInteger )

	x = 3

the literal 3 will use whatever (unqualified) "fromInteger" is in scope,
in this case the one gotten from MyPrelude.


On the way, though, I studied how HsLit worked, and did a substantial tidy
up, deleting quite a lot of code along the way.  In particular.

* HsBasic.lhs is renamed HsLit.lhs.  It defines the HsLit type.

* There are now two HsLit types, both defined in HsLit.
	HsLit for non-overloaded literals (like 'x')
	HsOverLit for overloaded literals (like 1 and 2.3)

* HsOverLit completely replaces Inst.OverloadedLit, which disappears.
  An HsExpr can now be an HsOverLit as well as an HsLit.

* HsOverLit carries the Name of the fromInteger/fromRational operation,
  so that the renamer can help with looking up the unqualified name 
  when -fno-implicit-prelude is on.  Ditto the HsExpr for negation.
  It's all very tidy now.

* RdrHsSyn contains the stuff that handles -fno-implicit-prelude
  (see esp RdrHsSyn.prelQual).  RdrHsSyn also contains all the "smart constructors"
  used by the parser when building HsSyn.  See for example RdrHsSyn.mkNegApp
  (previously the renamer (!) did the business of turning (- 3#) into -3#).

* I tidied up the handling of "special ids" in the parser.  There's much
  less duplication now.

* Move Sven's Horner stuff to the desugarer, where it belongs.  
  There's now a nice function DsUtils.mkIntegerLit which brings together
  related code from no fewer than three separate places into one single
  place.  Nice!

* A nice tidy-up in MatchLit.partitionEqnsByLit became possible.

* Desugaring of HsLits is now much tidier (DsExpr.dsLit)

* Some stuff to do with RdrNames is moved from ParseUtil.lhs to RdrHsSyn.lhs,
  which is where it really belongs.

* I also removed 
	many unnecessary imports from modules 
	quite a bit of dead code
  in divers places

Functional Dependencies were not getting simplified away when the dictionary
that generated them was simplified by instance resolution.  Fixed.