August 2006 - Haskell-Cafe

RE: [Haskell] thread-local variables
by Simon Peyton-Jones 08 Aug '06

08 Aug '06

| I have initialized a wiki page: | | http://haskell.org/haskellwiki/Thread_local_storage Great | I have put a page on the wiki summarizing the thread. However, I want | to say that I think that email is a better medium for most ongoing | discussions. I agree. Discussion by email Outcomes on Wiki (including outcomes recording differences of viewpoint) The goal is that the outcome is a comprehensible summary of the outcome of the discussion, for the benefit of the many who will not follow the evolving debate. Furthermore, can we move this thread from the Haskell mailing list (which should not have heavy traffic) to either Haskell-Café, or the libraries list? Simon

2 1

How can we detect and fix memory leak due to lazyness?
by Ahn, Ki Yung 08 Aug '06

08 Aug '06

Recently, I'm facing the dark side of laziness -- the memory leak because of laziness. Typical pattern that I encounter the problem is like this. My code was working fine and I was happy. I just wanted to inspect some properties of my code so I made a slight chage go the code such as adding counter argument or attaching auxiliary data filed to original data for tracing how the data has been constructed. All of a sudden the program runs out of memory or overflows the stack. One problem is that it comes up unexpectedly. Another even worse problem is that sometimes I get no idea for the exact location causing the leak! It really panics facing such darkness of lazy evaluation. Just a small innocent looking fix for inspection or tracing blow things up, sometime with no clue for its reason. When we implement a debugging or tracing option in the software and let the user toggle those features, how could we be sure that turning on those features won't crash the software written in Haskell? Are there standardized approaches for detecting and fixing these kind of problems? Haskell may be type safe but not safe at all from unexpanded diversion, which is not because of the programmers' mistake but just because of the laziness. I have posted an wiki article including one example of adding a counter to count the number of basic operations in sorting algorithm. http://www.haskell.org/haskellwiki/Physical_equality This was a rather simple situation and we figured out how to cure this by self equality check ( x==x ) forcing evaluation. There are worse cases not being able to figure out the cure. I wrote a function for analyzing some property of a graph, which worked fine. fixOnBy t p f x = if t x' `p` t x then x else fixOnBy t p f x' where x' = f x fixSize f x = fixOnBy Set.size (==) f x sctAnal gs = null cgs || all (not . null) dcs where gs' = fixSize compose $ Set.fromList [(x,y,cs) | To _ x y cs<-Set.toList gs] cgs = [z | z@(x,y,cs)<-Set.toList gs', x==y] dcs = [ [c| c@(a,D,b)<-Set.toList cs , a==b] | (_,_,cs)<-cgs] compose gs = trace ("## "++show (Set.size gs)) $ foldr Set.insert gs $ do (x1,y1,cs1) <- Set.toList gs (_,y2,cs2) <- takeWhileFst y1 $ Set.toList $ setGT (y1,Al""(-1),Set.empty) gs return (x1,y2,cs1 `comp` cs2) takeWhileFst y = takeWhile (\(y',_,_) -> y==y') This function makes a transitive closure of the given set of relations by fixpoint iteration on the size of the set of weighted edges. Sample output is like this. *Main> main ## 170 ## 400 ## 1167 ## 2249 ## 2314 False When I add an extra data field for tracing how the new relation was constructed, (e.g. tag [a,b,c] on a->c if it came from a->b and b->c) it suddenly overflows the stack even before printing out the trace. The following is the code that leaks memory. sctAnal gs = null cgs || all (not . null) dcs where gs' = fixSize compose $ Set.fromList [TT (x,y,cs) [] | To _ x y cs<-Set.toList gs] cgs = [z | z@(TT (x,y,cs) _)<-Set.toList gs', x==y] dcs = [[c| c@(a,D,b)<-Set.toList cs , a==b] | TT (_,_,cs) _<-cgs] compose gs = trace ("## "++show (Set.size gs)) $ foldr checkInsert gs $ do TT (x1,y1,cs1) l1 <- Set.toList gs TT (_,y2,cs2) l2 <- takeWhileTTfrom y1 . Set.toList $ setGT (TT (y1,Al""(-1),Set.empty) []) gs return $ TT (x1,y2,cs1 `comp` cs2) (l1++y1:l2) takeWhileTTfrom y = takeWhile (\(TT (y',_,_) _) -> y==y') checkInsert x s | Set.member x s = s | otherwise = Set.insert x s data TT a b = TT a b deriving (Show) instance (Eq a, Eq b) => Eq (TT a b) where (TT x lx) == (TT y ly) = lx==lx && ly==ly && x == y instance (Ord a, Ord b) => Ord (TT a b) where (TT x lx) < (TT y ly) = lx==lx && ly==ly && x < y The really intersting thing happens when I just make the Ord derived the stack does not overflow and starts to print out the trace. (It is not the result that I want though. My intention is to ignore the tags in the set operation) data TT a b = TT a b deriving (Show,Eq,Ord) I believe my Eq and Ord instances defined above are even more stricter than the derived ones. Is there some magic in "deriving" that prevents memory leak? I've even followed the instance declaration like the following that would be the same as deriving but still leaks memory. data TT a b = TT a b deriving (Show) instance (Eq a, Eq b) => Eq (TT a b) where (TT x lx) == (TT y ly) = x == y && lx == ly instance (Ord a, Ord b) => Ord (TT a b) where (TT x lx) < (TT y ly) = x < y || x == y && lx < ly This is really a panic. -- Ahn, Ki Yung

8 8

Re:Re: Why Haskell
by Hans van Thiel 07 Aug '06

07 Aug '06

From: Hans van Thiel <hthiel.char(a)zonnet.nl> Reply-To: hthiel.char(a)zonnet.nl To: Johan Tibell <johan.tibell(a)gmail.com> Subject: Re: [Haskell-cafe] Re: Why Haskell? Date: Mon, 07 Aug 2006 17:21:17 +0200 On Mon, 2006-08-07 at 15:23 +0200, Johan Tibell wrote: > For me library support, for networking in particular, has been the > major hurdle. It gets problematic when too many libraries are still > marked as experimental and only partially implements the specification > (e.g. protocol) that they are supposed to handle. Also after a quick > look at the source for some common (networking) libraries I found a > few too many calls to error to feel comfortable. It's not okay for a > library to bring down my application behind my back, error should be > reported even if this uglifies the code and interfaces. Furthermore I > think that Haskell would benefit from moving some commonly used > functionality such as HTTP, SQL and XML support into the standard > libraries. I haven't seen any news about the progress of HaskellNet > but I guess it could solve my problems. > That's good to know, thanks! > I really don't have much problems with tool support, speed and the > like. I'm convinced it's a library (and library documentation!) thing. > Likewise. > > > Having someone pay a group of people to hack on Haskell > implementations would indeed be desirable. Without knowing the details > Ubuntu looks like a promising model. If we could just find a willing > billionaire out there.. Candidates would be companies that have an interest in promoting Haskell and/or fp, large and small. Ericsson comes to mind, if they are still active in fp. Or maybe one of the rising Indian, Chinese or or other 'globalization' firms could be the principal here? Personally, I'd love to see a Brazilian company like, for example, PetroBras pick this up. And just from a PR point of view, Haskell does project a cutting edge image. Anyway... Regards, Hans > Cheers, > > Johan

2 1

Need a good book on Haskell
by Johan Tibell 07 Aug '06

07 Aug '06

I've read Haskell: The Craft of Functional Programming on a course on functional programming at Chalmers (I also took the advanced course) and now I'm looking for some more reading material. Are there any other good Haskell books? Is there a Pick Axe, Camel or Dragon Book for Haskell?

3 2

The dark side of lazyness - memory leak
by Ahn, Ki Yung 07 Aug '06

07 Aug '06

I'm facing the dark side of lazyness recently. Typical pattern is like this. My code was working fine and I was happy. I just wanted to inspect some properties of my code so I made a slight chane go the code such as adding counter argument or attaching axulary data filed to original data for tracing how the data has been constructed. All of a sudden the program runs out of memory or overflows the stack. One problem is that it comes up unexptectedly. Another even worse problem is that sometimes I get no idea for the exact loation causing the leak! It really panics facing such darkness of lazy evaluation. Just a small innocent looking fix for inspection or tracing blow things up, sometime with no clue for its reason. When I put a debugging or tracing operating in my software that can be toggled, how could I be sure that turning on those features won't crash my software written in Haskell? Are there appraoches to detect and fix these kind of problem? Haskell may be type safe but not safe at all from unexpteded diversion, not because of the programmers' mistake but just because of the lazyness. I have posted an wiki article including one example of this dark side of lazyness I encountered when I tried to count the number of basic operations in sorting algorithm. This was a rather simple situation and we figured out how to cure this by self equality check ( x==x ) forcing evaluation. There are wose cases not being able to figure out the cure. I wrote a fucntion for analyzing some property of a graph, which worked fine. fixOnBy t p f x = if t x' `p` t x then x else fixOnBy t p f x' where x' = f x fixSize f x = fixOnBy Set.size (==) f x sctAnal gs = null cgs || all (not . null) dcs where gs' = fixSize compose $ Set.fromList [(x,y,cs) | To _ x y cs<-Set.toList gs] cgs = [z | z@(x,y,cs)<-Set.toList gs', x==y] dcs = [ [c| c@(a,D,b)<-Set.toList cs , a==b] | (_,_,cs)<-cgs] compose gs = trace ("## "++show (Set.size gs)) $ foldr Set.insert gs $ do (x1,y1,cs1) <- Set.toList gs (_,y2,cs2) <- takeWhileFst y1 $ Set.toList $ setGT (y1,Al""(-1),Set.empty) gs return (x1,y2,cs1 `comp` cs2) takeWhileFst y = takeWhile (\(y',_,_) -> y==y') This fucntion makes a transitive closure of the given set of relations by fixpoint iteration on the size of the set of weighted edegs. Sample output is like this. *Main> main ## 170 ## 400 ## 1167 ## 2249 ## 2314 False When I add an extra data field for tracing how the new item was made (e.g. tag [a,b,c] on a->c if it was generated by a->b and b->c) It suddenly overflows the stack even before printing out the trace. The following is the code that leaks memory. sctAnal gs = null cgs || all (not . null) dcs where gs' = fixSize compose $ Set.fromList [TT (x,y,cs) [] | To _ x y cs<-Set.toList gs] cgs = [z | z@(TT (x,y,cs) _)<-Set.toList gs', x==y] dcs = [[c| c@(a,D,b)<-Set.toList cs , a==b] | TT (_,_,cs) _<-cgs] compose gs = trace ("## "++show (Set.size gs)) $ foldr checkInsert gs $ do TT (x1,y1,cs1) l1 <- Set.toList gs TT (_,y2,cs2) l2 <- takeWhileTTfrom y1 . Set.toList $ setGT (TT (y1,Al""(-1),Set.empty) []) gs return $ TT (x1,y2,cs1 `comp` cs2) (l1++y1:l2) takeWhileTTfrom y = takeWhile (\(TT (y',_,_) _) -> y==y') checkInsert x s | Set.member x s = s | otherwise = Set.insert x s data TT a b = TT a b deriving (Show) instance (Eq a, Eq b) => Eq (TT a b) where (TT x lx) == (TT y ly) = lx==lx && ly==ly && x == y instance (Ord a, Ord b) => Ord (TT a b) where (TT x lx) < (TT y ly) = lx==lx && ly==ly && x < y The really intersting thing happens when I just make the Ord derived the stack does not overflow and starts to print out the trace. (It is not the result that I want though. My intention is to ignore the tags in the set operation) data TT a b = TT a b deriving (Show,Eq,Ord) I believe my Eq and Ord instances are even more stricter than the derived ones. Is there some magic in "deriving" that prevents memory leak? I've even followed the instance declaration that would be the same as deriving but the that leaks memory. data TT a b = TT a b deriving (Show) instance (Eq a, Eq b) => Eq (TT a b) where (TT x lx) == (TT y ly) = x == y && lx == ly instance (Ord a, Ord b) => Ord (TT a b) where (TT x lx) < (TT y ly) = x < y || x == y && lx < ly This is really a panic. -- Ahn, Ki Yung

1 0

Re: Why Haskell?
by Hans van Thiel 07 Aug '06

07 Aug '06

Hello All, Thanks for the many helpful replies to my question about the suitability of Haskell for industrial/commercial application. >From those I gather there are no licensing problems regarding the use of the standard functions and modules. Use of proprietary modules may or not be restricted by the authors, but of course this is to be expected and fair. Performance and size of Haskell programs don't seem to be problematic either, at least for small and medium size applications. Tool support, however, is less than for the more established languages. But maybe the Eclipse support which is under development will be a boost. Also, there are good interfaces with open source gui widgets etc. So, the summary conclusion would be that Haskell can be used (and is being used) provided the developers are aware that unexpected problems may arise in practice. Advantages of Haskell seem to be short size of code (and all the advantages that implies) and the high abstraction level and mathematical rigour (which makes for less programming errors). As for the 'popularity' of Haskell, someone made the very common sense remark that all successful languages have been promoted by some large corporation. (Please note 'successful' stands for 'spread of use', not 'quality' here.) If fp is to reach the mainstream, it will probably be because of some centralized support from outside the academic world. Maybe something like a 'Haskell Consortium' or 'Haskell Initiative' to promote Haskell should be set up. An example could be the promotion of SystemC for hardware and software co-design by the Open SystemC Initiative www.systemc.org . Availability of an IEEE standard for Haskell would also be a good thing for its acceptance, I think. That is, assuming 'mainstream' is the goal, of course. Regards, Hans van Thiel

1 0

Variants of a recursive data structure
by tpledger＠ihug.co.nz 07 Aug '06

07 Aug '06

Klaus Ostermann wrote: [...] > data Exp e = Num Int | Add e e > > data Labelled a = L String a > > newtype Mu f = Mu (f (Mu f)) > > type SimpleExp = Mu Exp > > type LabelledExp = Mu Labelled Exp > > The "SimpleExp" definition works fine, > but the LabeledExp definition doesn't > because I would need something like > "Mu (\a -> Labeled (Exp a))" where "\" > is a type-level lambda. > > However, I don't know how to do this in > Haskell. I'd need something like the > "." operator on the type-level. One way, that I haven't spotted in any of the replies so far, is to declare a composition type data BComp m n a = BC (m (n a)) as seen in http://web.cecs.pdx.edu/~mpj/pubs/springschool.html , so that type LabelledExp = Mu (BComp Labelled Exp) See http://haskell.cs.yale.edu/pipermail/haskell/2001-May/003942.html for more crafty tricks, including making Eq instances for such Mu-based recursive structures. Regards, Tom

1 0

Type inference problem
by Joel Björnson 07 Aug '06

07 Aug '06

Hi. I have a type inference related problem which causes me some confusion. The following is a simplified example capturing the key aspects. First of all, consider a data type (here called) Elem and a type class IsElem. data Elem = E class IsElem a where toElem :: a -> Elem instance IsElem Elem where toElem = id instance Show a => IsElem a where toElem _ = E Values of type Elem along with all instances of Show, instansitates the IsElem class. What I want to achieve is the enabling of definitions of classes/member functions corresponding to the following. class SetId t v r | t -> r where setId :: t -> v -> r And to instantiate the class, allowing 'setId' to produce values of type Elem as in instance SetId Elem String Elem where setId x _ = x Note that the fundep (t -> r) enables the type checker to uniquely determine the return type of setId, depending on it's first argument. It is now possible to write function definitions according to myElem = E `setId` "id" Checking the type of 'myElem' using ghci confirms that it has type 'Elem'. (Because of the E and the fundep) So far, so good... However, problems arises trying to define the function : test = toElem myElem Yielding the error message : 'No instance for (Show Elem) arising use of `toElem` at ...' For some reason it seems like the type checker picks the *wrong* 'toElem', and that the type of 'myElem' can't be properly determined (without adding explicit type signatures). It seems strange though the the type of myElem really can be determined and that the instance (IsElem Elem) is more specific then the instance for Show types. Anyway, I just realised that turning off the 'monomorphism-restriction' solves the problem. (Don't know why though). Is this *the* recommended solution here and is there any general policy regarding the flag ? Help/explanations are appreciated! Thanks a lot /Joel

1 1

Variants of a recursive data structure
by Klaus Ostermann 07 Aug '06

07 Aug '06

Hi all, I have a problem which is probably not a problem at all for Haskell experts, but I am struggling with it nevertheless. I want to model the following situation. I have ASTs for a language in two variatns: A "simple" form and a "labelled" form, e.g. data SimpleExp = Num Int | Add SimpleExp SimpleExp data LabelledExp = LNum Int String | LAdd LabelledExp LabelledExp String I wonder what would be the best way to model this situation without repeating the structure of the AST. I tried it using a fixed point operator for types like this: data Exp e = Num Int | Add e e data Labelled a = L String a newtype Mu f = Mu (f (Mu f)) type SimpleExp = Mu Exp type LabelledExp = Mu Labelled Exp The "SimpleExp" definition works fine, but the LabeledExp definition doesn't because I would need something like "Mu (\a -> Labeled (Exp a))" where "\" is a type-level lambda. However, I don't know how to do this in Haskell. I'd need something like the "." operator on the type-level. I also wonder whether it is possible to curry type constructors. The icing on the cake would be if it would also be possible to have a function unlabel :: LabeledExp -> Exp that does *not* need to know about the full structure of expressions. So, what options do I have to address this problem in Haskell? Klaus

10 18

Compiling To C And Why Not Compiling To Java Or C#?
by Kaveh Shahbazian 06 Aug '06

06 Aug '06

1 & 2 - Maybe this is not a proper question but I think It has a point. Why Not Compiling To Java Or C#? What is the need of implementing a class interoperability between Haskell and other plateforms? Maybe we donot need that. Haskell can be the big infrastructure and code snippets in Java or C# can serve in a monadic wrapper. It looks like that we can scripting Haskell in that languages. For example F# 's target code is ILX (an extension of MSIL for functional languages). But I think interoperablity between languages - like what .NET claims - is totaly pointless. Again think of an infrastructure that has a Haskell core which defines and controls very high level processes. Then there will be a running machine that Haskell is sitting on top of it. This running machine implement haskell in the plateform language. This is what I mean. 3 - And for an OOP style interoperability between languages, I think most usefull is to have a robust standard for Object-Broking. Something like IEC 61850 in new power systems in industry. A tool from siemens can understand what a hitachi high voltage key commands and all of these devices are from different providers with different internal implementations that meets the standard.

2 1