RE: Is this a concurrency bug in base?
Thank you for the detailed investigation. I have not followed all the details of this thread, but I think that it may (happily) represent a bug in generating TypeReps that is already fixed. · We used to have a global cache from which we generated unique Int keys corresponding to type constructors. The trouble with this was that (a) you weren’t guaranteed to get the same key in every run, and (b) the cache was not initially designed to be thread-safe, and I’m not sure that we’d closed all race conditions. · But NOW we generate a MD5 hash, or fingerprint, of the type. So there is no global cache, no race condition, and you should get the same behaviour ever time. In short, can you try with 7.2? Thanks Simon From: glasgow-haskell-users-boun...@haskell.org [mailto:glasgow-haskell-users-boun...@haskell.org] On Behalf Of Jean-Marie Gaillourdet Sent: 09 October 2011 12:53 To: glasgow-haskell-users Subject: Is this a concurrency bug in base? Hi, I am working on a library I'd like to release to hackage very soon, but I've found a problem with supporting GHC 6.12 and GHC 7.0. Consider the following program: import Control.Concurrent import Data.Typeable main :: IO () main = do { fin1 - newEmptyMVar ; fin2 - newEmptyMVar ; forkIO $ typeRepKey (typeOf ()) = print putMVar fin1 () ; forkIO $ typeRepKey (typeOf ()) = print putMVar fin2 () ; () - takeMVar fin1 ; () - takeMVar fin2 ; putStrLn --- ; return () } When compiled with GHC 7.0.x or GHC 6.12.x, it should print two identical numbers. Sometimes it does not. To reproduce this compile and execute as follows: $ ghc-7.0.3 -rtsopts -threaded TypeRepKey.hs -o TypeRepKey $ while true ; do ./TypeRepKey +RTS -N ; done 0 0 --- 0 0 --- 0 0 --- 0 1 --- 0 0 --- … Ideally you should get an infinite number of zeros but once in a while you have a single(!) one in between. The two numbers of one program run should be identical, but their values may be arbitrary. But it should not be possible to have single outliers. This only happens when executed with more than one thread. I've also a somewhat larger program which seems to indicate that fromDynamic fails occasionally. I can post it as well if it helps. This seems to be a Heisenbug as it is extremely fragile, when adding a | grep 1 to the while loop it seems to disappears. At least on my computers. All this was done on several Macs running the latest OS X Lion with ghc 7.0.3 from the binary distribution on the GHC download page. Actually, I am trying to find a method to use a type as key in a map which works before GHC 7.2. I'd be glad to get any ideas on how to achieve that, given that typeRepKey seems to buggy. I'd be happy to get any comments on this matter. Regards, Jean ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: log time instead of linear for case matching
Greg In GHC, big cases are done as tables (if dense) or trees (if sparse). If you have some examples where things go bad, do submit a bug report. For big dispatches on strings, I'm pretty sure we do something linear, top to bottom. I'd be strongly inclined to use a proper Map structure if you want good performance on that. Is there some reason you don't want to? Simon From: glasgow-haskell-users-boun...@haskell.org [mailto:glasgow-haskell-users-boun...@haskell.org] On Behalf Of Greg Weber Sent: 09 October 2011 17:39 To: GHC users Subject: log time instead of linear for case matching We have a couple use cases in Yesod that can potentially match many different patterns. Routing connects the url of an http request to a Haskell function. The current code just uses a pattern match, which scales linearly. So if a site has a hundred different routes (urls), it could take 100 comparisons to finally match the url to a function. Michael Snoyman is writing some code to make this issue obsolete. One of the things it does is use a Map lookup instead of a case match. More worrying is our system for internationalization of a website. A user is supposed to make a sum type with every custom message as a constructor in that sum type. data Msg = Model | Year | Please -- Rendering function for English. renderEnglish Model = Model renderEnglish Year = Year renderEnglish Please = Please fill in your car's details -- Rendering function for Swedish. renderSwedish Model = Modell renderSwedish Year = Årgång renderSwedish Please = Vänligen fyll i uppgifterna för din bil So if there are 100 custom messages on a site, that will setup a case match with potentially 100 comparisons. Note that we are using this technique for type safety- switching to a map here would be difficult. We want to know at compile time that a translation exists for every message. So first of all I am wondering if a sum type comparison does in fact scale linearly or if there are optimizations in place to make the lookup constant or logarithmic. Second, I as wondering (for the routing case) if Haskell can make a string case comparison logarithmic so that users can use case comparisons instead of maps for string collections that are known at compile time and won't change. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Is this a concurrency bug in base?
On 10/10/2011 09:04, Simon Peyton-Jones wrote: Thank you for the detailed investigation. I have not followed all the details of this thread, but I *think* that it may (happily) represent a bug in generating TypeReps that is already fixed. ·We used to have a global cache from which we generated unique Int keys corresponding to type constructors. The trouble with this was that (a) you weren’t guaranteed to get the same key in every run, and (b) the cache was not initially designed to be thread-safe, and I’m not sure that we’d closed all race conditions. Indeed, I don't think we closed *any* race conditions. The code looks completely unthreadsafe to me. There's a non-atomic lookup and update in the cache, and a non-atomic genSym to get new keys. It's pretty bad that we didn't notice this or fix it earlier. Sorry about the bug. As Simon said, 7.2 and later should fix it. Cheers, Simon ·But NOW we generate a MD5 hash, or fingerprint, of the type. So there is no global cache, no race condition, and you should get the same behaviour ever time. In short, can you try with 7.2? Thanks Simon *From:*glasgow-haskell-users-boun...@haskell.org [mailto:glasgow-haskell-users-boun...@haskell.org] *On Behalf Of *Jean-Marie Gaillourdet *Sent:* 09 October 2011 12:53 *To:* glasgow-haskell-users *Subject:* Is this a concurrency bug in base? Hi, I am working on a library I'd like to release to hackage very soon, but I've found a problem with supporting GHC 6.12 and GHC 7.0. Consider the following program: import Control.Concurrent import Data.Typeable main :: IO () main = do { fin1 - newEmptyMVar ; fin2 - newEmptyMVar ; forkIO $ typeRepKey (typeOf ()) = print putMVar fin1 () ; forkIO $ typeRepKey (typeOf ()) = print putMVar fin2 () ; () - takeMVar fin1 ; () - takeMVar fin2 ; putStrLn --- ; return () } When compiled with GHC 7.0.x or GHC 6.12.x, it should print two identical numbers. Sometimes it does not. To reproduce this compile and execute as follows: $ ghc-7.0.3 -rtsopts -threaded TypeRepKey.hs -o TypeRepKey $ while true ; do ./TypeRepKey +RTS -N ; done 0 0 --- 0 0 --- 0 0 --- 0 1 --- 0 0 --- … Ideally you should get an infinite number of zeros but once in a while you have a single(!) one in between. The two numbers of one program run should be identical, but their values may be arbitrary. But it should not be possible to have single outliers. This only happens when executed with more than one thread. I've also a somewhat larger program which seems to indicate that fromDynamic fails occasionally. I can post it as well if it helps. This seems to be a Heisenbug as it is extremely fragile, when adding a | grep 1 to the while loop it seems to disappears. At least on my computers. All this was done on several Macs running the latest OS X Lion with ghc 7.0.3 from the binary distribution on the GHC download page. Actually, I am trying to find a method to use a type as key in a map which works before GHC 7.2. I'd be glad to get any ideas on how to achieve that, given that typeRepKey seems to buggy. I'd be happy to get any comments on this matter. Regards, Jean ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unwanted eta-expansion
Hi, Am Dienstag, den 04.10.2011, 09:39 +0300 schrieb Roman Cheplyaka: Suppose I want a foldl which is evaluated many times on the same list but with different folding functions. I used this pattern successfully in SAT-Britney, where I generate a huge list quite quickly, and I don’t want this list to stay in memory. I had to pay a lot of attention to sharing, e.g. by making sure the parameters to the function that generate the left fold are only passed when the folding functions are also given, see in http://git.nomeata.de/?p=sat-britney.git;a=commitdiff;h=e8a1eea156b76d76729a0ae55dbd7ac244f03470;hp=3bf044025665e3c7a925ca38cdcb945a103c9e6f the changes to TransRules.hs. Otherwise, I’d get a huge thunk of closures representing the list, as Jan-Willem predicted. Note that I want to achieve something differently than you, unless I am mistaken: In my case, I want to make sure the list can be fused or at least immediately garbage-collected with every use, even if the code that calculates the list has to be run multiple times. Greetings, Joachim -- Joachim nomeata Breitner m...@joachim-breitner.de | nome...@debian.org | GPG: 0x4743206C xmpp: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ signature.asc Description: This is a digitally signed message part ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: log time instead of linear for case matching
I thought it could be a nice GHC feature to optimize string lookup, and that using case arrows could be a nice syntax for creating maps. We will be fine using a Map. Making sure that sum types are optimized was the important thing, thanks! On Mon, Oct 10, 2011 at 1:14 AM, Simon Peyton-Jones simo...@microsoft.comwrote: Greg ** ** In GHC, big cases are done as tables (if dense) or trees (if sparse). If you have some examples where things go bad, do submit a bug report. ** ** For big dispatches on strings, I’m pretty sure we do something linear, top to bottom. I’d be strongly inclined to use a proper Map structure if you want good performance on that. Is there some reason you don’t want to? Simon ** ** *From:* glasgow-haskell-users-boun...@haskell.org [mailto: glasgow-haskell-users-boun...@haskell.org] *On Behalf Of *Greg Weber *Sent:* 09 October 2011 17:39 *To:* GHC users *Subject:* log time instead of linear for case matching ** ** We have a couple use cases in Yesod that can potentially match many different patterns. Routing connects the url of an http request to a Haskell function. The current code just uses a pattern match, which scales linearly. So if a site has a hundred different routes (urls), it could take 100 comparisons to finally match the url to a function. Michael Snoyman is writing some code to make this issue obsolete. One of the things it does is use a Map lookup instead of a case match. ** ** More worrying is our system for internationalization of a website. A user is supposed to make a sum type with every custom message as a constructor in that sum type. ** ** data Msg = Model | Year | Please ** ** -- Rendering function for English. renderEnglish Model = Model renderEnglish Year = Year renderEnglish Please = Please fill in your car's details ** ** -- Rendering function for Swedish. renderSwedish Model = Modell renderSwedish Year = Årgång renderSwedish Please = Vänligen fyll i uppgifterna för din bil ** ** So if there are 100 custom messages on a site, that will setup a case match with potentially 100 comparisons. ** ** Note that we are using this technique for type safety- switching to a map here would be difficult. We want to know at compile time that a translation exists for every message. ** ** So first of all I am wondering if a sum type comparison does in fact scale linearly or if there are optimizations in place to make the lookup constant or logarithmic. Second, I as wondering (for the routing case) if Haskell can make a string case comparison logarithmic so that users can use case comparisons instead of maps for string collections that are known at compile time and won't change. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Two Proposals
For instance, at your day job, the Array type. On Wed, Oct 5, 2011 at 12:23 PM, Roman Leshchinskiy r...@cse.unsw.edu.auwrote: Simon Peyton-Jones wrote: I'm not sure if this plan would support [(fred,45), (bill,22)] :: Map String Int. Probably not. Maybe that's a shortcoming... but such Maps are a rather surprising use of list literals. What data structures other than lists do we want to construct using list literals? I'm not really sure what the use cases are. Roman ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Two Proposals
A quick thought that came to me after hoogling [a] - [[a]]. The first four functions in the search result are named after what they return (noun in plural) rather than what they do (verb). I am talking about inits, permutations, subsequence and tails. So I thought the following syntax might work as well if (as it is already common) grouping functions are named after what they return. then f then f by e then group f then group f by e For example the following code fragments read well: then group inits then group permutations then group subsequences then group tails Here we use the special identifier group as a verb. I have not told you about the fifth result of the hoogling, the groupWith function. The following really looks ugly: then group groupWith by e But following the aforementioned naming convention the groupWith function could as well be named as equals. Now this reads well: then group equals by e Cheers, George On 2011-Oct-5, at 09:14 , Simon Peyton-Jones wrote: [adding ghc-users] It's not easy, Phil. Do you have any ideas? For the 'then' case the name of the function serves as the verb. One might say then take 4 or then takeWhile by salary 40 For grouping one might like to say the same thing, such as then groupBy by salary but the typing rule is quite different, so we really need a different keyword. We chose the compound keyword then group to avoid needing a whole new keyword (group is treated specially only in tthis context). So you write then group by salary using groupBy Using this order of the pieces for the sorting case is harder. What would one say? then process? Like this? then process by salary 40 using takeWhile Not very nice. One could use a new keyword for grouping theng say, thus: theng groupBy by salary But that is hardly beautiful either. So the current story is not great, but it's the best I could think of. Improvements welcome. Simon | -Original Message- | From: Philip Wadler [mailto:wad...@inf.ed.ac.uk] | Sent: 04 October 2011 18:15 | To: Simon Peyton-Jones; George Giorgidze | Subject: Re: FW: Two Proposals | | George, | | Nice proposal. I like the idea of symmetry, but don't at all like the | idea that f comes before e for 'then' but f comes after e for 'then | group'. Can you rethink it and come up with something even more | symmetric? | | Yours, -- P | | | On Tue, Oct 4, 2011 at 9:23 AM, Simon Peyton-Jones | simo...@microsoft.com wrote: | FYI | | -Original Message- | From: glasgow-haskell-users-boun...@haskell.org [mailto:glasgow-haskell- | users-boun...@haskell.org] On Behalf Of George Giorgidze | Sent: 30 September 2011 18:28 | To: glasgow-haskell-users@haskell.org | Subject: Two Proposals | | GHC Users, | | I would like to make to the following two proposals: |* Eliminate the default grouping close from SQL-like comprehensions |* Introduce a GHC extension for list literal overloading | | OK, let me start with the first proposal. | | Currently, the SQL-like comprehension notation (both in its list comprehension | and monad comprehension variants) features the following five clauses: | | then f | then f by e | then group by e | then group using f | then group by e using f | | The first two clauses are used for specifying transformations of type [a] - [a] | (or Monad m = m a- m a for monad comprehensions). The following three | clauses are used for specifying transformations of type [a] - [[a]] (or Monad m, | Functor f = m a - m (f a) for monad comprehensions). See [1] for further | details. | | Note that the third clause does not mention which function is used for grouping. | In this case GHC.Exts.groupWith function is used as a default for list | comprehensions and the mgroupWith function from the MonadGroup class is used | as a default for monad comprehensions. | | I would like to suggest to remove the third clause for the following reasons: | * Currently the syntax is asymmetrical. Note that there is the default case for | the 'then group' clause and not for the 'then' clause. | * In the current notation it is not clear which grouping function is used in the | default case | * For many monads including lists it is not clear which function should be | selected as a default (e.g., the groupWith function also does sorting and it is not | clear to me why this should be the default) | * Gets rid of the MonadGroup class. Currently the sole purpose of this class is to | introduce a default grouping function for monad comprehensions. | * Explicit mention of the grouping function would make monad/list | comprehensions much easier to read by making it immediately apparent which | function is used for grouping. | | My second proposal is to
Re: case of an empty type should have no branches
On 2011-10-09 07:26, Roman Beslik wrote: Why the following code does not work? data Empty quodlibet :: Empty - a quodlibet x = case x of parse error (possibly incorrect indentation) It's a potential extension to ghc. See http://hackage.haskell.org/trac/ghc/ticket/2431 ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: case of an empty type should have no branches
What are you trying to acomplish? A case doesn't necessarily force evaluation in haskell depending on the binding pattern. for instance case x of _ - undefined will parse, but the function is still lazy in x. it is exactly equivalant to quodlibet x = undefined If you want to actually enforce that quodlibet _|_ evaluates to _|_ then you want quodlibet x = x `seq` undefined. Though, that too is technically equivalent in a theoretical sense, but may have practical benefits when it comes to error messages depending on what you are trying to acomplish. John On Sun, Oct 9, 2011 at 4:26 AM, Roman Beslik ber...@ukr.net wrote: Hi. Why the following code does not work? data Empty quodlibet :: Empty - a quodlibet x = case x of parse error (possibly incorrect indentation) This works in Coq, for instance. Demand for empty types is not big, but they are useful for generating finite types: Empty ≅ {} Maybe Empty ≅ {0} Maybe (Maybe Empty) ≅ {0, 1} Maybe (Maybe (Maybe Empty)) ≅ {0, 1, 2} etc. Number of 'Maybe's = number of elements. I can replace @Maybe Empty@ with @()@, but this adds some complexity. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users