- Haskell-Cafe - Haskell.org

Performance and STUArrays
by Dominic Steinitz 23 Apr '07

23 Apr '07

I've been playing around some more trying improve the performance of the SHA1 implmentation in the crypto library. I've isolated one of the functions and implemented it using a) unfold and b) STUArray The STUArray implementation is about twice as fast but I was expecting an order of magnitude improvement given I thought I would have been allocating 16 x 80 new 32 bit words with unfold but nothing with the STUArray. Should I have been disappointed? dom@heisenberg:~/sha12> time ./arrTest 17 STUArray > /dev/null real 0m11.102s user 0m9.129s sys 0m0.112s dom@heisenberg:~/sha12> time ./arrTest 17 Unfold > /dev/null real 0m18.381s user 0m16.361s sys 0m0.212s Dominic. import Data.Bits import Data.List import Data.Word import Control.Monad.ST import Data.Array.ST import System import System.IO data Word160 = Word160 !Word32 !Word32 !Word32 !Word32 !Word32 deriving (Eq, Show) ss :: Word160 ss = Word160 0x67452301 0xefcdab89 0x98badcfe 0x10325476 0xc3d2e1f0 test :: [Word32] test = [0x61626380, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000018] tests :: Int -> [[Word32]] tests n = map (\n -> n:[0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x18]) [1..2^n] rotL :: Bits b => Int -> b -> b rotL = flip rotateL v1 :: a -> [Word32] -> [Word32] v1 ss xs = take 80 (n xs) where h [w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15] = Just (w0,[w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15, (rotL 1 (w0 `xor` w2 `xor` w8 `xor` w13))]) n = unfoldr h v2 ss xs = vs where us = do w <- newArray (0,79) 0 :: ST s (STUArray s Int Word32) let initLoop 15 = writeArray w 15 (xs!!15) initLoop n = do writeArray w n (xs!!n) initLoop (n+1) mainLoop 79 = nextW 79 mainLoop n = do nextW n mainLoop (n+1) nextW n = do wm16 <- readArray w (n-16) wm14 <- readArray w (n-14) wm8 <- readArray w (n-8) wm3 <- readArray w (n-3) writeArray w n (rotL 1 (wm3 `xor` wm8 `xor` wm14 `xor` wm16)) initLoop 0 mainLoop 16 getElems w vs = runST us test1 n = map (v1 ss) (tests n) test2 n = map (v2 ss) (tests n) data TestType = Unfold | STUArray deriving (Eq, Read, Show) main = do progName <- getProgName args <- getArgs if length args /= 2 then putStrLn ("Usage: " ++ progName ++ " <testSize> <testType>") else do let n = read (args!!0) t = read (args!!1) if t == Unfold then putStrLn (show (test1 n)) else putStrLn (show (test2 n))

3 2

Creating QuickCheck properties
by Joel Reymont 23 Apr '07

23 Apr '07

Folks, I have code like this that I want to test with QuickCheck but I'm having trouble imagining how I would wrap it up in a property. Do I make sure that id, subs, back are always morphed properly or do I leave that to separate properties for their respective types? Do I then ensure that array types are always unwrapped (see getType below), that a "series" variable is always declared, code added and a series reference returned? Last but not least, is monadic testing part of Test.QuickCheck.*? Thanks, Joel type Core a = State CoreUnit a data CoreUnit = Core { coreSym :: Integer -- starting # for gensym , coreVars :: M.Map String VarDecl , coreCode :: M.Map Integer [Statement] } deriving (Show, Eq) morphHistArrayAccess :: VarIdent -> Subscript -> BackRef -> C.Core C.Expr morphHistArrayAccess id subs back = do id' <- morph id subs' <- morph subs back' <- morph back (C.TyArray ty) <- getType id' s <- genSym "series" addVar s (C.TySeries ty) [] Nothing addCodeFront 1 [ C.AddToSeries (C.VarIdent s) (C.Var id' subs') ] return $ C.Series (C.VarIdent s) back' -- http://wagerlabs.com/

1 0

Gotta love Haskell
by Justin Bailey 23 Apr '07

23 Apr '07

My wife has been put in charge of scheduling lectors and ministers at our church, so of course she needs a Haskell program to do the schedules for her! While I've been working on it, I wrote something that I thought was a pretty cool trick. Each Mass requires a variety of different type and number of participants, so when defining the "Mass" data structure I put a function in which selects participants for that type of Mass from a given list: data MassTime = MassTime { ... selectParticipants :: (Participants -> Maybe Participants), -- Picks participants for this mass ... } Each mass has particular requirements. Notice the 'selectParticipants' function does not take a mass definition as an argument. Here's the trick I thought was neat. When creating the MassTime value, I capture it in a closure and bind it to the selector function, as below: makeMass :: Day -> MassTime makeMass day = mass where -- Use trick here to capture mass defined and pass to our selection function. mass = MassTime ... (weekendMassSelector mass) ... 'weekendMassSelector' is defined elsewhere, and basically knows how to count up the right number of participants based on the mass definition given. It's signature is: weekendMassSelector :: MassTime -> Participants -> Maybe Participants So weekendMassSelector gets the MassTime value it needs, before it is even constructed. Partial evaluation then gives a function with the (Participants -> Maybe Participants) signature required by the data constructor. I love Haskell - this just seems too cool. Since I really doubt this is something new - is this a technique that's commonly used? Does it have a name? It looks a lot like passing a "this" argument to a function - have I re-invented OOP encapsulation? :) Justin

