- Haskell-Cafe - Haskell.org

Trouble with Cabal
by Scherrer, Chad 23 May '06

23 May '06

Thanks to all who responded about the benefits of using Cabal. After trying out Bulat's Streams library, I thought I would download ByteString (aka FPS) to compare the wc demos. To compile something using Streams, I need to use a -i flag (thanks Bulat). When I followed the README that comes with ByteString, I get this: % ./Setup.hs install Installing: /f/g/lib/fps-0.7 & /f/g/bin fps-0.7... *** Exception: /f: createDirectory: permission denied (Permission denied) I don't have root on this machine, and it's not obvious (to me) how to specify that everything should be installed locally. Any suggestions? Thanks, Chad Scherrer Computational Mathematics Group Pacific Northwest National Laboratory "Time flies like an arrow; fruit flies like a banana." -- Groucho Marx

3 5

QuickCheck Fun with Phantom Types
by Dominic Steinitz 22 May '06

22 May '06

I was doing Exercise 5 of Ralf's Fun with Phantom Types and naturally thought I'd check my solution with QuickCheck. The best I could was this. Is there something better? Can you somehow generate random types as well as random values in those types? Thanks, Dominic. PS the full source for my solution with tests is attached. prop_Idem t x = x == uncompress t (compress t x) instance Arbitrary Char where arbitrary = oneof (map return ['A'..'z']) class Reflect a where reflect :: Type a instance Reflect Int where reflect = RInt instance Reflect Char where reflect = RChar instance (Reflect a, Reflect b) => Reflect (a,b) where reflect = RPair reflect reflect instance Reflect a => Reflect [a] where reflect = RList reflect type Test1 = Int -> Bool type Test2 = (Int,Int) -> Bool type Test3 = String -> Bool type Test4 = (String,String) -> Bool main = do quickCheck ((prop_Idem reflect) :: Test1) quickCheck ((prop_Idem reflect) :: Test2) quickCheck ((prop_Idem reflect) :: Test3) quickCheck ((prop_Idem reflect) :: Test4)

1 1

Re: Writing an extensible interpreter
by Jonathan Tang 22 May '06

22 May '06

> Message: 2 > From: "David House" <dmhouse(a)gmail.com> > Subject: [Haskell-cafe] Writing an extensible interpreter > I'm in the process of writing an interpreter for the self-modifying > automaton languages SMATINY [1], designed by ihope (whose name some of > you may recognise from IRC). The current effort is online [2], but > it's at a rather early stage and there's a few modifications I'd like > to make to it. [snip] However, the remaining issue is step 1): how would the metacode handle > additional constructors to the Step ADT? Type classes won't work here: > the intepreter has a type of [Step] -> String. With type classes this > would have a type of something like Step a => [a] -> String, but by > the homogeneity of lists you'd only be able to have one type of step > in your program. > > You can get around the homogeneity of lists problem with existential types: http://www.haskell.org/hawiki/ExistentialTypes http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/evaluator2.ht… Another solution might be to eliminate the algebraic data type entirely and have the Parsec actions return a Smatiny action. Instead of dispatching on the constructor of Step, package up any information you need as a closure and make Step a type synonym for 'Smatiny ()' or 'Smatiny a' or whatever type you need. Then the interpreter main loop just executes the action returned by the parser. - Jonathan

1 0

Writing an extensible interpreter
by David House 22 May '06

22 May '06

