March 2002 - Haskell - Haskell.org

Re: using less stack
by John Hughes 21 Mar '02

21 Mar '02

\begin{rant} I think the whole seq thing is very confusing for beginning/intermediate haskell programmers. I was very confused for a long time as to why > (unsafePerformIO (putStrLn "Hello")) `seq` 5 would print "Hello", but > [unsafePerformIO (putStrLn "Hello")] `seq` 5 would not. ... I would almost prefer if the semantics of `seq` were instead those of rnf or deepSeq, so long as either (a) we were allowed to derive DeepSeq or NFData, or (b) if the compiler would just do it itself. Yes, this would cut down on the expressions which we could `seq`, but does that really matter. ... \end{rant} Well, seq isn't there to enable sequencing of unsafe IO. It's there to enable space optimisation. When heap profiling was first developed for Haskell, it fairly soon became clear that fine control of evaluation order was often the key to fixing space leaks. (Note: "fine control" includes making things lazier at times via ~ patterns, but also making things stricter at times). Seq is designed so that you can take ANY expression and move its evaluation where you want. If we only had deepSeq, we could only move an expression together with all of its subexpressions -- not good if a lazy list needs to be forced a little earlier! As for putting seq in a class excluding functions, that would mean that if you happened to use a function to represent an abstract data type, you would suddenly be unable to control the evaluation order of programs using that abstract data type -- and so potentially, unable to fix space leaks in them. That would make functions a kind of second class citizen: you would always know, when choosing a representation for an ADT, that if you chose a function then that would have an impact on space debugging later... If one is going to provide control of evaluation order (and it IS important), why surround it with complex rules and restrictions, when seq provides it simply for every single expression in the language? Space debugging is a bit of a hobby horse of mine, and I know it is considered by many to be something of a black art. It isn't so hard really: just run the heap profiler, find the leaks, and often the fix involves changing evaluation order. Use seq or ~ to do so. (There can be other fixes also, but these are a good start). I can't emphasize too much how useful the heap profiler is for building good intuitions about how programs are evaluated. I'd strongly advise intermediate Haskell programmers to spend some time using it: one learns a LOT! John Hughes

1 0

Re: using less stack
by C.Reinke 20 Mar '02

20 Mar '02

> > Actually, and quite apart from it being cumbersome to use, I've got > > my doubts about whether this cpsfold really does the job (is that > > just me missing some point?-). > > It does the job for me! In practical terms I can see it works. ..[explanation omitted].. I didn't express myself well: I don't doubt that you solved your problem by using cpsfold, but the cpsfold alone doesn't do the trick. It just translates the implicit continuation (which uses stack space) into an explicit continuation function (which uses heap space). So there's something else going on. As you explained, having the continuation explicit makes it easier to get a handle on what happens next at every step, which is the usual reason for using CPS style. And if neither the cautious evaluate-to-weak-head-normal-form seq nor the all-out evaluate-to-normal-form deepSeq do the job for you, I can well imagine that CPS style permits you to fine-tune evaluation to the needs of your application. But as Olaf has pointed out, having that much control can be a bit of a fragile construction. So I was just wondering about the specific use of fold in your application, and how you've redefined your operator to make use of your CPS version of fold (in order to solve the space problem). Incidentally, cpsfold processes the list in reversed order, which may or may not matter, depending on the operator passed to it. Hugs session for: Prelude.hs R.hs folds.hs Main> foldr (-) 0 [1..4] (1 - (2 - (3 - (4 - 0)))) Main> foldl (-) 0 [1..4] ((((0 - 1) - 2) - 3) - 4) Main> cpsfold (\x y c-> c $ x - y) 0 [1..4] (4 - (3 - (2 - (1 - 0)))) Claus -- Research Opportunity: Refactoring Functional Programs (UKC) Closing date: Friday 22 March 2002 <------- !!! http://www.cs.ukc.ac.uk/vacancies_dir/r02-24.html

1 0

[E-CFP] WFLP2002 - deadline EXTENSION
by WFLP2002 Organizing Committee 20 Mar '02

20 Mar '02

Dear Colleague The submission deadline for the WFLP 2002 has been extended till March 27, 2002 WFLP 2002 is the 11th international workshop on functional and (constraint) logic programming. WFLP 2002 aims to bring together researchers interested in functional programming, (constraint) logic programming, as well as their integration. For further details about the workshop please visit the web site http://www.dimi.uniud.it/~wflp2002/ Papers are due by March 27, 2002. This is a firm deadline. You can submit papers following the electronic submission process at: http://www.dimi.uniud.it/~wflp2002/submit/ We hope that this "Call For Papers" will be useful for your work. Please forward the following to anybody who you think may be interested. Our apologies if you received multiple copy of this. -- WFLP 2002 Organizing Committee http://www.dimi.uniud.ut/~wflp2002/

1 0

RE: question about concurrency implementation
by Simon Marlow 20 Mar '02

