March 2001 - Haskell - Haskell.org

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