Hi all. I'm in the process of writing an interpreter for the self-modifying automaton languages SMATINY [1], designed by ihope (whose name some of you may recognise from IRC). The current effort is online [2], but it's at a rather early stage and there's a few modifications I'd like to make to it. To begin with, extensibility is key. Such tiny languages are designed to be easily extendable, and I'd like my interpreter to follow suit. At the moment, adding a new command is as follows: 1) Add a new constructor for the Step type to represent your command. 2) Write a Parsec parser for your command in Smatiny.hs. 3) Add said parser to the 'inputs' list in Smatiny.hs. 4) Write a 'handler' for your command; a function in State that will take the appropriate action. This is a bit of an ordeal; I'd like new commands to be addable without touching Smatiny.hs, which will form the base of the interpreter. One solution I was thinking about was to write a new module for each command that exports a "parser" and "handler" function. A bit of metacode would read the Commands directory then import qualified all the modules it finds in there. Subsequently, it would call parseSmatiny (the parser; in Smatiny.hs) with all the parsers it found as an argument, then send the output of this into runSmatiny (the interpreter; also in Smatiny.hs). However, the remaining issue is step 1): how would the metacode handle additional constructors to the Step ADT? Type classes won't work here: the intepreter has a type of [Step] -> String. With type classes this would have a type of something like Step a => [a] -> String, but by the homogeneity of lists you'd only be able to have one type of step in your program. Thanks in advance for your input. Let me know if I didn't explain something too well; I have a tendancy toward brevity :) [1]: http://esoteric.voxelperfect.net/wiki/SMATINY [2]: http://esoteric.voxelperfect.net/files/smatiny/impl/smatiny.tar.gz -- -David House, dmhouse(a)gmail.com

2 1

parsing machine-generated natural text
by Evan Martin 22 May '06

22 May '06

For a toy project I want to parse the output of a program. The program runs on someone else's machine and mails me the results, so I only have access to the output it generates, Unfortunately, the output is intended to be human-readable, and this makes parsing it a bit of a pain. Here are some sample lines from its output: France: Army Marseilles SUPPORT Army Paris -> Burgundy. Russia: Fleet St Petersburg (south coast) -> Gulf of Bothnia. England: 4 Supply centers, 3 Units: Builds 1 unit. The next phase of 'dip' will be Movement for Fall of 1901. I've been using Parsec and it's felt rather complicated. For example, a "location" is a series of words and possibly parenthesis, except if the word is SUPPORT. And that "Supply centers" line ends up being code filled with stuff lie "char ':'; skipMany space". I actually have a separate parser that's Javascript with a bunch of regular expressions and it's far shorter than my Haskell one, which makes sense as munging this sort of text feels to me more like a regexp job than a careful parsing job. I'm considering writing a preprocessing stage in Ruby or Perl that munges those output lines into something a bit more "machine-readable", but before I did that I thought I'd ask here if anyone had any pointers, hints, or better ideas.

5 8

Re: [Haskell] installing streams library
by Chad Scherrer 20 May '06

20 May '06

Thanks Jared, but already tried those. I was able to download the Streams library, but I have know idea how to install it. On 5/19/06, Jared Updike <jupdike(a)gmail.com> wrote: > > I found this in an old post (gotta love GMail search): > > > You can find further information about the library at the > > page http://haskell.org/haskellwiki/Library/Streams and > > download it as http://freearc.narod.ru/Streams.tar.gz > > from a thread in February entitled: > > Streams: the extensible I/O library (Feb 21) > > Google site:haskell.org bulat extensible I/O library for the thread, etc. > > Hope that helps, > Jared. > > On 5/19/06, Chad Scherrer <chad.scherrer(a)gmail.com> wrote: > > It sounds like Bulat has gotten some impressive I/O speedups with his > > Streams library. I'd like to try this out, but I'm having some trouble > > installing it. I'm using GHC on Linux. > > > > My first attempt was looking around on this page: > > http://www.haskell.org/haskellwiki/Library/Streams > > > > There's a really nice description, but no signs of where to actually get > the > > library. Eventually (thanks to Google) I tracked down this message: > > http://article.gmane.org/gmane.comp.lang.haskell.general/13625 > > > > From here I was able to download it, but there's no information > regarding > > how this needs to be set up. There are directories "Data", "Examples", > and > > "System", which I assume are supposed to be plugged into the > hierarchical > > module structure, but how do I do that? I thought this might have > something > > to do with Cabal (I've not yet used that), but the Cabal manual talks > about > > a .cabal file, which doesn't exist here. > > > > Does this follow some standard approach that I'm not familiar with? > Where > > should I look to learn more? > > > > Thanks, > > -- > > > > Chad Scherrer > > > > "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx > > _______________________________________________ > > Haskell mailing list > > Haskell(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell > > > > > > > > > -- > http://www.updike.org/~jared/ > reverse ")-:" > -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Troubles with FFI
by Matthew Bromberg 20 May '06

20 May '06