20 Mar '02

> I'm curious about the implementation of Concurrent Haskell in GHC and > Hugs. Does access to values possibly shared among threads > cost the same > in Concurrent Haskell as in regular Haskell? I'm guessing > the answer is > "yes", because Concurrent Haskell is provided by default in > GHC. "yes" > If the costs are the same, does that rely on there being no true > concurrency in > the current implementations? It depends what you mean by true concurrency: from the point of view of the Haskell programmer, GHC's implementation of concurrency is "almost" preemptive, because we can context-switch at any allocation. Most computation does some allocation, but it's possible to write functions that don't (although these tend to be on the trivial side - an optimised nfib won't allocate, for example). We could artificially cause all computation to do some allocation to avoid this problem, but we haven't found it necessary so far. But I suspect by "true concurrency" you're referring at the kind of concurrent processes that can be executed on multiple CPUs simultaneously. We did investigate doing this a while back, and found that the locking required on thunks was very expensive (slowed down the program by at least 2x on the bog-standard SMP machine we had here). However there are some clever techniques that can be used to reduce the cost - giving each process its own private allocation area and only degrading to full locking for access to the shared portion of the heap is one such technique we experimented with briefly but I don't have any concrete benchmarks I'm afraid. Also you really need a multithreaded garbage collector, which is a lot of work. Cheers, Simon

2 1

finding ....
by Diego Yanivello 20 Mar '02

20 Mar '02

hi, is there (in Haskell) a function like existFile :: FilePath -> IO (Bool) ? Thanks!

7 10

using less stack
by Amanda Clare 20 Mar '02

20 Mar '02

I have stack problems: my program uses too much stack. I suspect, from removing bits of code, that it's due to a foldr in my program. If I use foldr or foldl on a long list (eg >500 bulky elements for a 3M stack), is this likely to be filling the stack? What is it that gets stored on the stack? If so, is there an obvious refactoring of the fold to use? Amanda -- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621787 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB

2 4

Empirical Software Engineering: An International Journal - CALL FOR PAPERS
by ESEJournal＠unisannio.it 19 Mar '02

19 Mar '02

*********************************************************** Empirical Software Engineering: An International Journal - CALL FOR PAPERS - *********************************************************** http://www.kluweronline.com/issn/1382-3256 . Consider submitting papers on your latest experiments and field studies! . The journal focuses on software measurement, quality and productivity improvement, and technology evaluation . Empirical studies addressing important software development issues are reported, providing results and data . Check the Journal Contents link for a sample of published articles . Papers can be searched and downloaded on line! . Individual subscription: USD $68 - subscribe on-line Please forward the following to anybody who you think may be interested. Our apologies if you received multiple copy of this message. If you would like to be removed from our list please send an email to ESEJournal(a)unisannio.it with REMOVE in the subject.

1 0

Re: Haskell puzzles!
by Jan-Willem Maessen 19 Mar '02

19 Mar '02

Daan Leijen writes: > 1) Are e1 and e2 equal? > > > f (x:xs) y = x > > g (x:xs) = \y -> x > > > > e1 = seq (f []) 1 > > e2 = seq (g []) 1 > ... > 1) > answer: > "e1" equals the value 1, while "e2" is undefined. > ... > opinion: > I think that the pattern matching translation rules > are wrong here and we shouldn't push the "case" through > the lambda's. However, the current rules are potentially > more efficient since all arguments can be collected > before matching. On the contrary, I far prefer the way things are now. Matching arguments as they arrive makes programs far too eager about pattern matching. Consider the following minor variation on your example (which happily also avoids using "seq"): Q) Are e1 and e2 both defined? > f (x:xs) y z = x > g (x:xs) = \y -> \z -> x > > e1 = f [] 1 > e2 = g [] 1 A) No, e1 is defined---pattern matching happens only when all the arguments have arrived. This is nice and lazy---we don't do any work until we know we have to. By contrast, e2 performs the matching as soon as (g []) is applied to 1. We've matched eagerly, and our program fails. opinion: In practice, pattern matches are much more complicated than f and g. There is no easy and convenient way to get the behavior of e1 if matching always works as in e2. Indeed, it's not even clear how to do complex multiple-argument pattern matches if we proceed this way. Meanwhile, there's a simple way to turn f into g if that's what is desired. -Jan-Willem Maessen And I've implemented *Eager* Haskell, too.

1 0

Haskell puzzles!
by Daan Leijen 19 Mar '02

19 Mar '02

