- Glasgow-haskell-users

Wrong Answer Computing Graph Dominators
by Denis Bueno 12 Apr '08

12 Apr '08

I'm using the Data.Graph.Inductive.Query.Dominators library (http://haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-…) The library is a bit spare on comments, so I may or may not be using it correctly. My goal is to compute the set of nodes that dominate two different nodes of a DAG, with respect to one initial node. My approach is: import qualified Data.Graph.Inductive.Graph as Graph import qualified Data.Graph.Inductive.Query.Dominators as Dom uips = intersect domConfl domAssigned :: [Graph.Node] -- my goal domConfl = fromJust $ lookup conflNode domFromLastd -- dominators of first node domAssigned = fromJust $ lookup (negate conflNode) domFromLastd -- dominators of second node domFromLastd = Dom.dom conflGraph lastd -- source node I compute the dominators individually and my answer is their intersection. When I call the dom function, my assumption is that I need to pass it the source node, and it tells me, for any node x to which there is a path from the source, the list of nodes for which *any path* from source to x must touch, i.e., the list of dominators of x. The DAG in question is attached as a postscript file, which is generated by `dot -Tps` using the output of the Graphviz module directly from the graph object. The nodes for which I'm computing dominators are labeled -2 and 2 (that is, conflNode = 2). The problem is that I think the answer is wrong. In particular I think the set of dominators for -2 is {20, -2}, and the set for 2 is {20, 2}. Their intersection is {20}, which is what I expect. But what I am getting is: --> uips = [-9,20] --> domConfl = [2,-9,20] --> domAssigned = [-2,-9,-12,20] --> lastd = 20 But -9 is not a dominator for 2, since 20,-7,8,6,2 is a path from 20 to 2 that does not touch 9. -9 is also not a dominator for -2, since 20,-7,8,6,-2 is a path from 20 to -2 not touching 9. Am I missing something? I've simplified the code above slightly from the original code in order to ignore some irrelevancies. The original code is for computing a learned clause in a SAT solver. The code in the state that will reproduce the error above is available via a git clone: git clone http://fid.stygian.net/dpllsat Build via cabal, using the --disable-optimization option to configure in order to enable assertions, then run: ./dist/build/dsat/dsat ./tests/problems/uf20/uf20-0226.cnf The graph should be saved in conflict.dot and with `dot -Tps -o conflict.ps conflict.dot` you should be able to turn it into the ps file attached. The problematic code referenced above starts on line 759. -- Denis

1 0

Unexpected lack of optimisation in -O0
by Neil Mitchell 10 Apr '08

10 Apr '08