I am a newcomer to Haskell and I'm offering my perspective on the troubles I endured trying to make Haskell interface to some simple C programs. It is my hope, that by documenting this, someone else will benefit from my mistakes and errors and climb the learning curve somewhat faster than me. I was attracted to Haskell, after playing around with OCAML, and realizing that functional programming offers some nice advantages to scientific programming. Mainly because the notation and thinking is very mathematical. But first, in order to evaluate the suitability of this language for my purposes, I had to verify that the foreign function interface (FFI) was suitable. There are a number of numerical libraries, all in imperative languages, that I want to link to. I quickly discovered that the documentation on Haskell's FFI is rather poor currently. This topic is simply not of interest to the academics I suppose. It took many hours of searching to find this document: http://www.cs.caltech.edu/courses/cs11/material/haskell/papers/tackling_the… This little tutorial was a goldmine of information about monads and an introduction to the FFI. (No template solutions for my problem sorry to say.) It was certainly dismaying to see that even the simplest IO requires at least a minimal understanding of monads, and adds a bunch of extra semantics to the problem. However none of the solutions offered, even the automated ones, seemed to handle the case of passing numerical arrays to C, and having them get updated and passed back. That is my primary interest in the FFI and yet no obvious solution or example could be found after days of internet searching and pouring over tutorials etc. My conclusion, after hours of studying the hierarchical libraries was that I needed to use the StorableArray type which led me to this site, http://www.haskell.org/haskellwiki/Arrays#StorableArray_.28module_Data.Arra… This site proposes the following curious piece of code: {-# OPTIONS_GHC -fglasgow-exts #-} import Data.Array.Storable import Foreign.Ptr import Foreign.C.Types main = do arr <- newArray (1,10) 37 :: IO (StorableArray Int Int) readArray arr 1 >>= print withStorableArray arr $ \ptr -> memset ptr 0 40 readArray arr 1 >>= print foreign import ccall unsafe "string.h" memset :: Ptr a -> CInt -> CSize -> IO () After having freshly read the tutorial on monads I thought I was ready for this, but I ran into some parsing problems. I don't have a full grasp of the precedence rules for the operators, >>= , $ and function evaluation are, and whether they group left to right or right to left. A little type parsing on the inputs and outputs allowed me to resolve all but the line withStorableArray arr $ \ptr -> memset ptr 0 40 Which should resolve to a monad if I understand the do notation correctly. My first assumption was that $ has lower precedence than function application, but a higher precendence than >> or >>=, so I assumed the grouping, (withStorableArray arr) $ (\ptr -> (memset ptr 0 40)) Now withStorableArray has the type specification StorableArray i e -> (Ptr e -> IO a) -> IO a , so it should be obvious how to use it (Not). At any rate it takes two arguments so I might assume that (withStorableArray arr) curries the first argument so that this expression is a function of type (Ptr e -> IO a) -> IO a . Because of the type of the array, it appears that a = Int. However (\ptr -> (memset ptr 0 40)) should be a function of type Ptr a -> IO(a) in order to qualify as the second argument of withStorableArray. This almost fits, but not quite. memset should return type IO(Int) for this to work correctly, however according to it's type declaration it returns IO (). Shouldn't the compiler complain about this? So after about 10 hours of wrestling with syntax, including messing up the initial capitalization of module names, indenting in do lists, forgetting to put commas in tuples and lists I finally got the following example to compile without error or warning Matrix.hs __________ import Foreign import Foreign.C import Foreign.C.Types (CInt, CDouble ) import Data.Array.Storable foreign import ccall "matrix_c.h sumarr" sumarr :: Ptr CDouble -> CDouble main = do arr <- newListArray (1 , 3) [3,2,1]:: IO (StorableArray Int CDouble) -- extract the pointer to arr dsum <- withStorableArray arr (\ptr -> return (sumarr ptr )) print dsum matrix_c.c ------------------ #include <math.h> double sumarr(double *in) { return(in[0] + in[1]) ; } This is how I compiled it using ghc 6.4.2 > ghc -c matrix_c.o matrix_c.c > ghc -O -o Matrix.exe -fglasgow-exts Matrix.hs matrix_c.o It runs correctly > Matrix > 5.0 Notes: ---------------------------------------------- Matrix.exe fails to work correctly if the header file matrix_c.h is not included in the foreign import statement The hack? where the second argument of withStorableArray is a -> IO() instead of a -> IO(a) allows the do clause to be simplified to main = do arr <- newListArray (1 , 3) [3,2,1]:: IO (StorableArray Int CDouble) withStorableArray arr $ print . sumarr If one changes the array in[] in the C code, e.g. double sumarr(double *in) { in[0] = -10.0 ; return(in[0] + in[1]) ; } The array is changed inside the haskell program as a side effect. main = do arr <- newListArray (1 , 3) [3,2,1]:: IO (StorableArray Int CDouble) -- extract the pointer to arr withStorableArray arr $ print . sumarr (readArray arr 1 ) >>= print I suppose this is one way to 'pass' arrays back to Haskell.