2 1

newbie question on ordering
by Nikolay Metchev 23 Apr '07

23 Apr '07

Hello guys, I have decided to try and get back into Haskell recently. I have used it in the past but have forgotten large chunks. I am trying to express the logic of a particular card game. For this purpose I need to be able to order cards in various orders. At first I thought that the Ord class was my answer but I found it very verbose. Below is my best attempt so far but I can't help but feel it too is verbose and that there must be a better way of comparing cards in different orders. data Face = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King deriving (Enum, Show, Eq) data Suit = Clubs | Diamonds | Hearts | Spades deriving (Show, Enum, Eq) type Card = (Face, Suit) listComparator :: (Eq a) => [a] -> a -> a -> Ordering listComparator xs a b = compare x y where x = elemIndex a xs y = elemIndex b xs sequentialBonusFaceOrder :: [Face] sequentialBonusFaceOrder = [Seven, Eight, Nine, Ten, Jack, Queen, King, Ace] fourOfAKindBonusFaceOrder :: [Face] fourOfAKindBonusFaceOrder = [Queen, King, Ten, Ace, Nine, Jack] sequentialBonusFaceComparator :: Face -> Face -> Ordering sequentialBonusFaceComparator = listComparator sequentialBonusFaceOrder fourOfAKindBonusFaceComparator :: Face -> Face -> Ordering fourOfAKindBonusFaceComparator = listComparator fourOfAKindBonusFaceOrder The problem with this approach is that if you want to compare you to write things of the following nature: fourOfAKindBonusFaceComparator f1 f2 == GT this isn't very clear especially if you want "<=" you have to do fourOfAKindBonusFaceComparator f1 f2 /= GT Any suggestions would be nice.

3 2

question about Data.Binary and Double instance
by David Roundy 22 Apr '07

22 Apr '07

Hi all, I'm wondering what exactly inspired the decode/encodeFloat implementation for Data.Binary? It seems to me like it'd be much better to use a standard format like IEEE, which would also be much more efficient, since as far as I know, on every implementation a Double and a CDouble are identical. Are there any suggestions how I could use Data.Binary to actually read a binary file full of Doubles? Should I just use the Array interface, and forget laziness and hopes of handling different-endian machines? Or is there some way to reasonably do this using Data.Binary? -- David Roundy Department of Physics Oregon State University

6 15

ANNOUNCE: xmonad 0.1
by Spencer Janssen 22 Apr '07

22 Apr '07

The xmonad dev team is pleased to announce the inaugural release of: xmonad: a tiling window manager http://xmonad.org Xmonad is a minimalist tiling window manager for X, written in Haskell. Windows are managed using automatic layout algorithms, which can be dynamically reconfigured. At any time windows are arranged so as to maximise the use of screen real estate. All features of the window manager are accessible purely from the keyboard: a mouse is entirely optional. Xmonad is configured in Haskell, and custom layout algorithms may be implemented by the user in config files. A principle of Xmonad is predictability: the user should know in advance precisely the window arrangement that will result from any action. By default xmonad provides three layout algorithms: tall, wide and fullscreen. In tall or wide mode, windows are tiled and arranged to prevent overlap and maximise screen use. Sets of windows are grouped together on virtual screens, and each screen retains its own layout, which may be reconfigured dynamically. Multiple physical monitors are supported via Xinerama, allowing simultaneous display of a number of screens. By utilising the expressivity of a modern functional language with a rich static type system, Xmonad provides a complete, featureful window manager in less than 500 lines of code, with an emphasis on correctness and robustness. Internal properties of the window manager are checked using a combination of static guarantees provided by the type system, and type-based automated testing. A benefit of this is that the code is simple to understand, and easy to modify. More information, screenshots, documentation and community resources are available from: http://xmonad.org Xmonad is available from hackage, and via darcs. Happy hacking! The Xmonad Team: Spencer Janssen Don Stewart Jason Creigh

1 0

Lessons from memory leak in streaming parser
by Oren Ben-Kiki 21 Apr '07

21 Apr '07

