- Haskell - Haskell.org

RE: strictness question
by S. Doaitse Swierstra 02 Mar '01

02 Mar '01

Thanks for the prompt reply. Hugs apparently is more lazy and performs all the matching lazily, and that really makes a difference in my case. Doaitse At 8:11 AM -0800 3/2/01, Simon Peyton-Jones wrote: >Strange. You don't supply a complete program, so it's hard to >test. > >Nevertheless, the Haskell Report (Sect 3.12) specifies that >a let adds a single twiddle. Thus > > let (x, (y,z)) = e in b > >means > > let x = case e of (x,(y,z)) -> x > y = case e of (x,(y,z)) -> y > z = case e of (x,(y,z)) -> z > in b > >And that is what GHC implements. You get something different if you >add twiddles inside: > > let (x, ~(y,z)) = e in b > >means > let x = case e of (x,_) -> x > y = case e of (_,(y,_)) -> y > etc > >Adding more twiddles means less eager matching. I don't know whether >Hugs implements this. > >Simon > >| -----Original Message----- >| From: S. Doaitse Swierstra [mailto:doaitse@cs.uu.nl] >| Sent: 01 March 2001 11:26 >| To: haskell(a)haskell.org >| Subject: strictness question >| >| >| I ran into a difference between GHC and Hugs. The following code: >| >| f (P p) ~(P q) = P (\ k -> \inp -> let (((pv, (qv, r)), m), st) = >| p (q k) inp >| in (((pv qv , r ), m), st)) >| >| runs fine with Hugs but blows up with GHC, whereas: >| >| f (P p) ~(P q) = P (\ k -> \inp -> let ~(~(~(pv, ~(qv, r)), m), >| st) = p (q k) inp >| in (((pv qv , r ), m), st)) >| >| runs fine with GHC too. >| >| From the Haskell manual I understand that pattern matching >| in "let"'s >| should be done lazily, so the addition of a collection of ~'s should >| not make a difference. Am I right with this interpretation? >| >| A possible source of this problem may be origination from the smarter >| GHC optimiser, but in that case the optimiser is not doing its work >| well. >| >| Doaitse Swierstra >| >| >| >| >| -- >| ______________________________________________________________ >| ____________ >| S. Doaitse Swierstra, Department of Computer Science, Utrecht >| University >| P.O.Box 80.089, 3508 TB UTRECHT, the >| Netherlands >| Mail: mailto:doaitse@cs.uu.nl >| WWW: http://www.cs.uu.nl/ >| PGP Public Key: >http://www.cs.uu.nl/people/doaitse/ > tel: +31 (30) 253 3962, fax: +31 (30) 2513791 >__________________________________________________________________________ > >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell -- __________________________________________________________________________ S. Doaitse Swierstra, Department of Computer Science, Utrecht University P.O.Box 80.089, 3508 TB UTRECHT, the Netherlands Mail: mailto:doaitse@cs.uu.nl WWW: http://www.cs.uu.nl/ PGP Public Key: http://www.cs.uu.nl/people/doaitse/ tel: +31 (30) 253 3962, fax: +31 (30) 2513791 __________________________________________________________________________

1 0

Pattern guards vs. case (was, unfortunately :Re: interesting example of laziness/ghc optimisation)
by Ketil Malde 02 Mar '01

02 Mar '01

(Apologies, I forgot to change the subject) Laszlo Nemeth <laszlo(a)ropas.kaist.ac.kr> writes: > * * * Ketil Malde <ketil(a)ii.uib.no> wrote: > There is no difference. The 'pipe-syntax' (or pattern guards) gets > desugared (by the pattern matching compiler) to case statements i.e.: > runRandom = \ last max num.case (num > 1) of > True -> runRandom (fst new) max (num-1) > False -> snd new But - the converse is not true, is it? I can write ... = case foo of (Foo f) -> ... (Bar b) -> ... but I can't express that as a pattern-guarded expression, can I? My impression here is that the PG syntax adds nothing, and is hardly any more readable, and less intuitive for migrators from more traditional language. Why is it there at all? Is there a (rough) guideline for when to use one or the other? > For a more detailed discussion see SPJ's book, Augustsson original > paper, or M Pettersen't thesis (LNCS 1549). Okay, I'll try to look them up. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