10 19

Space leak when returning pairs?
by Shin-Cheng Mu 20 May '06

20 May '06

Dear members, I am experiencing a space leak, which I suspect to be an instance of the problem addressed by Wadler before. I'd appreciate if someone here would take a look. Given the following datatype: data XMLEvent = StartEvent String | EndEvent String | TextEvent String deriving Show where the three constructors represent the start tag (<a> where a is a string), end tag (</a>), and text data, respectively, of an XML stream. (They are actually from the library HXML). The following function simply returns the same stream while doing a minimal amount of validation (ignoring the closing tag). idX :: [XMLEvent] -> ([XMLEvent], [XMLEvent]) idX [] = ([], []) idX (StartEvent a : strm) = let (ts, strm') = idX strm (us, strm'') = idX strm' in (StartEvent a [] : ts ++ EndEvent a : us, strm'') idX (EndEvent _: strm) = ([], strm) idX (TextEvent s : strm) = let (ts, strm') = idX strm in (TextEvent s : ts, strm') The function idX returns a pair, where the first component is the processed stream, while the second component is the rest of the input. The intention is to thread the input and release processed events. If the function is used in a pipelined manner: print . fst . idX . parseInstance $ input where parseInstance :: String -> [XMLEvent] is a lexical analyser, I would expect that the input stream will be consumed one by one as the output is produced, and the program would use a constant amount of heap space (while keeping a program stack proportional to the depth of the XML tree). This was not the case, however. For some reason the heap grew linearly. The GHC profiler showed that most of the thunks are created by parseInstance, which implies that the entire input stream somehow still resides in memory. I was wondering where the space leak came from and suspected that it's the leak described in one of Philip Wadler's early paper Fixing Some Space Leaks With a Garbage Collector (1987). Consider idX (StartEvent a : strm) = let (ts, strm') = idX strm (us, strm'') = idX strm' in (StartEvent a [] : ts ++ EndEvent a : us, strm'') The body of the let clause might have actually been treated as (StartEvent a [] : ts ++ EndEvent a : fst (idX (snd strm)), snd (idX (snd strm))) Therefore strm will not be freed until the whole evaluation finishes. But since Wadler has addressed this problem a long time ago, I think the fix he proposed should have been implemented in GHC already. Was that really the source of the space leak? If so is there a way to fix it? Or is there another reason for the leak? * * * The function idX above actually resulted from fusing two functions: buildF parses a stream into a forest, while idF flattens the tree. data ETree = Element String [ETree] | Text String buildF :: [XMLEvent] -> ([ETree], [XMLEvent]) buildF [] = ([],[]) buildF (StartEvent a : strm) = let (ts, strm') = buildF strm (us, strm'') = buildF strm' in (Element a ts : us, strm'') buildF (EndEvent _ : strm) = ([], strm) buildF (TextEvent s : strm) = let (ts, strm') = buildF strm in (Text s : ts, strm') idF :: [ETree] -> [XMLEvent] idF [] = [] idF (Element a ts : us) = StartEvent a : idF ts ++ EndEvent a : idF us idF (Text s : ts) = TextEvent s : idF ts My original program was like print . idF . fst . buildF . parseInstance $ input and it had the same space leak. By accident (assuming that the input is always a single tree), I discovered that if I added a "wrap . head" into the pipe: print . idF . wrap . head . fst . buildF . parseInstance $ input where wrap a = [a], the heap residency would reduce by half! The output remains the same. My explanation is that applying a "head" means that (in the definition of buildF): buildF (StartEvent a : strm) = let (ts, strm') = buildF strm (us, strm'') = buildF strm' in (Element a ts : us, strm'') the "us" part , which contains a reference to strm, need not be kept. Thus the reduced heap residency. This seems to support that the space leak resulted from the same problem Wadler addressed before. But isn't that solved already in GHC? * * * I'd appreciate if someone could look into it. The actual program is available at http://www.psdlab.org/~scm/hx.tar.gz It actually uses HXML, a library by Joe (Joe English?) to do the parsing. The main program is hxpc.hs. There is a 1 MB sized sample input file size1m.xml. There are two simple scripts "recompile" and "runhxpc" for compiling and running the program. Thank you! sincerely, Shin-Cheng Mu

