 25 Jan, 2006 3 commits


simonpj@microsoft.com authored
This very large commit adds impredicativity to GHC, plus numerous other small things. *** WARNING: I have compiled all the libraries, and *** a stage2 compiler, and everything seems *** fine. But don't grab this patch if you *** can't tolerate a hiccup if something is *** broken. The big picture is this: a) GHC handles impredicative polymorphism, as described in the "Boxy types: type inference for higherrank types and impredicativity" paper b) GHC handles GADTs in the new simplified (and very sligtly less epxrssive) way described in the "Simple unificationbased type inference for GADTs" paper But there are lots of smaller changes, and since it was preDarcs they are not individually recorded. Some things to watch out for: c) The story on lexicallyscoped type variables has changed, as per my email. I append the story below for completeness, but I am still not happy with it, and it may change again. In particular, the new story does not allow a patternbound scoped type variable to be wobbly, so (\(x::[a]) > ...) is usually rejected. This is more restrictive than before, and we might loosen up again. d) A consequence of adding impredicativity is that GHC is a bit less gung ho about converting automatically between (ty1 > forall a. ty2) and (forall a. ty1 > ty2) In particular, you may need to etaexpand some functions to make typechecking work again. Furthermore, functions are now invariant in their argument types, rather than being contravariant. Again, the main consequence is that you may occasionally need to etaexpand function arguments when using higherrank polymorphism. Please test, and let me know of any hiccups Scoped type variables in GHC ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ January 2006 0) Terminology. A *pattern binding* is of the form pat = rhs A *function binding* is of the form f pat1 .. patn = rhs A binding of the formm var = rhs is treated as a (degenerate) *function binding*. A *declaration type signature* is a separate type signature for a letbound or wherebound variable: f :: Int > Int A *pattern type signature* is a signature in a pattern: \(x::a) > x f (x::a) = x A *result type signature* is a signature on the result of a function definition: f :: forall a. [a] > a head (x:xs) :: a = x The form x :: a = rhs is treated as a (degnerate) function binding with a result type signature, not as a pattern binding. 1) The main invariants: A) A lexicallyscoped type variable always names a (rigid) type variable (not an arbitrary type). THIS IS A CHANGE. Previously, a scoped type variable named an arbitrary *type*. B) A type signature always describes a rigid type (since its free (scoped) type variables name rigid type variables). This is also a change, a consequence of (A). C) Distinct lexicallyscoped type variables name distinct rigid type variables. This choice is open; 2) Scoping 2(a) If a declaration type signature has an explicit forall, those type variables are brought into scope in the right hand side of the corresponding binding (plus, for function bindings, the patterns on the LHS). f :: forall a. a > [a] f (x::a) = [x :: a, x] Both occurences of 'a' in the second line are bound by the 'forall a' in the first line A declaration type signature *without* an explicit toplevel forall is implicitly quantified over all the type variables that are mentioned in the type but not already in scope. GHC's current rule is that this implicit quantification does *not* bring into scope any new scoped type variables. f :: a > a f x = ...('a' is not in scope here)... This gives compatibility with Haskell 98 2(b) A pattern type signature implicitly brings into scope any type variables mentioned in the type that are not already into scope. These are called *patternbound type variables*. g :: a > a > [a] g (x::a) (y::a) = [y :: a, x] The pattern type signature (x::a) brings 'a' into scope. The 'a' in the pattern (y::a) is bound, as is the occurrence on the RHS. A pattern type siganture is the only way you can bring existentials into scope. data T where MkT :: forall a. a > (a>Int) > T f x = case x of MkT (x::a) f > f (x::a) 2a) QUESTION class C a where op :: forall b. b>a>a instance C (T p q) where op = <rhs> Clearly p,q are in scope in <rhs>, but is 'b'? Not at the moment. Nor can you add a type signature for op in the instance decl. You'd have to say this: instance C (T p q) where op = let op' :: forall b. ... op' = <rhs> in op' 3) A patternbound type variable is allowed only if the pattern's expected type is rigid. Otherwise we don't know exactly *which* skolem the scoped type variable should be bound to, and that means we can't do GADT refinement. This is invariant (A), and it is a big change from the current situation. f (x::a) = x  NO; pattern type is wobbly g1 :: b > b g1 (x::b) = x  YES, because the pattern type is rigid g2 :: b > b g2 (x::c) = x  YES, same reason h :: forall b. b > b h (x::b) = x  YES, but the inner b is bound k :: forall b. b > b k (x::c) = x  NO, it can't be both b and c 3a) You cannot give different names for the same type variable in the same scope (Invariant (C)): f1 :: p > p > p  NO; because 'a' and 'b' would be f1 (x::a) (y::b) = (x::a)  bound to the same type variable f2 :: p > p > p  OK; 'a' is bound to the type variable f2 (x::a) (y::a) = (x::a)  over which f2 is quantified  NB: 'p' is not lexically scoped f3 :: forall p. p > p > p  NO: 'p' is now scoped, and is bound to f3 (x::a) (y::a) = (x::a)  to the same type varialble as 'a' f4 :: forall p. p > p > p  OK: 'p' is now scoped, and its occurences f4 (x::p) (y::p) = (x::p)  in the patterns are bound by the forall 3b) You can give a different name to the same type variable in different disjoint scopes, just as you can (if you want) give diferent names to the same value parameter g :: a > Bool > Maybe a g (x::p) True = Just x :: Maybe p g (y::q) False = Nothing :: Maybe q 3c) Scoped type variables respect alpha renaming. For example, function f2 from (3a) above could also be written: f2' :: p > p > p f2' (x::b) (y::b) = x::b where the scoped type variable is called 'b' instead of 'a'. 4) Result type signatures obey the same rules as pattern types signatures. In particular, they can bind a type variable only if the result type is rigid f x :: a = x  NO g :: b > b g x :: b = x  YES; binds b in rhs 5) A *pattern type signature* in a *pattern binding* cannot bind a scoped type variable (x::a, y) = ...  Legal only if 'a' is already in scope Reason: in type checking, the "expected type" of the LHS pattern is always wobbly, so we can't bind a rigid type variable. (The exception would be for an existential type variable, but existentials are not allowed in pattern bindings either.) Even this is illegal f :: forall a. a > a f x = let ((y::b)::a, z) = ... in Here it looks as if 'b' might get a rigid binding; but you can't bind it to the same skolem as a. 6) Explicitlyforall'd type variables in the *declaration type signature(s)* for a *pattern binding* do not scope AT ALL. x :: forall a. a>a  NO; the forall a does Just (x::a>a) = Just id  not scope at all y :: forall a. a>a Just y = Just (id :: a>a)  NO; same reason THIS IS A CHANGE, but one I bet that very few people will notice. Here's why: strange :: forall b. (b>b,b>b) strange = (id,id) x1 :: forall a. a>a y1 :: forall b. b>b (x1,y1) = strange This is legal Haskell 98 (modulo the forall). If both 'a' and 'b' both scoped over the RHS, they'd get unified and so cannot stand for distinct type variables. One could *imagine* allowing this: x2 :: forall a. a>a y2 :: forall a. a>a (x2,y2) = strange using the very same type variable 'a' in both signatures, so that a single 'a' scopes over the RHS. That seems defensible, but odd, because though there are two type signatures, they introduce just *one* scoped type variable, a. 7) Possible extension. We might consider allowing \(x :: [ _ ]) > <expr> where "_" is a wild card, to mean "x has type list of something", without naming the something.