5 5

RE: strictness question
by Simon Peyton-Jones 02 Mar '01

02 Mar '01

Strange. You don't supply a complete program, so it's hard to test. Nevertheless, the Haskell Report (Sect 3.12) specifies that a let adds a single twiddle. Thus let (x, (y,z)) = e in b means let x = case e of (x,(y,z)) -> x y = case e of (x,(y,z)) -> y z = case e of (x,(y,z)) -> z in b And that is what GHC implements. You get something different if you add twiddles inside: let (x, ~(y,z)) = e in b means let x = case e of (x,_) -> x y = case e of (_,(y,_)) -> y etc Adding more twiddles means less eager matching. I don't know whether Hugs implements this. Simon | -----Original Message----- | From: S. Doaitse Swierstra [mailto:doaitse@cs.uu.nl] | Sent: 01 March 2001 11:26 | To: haskell(a)haskell.org | Subject: strictness question | | | I ran into a difference between GHC and Hugs. The following code: | | f (P p) ~(P q) = P (\ k -> \inp -> let (((pv, (qv, r)), m), st) = | p (q k) inp | in (((pv qv , r ), m), st)) | | runs fine with Hugs but blows up with GHC, whereas: | | f (P p) ~(P q) = P (\ k -> \inp -> let ~(~(~(pv, ~(qv, r)), m), | st) = p (q k) inp | in (((pv qv , r ), m), st)) | | runs fine with GHC too. | | From the Haskell manual I understand that pattern matching | in "let"'s | should be done lazily, so the addition of a collection of ~'s should | not make a difference. Am I right with this interpretation? | | A possible source of this problem may be origination from the smarter | GHC optimiser, but in that case the optimiser is not doing its work | well. | | Doaitse Swierstra | | | | | -- | ______________________________________________________________ | ____________ | S. Doaitse Swierstra, Department of Computer Science, Utrecht | University | P.O.Box 80.089, 3508 TB UTRECHT, the | Netherlands | Mail: mailto:doaitse@cs.uu.nl | WWW: http://www.cs.uu.nl/ | PGP Public Key: http://www.cs.uu.nl/people/doaitse/ tel: +31 (30) 253 3962, fax: +31 (30) 2513791 __________________________________________________________________________ _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

1 0

WRS'2001 - Extended deadline
by Salvador Lucas Alba 02 Mar '01

02 Mar '01

