September 2010 - Haskell-Cafe

ANN: BNFC-meta-0.1.0
by Jonas Almström Duregård 22 Sep '10

22 Sep '10

I'm pleased to announce BNFC-meta-0.1.0! BNFC-meta can take a quasi-quoted LBNF grammar (as used by the BNF Converter) representation of a language and generate (using Template Haskell) a number of wonderful tools for dealing with this language, including: * Abstract syntax types * Lexer * LALR Parser * Pretty-printer * Quasi-quoter Apart from the quasi-quoter, these are all features of the BNF Converter, but grammars can now be embedded directly into Haskell modules. Here's an example of a small subset of C: \begin{code} {-# LANGUAGE QuasiQuotes #-} module MiniLanguage where import Language.LBNF -- 'Compile' is a Template Haskell function, 'cf' is a QuasiQuoter. compile [$cf| antiquote "[" ":" ":]" ; Fun. Prog ::= Typ Ident "(" ")" "{" [Stm] "}" ; SDecl. Stm ::= Typ Ident ";" ; SAss. Stm ::= Ident "=" Expr ";" ; SIncr. Stm ::= Ident "++" ";" ; SWhile. Stm ::= "while" "(" Expr ")" "{" [Stm] "}" ; ELt. Expr0 ::= Expr1 "<" Expr1 ; EPlus. Expr1 ::= Expr1 "+" Expr2 ; ETimes. Expr2 ::= Expr2 "*" Expr3 ; EVar. Expr3 ::= Ident ; EInt. Expr3 ::= Integer ; []. [Stm] ::= ; (:). [Stm] ::= Stm [Stm] ; _. Stm ::= Stm ";" ; _. Expr ::= Expr0 ; _. Expr0 ::= Expr1 ; _. Expr1 ::= Expr2 ; _. Expr2 ::= Expr3 ; _. Expr3 ::= "(" Expr ")" ; TInt. Typ ::= "int" ; comment "/*" "*/" ; comment "//" ; |] \end{code} And here is a module that uses it: \begin{code} {-# LANGUAGE QuasiQuotes #-} import MiniLanguage import Language.LBNF(pp) -- overloaded pretty-printing function import Prelude hiding (exp) power :: Ident -> Integer -> Prog power var x = [$prog| // This quoter accepts C-style comments int myPower() { int tmp; tmp = 0; // Things in [: :] are anti-quoted Haskell expressions. [: repeatWhile (Ident "tmp") x mult :] } |] where -- [X:haskell:] means the anti-quoted expression represents non-terminal X, -- Used to resolve ambiguities (in this case between Ident/Expr/Integer). mult = [$stm| [:var:] = [Ident:var:] * [Ident:var:] ; |] -- Repeats a statement n times. (at least if variable var is 0... ) repeatWhile var n statement = [$stm| while ([Ident:var:] < [:n:]) { [Stm:statement:] [:var:] ++ ; }|] pr = power (Ident "n") 10 main = putStr $ pp pr \end{code} There are a few more examples in the source tarball. More documentation on these features will be supplied eventually :) Best regards, Jonas

1 0

ANNOUNCE: http-enumerator 0.0.0
by Michael Snoyman 22 Sep '10

22 Sep '10

Hi all, I'd like to announce the first release of http-enumerator[1], an HTTP client package with support for HTTPS connections. This release is very experimental; bug reports and API feedback are very welcome. In addition to providing built-in HTTPS support, this package also attempts to improve upon current offerings by offering a very simple API, being built on bytestrings by default, and using the enumerator package to allow efficient parsing of response bodies. I've also put up a blog post[2] giving some more motivation and future goals for those interested. Michael [1] http://hackage.haskell.org/package/http-enumerator [2] http://docs.yesodweb.com/blog/announcing-http-enumerator/

4 4

Cleaning up threads
by Mitar 22 Sep '10

22 Sep '10

Hi! I run multiple threads where I would like that exception from any of them (and main) propagate to others but at the same time that they can gracefully cleanup after themselves (even if this means not exiting). I have this code to try, but cleanup functions (stop) are interrupted. How can I improve this code so that this not happen? module Test where import Control.Concurrent import Control.Exception import Control.Monad thread :: String -> IO ThreadId thread name = do mainThread <- myThreadId forkIO $ handle (throwTo mainThread :: SomeException -> IO ()) $ -- I want that possible exception in start, stop or run is propagated to the main thread so that all other threads are cleaned up bracket_ start stop run where start = putStrLn $ name ++ " started" stop = forever $ putStrLn $ name ++ " stopped" -- I want that all threads have as much time as they need to cleanup after themselves (closing (IO) resources and similar), even if this means not dying run = forever $ threadDelay $ 10 * 1000 * 1000 run :: IO () run = do threadDelay $ 1000 * 1000 fail "exit" main :: IO () main = do bracket (thread "foo") killThread $ \_ -> bracket (thread "bar") killThread $ \_ -> bracket (thread "baz") killThread (\_ -> run) Mitar

11 25

Cabal-install prefix
by N. Raghavendra 22 Sep '10

22 Sep '10

I am new to Haskell, and am trying to install a package (scan) using cabal-install. I want it to install all files under the directory ${HOME}/nonvc, like in ~/nonvc/share and ~/nonvc/bin. So I specified install-dirs user -- prefix: /home/raghu/nonvc in ~/.cabal/config. But when I do `cabal install scan', it still installs the files in ~/.cabal/bin and ~/.cabal/share. How do I make cabal install these files in ~/nonvc? Thanks and regards, Raghavendra. -- N. Raghavendra <raghu(a)mri.ernet.in> | http://www.retrotexts.net/ Harish-Chandra Research Institute | http://www.mri.ernet.in/ See message headers for contact and OpenPGP information.

2 2

ANN: Copilot 0.22 -- A stream DSL for writing embedded C.
by Lee Pike 22 Sep '10

22 Sep '10

Announcing Copilot 0.22: Can you write a list in Haskell? Then you can write embedded C code using Copilot. Here's a Copilot program that computes the Fibonacci sequence (over Word 64s) and tests for even numbers: fib :: Streams fib = do "fib" .= [0,1] ++ var "fib" + (drop 1 $ varW64 "fib") "t" .= even (var "fib") where even :: Spec Word64 -> Spec Bool even w = w `mod` const 2 == const 0 Copilot contains an interpreter, a compiler, and uses a model-checker to check the correctness of your program. The compiler generates constant time and constant space C code via Tom Hawkin's Atom[1] (thanks Tom!). Copilot was originally developed to write embedded monitors for more complex systems, but it can be used to develop a variety of embedded code. HACKAGE: http://hackage.haskell.org/package/copilot WEBPAGE: http://leepike.github.com/Copilot/ (with more info). PICS/VIDEO of Copilot's maiden flight: http://picasaweb.google.com/105722675808588603973 A PAPER (PDF): http://www.cs.indiana.edu/~lepike/pub_pages/rv2010.html The Copilot Team * Maintainer: Lee Pike (leepike(a)galois.com) Galois, Inc. * Alwyn Goodloe, National Institute of Aerospace * Robin Morisset, École Normale Supérieure * Sebastian Niller, Technische Universität Ilmenau [1] http://hackage.haskell.org/package/atom

4 5

Ultra-newbie Question
by Christopher Tauss 21 Sep '10

21 Sep '10

Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]->Int->[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = ???? The issue is I do not see how you can store the last elements of the list. Thanks in advance. ctauss

17 24

asymmetric runtimes for symmetric trees
by Daniel Seidel 21 Sep '10

21 Sep '10

Hi, I'm having a tree data type data Tree a = Leaf a | Fork (Tree a) (Tree a) , a generator for the left-most path of the tree, taking the depth leftPath :: Int -> Tree Int leftPath d | d > 1 = Fork (leftPath (d-1)) (Leaf 1) | d == 1 = (Leaf 1) | otherwise = error "Can't make tree of depth <= 0." and the similar thing for a right-most path rightPath :: Int -> Tree Int rightPath d | d > 1 = Fork (Leaf 1) (rightPath (d-1)) | d == 1 = (Leaf 1) | otherwise = error "Can't make tree of depth <= 0." Now I measured how long it takes to build a huge tree via print $ sumLeafs $ leftPath 1000000 and print $ sumLeafs $ rightPath 1000000 as main functions where sumLeafs (Fork l r) = sumLeafs l + sumLeafs r sumLeafs (Leaf i) = i Compiling without optimisation and running with no extra runtime options, besides -K50M to make available enough stack, yields on my machine (measured via time) that for leftPath the runtime is 3.8s, for rightPath 2.9s. If I optimize with -O2 runtimes decrease to approx. 1s / 0.8s, meaning the difference is still there. Using the -sstderr runtime option shows that (also with the runtime option -H2.5G) garbage collection for the leftPath case takes always slightly longer than for the rightPath case. Can anyone explain why there is that difference? Cheers, Daniel. PS: Here the programs as one block: ---LeftPath.hs module Main where data Tree a = Leaf a | Fork (Tree a) (Tree a) leftPath :: Int -> Tree Int leftPath d | d > 1 = Fork (leftPath (d-1)) (Leaf 1) | d == 1 = (Leaf 1) | otherwise = error "Can't make tree of depth <= 0." sumLeafs (Fork l r) = sumLeafs l + sumLeafs r sumLeafs (Leaf i) = i main = print $ sumLeafs $ leftPath 1000000 ---RightPath.hs module Main where data Tree a = Leaf a | Fork (Tree a) (Tree a) rightPath :: Int -> Tree Int rightPath d | d > 1 = Fork (Leaf 1) (rightPath (d-1)) | d == 1 = (Leaf 1) | otherwise = error "Can't make tree of depth <= 0." sumLeafs (Fork l r) = sumLeafs l + sumLeafs r sumLeafs (Leaf i) = i main = print $ sumLeafs $ rightPath 1000000

2 2

Re: ANNOUNCE: GotoT-transformers version 1.0
by oleg＠okmij.org 21 Sep '10

21 Sep '10

Let us look at GoTo from several angles: (un)delimited continuations, exceptions and trampolines. Gregory Crosswhite wrote regarding the definition goto (ContT m) = ContT $ \_ -> m return > *HOWEVER*, if we replace main with > > main = runContT myComp (const $ putStrLn "I can't wait to print > this string!") > > Then the program will be eternally disappointed because it will never > actually get to print that string at the end [if goto had been used] > > it just seems to me like at that point the spirit of the > continuation monad is being violated since the final continuation is > never actually called. That isn't necessarily a big deal, but it is the > kind of behavior that could bite someone if they weren't aware or forgot > about it. Let us start by looking at the problem from the point of view of undelimited continuations. Although that is not my preferred one, it could be instructive. An undelimited continuation -- the kind that is typically associated with call/cc -- has no ``final continuation'' to run at the end. There is no end. The value produced by the undelimited continuation can never be used by the program itself, because by the time that value is produced the program shall be dead. It may help to think of the return value of an undelimited continuation as the value produced when a computer crashes or the universe ends. Therefore the type ContT from mtl or MonadLib is not a good model of undelimited continuations. Better is the following > data Falsum -- it doesn't exist > > type K m a = a -> m Falsum -- NOT a, or the continuation from a > > newtype ContT m a = ContT{unC:: K m a -> m Falsum} -- NOT NOT a > > > instance Monad m => Monad (ContT m) where > return x = ContT $ \k -> k x > m >>= f = ContT $ \k -> unC m (\v -> unC (f v) k) > > instance (Monad m, MonadIO m) => MonadIO (ContT m) where > liftIO m = ContT $ \k -> liftIO m >>= k > > callCC :: (K m a -> ContT m a) -> ContT m a > callCC f = ContT (\k -> unC (f k) k) Given such ContT, the original goto expression would not type: goto :: (Monad m) => ContT m () -> ContT m a goto (ContT m) = ContT $ \_ -> m return Couldn't match expected type `()' against inferred type `Falsum' If we drop the type annotation, the goto will type, but the argument computation will be assigned the type ContT m Falsum. There can be no non-divergent computation with that type. That typing failure points to the problem with the definition: the argument of goto was a ContT computation that expects a continuation. We supplied `return' -- assuming that was the `initial, or system' continuation. That is, we assumed that the corresponding runContT indeed supplied `return' as the initial continuation. If runContT supplied something else, we run into inconsistency. Thus the correct definition of goto, in the current approach, instead of guessing the continuation to abort it, should ask the user. We obtain the following definition > goto :: Monad m => K m () -> ContT m () -> ContT m a > goto k (ContT m) = ContT (\_ -> m k) We need a way to obtain the continuation to pass to goto. That's where callCC comes in handy: > myComp :: ContT IO () > myComp = callCC $ \k0 -> do > input <- liftIO $ putStrLn "Print something (y/n)?" >> getLine > unless ("y" `isPrefixOf` input) $ goto k0 exit > liftIO $ putStrLn "Something." > > input <- liftIO $ putStrLn "Print more (y/n)?" >> getLine > unless ("y" `isPrefixOf` input) $ goto k0 exit > liftIO $ putStrLn "More." > > where > exit = liftIO $ putStrLn "Ok, I'm exiting." A reader must have been wondering since five paragraphs ago about running ContT computations. Ideally, there should be no runContT -- as there is no runIO. Since we can't change the behavior of `main' or add a similarly distinguished `mainCont', we have to find a continuation to supply to our ContT computation -- the continuation from the present state till the end of the universe. That seems problematic. Fortunately, cheating is always an option: > data FinalExit = FinalExit deriving (Show, Typeable) > instance Exception FinalExit > > main :: IO () > main = do > handle (\FinalExit -> return ()) > (unC myComp (\() -> putStrLn "At the end" >> throw FinalExit) >> > error "unreachable") The string "At the end" is printed at every end, caused by goto or the normal termination. Although the program type-checks and runs with the expected behavior, it seems quite contrived. Our goto only skips a prefix of the current continuation, from the current point to some definite point in the program, marked by `handle' or runContT, etc. We don't make any essential use of undelimited continuations. In fact, I am yet to see any practical use for undelimited continuations. Delimited continuations are much more useful. The monad ContT of mtl or MonadLib is the monad for simple delimited continuations; runContT is the delimiter, and (\m -> lift $ runContT m return) is the reset. Our example makes a special use of delimited continuations: we capture the continuation from the current point till the main point, and throw it away. That pattern is called abort, and it undelies exceptions. We immediately obtain the following simplified implementation: > data GoTo = GoTo deriving (Show, Typeable) > instance Exception GoTo > > goto :: IO () -> IO a > goto m = m >> throw GoTo > > myComp :: IO () > myComp = do > input <- putStrLn "Print something (y/n)?" >> getLine > unless ("y" `isPrefixOf` input) $ goto exit > putStrLn "Something." > > input <- putStrLn "Print more (y/n)?" >> getLine > unless ("y" `isPrefixOf` input) $ goto exit > putStrLn "More." > > where > exit = putStrLn "Ok, I'm exiting." > > > main :: IO () > main = do > handle (\GoTo -> return ()) myComp > putStrLn "At the end" There is no longer any need in the ContT monad transformer: IO supports exceptions natively. The solution exhibits a well-known memory leak. Consider do x <- make_huge_value goto long_running_computation return x While long_running_computation keeps running, the value x is being referenced from the stack and cannot be garbage collected. There is a well-known solution to the problem: trampolining. We abort first and then run the goto computation. This leads us to the final solution: {-# LANGUAGE DeriveDataTypeable #-} module C2 where import Data.List import Control.Monad import Control.Exception import Data.Typeable data GoToIt = GoToIt (IO ()) deriving (Typeable) instance Show GoToIt where show _ = "Trampoline" instance Exception GoToIt goto :: IO () -> IO a goto m = throw (GoToIt m) myComp :: IO () myComp = do input <- putStrLn "Print something (y/n)?" >> getLine unless ("y" `isPrefixOf` input) $ goto exit putStrLn "Something." input <- putStrLn "Print more (y/n)?" >> getLine unless ("y" `isPrefixOf` input) $ goto exit putStrLn "More." where exit = putStrLn "Ok, I'm exiting." main :: IO () main = do handle_it myComp putStrLn "At the end" where handle_it m = handle (\(GoToIt m) -> handle_it m) m

1 0

[ANN] Crypto-API 0.1.0.0
by Thomas DuBuisson 20 Sep '10

20 Sep '10

Crypto-API is a project aimed at unifying algorithm developers and users by presenting a uniform typeclass interface to low level algorithms and providing generalized helper functions for the (slightly) higher-level interactions needed by crypto-users. The main features are typeclasses (hash, cipher, signing and RNG), block cipher modes, platform independent entropy/seed acquisition, padding, testing and benchmarking. This release represents a fleshing out of the testing infrastructure, addition of padding mechanisms, and a reduction in build dependencies. In particular, I want to encourage package maintainers of TwoFish, AES, and SHA* algorithms to use the included test infrastructure - examples can be found on the homepage. == Project Management == Homepage: http://trac.haskell.org/crypto-api/wiki Bug trac: http://trac.haskell.org/crypto-api/report/1 Repo: http://code.haskell.org/crypto-api/ == API Removals == * Test.ParseNistKATs doesn't use Parsec and has a barebones interface. * Crypto.Random does not export "AsRG" or "Splittable" (see change log, 'random' build dep removed) == API Additions == * class Signing p v | p -> v, v -> p where ... * instance Monad (Either GenError) where ... * cereal >= 0.2 && < 0.4 (was == 0.2.*) * Testing ** Tests are split from Test.Crypto ** SHA, HMAC tests are new and from NIST CAVP KATs ** AES CFB128 mode KATs ** TwoFish NIST KATs ** Cipher property tests included (enc . dec ~ id, and many mode specific tests) * Crypto.Padding is included with PKCS5 and ESP padding methods. * "blockSizeBytes" helper function is now included == Build Dependencies == While I've never had objections to dependencies (this is what cabal is for and removing unused code is what GHC+linkers are for), I feel this is a good minimum and hope others agree. Some potential users made noise about having both Binary and Cereal and just the number of deps in general. * deps removed: binary, parsec, random (and indirectly: time, old-locale) * deps remaining: base, tagged, bytestring, cereal, filepath, directory * indirect deps remaining: data-default, containers, arrays To reiterate, the only deps above a normal GHC baseline are tagged, cereal, and data-default. CHANGE LOG (since 0.0.0.2) * Add 'Signing' class. * Tests showing the strict and lazy Crypto.Modes functions are eq * Basic BlockCipher property tests (enc . dec ~ id) * Enable tests for CFB128 * Added ESP and PCKS5 padding * add a 'blockSizeBytes' helper * TwoFish KATs * Bump 'cereal' version bound to include 0.3 * instance Monad (Either GenError) -- that was an obvious oversight * Remove the 'binary' dep. (cereal makes more sense and can be leveraged in Binary.{Get,Put} routines). * Removed the 'parsec' dep, which was only needed for Test.* but not even that now. * Updated the CPP tests for Windows in System.Random.Crypto (still need a tester) * Fixed up the testing infrastructure. Algorithms now use separate modules (Test.SHA, Test.HMAC, Test.AES). more NIST KATs included: ~1000 SHA tests, hundreds of SHA HMAC tests. * Fixed ugly bug for HMACs using keys > blockSize (eep! Obvious interop problem, but there was no-less security in the hmac result) * Removes the 'random' dep and by extension removes indirect deps on time and old-locale. Random was only used to provide trivial lifting of a newtype wrapped CryptoRandomGen instances into the RandomGen class, which was of questionable sense in the first place. == TODO == * Improve benchmarking infrastructure ** Improved reporting ** Benchmark modes and other higher-level functions, but in a generic way ** Benchmark asymmetric algorithms * Optimize block cipher modes * Statistical RNG tests * Portability testing (Mac, Windows testing needed) Cheers, Thomas

1 0

Re: Ultra-newbie Question
by Henrique Becker 20 Sep '10

20 Sep '10

Why not? import Data.Number.Nat as N lastN :: Integral b => b -> [a] -> [a] lastN n xs = N.drop (N.length xs - n') xs where n' = N.toNat n Not import Prelude maybe make more clear. []'s Henrique Becker

2 3