June 2002 - Haskell - Haskell.org

trees with pointers to parents & memory gobbling
by Hal Daume III 15 Jun '02

15 Jun '02

Hi all, I have a datatype which (simplified) looks like: data FBTree a = FBLeaf (Maybe (FBTree a)) a | FBBranch (Maybe (FBTree a)) (FBTree a) (FBTree a) is basically a tree with Maybe a parent node. however, unlike the nice non-haskell equivalent, they tend to eat up memory as you traverse them. for instance, given the conversion functions and helper functions: data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Eq, Show) data FBTree a = FBLeaf (Maybe (FBTree a)) a | FBBranch (Maybe (FBTree a)) (FBTree a) (FBTree a) instance Eq a => Eq (FBTree a) where a == b = unFBTree a == unFBTree b instance Show a => Show (FBTree a) where showsPrec i = showsPrec i . unFBTree mkFBTree = mkFBTree' Nothing where mkFBTree' par (Leaf a) = FBLeaf par a mkFBTree' par (Branch l r) = this where this = FBBranch par (mkFBTree' (Just this) l) (mkFBTree' (Just this) r) unFBTree (FBLeaf _ a) = Leaf a unFBTree (FBBranch _ l r) = Branch (unFBTree l) (unFBTree r) findRoot (FBLeaf (Just par) _) = findRoot par findRoot (FBBranch (Just par) _ _) = findRoot par findRoot t = t findLeftMostChild (FBBranch _ l _) = findLeftMostChild l findLeftMostChild t = t if we just walk up and down a tree a bunch of time, heap profiling reports huge amounts of memory usage. witness: tree = Branch (Branch (Branch (Branch (Branch (Leaf 'h') (Branch (Leaf 'a') (Leaf 's'))) (Leaf 'k')) (Branch (Leaf 'e') (Leaf 'l'))) (Leaf 'l')) (Leaf '!') fbtree = mkFBTree tree main = print $ last $ take 100000 $ iterate (findLeftMostChild . findRoot) fbtree even if i put an appropriate call to seq in the iteration, i still get lots of memory eaten up, can someone say how i can fix this? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

Summer School on Generic Programming, Oxford, UK
by Roland Backhouse 14 Jun '02

14 Jun '02

Summer School and Workshop on Generic Programming St Anne's College, Oxford, UK 26th to 30th August 2002 In conjunction with Summer School and Workshop on Advanced Functional Programming This school is a successor to the Summer School and Workshop on Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, held in Oxford in April 2000 and with lecture notes shortly to appear as LNCS 2297. For this school we have recruited an excellent group of lecturers on generic programming, that is, the construction of programs that work on different datatypes and yet may exploit the structure of that data. ************ Lecturers ************ * Roland Backhouse (University of Nottingham): A Generic Theory of Datatypes * Peter Buneman (University of Edinburgh): Semi-Structured Data * Roy Crole (University of Leicester): Categories and Types * Jose Luiz Fiadeiro (University of Lisbon and ATX Software): Theory and Practice of Software Architecture * Johan Jeuring (University of Utrecht): Generic Haskell * Martin Odersky (Ecole Polytechnique Federale de Lausanne): Object-Oriented and Functional Approaches to Compositional Programming ************ Deadlines ************ For registration: 12th July 2002 ************ Organizers ************ Roland Backhouse (University of Nottingham) Jeremy Gibbons (University of Oxford) ************ Further information ************ Web: http://www.comlab.ox.ac.uk/oucl/research/areas/ap/ssgp/info.html PDF poster: http://www.comlab.ox.ac.uk/oucl/research/areas/ap/ssgp/ssgp-poster.pdf Email: ssgp-info(a)comlab.ox.ac.uk Post: SSGP, c/o Jane Ellory, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom. Fax: +44 1865 273839; mark "fao SSGP (Jane Ellory)"

1 0

FW: Haskell accumulator
by Dominic Cooney 14 Jun '02

14 Jun '02

Paul Graham is collecting canonical accumulator generators at http://www.paulgraham.com/accgen.html , and has Dylan, E, JavaScript, various dialects Lisp, Lua, Rebol, Ruby, Perl, Python and Smalltalk. Could the serious Haskellers comment on this attempt of mine? foo n = do n' <- newIORef n return (\i -> do { modifyIORef n' (i+); readIORef n' }) This is all related to arguments about the benefits of succinctness and expressivity in programming languages. Dominic Cooney -----Original Message----- From: Paul Graham [mailto:pg@archub.org] Sent: Thursday, 13 June 2002 11:17 PM To: dominic(a)dcooney.com Subject: Re: Haskell accumulator Would this (if the type signature is unnecc) then be the canonical def in Haskell? foo n = do n' <- newIORef n return (\i -> do { modifyIORef n' (i+); readIORef n' }) --Dominic Cooney wrote: > This is a multi-part message in MIME format. > > ------=_NextPart_000_0001_01C212A8.F2F6A010 > Content-Type: text/plain; > charset="us-ascii" > Content-Transfer-Encoding: 7bit > > If you are still collecting these Revenge of the Nerds accumulators, > here it is in literate Haskell: > > > mkAccum :: (Num a) => a -> IO (a -> IO a) > > mkAccum n = do > > n' <- newIORef n > > return (\i -> do { modifyIORef n' (i+); readIORef n' }) > > There are a couple of interesting things here; firstly the (Num a) => is > an example of Haskell's type classes. > > The second is the 'IO' written everywhere. Haskell is pure, and IO is > the library-sanctioned state monad. Thus mkAccum and the accumulator > itself evaluate to "IO things" since they involve mutable state. > > The only other interesting thing about the type signature is that it is > completely unnecessary. The compiler infers the most general type. The > programmer can write explicit type signatures to narrow the type of a > function, or (more commonly) have the compiler provide a sanity check. > > 'Return' is unusual too-- it wraps things in the IO monad. Ordinarily it > is not required, e.g. > > > incr n = \x -> n + x > > Although this could simply be written as a partial application, like: > > > incr n = (+) n > > A whole test program is attached re: the accumulator. > > On another note, I am eagerly awaiting the arrival of ANSI Common Lisp > from Amazon. I may be converted yet. > > Dominic Cooney > > > ------=_NextPart_000_0001_01C212A8.F2F6A010 > Content-Type: application/octet-stream; > name="accum.lhs" > Content-Transfer-Encoding: 7bit > Content-Disposition: attachment; > filename="accum.lhs" > > This can be built with: > > ghc -fglasgow-exts -package lang --make accum.lhs -o accum > > GHC is available from http://www.haskell.org/ghc . > > > > module Main (main) where > > Haskell is pure-- the state of the world is in the IO monad. Hence > the accumulator requires these imports. > > > import IOExts (IORef, newIORef, readIORef, modifyIORef) > > > The accumulator. > > > mkAccum :: (Num a) => a -> IO (a -> IO a) > > mkAccum n = do > > n' <- newIORef n > > return (\i -> do { modifyIORef n' (i+); readIORef n' }) > > > Small test program. > > > main :: IO () > > main = do > > acc <- mkAccum 42 > > x <- acc 1 > > put x > > x <- acc 2 > > put x > > > Put is a small function that prints something. > > > put :: (Show a) => a -> IO () > > put = putStrLn.show > ------=_NextPart_000_0001_01C212A8.F2F6A010-- >

5 4

TERMGRAPH 2002: Extended submission deadline
by Detlef Plump 14 Jun '02

14 Jun '02

Dear Colleagues, Due to request the submission deadline for TERMGRAPH 2002 - The International Workshop on Term Graph Rewriting - has been extended to June 20, 2002. The Call for Papers can be found at: http://www.cs.york.ac.uk/~det/Termgraph_2002/cfp.html With best regards, Detlef Plump

1 0

Call for Participation: 7th ERCIM FMICS (Malaga, Spain) July 12-13, 2002
by Hubert Garavel 14 Jun '02

14 Jun '02

****************************************************************************** * * CALL FOR PARTICIPATION * * 7th International Workshop on Formal Methods for Industrial Critical Systems * (FMICS 02) * * University of Málaga (Spain) * July 12-13, 2002 * Colocated with the 29th ICALP conference * * http://www.inrialpes.fr/vasy/fmics/workshop-7 * ****************************************************************************** *** SCOPE OF THE WORKSHOP *** The aim of the FMICS workshops is to provide a forum for researchers who are interested in the development and application of formal methods in industry. In particular, these workshops should bring together scientists who are active in the area of formal methods and interested in exchanging their experiences in the industrial usage of these methods. They also aim at the promotion of research and development for the improvement of formal methods and tools for industrial applications. *** INVITED SPEAKERS *** Andrew Gordon (Microsoft Research Cambridge, UK) Andreas Podelski Max-Planck Institut für Informatik, Germany) Wang Yi (Uppsala University, Sweden) *** PROGRAMME *** ------------------------ FRIDAY 12 July 2002 --------------------------------- INVITED PRESENTATION Andreas Podelski (Max-Planck Institut für Informatik, Germany) Abstraction for Software Model-Checking SESSION - ABSTRACTION AND MODEL-CHECKING - Chair: H. Garavel (INRIA, France) M. Bourahla (Univ. of Biskra, Algeria), M. Benmohamed (Univ. of Constantine, Algeria) Predicate Abstraction and Refinement for Model Checking VHDL State Machines M. del Mar Gallardo, J. Martinez, P. Merino, E. Pimentel (Univ. of Málaga, Spain) A Tool for Abstraction in Model Checking SESSION - TESTING - Chair: R. Cleaveland (SUNY, New York, USA) D. Lugato, C. Bigot, Y. Valot (CEA Saclay, France) Validation and Automatic Test Generation on UML Models: the AGATHA approach J.C. Burguillo, M. Llamas, M.J. Fernández (Univ. of Vigo, Spain), T. Robles (Polytechnical Univ. of Madrid, Spain) Heuristic-Driven Techniques for Testing Distributed Systems B. Steffen (Univ. of Dortmund, Germany), T. Margaria (METAFrame, Germany), O.Niese (Univ. of Dortmund, Germany) Scalable System-level CTI Testing through Lightweight Coarse-grained Coordination INVITED PRESENTATION Andrew D. Gordon (Microsoft Research, Cambridge, UK) Authenticity Types for Cryptographic Protocols SESSION - INDUSTRIAL CASE STUDIES I - Chair: H. Hermanns (Univ. of Twente, NL) N. Lopez, M. Simonot, V. Donzeau-Gouge (CNAM, Paris, France) A Methodological Process for the Design of a Large System: Two Industrial Case-Studies C. Daws (CWI, Amsterdam, NL), M. Kwiatkowska, G. Norman (Univ. of Birmingham, UK) Automatic Verification of the IEEE-1394 Root Contention Protocol with KRONOS and PRISM TOOL DEMOS WORKSHOP BANQUET ----------------------- SATURDAY 12 July 2002 ------------------------------- INVITED PRESENTATION Wang Yi (Uppsala Univ., Sweden) Synthesis of Verified Real Time Software SESSION - INDUSTRIAL CASE STUDIES II - Chair: W. Fokkink (CWI, Amsterdam, NL) V. Valero, F.L. Pelayo, F. Cuartero, D. Cazorla (Univ. of Castilla, Spain) Specification and Analysis of the MPEG-2 Video Encoder with Timed-Arc Petri Nets S. Boldo, M. Daumas (Ecole Normale Supérieure de Lyon, France) Properties of the Subtraction Valid for any Floating Point System SESSION - MODEL CHECKING Chair: S. Gnesi (IEI-CNR, Pisa, Italy) X. Thirioux (IRIT-LIMA, Toulouse, France) Simple and Efficient Translation from LTL Formulas to Buchi Automata A. Biere, C. Artho, V. Schuppan (ETH Zürich, Switzerland) Liveness Checking as Safety Checking H. Hansen (Tempere Univ. of Technology, Finland), W. Penczek (Institute of Computer Science, Warsaw, Poland), A. Valmari (Tempere Univ. of Technology) Stuttering-Insensitive Automata for On-the-Fly Detection of Livelock Properties A.Valmari, H. Virtanen, A. Puhakka (Tempere Univ. of Technology, Finland) Context-Sensitive Visibility FMICS WORKING GROUP MEETING ----------------------------------------------------------------------------- *** REGISTRATION **** The registration procedure is described on the FMICS 02 web site http://www.inrialpes.fr/vasy/fmics/workshop-7 which also provides traveling and accomodation information. *** ORGANIZATION *** FMICS 02 Programme Committee Chairs H. Garavel (INRIA Rhone-Alpes, France) R. Cleaveland (SUNY, New York, USA) FMICS 02 Local Organizing Committee (University of Málaga) M. del Mar Gallardo P. López J. Martínez P. Merino (local organization chair) _____________________________________________________________________________

1 0

tables
by Peter Padawitz 13 Jun '02

13 Jun '02

Have Parnas' tabular expressions and algorithms ever been implemented in Haskell? Would anyone consider this a reasonable project? Peter --- Prof. Dr. Peter Padawitz Informatik 5 University of Dortmund D-44221 Dortmund Germany phone +49-231-755-5108 fax +49-231-755-4851 or -5802 secretary +49-231-755-5801 email peter.padawitz(a)udo.edu internet http://ls5.cs.uni-dortmund.de/~peter "Computer science is no more about computers than astronomy is about telescopes." -Dijkstra

2 1

Say�n haskell ,
by abdyesilkart.com 13 Jun '02

13 Jun '02

1 0

Binary question
by alexey_rod 12 Jun '02

12 Jun '02

Hi! I am using the ghc compiler for my final project and i am having some problems. I need some amount of serialization for my project so i decided to use drift to generate binary instances. I downloaded a port of the binary class for ghc but i am afraid it is outdated and probably not working correctly. My first question would be if someone has a working version of binary for ghc 5.02.2. In the meantime i have a temporary version of binary but its performance is not what i would like. Let me paste some of it class Binary a where put :: WCarrier -> a -> IO () get :: RCarrier -> IO a data RCarrier = RCarrier {handle::Handle ,byte::IORef Integer ,remb::IORef Int ,temp::IORef Integer} getBits :: RCarrier -> Int -> IO Integer getBits c w = if w == 0 then do x <- readIORef . temp $ c writeIORef (temp c) 0 return x else do r <- readIORef . remb $ c n <- readIORef . byte $ c t <- readIORef . temp $ c if w <= r then do let n' = n `shiftL` w .&. 255 r' = r - w t' = t `shiftL` w + n `shiftR` (8 - w) writeIORef (remb c) $! r' writeIORef (byte c) $! n' writeIORef (temp c) 0 return t' else do let w' = w - r t' = t `shiftL` r + n `shiftR` (8 - r) b <- hGetChar . handle $ c writeIORef (byte c) $! (toInteger (ord b)) writeIORef (remb c) 8 writeIORef (temp c) $! t' getBits c w' data WCarrier = WCarrier {whandle::Handle ,wbyte::IORef Integer ,wremb::IORef Int} ones n = (bit n) - 1 putBits :: WCarrier -> Int -> Integer -> IO () putBits (WCarrier ch cb cr) w n = f w n where f w n = if w == 0 then return () else do b <- readIORef cb r <- readIORef cr if w < r then do let b' = b `shiftL` w + n r' = r - w writeIORef cb $! b' writeIORef cr $! r' else do let n' = ones w' .&. n b' = b `shiftL` r + (n `shiftR` w' .&. ones r) w' = w - r hPutChar ch $! (chr (fromInteger b')) writeIORef cb 0 writeIORef cr 8 n' `seq` b' `seq` f w' n' My second question is how to optimize this piece of code. I suppose that the main performance bottleneck is the use of hPutChar. I did some profiling but some guidance will be really helpful. Regards, Alexey ------------------------------------- Comparte e interactua con personas de tus mismos intereses en: http://www.comunidadesweb.com