Simon Marlow authored

simonpj@microsoft.com authored

 24 Jan, 2006 3 commits


Simon Marlow authored

Simon Marlow authored

Simon Marlow authored

 22 Jan, 2006 1 commit


Dinko Tenev authored

 20 Jan, 2006 1 commit


Simon Marlow authored

 23 Jan, 2006 4 commits


Simon Marlow authored
Along the lines of the clean/dirty arrays and IORefs implemented recently, now threads are marked clean or dirty depending on whether they need to be scanned during a minor GC or not. This should speed up GC when there are lots of threads, especially if most of them are idle.

simonpj@microsoft.com authored

Simon Marlow authored

David Himmelstrup authored
Moved the utility functions out of hschooks, avoided linking the GHC library with hschooks.o and added a couple of symbols to the linkers export list.

 22 Jan, 2006 1 commit


duncan.coutts@worc.ox.ac.uk authored
For one thing this is the right thing to do anyway, it's what other tools do. Secondly it allows haddock to produce accurate source code links.

 23 Jan, 2006 1 commit


Simon Marlow authored
merged from CVS, because Tailor isn't merging the libraries subdir

 22 Jan, 2006 1 commit


Simon Marlow authored

 19 Jan, 2006 5 commits


simonmar authored
omit the Main module from libHSghc.a

