- Glasgow-haskell-users

GHC vs. GCC on raw vector addition
by Sven Moritz Hallberg 19 Jan '06

19 Jan '06

Hi List, I'm running GHC and GCC head-to-head on the task of adding a bunch of long IOUArray-Vectors really fast. My machine is a Linux-ppc PowerBook and gets a runtime for the GHC-compiled binary that's about 10x as long as for GCC. Simon M. tells me this should be much better. Here are the precise command lines: $ gcc -O3 -o b-addvec-gcc b-addvec-c.c $ ghc -O2 -fasm --make -o b-addvec-ghc b-addvec-hs.hs $ time ./b-addvec-gcc 100000 elements 1000 real 0m5.130s user 0m4.466s sys 0m0.061s $ time ./b-addvec-ghc 100000 elements 1000 real 0m49.701s user 0m43.466s sys 0m0.586s (compiling with -fvia-C -optc-O3 runs only about 1 second longer) Can somebody shed some light on this? Regards, Sven Moritz

5 11

Lexically scoped type variables
by Simon Peyton-Jones 18 Jan '06

18 Jan '06

Dear GHC users As part of a revision of GHC to make type inference for GADTs simpler and more uniform, I propose to change the way in which lexically- scoped type variables work in GHC. (Indeed, I have done so, and will commit it shortly.) This message explains the new system, highlighting the differences. I'm very interested to know whether you like it or hate it. In the latter case, I'd also like to know whether you also have programs that will be broken by the change. Simon 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 let-bound or where-bound 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 lexically-scoped type variable always names a rigid type variable (not a wobbly one, and not a non-type-variable 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 lexically-scoped type variables name distinct rigid type variables. This choice is open; This means that you cannot say \(x:: [a]) -> <expr> (where 'a' is not yet in scope) to enforce that x is a list without saying anything about 'a'. (Well, not unless the type of this lambda is known from the "outside".) 1a) 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. 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 top-level 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 *pattern-bound 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 pattern-bound 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 change from the current situation. f (x::a) = x -- NO 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 *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 f :: a -> Bool -> Maybe a f (x::p) True = Just x :: Maybe p f (y::q) False = Nothing :: Maybe q 3b) Scoped type variables respect alpha renaming. For example, function g from 2(b) above could also be written: g2 :: a -> a -> [a] g2 (x::b) (y::b) = [y :: b, x] where the scoped type variable is called 'b' instead of 'a'. However, you cannot write f :: a -> a -> [a] f (x::b) (y::c) = [y :: b, x] because then two scoped type variables ('b' and 'c') would be bound to the same underlying type variable. (Invariant (C) above.) 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) Explicitly-forall'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. Implementation notes ~~~~~~~~~~~~~~~~~~~~ 1) This means that dealing with pattern/result type signatures is simple: - if the signature binds one or more variables, and the pattern type is rigid, *match* the signature against the pattern type to bind the variables - if the signature binds no type variables, *unify* the pattern type against the (necessarily rigid) type signature 2) Skolem constants get introduced by a) Declaration type signatures with explicit foralls b) *Function* declaration type signatures on bindings where there is no explicit forall c) Existential pattern matches d) SKOL rule in subsumption checking A *declaration type signature* for a *pattern-bound* variable does not introduce a skolem, and is never the basis for refinement. Instead we use an ordinary meta type variable, and check after the event that everything is still distinct. That is how the x4/y4 example type-checks.

4 3

Linking with C++ produced by Visual Studio .NET on Windows XP?
by Brian Hulley 17 Jan '06

17 Jan '06

Hi - I'm wondering if anyone has a simple Visual Studio .NET C++ project that would demonstrate how to link C++ with Haskell (or vice versa). Ie a .sln, .vcproj, .cpp, and .h file containing one C++ function and a Haskell file main.hs that calls this function, so that if I click on the .sln file and hit F6 the VS project will build then on the command line if I type ghc --make main.hs the Haskell program will be built so that when I type "main" on the command line it will run and call the C++ function. Sorry if this all sounds too basic but I don't know how to compile C++ from the command line at all or how to use make files, and I need to use the Visual Studio compiler because my own C++ code relies on Microsoft extensions... Thanks, Brian.

1 0

RE: cvs commit: fptools/libraries/base/Data IntMap.hs Map.hs Sequence.hs Set.hs fptools/libraries/base/Data/Generics Instances.hs Twins.hs
by Simon Peyton-Jones 17 Jan '06

17 Jan '06