Hi all, I have put together some interesting Haskell puzzles! Not many people were able to solve all three puzzles so don't be discouraged you don't know all the answers. Have fun, Daan. ----------------------------------------------------- - All three puzzles are "Haskell 98"; you can solve them using the Haskell 98 manual and they should be implementation independent. - "equal" means that two evaluated expression denote the same semantical value; i.e. when typed on the Hugs prompt, I will see the same answer. - All the answers are at the end of this mail. ----------------------------------------------------- 1) Are e1 and e2 equal? > f (x:xs) y = x > g (x:xs) = \y -> x > > e1 = seq (f []) 1 > e2 = seq (g []) 1 ----------------------------------------------------- 2) Are e1 and e2 equal? Is one definition preferred over the other? (And what about "h x = nfib 30" ?) > f = const (nfib 30) > g = \x -> nfib 30 > > e1 = f 1 + f 2 > e2 = g 1 + g 2 ----------------------------------------------------- 3) Are e1 and e2 equal? And what if I typed them on the Hugs prompt? > f = \x -> x + x > g x = x + x > > e1 = f 1.0 + f 2.0 > e2 = g 1.0 + g 2.0 ----------------------------------------------------- Answers at the end of this email..... Answers: ----------------------------------------------------- 1) answer: "e1" equals the value 1, while "e2" is undefined. explanation: This is due to the translation of pattern matching. The functions are de sugared into: > f x' y = case x' of (x:xs) -> x > g x' = case x' of (x:xs) -> (\y -> x) Now, the expression "f []" is a partial application and thus in weak head normal form while "g []" is evaluated and the pattern matching fails. opinion: I think that the pattern matching translation rules are wrong here and we shouldn't push the "case" through the lambda's. However, the current rules are potentially more efficient since all arguments can be collected before matching. ----------------------------------------------------- 2) answer: Yes, "e1" and "e2" are equal. However, the "f" definition is preferred since it potentially shares the computation of "nfib 30". ("e1" will be almost twice as fast as "e2" on most systems). explanation: The Haskell language is only defined to be "non-strict". This means that there are no guarantees about sharing. However, all current Haskell systems use lazy semantics. This means that both "f" and "g" are caf's. When "g" is evaluated, the expression "\x -> nfib 30" is shared and on each call "nfib 30" is re-evaluated. When "f" is evaluated, the application node "const (nfib 30)" is shared and once it is applied it will be updated and "nfib 30" is only evaluated once. Smart compilers like GHC however, will inline definitions like "g" and after common expression elimination we also end up with an efficient version. Same would hold for a full laziness transformation. Note that "h x = nfib 30" behaves exactly like "g" except that it's type is more general due to the monomorphism restriction and defaulting: > f,g :: a -> Integer > h :: Num b => a -> b opinion: I believe that the operational distinction between both definitions is fundamentally important and should be expressible by the user. ----------------------------------------------------- 3) answer: Yes, "e1" and "e2" are equal (6.0). However, when "e1" and "e2" are used outside the scope of "f" and "g", for example when typed on the Hugs prompt, "e1" is not well-typed. explanation: The type of "g" is "Num a => a -> a". One would expect the same type for "f" but unfortunately, the monomorphism restriction prevents this and defaulting tries to resolve the instance. Based on the usage of "f", it will default to "Double" and we get the type "Double -> Double" for "f". However, if we would use it from the Hugs prompt, there is no usage site of "f" and defaulting will resort to the "default defaulting" rules and set the type of "f" to "Integer -> Integer" and the expression "f 1.0" becomes ill typed -- that is, unless I use a "default" declaration in the module, as in: > default (Double) opinion: Clearly, as puzzle 2 shows, we want to have a distinction between shared values and functions. So, we need at least to be warned when the compiler would add a dictionary argument. I would say that an "overloading warning" is more appropriate than a "monomorphism restriction". Anyway, the real culprit here is the horrible defaulting mechanism. I believe that defaulting has no place in Haskell modules and should probably only be used on expressions in a top-level interpreter.

1 0

Gaussian integers. Reply
by S.D.Mechveliani 19 Mar '02

19 Mar '02

dominic.j.steinitz(a)britishairways.com writes > On holiday, I started reading about Gaussian integers (as you do) and I > thought this should be a piece of cake for Haskell. I get the following > error in Hugs: > [..] > > data Integral a => Gaussian a = Gaussian a a > deriving (Eq, Show) > > instance Num (Gaussian a) where > Gaussian a b - Gaussian a' b' = Gaussian (a-a') (b-b') > Gaussian a b + Gaussian a' b' = Gaussian (a+a') (b+b') > Gaussian a b * Gaussian a' b' = Gaussian (a*a' - b*b') (a*b' + b*a') > negate (Gaussian a b) = Gaussian (negate a) (negate b) > fromInteger a = Gaussian (fromIntegral a) 0 To my mind, it is not good to set `Integral a =>' to data declaration. It is better to set such things in the instance declarations. Try, say data Gaussian a = Gau a a deriving (Eq, Show) instance Integral a => Num (Gaussian a) where Gau a b - Gau a' b' = Gau (a-a') (b-b') ... ------------------------------------------------- scico:~/t> ghci M.hs ... GHC Interactive, version 5.02.2, for Haskell 98. ... M> Gau 1 1 * Gau 1 (-1) Gau 2 0 ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0