simonmar authored
exposedmodules should include Config

sof authored
tryPutMVarzh_fast: make it work in the nonfull case. Merge to STABLE.

Simon Marlow authored

Simon Marlow authored

 13 Jan, 2006 2 commits


Ian Lynagh authored

Ian Lynagh authored

 18 Jan, 2006 10 commits


simonpj authored
Check for constructors in type signatures

simonpj authored
Expunge all mention of CCallable/CReturnable

simonpj authored
Ghci wibble; weaken assert

simonmar authored
Remove dead code

simonmar authored
Remove dead panic

simonmar authored
Remove dead error (darcs patch from Ian Lynagh)

simonmar authored
Implement :main (see ticket #662) Patch from Volker Stolz, minor mods by me When matching commands, we now look for (a) an exact match, and (b) the first prefix match we find in the list. This is so that :module can still be abbreviated by :m, to avoid surprise. Docs still to do.

simonmar authored
add a couple of missing symbols

simonmar authored
 fix a mixup in Capability.c regarding signals: signals_pending() is not used in THREADED_RTS  some cleanups and warning removal while I'm here

simonmar authored
Fix build on 5.04.x again

 17 Jan, 2006 6 commits


simonmar authored
Improve the GC behaviour of IORefs (see Ticket #650). This is a small change to the way IORefs interact with the GC, which should improve GC performance for programs with plenty of IORefs. Previously we had a single closure type for mutable variables, MUT_VAR. Mutable variables were *always* on the mutable list in older generations, and always traversed on every GC. Now, we have two closure types: MUT_VAR_CLEAN and MUT_VAR_DIRTY. The latter is on the mutable list, but the former is not. (NB. this differs from MUT_ARR_PTRS_CLEAN and MUT_ARR_PTRS_DIRTY, both of which are on the mutable list). writeMutVar# now implements a write barrier, by calling dirty_MUT_VAR() in the runtime, that does the necessary modification of MUT_VAR_CLEAN into MUT_VAR_DIRY, and adding to the mutable list if necessary. This results in some pretty dramatic speedups for GHC itself. I've just measureed a 30% overall speedup compiling a 31module program (anna) with the default heap settings :D

simonmar authored
Improve the GC behaviour of IOArrays/STArrays See Ticket #650 This is a small change to the way mutable arrays interact with the GC, that can have a dramatic effect on performance, and make tricks with unsafeThaw/unsafeFreeze redundant. Data.HashTable should be faster now (I haven't measured it yet). We now have two mutable array closure types, MUT_ARR_PTRS_CLEAN and MUT_ARR_PTRS_DIRTY. Both are on the mutable list if the array is in an old generation. writeArray# sets the type to MUT_ARR_PTRS_DIRTY. The garbage collector can set the type to MUT_ARR_PTRS_CLEAN if it finds that no element of the array points into a younger generation (discovering this required a small addition to evacuate(), but rough tests indicate that it doesn't measurably affect performance). NOTE: none of this affects unboxed arrays (IOUArray/STUArray), only boxed arrays (IOArray/STArray). We could go further and extend the DIRTY bit to be perblock rather than for the whole array, but for now this is an easy improvement.

simonmar authored
statDescribeGens: count large blocks in the "live" figure

simonmar authored
take into account unscavenged copied words in +RTS t stats.

wolfgang authored
Linux/PPC64: remove some dead code that accidentally slipped in. MERGE TO STABLE

wolfgang authored
Darwin/PPC: Make StgRunIsImplementedInAssembler nonstatic; gcc has recently acquired a habit of deadstripping it. MERGE TO STABLE

 16 Jan, 2006 1 commit


simonmar authored
Default signal handlers weren't being installed; amazing that this has been broken ever since I rearranged the signal handling code.

 13 Jan, 2006 1 commit


Simon Marlow authored
 get from the same repo as the main GHC repo, if that was a local filesystem  allow darcs whatsnew  use repodir if possible
