- Haskell - Haskell.org

RE: [Haskell] reader-like IO, parents of threads
by Simon Marlow 19 Oct '05

19 Oct '05

It seems that you can do this as long as you provide your own version of forkIO, but not if you want to use the built-in forkIO. One could argue that getting the parent ThreadId is something that should be supported natively by forkIO, and I might be inlined to agree. Unfortunately there are some subtleties: currently a ThreadId is represented by a pointer to the thread itself, which causes the thread to be kept alive. This has implications not only for space leaks, but also for reporting deadlock: if you have a ThreadId for a thread, you can send it an exception with throwTo at any time, and hence the runtime can never determine that the thread is deadlocked so it will never get the NonTermination exception. Perhaps we need two kinds of ThreadId: a weak one for use in Maps, and a strong one that you can use with throwTo. But then building a Map in which some elements can be garbage collected is a bit tricky (it can be done though; see our old Memo table implementation in fptools/hslibs/util/Memo.hs). Cheers, Simon On 16 October 2005 20:53, Frederik Eaton wrote: > John Meacham suggested that I should be a little more clear about the > semantics I'm seeking. Also, apparently it isn't possible to implement > writeTLRef/modifyTLRef with the data structure I gave: > >> data TLRef a = TLR a (MVar (Map ThreadId a)) > (the first argument is a default value, the second is a map storing > the values in each thread. The MVar is for safe concurrent access) > > Without those functions, it looks a little more like the Reader monad > I'm comparing it to. > > - What happens on fork? The child thread effectively gets a "copy" of > each TLRef in its parent. They have the same values, but modifying > them using withTLRef has no effect on the values in other threads. > > - Can you pass a TLRef to a different thread? Yes, but the value it > holds will not be the same when it is dereferenced in a different > thread. > > The problem with writeTLRef is that if a child thread looks up the > default value for an unbound reference by looking up the value in its > parent, but after calling forkIO the parent changes the value with > writeTLRef, then the child thread will get the wrong value. It is > supposed to only see the value which was stored in the reference at > the point where forkIO was called. > > Also, for this reason, I think withTLRef would have to be implemented > by creating a separate thread with forkIO and waiting for it to > finish. This would avoid overwriting a value which other child threads > might still need to access. > > Note that an e.g. "myParentThreadId" function isn't enough - what is > needed is a > > parentThreadId :: ThreadId -> IO (Maybe ThreadId) > > which can look up the parent of an arbitrary thread. > > Alternatively, if 'forkIO' supported hooks to run before and/or after > forking, then a 'parentThreadId' function could be implemented from > that. > > Frederik > > On Sun, Oct 16, 2005 at 04:40:40AM -0700, Frederik Eaton wrote: >> Hi, >> >> I'm trying to get MonadReader-like functionality in the IO monad. It >> doesn't appear possible implement it with the interfaces that >> Haskell98 or GHC provide. I'm looking for something like >> "thread-local variables". The interface could be something like this: >> >> newTLRef :: a -> IO (TLRef a) >> withTLRef :: TLRef a -> a -> IO b -> IO b >> readTLRef :: TLRef a -> IO a >> writeTLRef :: TLRef a -> a -> IO () >> modifyTLRef :: TLRef a -> (a -> a) -> IO () >> >> This would have a lot of uses. I am aware of the "Implicit >> Configurations" paper by Kiselyov and Shan, but a solution such as >> theirs which requires modifying the type signatures of all >> intermediate function calls is not suitable. I want to be able to say >> "run algorithm A using database D" without requiring all of the >> functions in algorithm A to know that databases are somehow involved. >> One way to look at it is that I am seeking something like the >> type-based approach, but easier and with less explicit syntax; >> another way to look at it is that I am seeking something like a >> global IORef based approach, but more safe. >> >> An implementation based on ThreadId-keyed maps is almost workable: >> >> data TLRef a = TLR a (MVar (Map ThreadId a)) >> >> The problem with this is that while it is possible to find out the >> ThreadId of the current thread, it doesn't appear to be possible to >> get the ThreadId of the parent thread, which would be needed for >> values to be properly inherited. >> >> Is there a way around this? Will there ever be standard support for >> either finding the thread id of the parent of the current thread, or >> for something like the thread-local references I have proposed? >> >> Thanks, >> >> Frederik >> _______________________________________________ >> Haskell mailing list >> Haskell(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell >> > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

3 2

RE: [Haskell] Excessive sharing and GHC
by Simon Peyton-Jones 19 Oct '05

19 Oct '05

| Clearly, in this instance GHC is not transforming either of these | definitions into the other. But are there other compile time transformations | performed by GHC that might result in more (excessive) sharing, in | particular the creation of new common sub-expressions such as pxs? If not, | is that a deliberate design decision? GHC tries not to create space leaks, but does not guarantee not to. In particular, the full laziness transformation is so beneficial most of the time that, even though it can create a space leak GHC still does it (unless you turn it off with a flag). GHC only does very limited common sub-expression elimination, which again is very beneficial usually but can have bad behaviour. It's not general CSE which is why it didn't kick in in the program you gave. | Since I guess the "excessive" bit of excessive sharing probably can't be | determined until run-time, would it be practical for the run-time system to | do something about it? For example, once the run-time system notices that | the graph size has breached a certain threshold it begins to decouple | references to "reduced" but bulky sections of the graph, forcing them to be | recomputed (from the original expression) at a later time. I don't know anyone who has tried to make this work. Sounds pretty tricky. Simon

3 3

Haskell Weekly News: October 18, 2005
by John Goerzen 18 Oct '05

18 Oct '05

Haskell Weekly News: October 18, 2005 Greetings, and thanks for reading the 12th issue of HWN, a weekly newsletter for the Haskell community. Each Tuesday, new editions will be posted (as text) to [1]the Haskell mailing list and (as HTML) to [2]The Haskell Sequence. 1. http://www.haskell.org/mailman/listinfo/haskell 2. http://sequence.complete.org/ New Releases * Decimal arithmetic library. Jeremy Shaw [3]announced the "premature release" of his new Decimal arithmetic library, which is designed for cases where binary floating point is not acceptable, such as money. 3. http://article.gmane.org/gmane.comp.lang.haskell.cafe/8734 * JRegex. John Meacham [4]announced JRegex, a library that interfaces to both PCRE and Posix regular expressions. 4. http://article.gmane.org/gmane.comp.lang.haskell.general/12340 * Haskell XML Toolbox 5.3. Uwe Schmidt [5]announced version 5.3 of the Haskell XML Toolbox. The main changes in this release are improvements to the arrow system. 5. http://article.gmane.org/gmane.comp.lang.haskell.general/12271 Requests for Participation Future Haskell Standard. Isaac Jones [6]posted a request for participation in the formation of the next standardized version of Haskell. 6. http://article.gmane.org/gmane.comp.lang.haskell.cafe/8646 HCAR Clarification. Last week's HWN story on the Haskell Communities & Activities Report (HCAR) had some misleading wording. Participation in this report is open to all, and submissions are encouraged from everyone. Discussion Haskell mentioned on Slashdot. Haskell was [7]mention on Slashdot. The post was refering to [8]an article about optimizing development for fun and had [9]pugs as its example. 7. http://developers.slashdot.org/article.pl?sid=05/10/09/1831219&tid=156 8. http://www.oreillynet.com/pub/wlg/7996 9. http://www.pugscode.org/ ZLib bindings. Joel Reymont [10]asked about code for handling GZip files. Henning Thielemann suggested the code in Darcs. Malcom Wallace pointed out code in qforeign, and John Goerzen mentioned the pure-Haskell implementation in MissingH. 10. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/8759 GADTs. Bulat Ziganshin began a [11]discussion asking for resources on GADTs. Several people posted links to helpful resources. 11. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/8708 Class aliases. John Meacham began a long [12]discussion by proposing class aliases, a language extension to solve problems of multiple implementations of the same concept in different libraries. 12. http://thread.gmane.org/gmane.comp.lang.haskell.general/12276 About Haskell Weekly News Thanks to Josef Svenningsson for contributing material towards this week's HWN. Want to continue reading HWN? Please help us create new editions of this newsletter. Please see the [13]contributing information, or send stories to hwn -at- complete -dot- org. There is also a Darcs repository available. 13. http://sequence.complete.org/hwn-contrib

1 0

RE: [Haskell] really undecidable instances?
by Simon Peyton-Jones 18 Oct '05

18 Oct '05

It's all very delicate. I believe, though I am not certain, that in the absence of functional dependencies, removing at least one type constructor might be an example of a rule that is sufficient to ensure termination. There are lots of such rules. Alas none known to me capture all cases. Functional dependencies make things much worse. Suppose you have instance C Int a => D Char [a] which looks safe enough. But now class C x y | x -> y instance D Char [b] => C Int [[b]] and now we loop. There's a paper on my home page explaining why functional dependencies are tricky (co-authored with Martin Sulzmann, Peter Stuckey and Gregory Duck). Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Wolfgang | Jeltsch | Sent: 17 October 2005 16:12 | To: Haskell ML | Subject: Re: [Haskell] really undecidable instances? | | Am Montag, 17. Oktober 2005 15:57 schrieben Sie: | > This one | | [That is the instance declaration instance C Int a => D Char [a].] | | > can't. But it's hard to formulate a general rule. | > -fallow-undecidable-instances simply says that you, the programmer, take | > responsibility for termination. Without the flag, GHC uses a simple but | > sometimes over-conservative rule | > | > Simon | | [Could you please put citations at the top of the respective mail?] | | Section 7.4.4.3 of the GHC User's guide says about the restrictions for | ensuring decidability: | | These restrictions ensure that context reduction terminates: each reduction | step removes one type constructor. | | But as far as I can see, in my example there is also one type constructor | removed. Why isn't this allowed then? | | Best wishes, | Wolfgang | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

2 1

ANNOUNCE: JRegex library
by John Meacham 18 Oct '05

18 Oct '05

JRegex is a library that provides interfaces to both PCRE (perl comptatable regular expressions) and Posix regular expressions. it also provides an operator (=~) which is similar, but much more powerful than the perl operator. In addition, the syntax uses extensible type classes so you may extend it with any regular expression or list matching types and the ability to match lists of any type (not just chars). for an example, here is the output of several calls to =~ just used at different types: -- return number of times the regex matches print ("hellofooobarbobfoobarbad" =~ "fo*bar" :: Int) => 2 -- returns the first matching expression print ("hellofooobarbobfoobarbad" =~ "fo*bar" :: String) => "fooobar" -- returns the string before the first match, the matching string, and the string after the first match print ("hellofooobarbobfoobarbad" =~ "fo*bar" :: (String,String,String)) => ("hello","fooobar","bobfoobarbad") -- returns true if there is a match at all and false otherwise print ("hellofooobarbobfoobarbad" =~ "fo*bar" :: Bool) => True -- always returns (). useful with the (=~~) monadic operator print ("hellofooobarbobfoobarbad" =~ "fo*bar" :: ()) => () -- returns all matching substrings print ("hellofooobarbobfoobarbad" =~ "fo*bar" :: [String]) => ["fooobar","foobar"] -- returns an array off all matching parenthesised substrings in the regex for first match print ("hellofooobarbobfoobaaarbad" =~ "f(o*)b(a+r)" :: Array Int String) => array (0,2) [(0,"fooobar"),(1,"ooo"),(2,"ar")] -- returns an array off all matching parenthesised substrings in the regex for all matches print ("hellofooobarbobfoobaaarbad" =~ "f(o*)b(a+r)" :: [Array Int String]) => [array (0,2) [(0,"fooobar"),(1,"ooo"),(2,"ar")],array (0,2) [(0,"foobaaar"),(1,"oo"),(2,"aaar")]] here is its homepage: http://repetae.net/john/computer/haskell/JRegex/ I released a different version of this library in the past, but this version has been cleaned up, moved to a proper spot in the libraries, and is cabalized. John -- John Meacham - ⑆repetae.net⑆john⑈

1 0

Excessive sharing and GHC
by paul boston 17 Oct '05

17 Oct '05

Questions prompted by the "Excessive Sharing" section, page 405, of SPJ's "The Implementation of Functional Programming". This section gives 2 variations of a power list function, semantically equivalent, but with different space behaviours. Paraphrasing, given a caller of "length (powerListXXX [1..20])", the powerListBad version gobbles more and more space as execution proceeds, whilst the powerListGood version runs in a small amount of constant space. Confirmed under GHC 6.2.2 with -O2. powerListBad [] = [[]] powerListBad (x:xs) = pxs ++ map ((:) x) pxs where (x:xs) pxs = powerListBad xs powerListGood [] = [[]] powerListGood (x:xs) = powerListGood xs ++ map ((:) x) (powerLIstGood xs) Clearly, in this instance GHC is not transforming either of these definitions into the other. But are there other compile time transformations performed by GHC that might result in more (excessive) sharing, in particular the creation of new common sub-expressions such as pxs? If not, is that a deliberate design decision? Since I guess the "excessive" bit of excessive sharing probably can't be determined until run-time, would it be practical for the run-time system to do something about it? For example, once the run-time system notices that the graph size has breached a certain threshold it begins to decouple references to "reduced" but bulky sections of the graph, forcing them to be recomputed (from the original expression) at a later time. _________________________________________________________________ Is your PC infected? Get a FREE online computer virus scan from McAfee® Security. http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

1 0

instance C (a -> a)
by Wolfgang Jeltsch 17 Oct '05

17 Oct '05

Lieber Herr Bachmann, instance-Deklarationen der Form instance C (a -> a) sind tatsächlich nicht konform zum Haskell-98-Standard, ebensowenig instance C (a,a) und dergleichen, was heißt, dass diese Einschränkung nichts mit dem Funktionstyp zu tun hat. Generell darf ein und dieselbe Typvariable nicht mehrfach im Kopf der instance-Deklaration vorkommen. Allerdings erlaubt Hugs98, wie ich vermutet hatte, derartige Konstruktionen, wenn man die Haskell-98-Kompatibilität ausschaltet (Kommandozeilen-Parameter -98). Auch der Glasgow Haskell Compiler unterstützt solche Sachen. Viele Grüße Wolfgang Jeltsch

1 1

really undecidable instances?
by Wolfgang Jeltsch 17 Oct '05

17 Oct '05

Hello, what ist the problem with instance declarations like the following: instance C Int a => D Char [a] Why are such declarations only allowed with -fallow-undecidable-instances in GHC? How can they result in undecidability? Best wishes, Wolfgang

1 0

multiple occurence of the same type variable in instance head
by Wolfgang Jeltsch 17 Oct '05

17 Oct '05

Hello, the following is not Haskell 98: class C a instance C (a,a) Well, GHC allows this with the -fglasgow-exts flag. Surprisingly, I cannot find a section in the GHC User's Guide which states that -fglasgow-exts can be used to allow this kind of instance declarations. Well, in the section on undecidable instances (7.4.4.3), one can read: Note that instance heads may contain repeated type variables. For example, this is OK: instance Stateful (ST s) (MutVar s) where ... But one has to note that in this expample, the different occurences of s aren't in the same type. Furthermore, multiple occurences of the same type variable cannot result in undecidability (as far as I understand). The above-mentioned statement talks about the things that are allowed *without* -fallow-undecidable-instances, and premises that multiple occurences of a type variable are okay. So am I missing something? Best wishes, Wolfgang

1 0

RE: GADTs and GHC
by Simon Peyton-Jones 17 Oct '05

17 Oct '05

Dear Hakellions PS: In my message about uses of GADTs I asked | ... | d) send Omega code, which GHC won't understand, but which | demonstrates some cunning use of GADTs | All of these would be useful, even (c) and (d) --- we can eyeball the code. I should have also asked you to send examples of Chameleon code. http://www.comp.nus.edu.sg/~sulzmann/chameleon/ that uses GADTs. (Actually Chameleon does a lot more besides GADTs. For example, it has an interesting type debugger.) Simon

1 0