[Apologies for multiple copies of this announcement] ************************************************************************** ******* Last call for papers - extended deadline: March 12, 2001 ******* ************************************************************************** International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2001) held in conjunction with RTA 2001 Utrecht, The Netherlands, May 26, 2001 -------------------------------------------------------------------------- BACKGROUND AND AIMS Reduction strategies in rewriting and programming have attracted an increasing attention within the last years. New types of reduction strategies have been invented and investigated, and new results on rewriting / computation under particular strategies have been obtained. Research in this field ranges from primarily theoretical questions about reduction strategies to very practical application and implementation issues. The need for a deeper understanding of reduction strategies in rewriting and programming, both in theory and practice, is obvious, since they bridge the gap between unrestricted general rewriting (computation) and (more deterministic) rewriting with particular strategies (programming). Moreover, reduction strategies provide a natural way to go from operational principles (e.g., graph and term rewriting, narrowing, lambda-calculus) and semantics (e.g., normalization, computation of values, infinitary normalization, head-normalization) to implementations of programming languages. Therefore any progress in this area is likely to be of interest not only to the rewriting community, but also to neighbouring fields like functional programming, functional-logic programming, and termination proofs of algorithms. The workshop wants to provide a forum for the presentation and discussion of new ideas and results, recent developments, new research directions, as well as of surveys on existing knowledge in this area. Furthermore we aim at fostering interaction and exchange between researchers and students actively working on such topics. The workshop will be held in conjunction with RTA 2001 in Utrecht (The Netherlands) on May 26, 2001. It will feature 2 invited talks, a panel discussion, and contributed presentations selected from the submissions, with ample time for discussion. The workshop is (co-)organized by U Utrecht, TU Valencia and TU Wien. TOPICS OF INTEREST Topics of interest include, but are not restricted to, - theoretical foundations for the definition and semantic description of reduction strategies - strategies in different frameworks (term rewriting, graph rewriting, infinitary rewriting, lambda calculi, higher order rewriting, conditional rewriting, rewriting with built-ins, narrowing, constraint solving, etc.) and their application in (equational, functional, functional-logic) programming (languages) - properties of reduction strategies / computations under strategies (e.g., completeness, computability, decidability, complexity, optimality, (hyper-)normalization, cofinality, fairness, perpetuality, context-freeness, neededness, laziness, eagerness, strictness) - interrelations, combinations and applications of reduction under different strategies (e.g., equivalence conditions for fundamental properties like termination and confluence, applications in modularity analysis, connections between strategies of different frameworks, etc.) - program analysis and other semantics-based optimization techniques dealing with reduction strategies - rewrite systems / tools / implementations with flexible / programmable strategies as essential concept / ingredient - specification of reduction strategies in (real) languages - data structures and implementation techniques for reduction strategies. SUBMISSIONS We solicit papers on all aspects of reduction strategies in rewriting and programming. Submissions should describe unpublished work, except for survey papers which are explicitly welcome, too. Submissions should not exceed 10 pages (however, survey papers may be longer) and be sent in postscript format to the PC co-chairs (wrs01(a)logic.at) by March 12, 2001. Selection of papers by the PC will be based on originality, significance, and correctness. Accepted papers will be included in the workshop proceedings that will be available at the workshop, and electronically on the web. Depending on the number and quality of submissions, formal publication of the proceedings is envisaged. Researchers just interested in attending the workshop may send a corresponding email to wrs01(a)logic.at by March 12, 2001, preferably together with a brief position paper (up to two pages in postscript) describing their interest and/or work in the area. However, we will also consider late requests for attendance. INVITED TALKS Sergio Antoy (U Portland State): Evaluation Strategies for Functional Logic Programming Eelco Visser (U Utrecht, The Netherlands): A Survey of Strategies in Program Transformation Systems PANEL DISCUSSION on ``Hot Topics in Reduction Strategies'' with Michael Hanus U Kiel (Germany) Tetsuo Ida U Tsukuba (Japan) Paul Klint CWI & U Amsterdam (The Netherlands) PROGRAM COMMITTEE Maria Alpuente TU Valencia (Spain) Rachid Echahed IMAG Grenoble (France) Bernhard Gramlich (co-chair) TU Wien (Austria) Salvador Lucas (co-chair) TU Valencia (Spain) Vincent van Oostrom U Utrecht (The Netherlands) Rinus Plasmeijer KU Nijmegen (The Netherlands) Manfred Schmidt-Schauss U Frankfurt a.M. (Germany) Yoshihito Toyama U Tohoku (Japan) LOCAL ORGANIZATION Vincent van Oostrom U Utrecht (The Netherlands) IMPORTANT DATES Submission March 12, 2001 (extended deadline) Notification March 31, 2001 Final version April 30, 2001 Workshop May 26, 2001 FURTHER INFORMATION workshop website http://www.logic.at/wrs01/ workshop email address wrs01(a)logic.at **************************************************************************

1 0

Re: interesting example of lazyness/ghc optimisation
by George Russell 01 Mar '01

01 Mar '01