First, let me thank all the people who responded to my issue, it was very helpful. I would have responded earlier but I was on a business trip and out of contact for the last week. On the bright side I used the time to re-work my implementation. Instead of relying on Haskell's lazy evaluation, elegant as it may be, I changed it to use a continuation passing style. Every invocation of the parser returns a few tokens and a parser for the rest of the input. Interestingly, this approach maps well to non-lazy languages - basically anything that supports closures - unlike the original method that relied on lazy evaluation. So in principle I can now convert the Haskell code to Scheme, Ruby, or even JavaScript. At any rate, once I have done that, things started to fall into place. I still had minor leaks, but the results of profiling were actually proving useful for a change. I needed to turn off lazy evaluation in several key places (almost all record fields are now strict, and a 'seq' was needed in one crucial location). The result is a parser that can handle anything you throw at it with constant (reasonably low) memory usage. It is dog-slow (about 8k/sec, or twice that if compiling with -O2) but I was expecting that. So, lesson learned - lazy evaluation in Haskell is a very nice feature, but extremely difficult to debug, profile and control. Using continuations may be less elegant at places, but is much more practical. You can see the final result in version 0.3 of the YamlReference package I just uploaded to the Cabal database. This is intended to be an "executable version" of the YAML specification (the BNF file, which is actually Haskell code, is almost exactly the list of spec BNF productions). Thanks again for all the help, Oren Ben-Kiki

1 0

Installation of hs-plugins
by Philipp Volgger 21 Apr '07

21 Apr '07

Hello everybody, could somebody please tell me how hs-plugins has to be installed. I tried it with hs-plguin 1.0rc1 and I was unable to build it. I did runhaskell Setup.lhs configure runhaskell Setup.lhs build (Crash without any information) I tried it wiht GHC 6.4, 6.4.1 and 6.6. I am using Windows XP with SP2.

2 2

anyone interested in developing a Language.C library?
by Duncan Coutts 21 Apr '07

21 Apr '07

Hi all, If anyone is interested in developing a Language.C library, I've just completed a full C parser which we're using in c2hs. It covers all of C99 and all of the GNU C extensions that I have found used in practise, including the __attribute__ annotations. It can successfully parse the whole Linux kernel and all of the C files in all the system packages on my Gentoo installation. It's implemented as an alex lexer and a happy parser. The happy grammar has one shift/reduce conflict for the dangling if/then/else issue (which could be hidden by using precedence but it's clearer not to). So if someone is interested in developing a more widely usable Language.C library, I think this would be a good place to start. There's plenty to do however: * The c2hs C AST is ok but probably not enough for a general purpose library. * The parser currently uses some other c2hs infrastructure which would need disentangling to pull the parser out (mostly identifiers and unique name supply management). * It does not record everything into the parse tree, eg __attribute__s are parsed but ignored. * It does no semantic analysis after parsing (though other bits of c2hs to a very little) * In at least one place the parser is deliberately too liberal (to avoid ambiguities) which would require simple extra checks after parsing to detect. * The lexical syntax has not been checked against the spec fully, it is probably over-liberal in some cases. * I've not done much performance work, the lexer has not been seriously tuned, it still lexes via a String. Having said that, the performance is not at all bad, on a 3Ghz box it does ~20k lines/sec. * The parser error messages are terrible (it might be interesting to try porting from happy to frown for this purpose) There's probably more stuff, but that's what I can think of right now. So if anyone is interested then let me know, I can give some pointers (hopefully the useful kind, not the void * kind). You can get the code from the c2hs darcs repo: darcs get --partial http://darcs.haskell.org/c2hs/ The C parser bits are under c2hs/c/ Duncan Licensing: It's not 100% clear. At the moment it's marked as GPL, but it's derived from several sources so we need to be careful about that. Personally I'm happy to use LGPL. It derives from c2hs obviously, which is GPL, though we could enquire about re-licencing, especially since there is very little of c2hs stuff used in it any more. It also derives partly from James A. Roskind's C grammar (in particular the grammar of declarations). His copyright license is fairly liberal but this need double-checking. It also derives from the C99 spec and I read the comments in the gcc C parser as a guide to GNU C's extensions to the C grammar (no code or comments were copied however). Testing: I tested it thus far by writing a little gcc wrapper script, so you can build any ordinary bit of C software using this wrapper and it'll call gcc with the same args but it'll also try and parse the input file. It reports into a log file. I've not tried the gcc C parser testsuite. This approach is probably good for other tests like trying to see if parsing and pretty printing can round-trip correctly; if not identical token streams (since parsing drops redundant brackets etc) checking if gcc produces identical .S/.o files. Something that c2hs needs is to calculate sizes of types and structure member offsets correctly. This is also something that could be tested in this style, by comparing on thousands of example .c files with what gcc thinks.

4 4

QuickCheck subsumes unit testing
by dons＠cse.unsw.edu.au 21 Apr '07

21 Apr '07

Just to walk the walk, and not just talk the talk, here's a quick unit testing 'diff' driver I hacked up for QuickCheck. When run, it 'diffs' (well, just prints ;-) the incorrect values from the unit test: $ runhaskell T.hs sort unit test : Falsifiable after 0 tests: - [1,2,3] + [1,3,2] >From a normal QC specification like: prop0 = (sort [3,2,1], [1,3,2]) main = mapM_ (\(s,a) -> printf "%-25s: " s >> a n) tests where n = 100 tests = [("sort unit test", mytest prop0)] The full driver code is attached. It is just proof of concept, but you can see how to extend it to be smarter/prettier. Note that we actually probably want to use SmallCheck here, to prevent bogus repetition of the test. (I.e. 500 tests all passed, for a unit test). Note also, the driver would need further extending, since we've changed the structure of the Testable values. Cheers, Don

2 1