Hi, I just tried compiling the following program: foo = (1 :: Int) == (2 :: Int) with ghc --ddump-simpl, and no optimisation flags, in GHC 6.6.1 The resultant code is: Test.foo = case GHC.Base.$f2 of tpl_X8 { GHC.Base.:DEq tpl1_B2 tpl2_B3 -> tpl1_B2 (GHC.Base.I# 1) (GHC.Base.I# 2) } GHC has introduced dictionaries in this example. In comparison, Yhc and nhc wouldn't introduce dictionaries here, as the type class desugaring knows the type of the item is fixed, and makes a direct call to the appropriate function. If the desugaring was changed, it would make programs in GHCi run faster, would reduce the size of programs, and would speed up the optimiser, as it would have less to do. I am not sure how much additional work this would require in the simplifier, but if it was minimal, the gains would probably be worth it. I was just reading the Monad.Reader, where a Yhc based Haskell Interpreter states that comparisons against GHCi are "unfair", because Yhc gains too much benefit from this desguaring. Thanks Neil

2 1

RE: [GHC] #2153: GHCi does not have a :source command to load further .ghci files
by Simon Peyton-Jones 09 Apr '08

09 Apr '08

| Wow, that simple??? | | What needs to be done to get this in ":?" output? (It should be in the | manual, at least...) Indeed! But it's more application-note than user manual. Fortunately, we have a place for such material, namely GHC's "collaborative documentation" (a wiki) http://haskell.org/haskellwiki/GHC Would someone like to copy Claus's excellent message http://www.haskell.org/pipermail/haskell-cafe/2007-September/032260.html to the Wiki documentation on GHCi, here: http://haskell.org/haskellwiki/GHC/GHCi (with his permission of course). That's the right place for it. Sam, you'd be an ideal person to do this, because you know what you wanted in the first place, so you could make sure the answer is easy to find. But anyone else would do fine! Simon | -----Original Message----- | From: glasgow-haskell-bugs-bounces(a)haskell.org [mailto:glasgow-haskell-bugs-bounces@haskell.org] On | Behalf Of GHC | Sent: 07 April 2008 02:46 | Cc: glasgow-haskell-bugs(a)haskell.org | Subject: Re: [GHC] #2153: GHCi does not have a :source command to load further .ghci files | | #2153: GHCi does not have a :source command to load further .ghci files | ---------------------+------------------------------------------------------ | Reporter: SamB | Owner: | Type: bug | Status: closed | Priority: normal | Milestone: | Component: GHCi | Version: 6.8.2 | Severity: normal | Resolution: wontfix | Keywords: | Difficulty: Unknown | Testcase: | Architecture: Unknown | Os: Unknown | | ---------------------+------------------------------------------------------ | Comment (by SamB): | | Wow, that simple??? | | What needs to be done to get this in ":?" output? (It should be in the | manual, at least...) | | -- | Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2153#comment:3> | GHC <http://www.haskell.org/ghc/> | The Glasgow Haskell Compiler

3 2

Re: Wanted: migration guide from ghc-6.6 to ghc-6.8
by Johannes Waldmann 07 Apr '08

07 Apr '08

>> list of things to watch out for >> when converting Haskell sources written for ghc-6.6 >> for compilation with ghc-6.8. Thanks for the pointers. Luckily, only a few changes were needed, http://leiffrenzel.de/eclipse/wiki/doku.php?id=hare_with_gh-6.8 (sic). and most of them related to GHC API. I'm not completely sure whether it's semantically correct but at least it compiles. Best regards, J.W.

1 0

Wanted: migration guide from ghc-6.6 to ghc-6.8
by Johannes Waldmann 04 Apr '08

04 Apr '08

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Dear all, I could use a list of things to watch out for when converting Haskell sources written for ghc-6.6 for compilation with ghc-6.8. Of course I'll try write down some items while I find them but I'd hope not to start at zero... Is there an easy way to get a "library API diff" (automatically, say, from full 6.6 and 6.8 installations)? Best regards, Johannes Waldmann. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.4-svn0 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFH9hn73ZnXZuOVyMIRAk1nAKDEteU/FHMHz4yDgL936r/rRfLy5gCfTTFz 0fv7U+nP4ELZ9xZT/qicODc= =B50t -----END PGP SIGNATURE-----

2 1

scope of header files
by Duncan Coutts 03 Apr '08

03 Apr '08

I was under the impression that with ghc, ffi import declarations like this do not escape the module: foreign import ccall unsafe "foo.h foo" foo :: IO () However it seems that this one does: foreign import ccall unsafe "curses.h & stdscr" stdscrp :: Ptr WINDOWptr from: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/mage-1.0 perhapsPbecause it's a pointer import it gets treated differently? Is this correct and expected behaviour? It's hard to tell what header files need to be used globally and inherited by client packages and which can safely be used privately. Duncan

10 32

Confused about typing in ghci
by Patrick Surry 02 Apr '08

02 Apr '08

I'm new to Haskell and functional programming; have been exploring the fixed-point combinator based on the exercise in the HSOE book. Having an odd issue with typing in ghci which I don't understand - maybe it's to do with section 3.4.5. "Type defaulting in GHCi" but I don't really grok that yet... (BTW, an unrelated question: is there a good reference where I can understand the precendence/associativity rules for Haskell? I continually find myself needing lots of parens before expressions behave as I expect, and get very confused trying to use the $ operator - usually resorting to lots of parens again :-) My typing question might boil down to this simple example, though my original example follows: -- Why don't these (particularly g and g') all have the same type? Prelude> :t (\x -> x+1) (\x -> x+1) :: (Num a) => a -> a Prelude> let g = (\x -> x+1) Prelude> :t g g :: Integer -> Integer Prelude> let g' x = x + 1 Prelude> :t g' g' :: (Num a) => a -> a -- Here's my original fixed-point combinator example: Prelude> let fix f = f (fix f) -- here's a silly (but working) implementation of length using fix: Prelude> fix (\g xs -> if xs == [] then 0 else (1 + g (tail xs))) [1,2,3,4] 4 -- so I examine the types of the parts, which seems fine: Prelude> :t fix (\g xs -> if xs == [] then 0 else (1 + g (tail xs))) ... :: (Num t, Eq a) => [a] -> t Prelude> :t (\g xs -> if xs == [] then 0 else (1 + g (tail xs))) ... :: (Num t, Eq a) => ([a] -> t) -> [a] -> t -- but now I try to bind the anonymous function to a name -- this seems to get the types wrong and no longer works as I expect: Prelude> let lenstep = (\g xs -> if xs == [] then 0 else (1 + g (tail xs))) Prelude> :t lenstep lenstep :: ([()] -> Integer) -> [()] -> Integer Prelude> :t fix lenstep fix lenstep :: [()] -> Integer Prelude> let len' = fix (\g xs -> if xs == [] then 0 else (1 + g (tail xs))) Prelude> :t len' len' :: [()] -> Integer Prelude> Prelude> len' [1,2,3,4] <interactive>:1:12: No instance for (Num ()) arising from the literal `4' at <interactive>:1:12 Possible fix: add an instance declaration for (Num ()) In the expression: 4 In the first argument of `len'', namely `[1, 2, 3, 4]' In the expression: len' [1, 2, 3, 4] -- maybe this is just me not understanding name binding properly; it seems to work if I do it this way: Prelude> let lenstep' g xs = (if xs == [] then 0 else (1 + g (tail xs))) Prelude> :t lenstep' lenstep' :: (Eq a, Num t) => ([a] -> t) -> [a] -> t Prelude> :t fix lenstep' fix lenstep' :: (Eq a, Num t) => [a] -> t Prelude> fix lenstep' [1,2,3,4] 4 -- but what's the difference? Cheers, Patrick Patrick.Surry(a)portraitsoftware.com <mailto:Patrick.Surry@portraitsoftware.com> , VP Technology Tel: (617) 457 5230 Mob: (857) 919 1700 Fax: (617) 457 5299 Map <http://maps.google.com/maps?f=q&hl=en&q=125+Summer+St,+Boston,+MA+02110 &ie=UTF8&z=15&ll=42.353153,-71.057296&spn=0.022644,0.054245&om=1&iwloc=A > Portrait Software introduces Portrait Campaign Manager <http://www.portraitsoftware.com/Products/portrait_campaign_manager> : Easy, integrated campaign management for automated and highly targeted outbound marketing http://supportcentre.portraitsoftware.com/Vmail/emailfooter/balloon.gif <http://www.portraitsoftware.com/> http://supportcentre.portraitsoftware.com/Vmail/emailfooter/portrait_sof tware_logo.gif <http://www.portraitsoftware.com/> www.portraitsoftware.com <http://www.portraitsoftware.com/> ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.

2 3

ANN: prof2dot, a graphical profiling tool
by Gregory Wright 02 Apr '08

02 Apr '08

I am pleased to announce the first release of prof2dot, a graphical profiling tool for use with GHC. While GHC has in the past worked with graphical profiling tools, they have been heavyweight and/or proprietary. Prof2dot is a simple tool for converting profiling information into a graphical format, released under a BSD3 license. It is simple because it offloads all of the work of rendering the graph onto Graphviz. So you need to install the Graphviz tools in order to use it. The program is a filter that takes the profiling output generated by running a GHC-compiled program with the "+RTS -px -RTS" option and turns it into a dot file. (The "dot" format is a textual representation of a directed or undirected graph.) The dot file can rendered in any format supported by Graphviz's dot program, and the file itself can be post-processed or edited to adjust the layout. Features of prof2dot: * display either the call graph (default) or the call tree, * colorize by cost center count, time or allocations, * group cost centers in the same module. Prof2dot installs as a typical caballized application. Running "prof2dot -?" from the command line will give a short summary of how to use the program and its options. Rendering very large graphs can exceed the internal resource limits of dot. You may have to compile your own version of the Graphviz tools with higher limits to handle these cases. A example of a colorized profile of a medium sized project is shown on our company's web site: http://antiope.com/downloads.html. Click on the small image to download a pdf of the complete profile graph. Prof2dot is available from hackage or the link given above. -Greg

2 2

ghc fails to find the right instance
by Joachim Breitner 01 Apr '08

01 Apr '08

Hi, I was told on #haskell that I should bring this up here, to ask whether this is a bug in ghc6 or otherwise explain this to me. I’m trying to write the function "addd" which takes an arbitrary number of Integer arguments and returns the sum. This code works: -- Try 1 class More a where more ::Integer -> a instance (More a, Integral i) => More (i -> a) where more v1 v2 = more (v1 + toInteger v2) instance More Integer where more v = v addd :: More a => a addd = more 0 printI :: Integer -> IO () printI = print main = do printI $ addd printI $ addd 1 printI $ addd 1 2 printI $ addd 1 2 3 -- SNIP But when I try to use a concret type (Integer) instead of the (Integral i =>) condition (which should make the program more concrete, I’d say) and write the following instance: -- Try 2 (changed lines of code) instance More a => More (Integer -> a) where more v1 v2 = more (v1 + v2) -- SNIP I get this error: test.hs:4:0: Illegal instance declaration for `More (Integer -> a)' (All instance types must be of the form (T a1 ... an) where a1 ... an are distinct type *variables* Use -XFlexibleInstances if you want to disable this.) In the instance declaration for `More (Integer -> a)' Failed, modules loaded: none. Well, I add {-# LANGUAGE FlexibleInstances #-} and get this error for the line "printI $ addd 1" (and similar errors for the other following addd lines): test.hs:19:17: No instance for (More (t -> Integer)) arising from a use of `addd' at test.hs:19:17-22 Possible fix: add an instance declaration for (More (t -> Integer)) In the second argument of `($)', namely `addd 1' In the expression: printI $ addd 1 In a 'do' expression: printI $ addd 1 And this is the point where I’m lost and would like to ask for hints what this means. Thanks, Joachim -- Joachim "nomeata" Breitner mail: mail(a)joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nomeata(a)joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nomeata(a)debian.org

2 3

simple CSE?
by Conal Elliott 01 Apr '08

01 Apr '08

I'd like to know if it's possible to get GHC to perform some simple CSE for function-level programming. Here's a simple example: liftA2 (*) sin sin :: Double -> Double which inlines and simplifies to \ t -> sin t * sin t A more realistic, equivalent, example: let b = sin <$> id in liftA2 (*) b b Can GHC be nudged into computing 'sin t' once rather than twice? Thanks, - Conal

4 3