I hope nobody actually uses this random number generator. It appears to be linear congruential with period less than 140000. The author of these benchmarks seem to have got this algorithm from "Numerical Recipes", whose code (at least, in the early editions) has come in for some very heavy criticism: http://math.jpl.nasa.gov/nr/nr.html I would take these benchmarks more seriously if "random" implied a slightly more modern algorithm, like the Mersenne Twister (which has been implemented in Haskell I believe). Julian Assange wrote: > Noticing the use of tuples and normalisation at each step of > the iteration, I re-wrote this as: > > module Main(main) where > import System(getArgs) > import Numeric(showFFloat) > > main = do > ~[n] <- getArgs > putStrLn (showFFloat (Just 12) (random 42 (read n::Int) 100.0) "") > return 1 > > random :: Int -> Int -> Double -> Double > random seed n max = norm (rand n seed) max > where norm x max = (fromIntegral x) * (max / imd) > rand n x = if n > 0 then rand (n-1) ((x * ia + ic) `mod` im) else x > im = 139968 > imd = fromIntegral im > ia = 3877 > ic = 29573

1 0

Re: interesting example of lazyness/ghc optimisation
by Ketil Malde 01 Mar '01

01 Mar '01

There's something that I've been wanting to ask sombody about, since it isn't terribly clear to me. Blatantly hijacking a function from Julian's code: > runRandom last max num > | num > 1 = runRandom (fst new) max (num-1) > | otherwise = snd new While ifs are perhaps more intuitive when there are only two choices (like here!), and pattern matching matches on the type of arguments and not (only) their values, What's the difference between the pipe-syntax, and a case statement, i.e. writing the function as runRandom last max num = case num of 1 -> runRandom .... otherwise -> snd new Is there a practical difference, and if not, why are there two ways to skin this particular cat? Apologies for coming up with a terribly naive question, but I've looked in the HR without gaining much wisdom (beyond the recipe for translating if to case). -kzm -- If I haven't seen further, it is by standing in the footprints of giants

4 3

2001 Haskell Workshop: 1st call for papers
by Ralf Hinze 01 Mar '01

01 Mar '01

============================================================================ FIRST CALL FOR PAPERS [Deadline for submission: 1st June 2001] 2001 Haskell Workshop Firenze, Italy, 2nd September 2001 The Haskell Workshop forms part of the PLI 2001 colloquium on Principles, Logics, and Implementations of high-level programming languages, which comprises the ICFP/PPDP conferences and associated workshops. Previous Haskell Workshops have been held in La Jolla (1995), Amsterdam (1997), Paris (1999), and Montreal (2000). http://www.cs.uu.nl/people/ralf/hw2001.{html,pdf,ps,txt} ============================================================================ Scope ----- The purpose of the Haskell Workshop is to discuss experience with Haskell, and possible future developments for the language. The scope of the workshop includes all aspects of the design, semantics, theory, application, implementation, and teaching of Haskell. Submissions that discuss limitations of Haskell at present and/or propose new ideas for future versions of Haskell are particularly encouraged. Adopting an idea from ICFP 2000, the workshop also solicits two special classes of submissions, application letters and functional pearls, described below. Application Letters ------------------- An application letter describes experience using Haskell to solve real-world problems. Such a paper might typically be about six pages, and may be judged by interest of the application and novel use of Haskell. Functional Pearls ----------------- A functional pearl presents - using Haskell as a vehicle - an idea that is small, rounded, and glows with its own light. Such a paper might typically be about six pages, and may be judged by elegance of development and clarity of expression. Submission details ------------------ Deadline for submission: 1st June 2001 Notification of acceptance: 1st July 2001 Final submission due: 1st August 2001 Haskell Workshop: 2nd September 2001 Authors should submit papers of at most 12 pages, in postscript format, formatted for A4 paper, to Ralf Hinze (ralf(a)cs.uu.nl) by 1st June 2001. The use of the ENTCS style files is strongly recommended. Application letters and functional pearls should be labeled as such on the first page. They may be any length up to twelve pages, though shorter submissions are welcome. The accepted papers will be published as a University of Utrecht technical report. Programme committee ------------------- Manuel Chakravarty University of New South Wales Jeremy Gibbons University of Oxford Ralf Hinze (chair) University of Utrecht Patrik Jansson Chalmers University Mark Jones Oregon Graduate Institute Ross Paterson City University, London Simon Peyton Jones Microsoft Research Stephanie Weirich Cornell University ============================================================================

