- Haskell - Haskell.org

strict vs. lazy state threads
by Wolfgang Jeltsch 31 Jul '05

31 Jul '05

Hello, http://haskell.org/ghc/docs/latest/html/libraries/base/Control.Monad.ST.html says about the module Control.Monad.ST: This library provides support for strict state threads, as described in the PLDI '94 paper by John Launchbury and Simon Peyton Jones Lazy State Threads. I cannot find a paper Lazy State Threads in the list of papers on Simon Peyton Jones' website but I assume that the library documentation refers to Lazy *Functional* State Threads. The problem is that I cannot find an exact specification about what strict and lazy means in conjunction with state threads. I thought that the (only) difference between strict and lazy state threads is that with strict state threads the result is _|_ if the final state is _|_ while with lazy state threads the result may be non-_|_ even if the final state is _|_. Operationally, this would mean that with strict state threads the final state would always be demanded which wouldn't be true for lazy state threads. Is this correct? But if it's correct, I don't understand why the library documentation claims that the above-mentioned paper describes strict state threads since from my studies of the paper I came to the conclusion that it describes lazy state threads. Any helpful comments are appreciated. Regards, Wolfgang

2 1

RE: [Haskell] combining IntMaps
by Scherrer, Chad 31 Jul '05

31 Jul '05

Thanks! It's interesting the way your AVL tree library is set up -- there seems to be a much broader degree of functionality than that provided by Data.Set. But I'm trying to see, is there a significant difference in the fundamental data structure, or is the main point that the additional functionality could not have otherwise been provided in an efficient way without going into the guts of Data.Set? Chad Scherrer -----Original Message----- From: Adrian Hey [mailto:ahey@iee.org] Sent: Wednesday, July 20, 2005 10:57 PM To: Scherrer, Chad; haskell(a)haskell.org Subject: Re: [Haskell] combining IntMaps On Wednesday 20 Jul 2005 4:05 am, Scherrer, Chad wrote: > I'm using the (IntMap Int) type to implement functions (Int -> Int), > by treating non-keys as values that map to zero. I'd like to be able > to add two of these pointwise, and delete the key from the resulting > map when the sum of the values is zero. My specification is > > addMaps :: IntMap Int -> IntMap Int -> IntMap Int addMaps m = > IntMap.filter (/= 0) . IntMap.unionWith (+) m > > But I'm not really happy with this because it traverses both maps for > the union, and then traverses the result to get rid of all the zeros. > (This function is a performance bottleneck in my current code). Examples like this are interesting because they show just how difficult it is produce a comprehensive library for even one common or garden data structure. I thought my AVL library was reasonably complete when I released it, but I've subsequently thought of plenty of stuff that's still missing (arguably), and you've just given me more. Anyway, you might like to try using AVL trees which I have just upgraded to provide the necessary functions.. http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/ You should be able to produce a reasonable alternative to Data.IntMap with this. I'd be interested to know how it performs. I won't do the whole thing myself, but here's a start (uses GHCs unboxed Ints). {-# OPTIONS -fglasgow-exts #-} import Data.COrdering import Data.Tree.AVL import GHC.Base data IntAssoc = IntAssoc Int# Int# --Perhaps use boxed values instead?? newtype IMap = IMap (AVL IntAssoc) emptyIMap :: IMap emptyIMap = IMap empty lookUp :: IMap -> Int -> Int lookUp (IMap avl) (I# skey) = genReadDefault 0 avl cmp where cmp (IntAssoc key v) = case compareInt# skey key of LT -> Lt EQ -> Eq (I# v) GT -> Gt set :: Int -> Int -> IMap -> IMap set (I# k) (I# v) (IMap avl) = IMap avl' where avl' = if v ==# 0# then genDel cmp avl else genPush ccmp ia avl ia = IntAssoc k v cmp (IntAssoc k' _) = compareInt# k k' ccmp (IntAssoc k' _) = case compareInt# k k' of LT -> Lt EQ -> Eq ia GT -> Gt addMaps :: IMap -> IMap -> IMap addMaps (IMap avl0) (IMap avl1) = IMap (genUnionMaybe ccmp avl0 avl1) where ccmp (IntAssoc k0 v0) (IntAssoc k1 v1) = case compareInt# k0 k1 of LT -> Lt EQ -> let s = v0 +# v1 in if s ==# 0# then Eq Nothing else Eq (Just (IntAssoc k0 s)) GT -> Gt Regards -- Adrian Hey

