May 2009 - Haskell-Cafe

Expression parsing problem
by leledumbo 20 May '09

20 May '09

I'm writing a paper as a replacement for writing exam and decided to write a simple compiler (got a little experience with it). However, I got trouble in parsing expression. The grammar: expression = "get" | [ "+" | "-" ] term { ( "+" | "-" ) term } term = factor { ( "*" | "/" ) factor } factor = IDENTIFIER | VALUE | "(" expression ")" I can't make term parse, for instance "1 * 2 / 3" (the number is not important, identifier is also accepted). It stops after parsing 2, i.e. only the first multiplication is parsed. Interchanging * and / gives the same result, only differs in operation. Whichever got encountered first will be parsed. The same problem also arises from expression, where it can't parse "1 + 2 - 3". Both problems are identical, but I can't figure out what's wrong (don't count the optional +/- before term in expression, I haven't done it yet). Sorry, but I'm lack of knowledge about Monad. I know it can be done better with it, but I need to learn a lot about it, while I don't have enough time (only 2 weeks). Below are necessary definitions for the parser (some taken from the scanner). For testing purpose, please try: expression [("1",Value),("+",Plus),("2",Value),("-",Minus),("3",Value),("EOF",EOF)] term [("1",Value),("*",Times),("2",Value),("/",Slash),("3",Value),("EOF",EOF)] expression [("1",Value),("-",Minus),("2",Value),("+",Plus),("3",Value),("EOF",EOF)] term [("1",Value),("/",Slash),("2",Value),("*",Times),("3",Value),("EOF",EOF)] > data Token = Identifier | OpenBlock | CloseBlock | SemiColon | Slash | > Equals | OpenBrace | CloseBrace | Minus | Times | > Plus | Nil | Value | Var | Const | > Put | Get | Comma | EOF > deriving (Show,Eq) > type Symbol = (String,Token) > type ASL = [Symbol] > type ParseFunc = ASL -> (ASL,[String]) > expression :: ParseFunc > expression (h:s) > | snd h == Get = (s,["IN"]) > | op `elem` [Plus,Minus] = (s2,r1 ++ r2 ++ [operation op]) > | otherwise = (s1,r1) > where (s1,r1) = term (h:s) > (s2,r2) = term $ tail s1 > op = if s1 /= [] then snd $ head s1 else Nil > expression s = (s,[]) > term :: ParseFunc > term s = if op `elem` [Times,Slash] > then (s2,r1 ++ r2 ++ [operation op]) > else (s1,r1) > where (s1,r1) = factor s > (s2,r2) = factor $ tail s1 > op = if s1 /= [] then snd $ head s1 else Nil > factor :: ParseFunc > factor ((id,Identifier):s) = (s,["LOAD " ++ id]) > factor ((val,Value):s) = (s,["PUSH " ++ val]) > factor (("(",OpenBrace):s) = if head s1 == (")",CloseBrace) > then (tail s1,r1) > else error $ "\")\" expected, got" ++ (show $ fst $ head s1) > where (s1,r1) = expression s > factor s = (s,[]) -- View this message in context: http://www.nabble.com/Expression-parsing-problem-tp23610457p23610457.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 8

Re: [Haskell-cafe] showing a user defined type
by michael rice 20 May '09

20 May '09

Hi Ryan, I'm afraid you've lost me. Maybe if you showed how this would be used in ML I would get the picture. Michael --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Tuesday, May 19, 2009, 2:40 PM On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: > A little further along in "The Little MLer" the ints function is replaced by > other functions like primes and fibs, which also return Links: > > fun primes(n) > = if is_prime(n+1) > then Link(n+1,primes) > else primes(n+1) > > fun fibs(n)(m) > = Link(n+m,fibs(m)) > > which are passed to chain_item: > > fun chain_item(n,Link(i,f)) > = if eq_int(n,1) > then i > else chain_item(n-1,f(i)) > > which can be called to request the nth (12th) prime number beginning at 1. > > - chain_item(12,primes(1)); > GC #0.0.0.1.3.61: (1 ms) > val it = 37 : int > - > > So I guess the answer to your question about whether the function is ever > called with a different value may be, yes. Actually, it's not calling it with another value; notice that chain_item calls f(i), with i coming directly from the chain. Consider this alternate definition: (I'm not sure the syntax is exactly right, but you get the idea) datatype chain = Link of (int * ( unit -> chain )) fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) fun ints(n) = intsFrom n () Now you *can't* call the function embedded in the link with another value. fun chain_item(n,Link(i,f)) = if eq_int(n,1) then i else chain_item(n-1,f unit) And this type for "chain" is almost the same as [Int] in Haskell, due to laziness. -- ryan