1 0

interesting example of lazyness/ghc optimisation
by Julian Assange 01 Mar '01

01 Mar '01

Brian Gregor wrote a haskell entrant for the random number generation in Doug's language shootout (http://www.bagley.org/~doug/shootout) Which is as follows: module Main where import System import Numeric iMi :: Int iMi = 139968 iMd :: Double iMd = 139968.0 iA ::Int iA = 3877 iC ::Int iC = 29573 nrRandom :: Int -> Double -> (Int,Double) nrRandom last max = (newlast,(max * (fromIntegral newlast)/iMd)) where newlast = (last*iA+iC) `mod` iMi runRandom :: Int -> Double -> Int -> Double runRandom last max num | num > 1 = runRandom (fst new) max (num-1) | otherwise = snd new where new = nrRandom last max main = do ~[n] <- getArgs putStrLn (showFFloat (Just 12) (runRandom 42 100.0 (read n::Int)) "") Noticing the use of tuples and normalisation at each step of the iteration, I re-wrote this as: module Main(main) where import System(getArgs) import Numeric(showFFloat) main = do ~[n] <- getArgs putStrLn (showFFloat (Just 12) (random 42 (read n::Int) 100.0) "") return 1 random :: Int -> Int -> Double -> Double random seed n max = norm (rand n seed) max where norm x max = (fromIntegral x) * (max / imd) rand n x = if n > 0 then rand (n-1) ((x * ia + ic) `mod` im) else x im = 139968 imd = fromIntegral im ia = 3877 ic = 29573 Interestingly, ghc / lazyness is able to detect that Brian's normalisation etc at each step is uneeded, and only perform it at the end. Consequently both of these programs are the the same speed (well, almost; bizarrely, Brian's seems to be about 2% faster). Julian.

1 0

My stack overflow was due to addListToFM
by senganb＠ia.nsc.com 01 Mar '01

01 Mar '01

Hi, Interestingly given the recent discussion about foldl versus foldl' I'd like to report that the stack overflow I was seeing was due to addListToFM which is defined using foldl although addToFM is strict in FiniteMap according to ghc: addToFM :: ... {PrelBase.Ord key} -> FiniteMap key elt -> key -> elt -> FiniteMap key elt {-## __A 4 __S LSLL __U ... So, I'd like to request that FiniteMap be changed to use foldl'. Compiler implementors, I'd also like to request that your compiler emit a warning in such cases if at all possible given that this has since even the best haskell programmers seem to miss this case (the authors of FiniteMap). --------------------------------------------------------------------------------- For those of you wondering how I found this, I used the following heuristic: 1 Build your program with -prof -auto-all -caf-all 2 Run your program with -h so that Main.hp is created. 3 Then look at the various functions that are reported to use a lot of heap. 4 Grep through Main.hp for the function that happens to have a recent rapid increase of heap. 5 Then look at its code. In my case I got find_atoms/add_atom_equalities 33808 find_atoms/add_atom_equalities 186128 find_atoms/add_atom_equalities 338448 find_atoms/add_atom_equalities 490768 find_atoms/add_atom_equalities 643088 find_atoms/add_atom_equalities 795408 find_atoms/add_atom_equalities 947728 find_atoms/add_atom_equalities 1100048 find_atoms/add_atom_equalities 1233976 find_atoms/add_atom_equalities 1302328 find_atoms/add_atom_equalities 1370680 find_atoms/add_atom_equalities 1439032 find_atoms/add_atom_equalities 1507384 find_atoms/add_atom_equalities 1575736 find_atoms/add_atom_equalities 1644088 find_atoms/add_atom_equalities 1697552 just before the crash. Reasoning --------- Since GHC optimizes tail recursion, the cause of a stack overflow must be something else, eg: a you've got a non-tail recursive function b your tail recursive function has built a long spine on the heap of functions that are strict in their 2cd argument so that you need to evaluate the bottom-most element of the spine (which causes you to push the address of all the functions along the spine onto the stack) c or... I assumed b since I know my code doesn't contain many cases of a. If b is the case, since the function that is overflowing is being evaluated, we know that it's going to build up its spine quickly and then try to evalute it, find that each function on the spine is strict in its second argument and then die. Therefore heuristic step 4. You also need it to use a fair bit of heap to actually be bad enough to overflow the stack (therefore heuristic step 3). Sengan

1 0

Re: Proposal: module namespaces.
by Christian Brolin 28 Feb '01

28 Feb '01

Malcolm Wallace wrote: > > Christian writes: > > What about the module declaration? Should it be: > > module Text.Xml.Parser where ... > > or just > > module Parser where ... -- located in Text/Xml/Parser.hs? > > The former. The reason is that a compiler needs to generate a unique > linker symbol for each defined function. If the full module name is > not encoded in the source file, you will need to add a commandline > option to the compiler, which is the wrong way to go in my opinion. What?? The compiler knows the full name of the module without the module clause. If it didn't do that, it can't find the modules to compile! Does the compiler opens every file on the Internet to check whether it is the file to compile? How does the compiler find the file to compile in the first place? What should the command line option you mentioned do? > Why is e.g. Parser.f not sufficient as a unique symbol for > Text.Xml.Parser.f? Well, what if you also have Text.Html.Parser.f? > You really need the full thing. Of course, see above. > > I would also like to import modules using relative addresses, e.g. the > > file: > > My/Small/Test/Xml/Parser.hs > > contains: > > import .Lexer -- Relative path to the module: My.Small.Test.Xml.Lexer > > import ..Data -- Relative path to the module: My.Small.Test.Xml.Parser.Data > > import Text.ParserCombinators.HuttonMeijer -- Absolute address > > I'm sorry, I don't entirely follow what the differing numbers of > initial dots mean. They are used to specify relative addresses to other modules. Relative addresses is a very important concept, but You missed it in your proposal. The dots was just my suggestion of a syntax for relative addresses. One dot: Relative to the parent of this module. Two dots: Relative to this module. E.g. module A.B.C.D1 where import A.B.C.D1.E1 import A.B.C.D1.E1.F import A.B.C.D1.E2 import A.B.C.D2 import X.Y.Z would be the same as (delete 'A.B.C'): module A.B.C.D1 where import .D1.E1 import .D1.E1.F import .D1.E2 import .D2 import X.Y.Z would be the same as (delete 'D1'): module A.B.C.D1 where import ..E1 import ..E1.F import ..E2 import .D2 import X.Y.Z Move the package of modules (A.B.C.*) to (Std.AAA.BBB.CCC.*) and rename D1 to DDD: module Std.AAA.BBB.CCC.DDD where import ..E1 import ..E1.F import ..E2 import .D2 import X.Y.Z The only thing that needs to be changed is the module clause. Which of course would be unnecessary if the module clause was dropped. > > When the world realize that this is the XML parser, they won't accept > > the name and I refuse to change my implementation. The only thing that > > is needed to rename (an unused) module hierarchy is to move it. > > If you refuse to change your implementation, someone else will change > it for you! You can't have closed standards. It is not necessary to modify the modules if the module system supports relative addresses!!! The steering wheel of my car is positioned relative to my car, so it is NOT necessary to change that position when I move the car. -- Christian Brolin

4 6