| > Eta-expand some higher-rank functions. GHC is about to | > move to *invariant* rather than *contra-variant* in function | > arguments, so far as type subsumption is concerned. These | > eta-expansions are simple, and allow type inference to | > go through with invariance. | | Why drop contra-variace? See the paper on "Boxy type inference" on my home page. Simon

1 0

GHC.Unicode
by Krasimir Angelov 17 Jan '06

17 Jan '06

Hello Guys, I saw that GHC already has complete support for Unicode character classification. I tend to use it but I saw that currently GHC.Unicode exports only few of all classification routines. Is it intentional? Cheers, Krasimir

2 5

RE: darcs switchover
by Mike Thomas 15 Jan '06

15 Jan '06

Hi Simon. Thanks for all the great work. | Please test, as we'd like to switch over as soon as possible. Have the nightly build scripts moved yet? Cheers Mike Thomas.

1 0

RE: storing highly shared data structures
by Simon Marlow 12 Jan '06

12 Jan '06

On 22 December 2005 13:43, Christian Maeder wrote: > for storing highly shared data structures we use so called Annotated > Terms (shortly ATerms, details below). > > http://www.cwi.nl/htbin/sen1/twiki/bin/view/SEN1/ATerm > > In contrast to the Binary (or GhcBinary) class we compute the sharing, > which saves a lot of space for data types that keep redundant > information. > > With this we can store some of our data structures (of course only > non-cyclic and finite ones) in a few KBs that need MBs if stored > without sharing (as when using the Binary or the Show/Read > classes). > > So far so good. The problem remaining is that an object is _traversed_ > as if being unshared and thus the _time_ for the ATermTable > construction becomes too long for us. > > GHC's internal data structures (on the heap) are in many cases shared, > by pointer references. I.e. if I add a (single) symbol table to every > symbol that I use, then the symbol table will not be copied, but only > a reference added to my symbol. > > How can I detect this sharing in order to avoid traversing the very > same symbol table for every symbol? > > I've tried to use a "Map (Ptr ()) ShATerm". So before traversing an > object I look up its address and check if is was traversed before (if > not I traverse it and store it in my map for future lookups). > > 1.) I'm not sure if it is safe to use "Ptr ()" (meanwhile garbage > collection, heap compaction and what not could happen). Right - Ptr isn't the right thing here, because GC will move objects around. That's why we have StablePtr and StableName. In fact, what you really want here is the pointer-equality memo table implementation in the Memo module (package util). This is scheduled to be removed in 6.6, but it will be available as a Cabal package. Cheers, Simon

5 15

The -static option of ghc, and choice between user-supplied library types (Unix)
by Dimitry Golubovsky 12 Jan '06

12 Jan '06