2 1

Performance Problem with Typeable
by Michael D. Adams 20 May '09

20 May '09

I'm not sure where this should be reported, but I think I've found a significant asymptotic performance problem with Data.Typeable. In the attached code, sum2 runs much slower than either sum1 or sum3. It should be linear but it seems to slow down quadratically (i.e. doubling "len" quadruples the time for sum2). Here is an example run: $ ghc --make -O3 CastSpeed.hs $ ./CastSpeed 20000 gsum1 Result: 200010000 Time(sec): 7.999e-3 Result: 200010000 Time(sec): 0.0 Result: 200010000 Time(sec): 1.0e-3 gsum2 Result: 200010000 Time(sec): 1.483774 Result: 200010000 Time(sec): 1.477776 Result: 200010000 Time(sec): 1.523768 gsum3 Result: 200010000 Time(sec): 5.999e-3 Result: 200010000 Time(sec): 0.0 Result: 200010000 Time(sec): 0.0 The only difference between sum1 and sum2 is that sum2 wraps a singleton list around each element (i.e. the cast is to [Int] instead of Int). The only difference between sum2 and sum3 is that sum3 uses an unchecked cast (unsafeCoerce) instead of a checked cast. This problem seems to crop up only for those types which are made up of a type constructor applied to an argument (e.g. "[]" applied to "Int"). Because of sum3 runs fast, I suspect that something is going wrong with the "typeOf" call in a checked cast, and because sum1 runs fast I suspect that what is going wrong is the call to appKey that is called from mkAppTy that is called from typeOfDefault that is called from the Typeable instance for [Int] (i.e. instance (Typeable1 s, Typeable a) => Typeable (s a)). This is a bit of speculation and I don't have hard evidence for that being the source of the problems, but tests that I have run (not listed here) are strongly suggestive of appKey being the culprit. Michael D. Adams mdmkolbe(a)gmail.com

2 2

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?
by Lee Duhem 20 May '09

20 May '09

2009/5/20 Bernie Pope <florbitous(a)gmail.com>: > Oh right. I didn't see your proposal (did it get sent to the list?). Yes, I just push the Replay button, not the > Sorry for the confusion. It's my fault, sorry. lee

1 0

How i use GHC.Word.Word8 wit Int ?
by z_axis＠163.com 20 May '09

20 May '09

Hi, friends rollDice :: Word8 -> IO Word8 rollDice n = do bracket (openFile "/dev/random" ReadMode) (hClose) (\hd -> do v <- fmap B.unpack (B.hGet hd 1) let v1 = Data.List.head v return $ (v1 `mod` n) + 1) ..... blueIdx <- rollDice $ length [1..33] Couldn't match expected type `Word8' against inferred type `Int' In the second argument of `($)', namely `length yesBlue I know "length [1..33]" is Int not Word8, but Word8 is enough here. Sincerely!

4 3

How to use Data.ByteString ?
by z_axis 20 May '09

20 May '09

Hi, friends the following function works well rollDice n = getStdRandom (randomR (1,n)) :: IO Int now i want to use /dev/random to produce better random number, but it doesnot work rollDice_t n = do hd <- openFile "/dev/random" ReadMode v <- B.hGet hd 1 return (v `mod` n) + 1 No instance for (Integral B.ByteString) arising from a use of `mod' at Money.hs:15:12-20 Possible fix: add an instance declaration for (Integral B.ByteString) In the first argument of `return', namely `(v `mod` n)' In the first argument of `(+)', namely `return (v `mod` n)' In the expression: return (v `mod` n) + 1 then how to use the ByteString properly ? Sincerely!

5 6

fast Eucl. dist. - Haskell vs C
by Patrick Perry 19 May '09

19 May '09

