1. 27 Oct, 2003 1 commit
  2. 09 Oct, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-10-09 11:58:39 by simonpj] · 98688c6e
      simonpj authored
      		GHC heart/lung transplant
      This major commit changes the way that GHC deals with importing
      types and functions defined in other modules, during renaming and
      typechecking.  On the way I've changed or cleaned up numerous other
      things, including many that I probably fail to mention here.
      Major benefit: GHC should suck in many fewer interface files when
      compiling (esp with -O).  (You can see this with -ddump-rn-stats.)
      It's also some 1500 lines of code shorter than before.
      **	So expect bugs!  I can do a 3-stage bootstrap, and run
      **	the test suite, but you may be doing stuff I havn't tested.
      ** 	Don't update if you are relying on a working HEAD.
      In particular, (a) External Core and (b) GHCi are very little tested.
      	But please, please DO test this version!
      		Big things
      Interface files, version control, and importing declarations
      * There is a totally new data type for stuff that lives in interface files:
      	Original names			IfaceType.IfaceExtName
      	Types				IfaceType.IfaceType
      	Declarations (type,class,id)	IfaceSyn.IfaceDecl
      	Unfoldings			IfaceSyn.IfaceExpr
        (Previously we used HsSyn for type/class decls, and UfExpr for unfoldings.)
        The new data types are in iface/IfaceType and iface/IfaceSyn.  They are
        all instances of Binary, so they can be written into interface files.
        Previous engronkulation concering the binary instance of RdrName has
        gone away -- RdrName is not an instance of Binary any more.  Nor does
        Binary.lhs need to know about the ``current module'' which it used to,
        which made it specialised to GHC.
        A good feature of this is that the type checker for source code doesn't
        need to worry about the possibility that we might be typechecking interface
        file stuff.  Nor does it need to do renaming; we can typecheck direct from
        IfaceSyn, saving a whole pass (module TcIface)
      * Stuff from interface files is sucked in *lazily*, rather than being eagerly
        sucked in by the renamer. Instead, we use unsafeInterleaveIO to capture
        a thunk for the unfolding of an imported function (say).  If that unfolding
        is every pulled on, TcIface will scramble over the unfolding, which may
        in turn pull in the interface files of things mentioned in the unfolding.
        The External Package State is held in a mutable variable so that it
        can be side-effected by this lazy-sucking-in process (which may happen
        way later, e.g. when the simplifier runs).   In effect, the EPS is a kind
        of lazy memo table, filled in as we suck things in.  Or you could think
        of it as a global symbol table, populated on demand.
      * This lazy sucking is very cool, but it can lead to truly awful bugs. The
        intent is that updates to the symbol table happen atomically, but very bad
        things happen if you read the variable for the table, and then force a
        thunk which updates the table.  Updates can get lost that way. I regret
        this subtlety.
        One example of the way it showed up is that the top level of TidyPgm
        (which updates the global name cache) to be much more disciplined about
        those updates, since TidyPgm may itself force thunks which allocate new
      * Version numbering in interface files has changed completely, fixing
        one major bug with ghc --make.  Previously, the version of A.f changed
        only if A.f's type and unfolding was textually different.  That missed
        changes to things that A.f's unfolding mentions; which was fixed by
        eagerly sucking in all of those things, and listing them in the module's
        usage list.  But that didn't work with --make, because they might have
        been already sucked in.
        Now, A.f's version changes if anything reachable from A.f (via interface
        files) changes.  A module with unchanged source code needs recompiling
        only if the versions of any of its free variables changes. [This isn't
        quite right for dictionary functions and rules, which aren't mentioned
        explicitly in the source.  There are extensive comments in module MkIface,
        where all version-handling stuff is done.]
      * We don't need equality on HsDecls any more (because they aren't used in
        interface files).  Instead we have a specialised equality for IfaceSyn
        (eqIfDecl etc), which uses IfaceEq instead of Bool as its result type.
        See notes in IfaceSyn.
      * The horrid bit of the renamer that tried to predict what instance decls
        would be needed has gone entirely.  Instead, the type checker simply
        sucks in whatever instance decls it needs, when it needs them.  Easy!
        Similarly, no need for 'implicitModuleFVs' and 'implicitTemplateHaskellFVs'
        etc.  Hooray!
      Types and type checking
      * Kind-checking of types is far far tidier (new module TcHsTypes replaces
        the badly-named TcMonoType).  Strangely, this was one of my
        original goals, because the kind check for types is the Right Place to
        do type splicing, but it just didn't fit there before.
      * There's a new representation for newtypes in TypeRep.lhs.  Previously
        they were represented using "SourceTypes" which was a funny compromise.
        Now they have their own constructor in the Type datatype.  SourceType
        has turned back into PredType, which is what it used to be.
      * Instance decl overlap checking done lazily.  Consider
      	instance C Int b
      	instance C a Int
        These were rejected before as overlapping, because when seeking
        (C Int Int) one couldn't tell which to use.  But there's no problem when
        seeking (C Bool Int); it can only be the second.
        So instead of checking for overlap when adding a new instance declaration,
        we check for overlap when looking up an Inst.  If we find more than one
        matching instance, we see if any of the candidates dominates the others
        (in the sense of being a substitution instance of all the others);
        and only if not do we report an error.
      	     Medium things
      * The TcRn monad is generalised a bit further.  It's now based on utils/IOEnv.lhs,
        the IO monad with an environment.  The desugarer uses the monad too,
        so that anything it needs can get faulted in nicely.
      * Reduce the number of wired-in things; in particular Word and Integer
        are no longer wired in.  The latter required HsLit.HsInteger to get a
        Type argument.  The 'derivable type classes' data types (:+:, :*: etc)
        are not wired in any more either (see stuff about derivable type classes
      * The PersistentComilerState is now held in a mutable variable
        in the HscEnv.  Previously (a) it was passed to and then returned by
        many top-level functions, which was painful; (b) it was invariably
        accompanied by the HscEnv.  This change tidies up top-level plumbing
        without changing anything important.
      * Derivable type classes are treated much more like 'deriving' clauses.
        Previously, the Ids for the to/from functions lived inside the TyCon,
        but now the TyCon simply records their existence (with a simple boolean).
        Anyone who wants to use them must look them up in the environment.
        This in turn makes it easy to generate the to/from functions (done
        in types/Generics) using HsSyn (like TcGenDeriv for ordinary derivings)
        instead of CoreSyn, which in turn means that (a) we don't have to figure
        out all the type arguments etc; and (b) it'll be type-checked for us.
        Generally, the task of generating the code has become easier, which is
        good for Manuel, who wants to make it more sophisticated.
      * A Name now says what its "parent" is. For example, the parent of a data
        constructor is its type constructor; the parent of a class op is its
        class.  This relationship corresponds exactly to the Avail data type;
        there may be other places we can exploit it.  (I made the change so that
        version comparison in interface files would be a bit easier; but in
        fact it tided up other things here and there (see calls to
        Name.nameParent).  For example, the declaration pool, of declararations
        read from interface files, but not yet used, is now keyed only by the 'main'
        name of the declaration, not the subordinate names.
      * New types OccEnv and OccSet, with the usual operations.
        OccNames can be efficiently compared, because they have uniques, thanks
        to the hashing implementation of FastStrings.
      * The GlobalRdrEnv is now keyed by OccName rather than RdrName.  Not only
        does this halve the size of the env (because we don't need both qualified
        and unqualified versions in the env), but it's also more efficient because
        we can use a UniqFM instead of a FiniteMap.
        Consequential changes to Provenance, which has moved to RdrName.
      * External Core remains a bit of a hack, as it was before, done with a mixture
        of HsDecls (so that recursiveness and argument variance is still inferred),
        and IfaceExprs (for value declarations).  It's not thoroughly tested.
      	     Minor things
      * DataCon fields dcWorkId, dcWrapId combined into a single field
        dcIds, that is explicit about whether the data con is a newtype or not.
        MkId.mkDataConWorkId and mkDataConWrapId are similarly combined into
      * Choosing the boxing strategy is done for *source* type decls only, and
        hence is now in TcTyDecls, not DataCon.
      * WiredIn names are distinguished by their n_sort field, not by their location,
        which was rather strange
      * Define Maybes.mapCatMaybes :: (a -> Maybe b) -> [a] -> [b]
        and use it here and there
      * Much better pretty-printing of interface files (--show-iface)
      Many, many other small things.
      	     File changes
      * New iface/ subdirectory
      * Much of RnEnv has moved to iface/IfaceEnv
      * MkIface and BinIface have moved from main/ to iface/
      * types/Variance has been absorbed into typecheck/TcTyDecls
      * RnHiFiles and RnIfaces have vanished entirely.  Their
        work is done by iface/LoadIface
      * hsSyn/HsCore has gone, replaced by iface/IfaceSyn
      * typecheck/TcIfaceSig has gone, replaced by iface/TcIface
      * typecheck/TcMonoType has been renamed to typecheck/TcHsType
      * basicTypes/Var.hi-boot and basicTypes/Generics.hi-boot have gone altogether
  3. 16 Sep, 2003 1 commit
    • simonmar's avatar
      [project @ 2003-09-16 13:03:37 by simonmar] · 2129fa6f
      simonmar authored
      Legacy Removal
      The following features have been consigned to the bit bucket:
        ``....''  (lit-lits)
        the CCallable class
        the CReturnable class
  4. 11 Sep, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-09-11 14:20:40 by simonpj] · 25aeb246
      simonpj authored
      	    Allow recursive dictionaries
      In response to various bleatings, here's a lovely fix that involved simply
      inverting two lines of code, to allow recursive dictionaries.  Here's
      the comment.  (typecheck/should_run/tc030 tests it)
          data D r = ZeroD | SuccD (r (D r));
          instance (Eq (r (D r))) => Eq (D r) where
              ZeroD     == ZeroD     = True
              (SuccD a) == (SuccD b) = a == b
              _         == _         = False;
          equalDC :: D [] -> D [] -> Bool;
          equalDC = (==);
      We need to prove (Eq (D [])).  Here's how we go:
      	d1 : Eq (D [])
      by instance decl, holds if
      	d2 : Eq [D []]
      	where 	d1 = dfEqD d2
      by instance decl of Eq, holds if
      	d3 : D []
      	where	d2 = dfEqList d2
      		d1 = dfEqD d2
      But now we can "tie the knot" to give
      	d3 = d1
      	d2 = dfEqList d2
      	d1 = dfEqD d2
      and it'll even run!  The trick is to put the thing we are trying to prove
      (in this case Eq (D []) into the database before trying to prove its
      contributing clauses.
  5. 09 Jul, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-07-09 11:08:03 by simonpj] · 983d2d8e
      simonpj authored
      	Wibble to GHCi constraint simplification
      The new GHCi constraint-simplification story, with defaulting for
      Show, Eq, Ord, should only apply to command-line expressions, not
      to modules loaded by GHCi.
      Hence new variant, TcSimplify.tcSimplifyInteractive
  6. 03 Jul, 2003 2 commits
    • simonpj's avatar
      [project @ 2003-07-03 16:22:16 by simonpj] · 38c8801e
      simonpj authored
      	Type defaulting in GHCi
      	[Merge to stable branch, I think.]
      [Part 2 to this commit: add Eq and Ord, to allow
      	[] == []
      at the prompt.
            Extend type defaulting in GHCi so that
      	ghci>  []
            works.  Suggested by Ralf Hinze.
    • simonpj's avatar
      [project @ 2003-07-03 14:33:18 by simonpj] · 5affd811
      simonpj authored
      	Type defaulting in GHCi
      	[Merge to stable branch, I think.]
      Extend type defaulting in GHCi so that
      	ghci>  []
      works.  Suggested by Ralf Hinze.
  7. 20 Jun, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-06-20 11:14:18 by simonpj] · 1f861358
      simonpj authored
      	Fix a small quantification bug
      We were quantifying over too few type variables, because fdPredsOfInsts was
      being too eager to discard predicates. This only affects rather obscure
      programs.  Here's the one Iavor found:
      	class C a b where f :: a -> b
      	g x = fst (f x)
      We want to get the type
         	g :: forall a b c.  C a (b,c) => a -> b
      but GHC 6.0 bogusly gets
         	g :: forall a b.  C a (b,()) => a -> b
      A test is in should_compile/tc168
  8. 09 Apr, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-04-09 08:07:58 by simonpj] · cf31797e
      simonpj authored
            Fix a functional-dependency-related bug in
      	MERGE TO STABLE if it goes over conveniently
      		(but I rather think it may not)
      tcSimplifyRestricted works by (a) simplifying brutall to find out
      what the constrained type variables are, and (b) simplifying more
      gently, knowing the constrained type varaibles.  The bug is that
      in step (b) we were not doing the check-for-improvement-and-loop
      part, thinking that step (a) had alrady done all the improvement.
      But not so, as an example in the code now shows.
      Simple to fix.  I rather think we could tidy up these various loops.
  9. 19 Feb, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-02-19 15:54:05 by simonpj] · 3355c9d5
      simonpj authored
      	 	Two minor wibbles
      1.  Make the generic toT/fromT Ids for "generic derived classes" into
          proper ImplicitIds, with their own GlobalIdDetails. This makes it
          easier to identify them.  (The lack of this showed up as a bug
          when I made an apparently-innocuous other change.)
      2.  Distinguish ClassOpIds from RecordSelIds in their GlobalIdDetails.
          They are treated differently here and there, so I made this change
          as part of (1)
      3.  Ensure that a declaration quotation [d| ... |] does not have a
          permanent effect on the instance environment. (A TH fix.)
  10. 14 Feb, 2003 1 commit
  11. 23 Jan, 2003 2 commits
  12. 13 Jan, 2003 1 commit
  13. 06 Jan, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-01-06 15:30:14 by simonpj] · fcf37c94
      simonpj authored
      	Several small but tiresome things shown up by Template Haskell
      1. Make the 'knot' in TcRnDriver much smaller; in fact move it to
         TcIfaceSig.tcInterfaceSigs.  Reasons
      	a) much tidier
      	b) avoids a loop in Template Haskell, when we try to run
      	   an expression during type checking (when the knot is
      	   not fully tied)
         See comments in TcIfaceSig
      2. Stop typechecking if tcGroup fails.  Reason: otherwise tcLookup can
         fail in the next group.
      3. Catch linking errors more gracefully when running a splice (in TcSplice)
  14. 28 Nov, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-11-28 17:17:41 by simonpj] · 3c58c25b
      simonpj authored
            A day's work to improve error messages
      1.  Indicate when the cause of the error is likely to be the monomorpism
          restriction, and identify the offending variables.  This involves
          mainly tcSimplifyTop and its error generation.
      2.  Produce much better kind error messages.  No more
      	  Couldn't match `* -> *' against `Type bx'
      	      Expected kind: * -> *
      	      Inferred kind: Type bx
      	  When checking that `DiGraph n' is a type
      It took a surprisingly long time to get the details right.
  15. 18 Nov, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-11-18 14:25:50 by simonpj] · 4e84be0c
      simonpj authored
      	Class ops that do not introduce for-alls
      	MERGE TO STABLE (if poss)
      The handling of class ops that do not add an extra for-all
      was utterly bogus.  For example:
      	class C a where
      	    fc :: (?p :: String) => a;
      	class D a where
      	    fd :: (Ord a) => [a] -> [a]
      De-bogus-ing means
      a) Being careful when taking apart the class op type in
      b) Ditto when making the method Id in an instance binding.
         Hence new function Inst.tcInstClassOp, and its calls
         in TcInstDcls, and TcClassDcls
  16. 09 Oct, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-10-09 15:03:48 by simonpj] · 8c1b6bd7
      simonpj authored
      	Lots more Template Haskell stuff
      At last!  Top-level declaration splices work!
      Syntax is
      	$(f x)
      not "splice (f x)" as in the paper.
      Lots jiggling around, particularly with the top-level plumbining.
      Note the new data type HsDecls.HsGroup.
  17. 13 Sep, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-09-13 15:02:25 by simonpj] · 9af77fa4
      simonpj authored
      	Make Template Haskell into the HEAD
      This massive commit transfers to the HEAD all the stuff that
      Simon and Tim have been doing on Template Haskell.  The
      meta-haskell-branch is no more!
      WARNING: make sure that you
        * Update your links if you are using link trees.
          Some modules have been added, some have gone away.
        * Do 'make clean' in all library trees.
          The interface file format has changed, and you can
          get strange panics (sadly) if GHC tries to read old interface files:
          e.g.  ghc-5.05: panic! (the `impossible' happened, GHC version 5.05):
      	  Binary.get(TyClDecl): ForeignType
        * You need to recompile the rts too; Linker.c has changed
      However the libraries are almost unaltered; just a tiny change in
      Base, and to the exports in Prelude.
      NOTE: so far as TH itself is concerned, expression splices work
      fine, but declaration splices are not complete.
      		The main change
      The main structural change: renaming and typechecking have to be
      interleaved, because we can't rename stuff after a declaration splice
      until after we've typechecked the stuff before (and the splice
      * Combine the renamer and typecheker monads into one
      	(TcRnMonad, TcRnTypes)
        These two replace TcMonad and RnMonad
      * Give them a single 'driver' (TcRnDriver).  This driver
        replaces TcModule.lhs and Rename.lhs
      * The haskell-src library package has a module
        which defines the Haskell data type seen by the TH programmer.
      * New modules:
      	hsSyn/Convert.hs 	converts THSyntax -> HsSyn
      	deSugar/DsMeta.hs 	converts HsSyn -> THSyntax
      * New module typecheck/TcSplice type-checks Template Haskell splices.
      		Linking stuff
      * ByteCodeLink has been split into
      	ByteCodeLink	(which links)
      	ByteCodeAsm	(which assembles)
      * New module ghci/ObjLink is the object-code linker.
      * compMan/CmLink is removed entirely (was out of place)
        Ditto CmTypes (which was tiny)
      * Linker.c initialises the linker when it is first used (no need to call
        initLinker any more).  Template Haskell makes it harder to know when
        and whether to initialise the linker.
      	Gathering the LIE in the type checker
      * Instead of explicitly gathering constraints in the LIE
      	tcExpr :: RenamedExpr -> TcM (TypecheckedExpr, LIE)
        we now dump the constraints into a mutable varabiable carried
        by the monad, so we get
      	tcExpr :: RenamedExpr -> TcM TypecheckedExpr
        Much less clutter in the code, and more efficient too.
        (Originally suggested by Mark Shields.)
      		Remove "SysNames"
      Because the renamer and the type checker were entirely separate,
      we had to carry some rather tiresome implicit binders (or "SysNames")
      along inside some of the HsDecl data structures.  They were both
      tiresome and fragile.
      Now that the typechecker and renamer are more intimately coupled,
      we can eliminate SysNames (well, mostly... default methods still
      carry something similar).
      		Clean up HsPat
      One big clean up is this: instead of having two HsPat types (InPat and
      OutPat), they are now combined into one.  This is more consistent with
      the way that HsExpr etc is handled; there are some 'Out' constructors
      for the type checker output.
      	HsPat.InPat	--> HsPat.Pat
      	HsPat.OutPat	--> HsPat.Pat
      	No 'pat' type parameter in HsExpr, HsBinds, etc
      	Constructor patterns are nicer now: they use
      	for the three cases of constructor patterns:
      		prefix, infix, and record-bindings
      	The *same* data type HsConDetails is used in the type
      	declaration of the data type (HsDecls.TyData)
      Lots of associated clean-up operations here and there.  Less code.
      Everything is wonderful.
  18. 17 Jun, 2002 1 commit
  19. 23 May, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-05-23 15:51:26 by simonpj] · 61193fe4
      simonpj authored
      Don't report ambiguity errors
      	if other type errors have happened
      This saves a gratuitous error cascade when the type checker
      recovers from one error by giving f type (forall a.a), and
      then find an ambiguity problem as a direct result.
  20. 10 Apr, 2002 1 commit
  21. 02 Apr, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-04-02 13:21:36 by simonpj] · 13878c13
      simonpj authored
      	Fix two nasty, subtle loops in context simplification
      The context simplifier in TcSimplify was building a recursive
      dictionary, which meant the program looped when run.  The reason
      was pretty devious; in fact there are two independent causes.
      Cause 1
       	class Eq b => Foo a b
      	instance Eq a => Foo [a] a
      If we are reducing
      	d:Foo [t] t
      we'll first deduce that it holds (via the instance decl), thus:
      	d:Foo [t] t = $fFooList deq
      	deq:Eq t = ...some rhs depending on t...
      Now we add d's superclasses.  We must not then overwrite the Eq t
      constraint with a superclass selection!!
      The only decent way to solve this is to track what dependencies
      a binding has; that is what the is_loop parameter to TcSimplify.addSCs
      now does.
      Cause 2
      This shows up when simplifying the superclass context of an
      instance declaration.  Consider
        class S a
        class S a => C a where { opc :: a -> a }
        class S b => D b where { opd :: b -> b }
        instance C Int where
           opc = opd
        instance D Int where
           opd = opc
      From (instance C Int) we get the constraint set {ds1:S Int, dd:D Int}
      Simplifying, we may well get:
      	$dfCInt = :C ds1 (opd dd)
      	dd  = $dfDInt
      	ds1 = $p1 dd
      Notice that we spot that we can extract ds1 from dd.
      Alas!  Alack! We can do the same for (instance D Int):
      	$dfDInt = :D ds2 (opc dc)
      	dc  = $dfCInt
      	ds2 = $p1 dc
      And now we've defined the superclass in terms of itself.
      Solution: treat the superclass context separately, and simplify it
      all the way down to nothing on its own.  Don't toss any 'free' parts
      out to be simplified together with other bits of context.
      This is done in TcInstDcls.tcSuperClasses, which is well commented.
      All this from a bug report from Peter White!
  22. 27 Mar, 2002 1 commit
  23. 18 Mar, 2002 1 commit
  24. 08 Mar, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-03-08 15:50:53 by simonpj] · a170160c
      simonpj authored
      	Lift the class-method type restriction
      Haskell 98 prohibits class method types to mention constraints on the
      class type variable, thus:
        class Seq s a where
          fromList :: [a] -> s a
          elem     :: Eq a => a -> s a -> Bool
      The type of 'elem' is illegal in Haskell 98, because it contains the
      constraint 'Eq a', which constrains only the class type variable (in
      this case 'a').
      This commit lifts the restriction.  The way we do that is to do a full
      context reduction (tcSimplifyCheck) step for each method separately in
      TcClassDcl.tcMethodBind, rather than doing a single context reduction
      for the whole group of method bindings.
      As a result, I had to reorganise the code a bit, and tidy up.
  25. 15 Feb, 2002 1 commit
  26. 13 Feb, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-02-13 15:14:06 by simonpj] · e7030995
      simonpj authored
      	Fix a bugs in type inference for rank-N types
      We discovered this bug when looking at type rules!
      1. When type checking (e :: sigma-ty), we must specialise sigma-ty,
         else we lose the invariant that tcMonoType has.
      2. In tcExpr_id, we should pass in a Hole tyvar not an ordinary tyvar.
      As usual, I moved some functions around in consequence.
  27. 11 Feb, 2002 1 commit
    • chak's avatar
      [project @ 2002-02-11 08:20:38 by chak] · 10fcd78c
      chak authored
      		       * Merging from ghc-ndp-branch *
      This commit merges the current state of the "parallel array extension" and
      includes the following:
      * (Almost) completed Milestone 1:
        - The option `-fparr' activates the H98 extension for parallel arrays.
        - These changes have a high likelihood of conflicting (in the CVS sense)
          with other changes to GHC and are the reason for merging now.
        - ToDo: There are still some (less often used) functions not implemented in
      	  `PrelPArr' and a mechanism is needed to automatically import
      	  `PrelPArr' iff `-fparr' is given.  Documentation that should go into
      	  the Commentary is currently in `ghc/compiler/ndpFlatten/TODO'.
      * Partial Milestone 2:
        - The option `-fflatten' activates the flattening transformation and `-ndp'
          selects the "ndp" way (where all libraries have to be compiled with
          flattening).  The way option `-ndp' automagically turns on `-fparr' and
        - Almost all changes are in the new directory `ndpFlatten' and shouldn't
          affect the rest of the compiler.  The only exception are the options and
          the points in `HscMain' where the flattening phase is called when
          `-fflatten' is given.
        - This isn't usable yet, but already implements function lifting,
          vectorisation, and a new analysis that determines which parts of a module
          have to undergo the flattening transformation.  Missing are data structure
          and function specialisation, the unboxed array library (including fusion
          rules), and lots of testing.
      I have just run the regression tests on the thing without any problems.  So,
      it seems, as if we haven't broken anything crucial.
  28. 07 Feb, 2002 1 commit
  29. 05 Feb, 2002 1 commit
  30. 01 Feb, 2002 1 commit
  31. 31 Jan, 2002 1 commit
  32. 28 Dec, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-12-28 17:25:31 by simonpj] · ae969b47
      simonpj authored
      	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.
  33. 20 Dec, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-12-20 11:19:05 by simonpj] · 91c750cb
      simonpj authored
      	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
      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?
  34. 29 Nov, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-11-29 13:47:09 by simonpj] · 32a89583
      simonpj authored
      	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
      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)
      		      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)
      	 		 (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.
      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)
      		      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)
      		      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.
  35. 26 Nov, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-11-26 09:20:25 by simonpj] · 5e3f005d
      simonpj authored
      	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
      	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
      	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
      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
      All of this doesn't come entirely for free.  Here's the typechecker
      line count (INCLUDING comments)
      	Before	16,551
      	After	17,116
  36. 31 Oct, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-10-31 15:22:53 by simonpj] · 61bfd5dd
      simonpj authored
      	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.
  37. 25 Oct, 2001 2 commits
    • simonpj's avatar
      [project @ 2001-10-25 14:30:43 by simonpj] · d5f94cc1
      simonpj authored
        Correct an error in the handling of implicit parameters
      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.
    • simonpj's avatar
      [project @ 2001-10-25 09:58:39 by simonpj] · 2007c7e6
      simonpj authored