3 3

combining IntMaps
by Scherrer, Chad 30 Jul '05

30 Jul '05

I'm using the (IntMap Int) type to implement functions (Int -> Int), by treating non-keys as values that map to zero. I'd like to be able to add two of these pointwise, and delete the key from the resulting map when the sum of the values is zero. My specification is addMaps :: IntMap Int -> IntMap Int -> IntMap Int addMaps m = IntMap.filter (/= 0) . IntMap.unionWith (+) m But I'm not really happy with this because it traverses both maps for the union, and then traverses the result to get rid of all the zeros. (This function is a performance bottleneck in my current code). I thought I could do something like addMaps' :: IntMap Int -> IntMap Int -> IntMap Int addMaps' = IntMap.foldWithKey f where f k x = IntMap.update (maybeAdd x) k maybeAdd x v = let s = v + x in if s == 0 then Nothing else Just s But this is no good, because IntMap.update only affects those keys where lookup succeeds, so IntMap.update (maybeAdd 3) 8 IntMap.empty returns IntMap.empty, rather than a map with 8 -> 3 as I had hoped. What would you suggest to help addMaps run faster? Do I need to pry open the IntMap implementation to do better? Thanks so much, Chad Scherrer PS - I mistakenly crosslisted this to the GHC users list, because I didn't realize how the mailing lists were set up. Please excuse my noobiness.

3 2

4-year PhD Positions at UPM -- MOBIUS EU Project
by MOBIUS PhD Grants 30 Jul '05

30 Jul '05