The Paragraph 4.10.7 of the GHC users guide contains this: -static Tell the linker to avoid shared Haskell libraries, if possible. This is the default. -dynamic Tell the linker to use shared Haskell libraries, if available (this option is only supported on Mac OS X at the moment, and also note that your distribution of GHC may not have been supplied with shared libraries). As I understand, this is related to the GHC own libraries. What about user-supplied libraries (listed in the `extra-libraries' field of a Cabal package description) e. g.: extra-libraries: gd, jpeg, m from http://www.cs.chalmers.se/~bringert/darcs/haskell-gd/gd.cabal There are usually files like libm.a and libm.so together in the same directory where GHC looks for libraries. Does the -static / -dynamic ghc flag affect the choice which library to link against?Or, to control this, one has to descend to the linker options, and the default would be the linker default? I believe, this is Unix-specific: AFAIR on Windows (and OS/2) dynamic implibs were indistinguishable by their names from static libraries and had the .lib suffix anyway? -- Dimitry Golubovsky Anywhere on the Web

2 1

storing highly shared data structures
by Christian Maeder 11 Jan '06

11 Jan '06

Dear Haskell Experts, for storing highly shared data structures we use so called Annotated Terms (shortly ATerms, details below). http://www.cwi.nl/htbin/sen1/twiki/bin/view/SEN1/ATerm In contrast to the Binary (or GhcBinary) class we compute the sharing, which saves a lot of space for data types that keep redundant information. With this we can store some of our data structures (of course only non-cyclic and finite ones) in a few KBs that need MBs if stored without sharing (as when using the Binary or the Show/Read classes). So far so good. The problem remaining is that an object is _traversed_ as if being unshared and thus the _time_ for the ATermTable construction becomes too long for us. GHC's internal data structures (on the heap) are in many cases shared, by pointer references. I.e. if I add a (single) symbol table to every symbol that I use, then the symbol table will not be copied, but only a reference added to my symbol. How can I detect this sharing in order to avoid traversing the very same symbol table for every symbol? I've tried to use a "Map (Ptr ()) ShATerm". So before traversing an object I look up its address and check if is was traversed before (if not I traverse it and store it in my map for future lookups). 1.) I'm not sure if it is safe to use "Ptr ()" (meanwhile garbage collection, heap compaction and what not could happen). 2.) A single "Map (Ptr ()) ShATerm" does not work! It seems that sometimes objects are shared that have different types (as tests revealed). This seems obvious for newtypes but also happens (I think) without newtype declarations. However, shared ATerms are always different for different types, because the corresponding data constructors are different. So, I'm now thinking if I should try using the type of my data as key as well, i.e. using "Map (TypeRep, Ptr ()) ShATerm" to avoid duplicate traversals. Would this be worth the effort? What other possibilities could I try? An obvious solution is to avoid the redundancy in the first place (i.e. simply don't store the symbol table with every symbol), but that would require a major change of our sources, and would the code become clearer? (Many functions would need more arguments.) Finally, _reading in_ shared ATerms is fast, since ghc seems to exploit the sharing given by the injective ATermTable. Thanks for any help Christian More details: Brand, M.G.J. van den, H.A. de Jong, P. Klint, and P.A. Olivier (2000). "Efficient Annotated Terms." Software -- Practice & Experience 30:259--291. (The link "ATerm Library" http://www.cwi.nl/projects/MetaEnv/haterm/ under http://www.haskell.org/libraries/#compilation looks outdated to me. We have extra source code that - at the moment - cannot be distributed separately) Via an extension to DrIFT, http://repetae.net/john/computer/haskell/DrIFT, we generate class instances (similar to the Binary class) for our types that we want to store. Our ATerms are (basically) constructor terms of the form: data ShATerm = ShAAppl String [Int] deriving (Eq, Ord) (The annotation part of ATerms is omitted here since we don't use it) The Int-list contains the arguments as indices into an ATermTable being an injective "IntMap ShATerm" with update and lookup functions: addATerm :: ShATerm -> ATermTable -> (ATermTable, Int) getATerm :: Int -> ATermTable -> ShATerm The class (that DriFT derives instances for) looks as follows: class ShATermConvertible t where toShATerm :: ATermTable -> t -> (ATermTable, Int) fromShATerm :: (ATermTable, Int) -> t The automatically derived instance of i.e. a user-defined List data type "data List a = Nil | Cons a (List a)" is: instance ShATermConvertible a => ShATermConvertible (List a) where toShATerm att0 Nil = addATerm (ShAAppl "Nil" []) att0 toShATerm att0 (Cons a b) = case toShATerm att0 a of { (att1, a') -> case toShATerm att1 b of { (att2, b') -> addATerm (ShAAppl "Cons" [a', b']) att2 }} fromShATerm (att, i) = case getATerm i att of ShAAppl "Nil" [] -> Nil ShAAppl "Cons" [a, b] -> case fromShATerm (att, a) of { a' -> case fromShATerm (att, b) of { b' -> Cons a' b' }} _ -> error "ShATermConvertible List" (Internally the ATermTable also keeps an inverse "Map ShATerm Int" to support the efficient implementation of addATerm.) We can use the "baffle" tool to convert our files from shared (TAF) to unshared ATerm format and vice versa.

4 6

darcs switchover
by Simon Marlow 09 Jan '06

09 Jan '06

Hi Folks, As you probably know, there is a mirror of the GHC source tree in a darcs repository. (information about accessing the darcs repository is here: http://cvs.haskell.org/trac/ghc/wiki/GhcDarcs) The aim is to eventually switch over to using darcs for our revision control. The point of this message is to find out what constraints people have that will affect when we can throw the switch. It doesn't look like we'll be able to keep a CVS mirror going once we switch to darcs, so darcs will be the only way to get an up-to-date GHC source tree. How will it affect you? - If you just get the GHC sources from anonymous cvs, then you have to switch to getting sources using darcs. It's pretty simple. - If you are a developer, then you need to: (a) get sources from darcs, and (b) use 'darcs push' instead of 'cvs commit'. - You won't be able to browse the CVS repository via cvsweb any more. You can browse the contents of the darcs repository directly, and we hope to set up some kind of darcs-aware browsing too. We've switched some of our nightly builds over to using darcs, and it seems to be working nicely. darcs get --partial can actually get the sources quicker than anonymous CVS used to. Please let me know if the switchover is going to adversely affect your life, so that we can formulate a plan and timescale for switching over. Malcolm, Ross - since you both also use the CVS libraries tree, is it going to be possible for you to switch to using darcs to get the libraries? Any idea how long you'll need? Cheers, Simon

9 17