Hi Kenneth, I wrote a benchmark similar to yours using the haskell blas library I wrote (latest version is on github at http://github.com/patperry/blas/tree/master , an older version is on hackage). The pure Haskell implementation is not very good, and the problem seems to be repeated boxing/unboxing of doubles. It may be possible to avoid this by writing a custom "fold" function for Vectors, but I haven't tried it. Using a vectorized subtraction function along with the BLAS1 "dnrm2" function, I was able to get performance about 2.8-5.4x worse than C. This isn't great, but it's not terrible, either. I didn't have the performance problems you ran in to using the FFI. My benchmark includes: distVectors1: a native implementation using foldl' and zipWith distVectors2: a vectorize implementation, defined as @distVectors2 x y = norm2 (x-y)@ distVectors3: a custom loop in haskell distVectors4: an FFI call to C All 4 functions use the "Vector" type, provided by the "blas" package. I compiled with "-O -fexcess-preceision" and ran timings for vectors of size 10, 100, and 1000. Here are the results: Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 10 n: 10 * distVectors1: ..................... 1.366ns per iteration / 732029.06 per second. * distVectors2: ..................... 1.286ns per iteration / 777734.02 per second. * distVectors3: ...................... 0.950ns per iteration / 1052847.93 per second. * distVectors4: ....................... 0.452ns per iteration / 2213752.56 per second. Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 100 n: 100 * distVectors1: .................. 12.496ns per iteration / 80025.79 per second. * distVectors2: .................... 2.149ns per iteration / 465311.61 per second. * distVectors3: .................. 8.728ns per iteration / 114572.53 per second. * distVectors4: ...................... 0.597ns per iteration / 1675765.65 per second. Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 1000 n: 1000 * distVectors1: .............. 125.920ns per iteration / 7941.52 per second. * distVectors2: .................. 10.677ns per iteration / 93661.99 per second. * distVectors3: ............... 85.533ns per iteration / 11691.42 per second. * distVectors4: .................... 1.962ns per iteration / 509668.17 per second. The "distVectors2" function is computing the norm in a more numerically-stable way. It is also allocating a temporary array to store x-y. I haven't looked over your benchmarking code too thoroughly, but parts of it seem suspect to me. Namely, you are using "mapM" instead of "mapM_". Also, it seems like you are including GC times in your benchmarks. Attached is my code. You will need the latest "blas" from github to compile it. You also might want to look into hmatrix. I have very little time for haskell code right now (I'm trying to finish my Ph.D. in the next month). This summer I plan to work more on this stuff, and I'll probably make a release in July. Patrick

1 0

ANN: atom 0.0.4
by Tom Hawkins 19 May '09

19 May '09

This new version of atom adds an array datatype (A a), which has helped us shrink and speed up the embedded code in our application. Enjoy! http://hackage.haskell.org/cgi-bin/hackage-scripts/package/atom -Tom

1 0

Gtk2Hs + Sourceview on Windows
by mwinter＠brocku.ca 19 May '09

19 May '09

Hi, I have ghc 6.10.1 and gtk2hs 0.10.0 installed on my windows vista computer. Both were installed using the installer on the webpages. I am able to use gtk, glade etc but not sourceview or cairo. If I compile the examples in the gtk2hs example folder, I get "not in scope" error messages for functions from those library components. In a forum I found that those have to be enabled using ./configure --enable-sourceview (similar for cairo). But my windows installation does not seem to have a script configure or a similar program. What am I supposed to do? Thanks, Michael ---------------------------------------------------------------------------------------------- Michael Winter Brock University Associate Professor 500 Glenridge Avenue Department of Computer Science St. Catharine, ON, L2S 3 A1 Phone: +1 905 688 5550 ext 3355 Fax: +1 905 688 3255 ---------------------------------------------------------------------------------------------

1 0

Question about IO, interact functions,
by David Leimbach 19 May '09

19 May '09

main = interact (unlines . lines) This *appears* to somewhat reliably get me functionality that looks like take a line of input, and print it out. Is this behavior something I can rely on working? I like the idea that lines can pull lines lazily from "getContents" which lazily consume the input. But I'm concerned that relying on a pure function like "unlines . lines" to sequence IO is a bit too implicit in nature. I really like the idea of doing things through functions like Interact in that they appear to allow me to keep most of my code pure, but if I can't get the IO sequencing I want to be guaranteed to work, I suppose I'll have to dive back into "imperative IO" land that I get from the IO Monad. Should I feel guilty for doing so? :-) Dave

3 2