4 6

Parsec memory behavior
by Juan Carlos Arevalo Baeza 19 May '06

19 May '06

Try this simple program: import Text.ParserCombinators.Parsec ppAny = tokenPrim show (\p _ _ -> p) (\t -> Just t) ppTest = many ppAny p s = case runParser ppTest True "" s of Left error -> show error Right result -> result main = do let fname = "C:/main.i" f <- readFile fname let tokens = p f putStrLn . show $ head tokens This is the simplest expression of using Parsec, it just returns the input unchanged. But it already seems to have a big memory leak. When parsing a 2 MB file, I'm seeing the program grow in size up to about 160 MB before it ends. I assume this is known behavior. I believe it's because of the way Parsec deals with errors: when you chain two parsers in sequence, the result of the first one (in this case the head of the list) is not available until it knows if the second one failed or not. Is there any known alternative that doesn't exhibit this behavior? It would have to somehow return errors inline or on a "side channel". I'll be toying with this sort of thing for a while. Thanx! JCAB

4 5

shared local definitions
by Alberto Ruiz 19 May '06

19 May '06

Hi all, I have a question about optimization of shared values in local definitions. I frequently use this scheme: fun a b c d x = r where q = costly computation depending only on a, b, c, and d r = depends only on q and x g1 = fun 1 2 3 4 g2 = fun 5 4 2 7 (etc.) When I compute (using ghc -O) things like map g1 [1 .. 1000] the common q is evaluated only once, which is very nice. But the problem is that in some strange cases this kind of optimization is not applied, and the same q is evaluated 1000 times. Curiously, this happens if I add just: module Main where to one of my programs. Optimization is also lost if in the same program I use two partially applied functions: map g1 [1 .. 1000] map g2 [1 .. 1000] And in some cases optimization is only applied if the local definition is "easy" enough. For example: --------------------------------------------------- fun1 :: Int -> Int -> Int fun1 a x = q*x where q = {-# SCC "easy" #-} a+1+a^2 -- OK fun2 :: Int -> Int -> Int fun2 a x = q*x where q = {-# SCC "hard" #-} a+1+a^2 +a^3+(2*a) -- NO fun3 :: Int -> Int -> Int fun3 a x = r where q = local a r = q*x local u = {-# SCC "local easy" #-} u+1 -- OK fun4 :: Int -> Int -> Int fun4 a x = r where q = local a r = q*x local u = {-# SCC "local hard" #-} u+1+u^2 -- NO test h = print $ sum $ map h [1 .. 100] main = do test (fun1 3) test (fun2 3) test (fun3 3) test (fun4 3) -------------------------------------------------- COST CENTRE MODULE no. entries MAIN MAIN 1 0 main Main 154 101 fun4 Main 166 300 local hard Main 167 100 NO fun3 Main 163 100 fun2 Main 161 100 hard Main 162 100 NO fun1 Main 157 100 test Main 155 4 CAF Main 148 6 fun4 Main 168 0 main Main 158 0 fun3 Main 164 1 local easy Main 165 1 OK fun1 Main 159 0 easy Main 160 1 OK test Main 156 0 CAF System.IO 103 1 CAF GHC.Handle 101 3 ------------------------------------------------------------ Where can I find information about this topic? I have made some searches but probably using wrong keywords. Should I use some individual optimization flags? Thanks, Alberto

4 3