---------------------------------------------------------------------- Announcement of up to three PhD Scholarships to pursue PhD studies in the CLIP group (http://clip.dia.fi.upm.es) Technical University of Madrid (Spain) in the context of the MOBIUS EU project (http://mobius.inria.fr) ---------------------------------------------------------------------- The CLIP group at the Technical University of Madrid (UPM) invites applications for up to three, fully funded, 4-year, PhD Scholarships for qualified graduate students. Candidates should have graduated in Computer Science, Computer Engineering, or related fields prior to the start of their study at UPM. The working language of the group is English, and candidates can be of any nationality. The Ph.D. work will center around the research areas of the CLIP group within the European research project "MOBIUS", under the direction of German Puebla and Manuel Hermenegildo. The general aim of "MOBIUS: Mobility, Ubiquity and Security" is to develop a framework for establishing trust and security of Java programs, using the Proof Carrying Code paradigm. The project will start September 1, 2005 and will run for four years. Within the MOBIUS project, the research of the CLIP group focuses on Abstraction Carrying Code, an Abstract Interpretation based approach to mobile code safety. This involves the development of new advanced program analysis techniques for security and verification, including resource consumption, both in terms of time and memory. The offered scholarships provide excellent opportunities for international collaboration since MOBIUS is a European project with 16 partners from 10 countries. Also, the CLIP group is active and international, with around 15 full-time members from 6 different countries. The grants include academic fees, medical care, plus a tax-free monthly payment which ranges from 1,100 to 1,600 euros, depending on experience. The following qualifications are not mandatory, but increase the chances of success: * Experience with Java, Java bytecode, and JML * Knowledge of (Constraint) Logic Programming * Interest in software verification and security Applications and information: ---------------------------- The deadline for applications is September 26, 2005. Applications received after this deadline may be considered if the scholarships have not been filled at the time. Applications should be sent to mobius-phd-grants(a)clip.dia.fi.upm.es and include a curriculum vitae, a listing of grades from previous studies, a brief description of research interests with regards to the CLIP group and MOBIUS, and, if at all possible, letters of recommendation from teachers or managers that the student has worked with. The latest information on the scholarships and the application process can be found at http://www.clip.dia.fi.upm.es/Job_Openings/mobius-phd-grants.html ---------------------------------------------------------------------- -- =============================================================== | German Puebla | http://clip.dia.fi.upm.es/~german | | Facultad de Informatica | Universidad Politecnica de Madrid | ===============================================================

1 0

RE: [Haskell] stack overflow - nonobvious thunks?
by Scherrer, Chad 29 Jul '05

29 Jul '05

Thanks! I was confused at first because ghci still runs into memory problems, though no longer stack overflows. ghc runs it beautifully, though. -Chad -----Original Message----- From: Amanda Clare [mailto:afc@aber.ac.uk] Sent: Thursday, July 28, 2005 3:20 AM To: Dean Herington Cc: Scherrer, Chad; haskell(a)haskell.org Subject: Re: [Haskell] stack overflow - nonobvious thunks? Dean's version certainly seems the neatest, but just for interest you can also do it with a cps fold instead of foldl' too: table xs = assocs $! cpsfold f empty xs where f x m k = case Map.lookup x m of Just v -> v `seq` (k $ Map.adjust (+1) x m) Nothing -> k $ Map.insert x 1 m cpsfold f a [] = a cpsfold f a (x:xs) = f x a (\y -> cpsfold f y xs) As far as I understand it this just makes sure the "seq" happens before the folding continues. When compiled with ghc, both solutions are very well behaved, and seem to take the same small amount of memory whether for 10000000 or 100000000. Amanda Dean Herington wrote: > The following version seems to do the trick (and still remain quite > readable). It worked for 100000000 as well. > > import Data.Map as Map > import System.Random > import Data.List (foldl') > > table :: (Ord a) => [a] -> [(a,Int)] > table xs = Map.assocs $! foldl' f Map.empty xs > where f m x = let m' = Map.insertWith (+) x 1 m > Just v = Map.lookup x m' > in v `seq` m' > > unif :: [Int] > unif = randomRs (1,10) $ mkStdGen 1 > > f :: Int -> [(Int, Int)] > f n = table $ take n unif > main = print $ f 10000000 > > - Dean

1 0

RE: [Haskell] stack overflow - nonobvious thunks?
by Scherrer, Chad 29 Jul '05

29 Jul '05

Adrian, Does your AVL library have an "insertWith'"-type function mentioned by Udo? If I lookup and insert into the table separately, forcing evaluation at each step, I can do table' :: (Ord a) => [a] -> [(a, Int)] table' xs = Map.assocs $! foldl' f Map.empty xs where f m x = (Map.insert x $! 1 + Map.findWithDefault 0 x m) $! m This helps with the stack overflow problem, but now I'm hitting a different wall: *Main> table $ take 10000000 unif [(1,999662),(2,1000220),(3,998800),(4,1000965),(5,999314),(6,1001819),(7 ,1000997),(8,999450),(9,999877),(10,998896)] *Main> table $ take 100000000 unif <interactive>: out of memory (requested 1048576 bytes) I thought I may have found a good approach using an idea from one of Amanda Clare's pages http://users.aber.ac.uk/afc/stricthaskell.html If I write eqSeq x y = if x==x then y else y this forces evaluation of x further than seq alone. Then I can write table :: (Ord a) => [a] -> [(a, Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = m `eqSeq` Map.insertWith (+) x 1 m Same result as Udo's suggestion - out of memory. I still don't see why this function should need any more than a few kilobytes, even for very large n like this. -Chad -----Original Message----- From: u.stenzel(a)web.de [mailto:u.stenzel@web.de] Sent: Wednesday, July 27, 2005 11:02 AM To: Scherrer, Chad Cc: haskell(a)haskell.org Subject: Re: [Haskell] stack overflow - nonobvious thunks? Scherrer, Chad wrote: > f m x = Map.insertWith (+) x 1 m insertWith is inserting the "nonobvious thunks". Internally it applies (+) to the old value and the new one, producing a thunk. There is no place you could put a seq or something to force the result. You basically need insertWith', which isn't there. I think, your best best is to manually lookup the old value, combine with the new, force the result, then insert that, overwriting the old value. On top of that you still need foldl' to avoid building long chains of Map.insert. Udo. -- The Second Law of Thermodynamics: If you think things are in a mess now, just wait! -- Jim Warner

4 3

ICFP 2005 - Final Call for Papers
by Benjamin C. Pierce 28 Jul '05

28 Jul '05

NEWS: * submission and formatting instructions are now available * the dates of the author response period have changed slightly --------- International Conference on Functional Programming (ICFP 2005) Call for Papers September 26-28, 2005 Tallinn, Estonia Submission deadline: 13 April, 2005 Submission instructions: http://www.cis.upenn.edu/~bcpierce/icfp05 ICFP 2005 seeks original papers on the art and science of functional programming. Submissions are invited on all topics ranging from principles to practice, from foundations to features, from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects and concurrency. Particular topics of interest include: * Applications and domain-specific languages: Systems programming, scientific and numerical computing, symbolic computing and artificial intelligence, databases, graphical user interfaces, multimedia programming, application scripting, system administration, distributed-systems and web programming, XML processing, security. * Foundations: Formal semantics, lambda calculus, type theory, monads, continuations, control, state, effects. * Design: Algorithms and data structures, modules and type systems, concurrency and distribution, components and composition, relations to object-oriented and logic programming. * Implementation: Abstract machines, compile-time and run-time optimization, just-in-time compilers, memory management. Interfaces to foreign functions, services, components and low-level machine resources. * Transformation and analysis: Abstract interpretation, partial evaluation, program transformation. * Software-development techniques for functional programming: Design patterns, specification, verification, validation, debugging, test generation, tracing and profiling. * Practice and experience: Functional programming in education and industry. * Functional pearls: Elegant, instructive examples of functional programming. Papers in the last three categories need not necessarily report original research results; they may instead, for example, report practical experience that will be useful to others, re-usable programming idioms, or elegant new ways of approaching a problem. A special issue of the Journal of Functional Programming will highlight selected papers from the meeting. Submission instructions are available here: http://www.cis.upenn.edu/~bcpierce/icfp05 Important Dates: Submission deadline: 13 April, 2005, at 6PM (in Philadelphia) On-line response to reviews: 19-21 May, 2005 Author notification: 3 June, 2005 Camera-ready copy: 10 July, 2005 Organizers: Conference Chair: Olivier Danvy (BRICS, University of Aarhus) Program Chair: Benjamin Pierce (University of Pennsylvania) Program Committee: Mariangiola Dezani (Universita di Torino) Mary Fernandez (AT&T Labs) Matthew Flatt (University of Utah) Cedric Fournet (Microsoft Research) Jacques Garrigue (Kyoto University) Jason Hickey (California Institute of Technology) John Hughes (Chalmers University) Johan Jeuring (Utrecht University) Frank Pfenning (Carnegie Mellon University) Benjamin Pierce (University of Pennsylvania) Andrew Pitts (University of Cambridge) Norman Ramsey (Harvard University) Manuel Serrano (INRIA Sophia Antipolis) Peter Thiemann (Universitat Freiburg) Jan Vitek (Purdue University)

2 1

Call for participation: CUFP 2005
by Andy Moran 28 Jul '05

28 Jul '05

IMPORTANT NOTE: Registration is now available at: http://www.cs.ioc.ee/tfp-icfp-gpce05/ CUFP 2005 THE SECOND ACM SIGPLAN COMMERCIAL USERS OF FUNCTIONAL PROGRAMMING WORKSHOP http://www.galois.com/cufp/ Talinn, Estonia September 24th 2005 Co-located with ICFP http://www.brics.dk/~danvy/icfp05/ ---------------------------------------------------------------------- Important dates Early registration deadline July 29, 2005 Late registration deadline September 2, 2005 Workshop September 24, 2005 Registration is available at: http://www.cs.ioc.ee/tfp-icfp-gpce05 ---------------------------------------------------------------------- The goal of CUFP is to build a community for users of functional programming languages and technology, be they using functional languages in their professional lives, in an open source project (other than implementation of functional languages), as a hobby, or any combination thereof. In short: anyone who uses functional programming as a /means/, but not an /end/. ---------------------------------------------------------------------- Schedule The meeting will last a full day, with a mix of invited presentations and discussion sessions. This year, we have the following confirmed speakers: * Atrijus Tang; talking about PUGS, a Perl6 implementation, written in Haskell; * Fabrice Le Fessant; talking about MLDonkey, a popular multi-platform, multi-network P2P client written in OCaml. * Michael Sperber; talking about uses of Scheme in the banking industry. * David Roundy; talking about darcs, a popular and flexible revision control system well-suited to highly distributed development, written in Haskell. * Jim Grundy; talking his experiences with functional programming at Intel's Strategic CAD Labs. * Robert Boone; talking about his experiences at FreeScale. * Jonathan Soebel; talking about lessons the FP community can learn from the OMG's Model Driven Architecture (MDA) and its related marketing efforts. We will also be having two working sessions, where lively debate and brainstorming will be the order of the day: * FP, Education, and Industry: industry folks complain that there aren't enough FP folks being produced by schools, and educators complain that students don't see any point in studying FP if there are no jobs to be had. How can we break this stalemate? Simon Thompson of Functional and Declarative Programming in Education (FDPE05) will be joining us, and we'll be debriefing at FDPE05. * Stimulating a CUFP Community: we'd like the buzz and excitement surrounding CUFP to persist beyond the workshops. What would such a community look like? How do we make it happen? The session will kick off with two separate but complimentary starting points: a proposed "Users of FP" community web site and a proposed "Haskell Consortium" web site. There will be no published proceedings, as the meeting is intended to be more a discussion forum than a technical interchange. A full report of last year's workshop appeared in the Functional Programming column of the December 2004 issue of SIGPLAN Notices, and we plan to do the same this year. -- Andy Moran Phone: 503.626.6616, x113 Galois Connections Inc. Fax: 503.350.0833 12725 SW Millikan Way, Suite #290 http://www.galois.com Beaverton, OR 97005 moran(a)galois.com

1 0

runProcess with out=err
by Ian Lynagh 28 Jul '05

28 Jul '05

Hi, With the below code (compiled by ghc) I get "a.out: thread blocked indefinitely". Changing the second (Just hout) to Nothing makes it run as expected. If I dup fdout to get an fderr and then try to also convert that to a handle then I get "a.out: openFile: resource busy (file is locked)". Is there a way to write this with stdout and stderr going to the same handle? ------------------- module Main (main) where import System.Posix (openFd, defaultFileFlags, stdFileMode, OpenMode(ReadOnly, WriteOnly), fdToHandle) import System.Process (runProcess, waitForProcess) main :: IO () main = exec "echo" ["foo"] "in" "out" exec :: String -> [String] -> FilePath -> FilePath -> IO () exec c args inp out = do fdin <- openFd inp ReadOnly Nothing defaultFileFlags fdout <- openFd out WriteOnly (Just stdFileMode) defaultFileFlags hin <- fdToHandle fdin hout <- fdToHandle fdout ph <- runProcess c args Nothing Nothing (Just hin) (Just hout) (Just hout) waitForProcess ph >>= print ------------------- Thanks Ian

2 2

RE: [Haskell] combining IntMaps
by Scherrer, Chad 28 Jul '05

28 Jul '05

Ok, it looks like I have some more reading to do. Do you know where I can find a description of the Hedge algorithm? Also, I'm pretty new here - these conversations eventually need to get moved to haskell-cafe, right? Is there any concrete guidance regarding when that should happen? The distinction between the two lists is still vague to me. -Chad -----Original Message----- From: Adrian Hey [mailto:ahey@iee.org] Sent: Wednesday, July 27, 2005 12:04 AM To: Scherrer, Chad Cc: haskell(a)haskell.org Subject: Re: [Haskell] combining IntMaps Hello, On Tuesday 26 Jul 2005 7:58 pm, Scherrer, Chad wrote: > Thanks! It's interesting the way your AVL tree library is set up -- > there seems to be a much broader degree of functionality than that > provided by Data.Set. But I'm trying to see, is there a significant > difference in the fundamental data structure. Well Data.Set is based on a different balanced tree type (weight balanced trees), similar to those used in the Adams paper. I'm also quite sceptical about the Hedge algorithm, so the AVL library doesn't use it. It uses divide and conquer, but not quite as Adams describes it. But IMO the biggest problem with Data.Set is the inflexible API. For example.. >From Data.Set: union :: Ord a => Set a -> Set a -> Set a intersect :: Ord a => Set a -> Set a -> Set a >From Data.Tree.AVL: genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c Of course there's no reason why similar functions could not be provided by Data.Set, but they're not there at present. > or is the main point that > the additional functionality could not have otherwise been provided in > an efficient way without going into the guts of Data.Set? Yes. This why producing useable libraries like this is so difficult. There's plenty of reasonable things you just can't do efficiently with Data.Set. Same is probably true of Data.Tree.AVL of course, but I'm trying to make it more complete all the time. Anyway, please try out AVL and let me know if there's anything more missing. Regards -- Adrian Hey

2 1