2 1

TIP'02: Call for Participation
by Peter Thiemann 12 Jun '02

12 Jun '02

[ATTENTION: date changed!] Call for Participation Workshop on Types in Programming (TIP'02) Dagstuhl, Germany, July 8, 2002 Colocated with MPC'02 http://www.informatik.uni-freiburg.de/~thiemann/tip02/ Modern programming languages rely on type systems with static type checking to detect common errors at compile time. While the benefits of statically checked type systems have long been recognized, there are some areas where the type systems of modern programming languages are not expressive enough. Some interesting programs will always be rejected, despite their semantical soundness. There are several remedies to this situation, ranging from dependent types (where types may contain values) through intersection types to types with modalities. These systems are well-investigated from a theoretical point of view by logicians and type theorists. However, the impact of these developments on practical programming has been small, partly because they are trading simplicity against expressivity. The objective of the workshop is to make researchers in programming languages aware of new developments and research directions on the theory side while at the same time pointing out problems arising in practical uses to theorists. Technical topics include, but are not limited to: * Type systems in all variants: polymorphic, dependent, intersection, modal, linear. * Annotated type systems. * Low-level type systems. * Advanced uses and applications. Workshop Program: Monday, July 8, 2002 10:40 Welcome 10:45 Regular Expression Types for Strings in a Text Processing Language, Naoshi Tabuchi, Eijiro Sumii, and Akinori Yonezawa (University of Tokyo, Japan) 11:15 Syntactic Type Soundness for HM(X), Francois Pottier (INRIA Rocquencourt, France). Christian Skalka (Johns Hopkins University, USA) 11:45 Set Types and Applications, Christian Skalka and Scott Smith (Johns Hopkins University, USA) 12:15 Lunch 14:00 Break [Tour de France] 16:00 Rank 2 Types for Term Graph Rewriting, Steffen van Bakel (Imperial College, UK) 16:30 Using kinds to type partially-polymorphic methods, Daniel Bonniot (INRIA, France) 17:00 The Impact of Linearity Information on the Performance of TyCO, Francisco Martins (University of Azores, Portugal). Luis Lopes (University of Porto, Portugal). Vasco T. Vasconcelos (University of Lisbon, Portugal) 17:30 Compatibility Checking with Typed Autonomous Agents, Michael Zapf (Fraunhofer Gesellschaft, Germany) 18:00 Dinner Program Committee: Gilles Barthe, INRIA Sophia-Antipolis, France [co-chair] Jacques Garrigue, Kyoto University, Japan Eugenio Moggi, University of Genova, Italy Zhong Shao, Yale University, USA Peter Thiemann, Universität Freiburg, Germany [co-chair] Joe Wells, Heriot-Watt University, Edinburgh, Scotland

1 0

Re: ANNOUNCE: hIDE version 0.1346269
by Krasimir Angelov 12 Jun '02

12 Jun '02

Hello, Jonas Is there any chance to run the hIDE under Windows? __________________________________________________ Do You Yahoo!? Yahoo! - Official partner of 2002 FIFA World Cup http://fifaworldcup.yahoo.com

3 2