February 2008 - Haskell-Cafe

Problem with Python AST
by Roel van Dijk 21 Feb '08

21 Feb '08

Hello everyone, I am trying to create an AST for Python. My approach is to create a data type for each syntactic construct. But I am stuck trying to statically enforce some constraints over my statements. A very short example to illustrate my problem: newtype Ident = Id String data BinOp = Add | Sub data Exp = IntLit Integer | BinOpExp BinOp Exp Exp data NormalCtx data LoopCtx data Statement ctx where Compound :: Compound -> Statement ctx Pass :: Statement ctx Break :: Statement LoopCtx newtype Global = Global [Ident] data Suite ctx = Suite [Global] [Statement ctx] type Else = Suite NormalCtx data Compound = If [(Exp, Suite NormalCtx)] (Maybe Else) | While Exp (Suite LoopCtx) (Maybe Else) newtype Program = Program [Statement NormalCtx] The "global" statement makes an identifier visible in the local scope. It holds for the entire current code block. So it also works backwards, which is why I didn't make it a statement but part of a suite (= block of statements). Some statements may occur in any context, such as the "pass" statement. But others are only allowed in certain situations, such as the "break" statement. This is why I defined the Statement as a GADT. I just supply the context in which the statement may be used and the typechecker magically does the rest. Feeling very content with this solution I tried a slightly more complex program and discovered that my AST can not represent this Python program: for i in range(10): if i == 6: break The compound if statement is perfectly valid nested in the loop because the Compound constructor of Statement allows any context. But the suites inside the clauses of the if statement only allow normal contexts. Since Break has a LoopCtx the typechecker complains. Is there some other way to statically enforce that break statements can only occur _nested_ inside a loop? There is a similar problem with return statements that may only occur in functions. These nested statements should somehow 'inherit' a context, if that makes any sense :-) I know I can simply create separate data types statements that can occur inside loops and function bodies. But that would make the AST a lot more complex, something I try to avoid. Python's syntax is already complex enough! Most of these constraints are not in the EBNF grammar which can be found in the language reference, but they are specified in the accompanying text. The cpython interpreter will generate SyntaxError's when you violate these constraints. See also Python's language reference: http://docs.python.org/ref/ref.html (see sections 6 and 7)

2 2

stream/bytestring questions
by Chad Scherrer 21 Feb '08

21 Feb '08

ByteStrings have given a real performance boost to a lot of Haskell applications, and I'm curious why some of the techniques aren't more abstracted and widely available. If it's "because it's a big job", that's certainly understandable, but maybe there's something I'm overlooking that some of the abstractions aren't really desirable. My first question is about the stream fusion. This seems (based on the ByteString paper) to speed things up quite a lot, but for some reason this isn't necessarily the case for lists. Is this just a matter of the existing fusion for lists doing such a good job in many cases that it's hard to beat? The streams paper suggests that some contructors aren't optimized away during fusion, but wouldn't this also be a problem for fusion in the bytestring context? Are there many cases where it helps performance to program to streams directly, rather than letting the rules go back and forth between them and lists? I tried to do this, but kept getting hung up on the Unlifted stuff; it's not exposed (pardon the pun) in the API, and I don't understand why the types are different than the usual (), Either a b, (a,b), etc. Second, the idea of representing a sequence as a lazy list of strict arrays is very appealing. But why represent it so concretely? Wouldn't it make sense to do something like data ArrayList a i e = Empty | Chunk !(a i e) (ArrayList a i e) ? Then array fusion could be written for IArray types in general, and the ByteString library would become a set of instances with some specialization pragmas. Presumably a more general StorableVector could be represented as an IArray, and the NDP stuff seems a good fit too, so this would make it easy to leverage future work. Seems to separate the various concerns a little better, too, but again maybe there's a performance issue I'm missing. Sorry for the barrage of questions; I guess there's just a lot I'm trying to understand better. Thanks, Chad

5 12

question about STM and IO
by John Lato 21 Feb '08

21 Feb '08

Hello, I was recently looking at the STM library, and I have a question about the function "unsafeIOToSTM". Can anyone explain to me what is unsafe about it, and what sort of use would be considered "safe"? Thanks, John

6 8

Gobbler Benchmarks
by Adrian Hey 21 Feb '08

21 Feb '08

Hello Folks, There's been some discussions recently about the pros and cons of various coding styles, particularly whether stack greedy or heap greedy is best, and how (if) ghcs stack management in particular should affect all this. In particular, the problem of implementing an eager take function. Here's some real numbers measured with ghc 6.8.2 under windowsxp using AMD Athlon 64 1.8 GHz. The source code can be found here.. http://homepages.nildram.co.uk/~ahey/Test1.zip There are 4 possible implementations that have been tested: -- Uses O(n) stack stackGobbler :: Int -> [x] -> [x] stackGobbler 0 _ = [] stackGobbler _ [] = [] stackGobbler n (x:xs) = let xs' = stackGobbler (n-1) xs in xs' `seq` (x:xs') -- Uses O(n) heap instead, O(1) stack heapGobbler :: Int -> [x] -> [x] heapGobbler = heapGobbler' [] where heapGobbler' rxs 0 _ = reverse rxs heapGobbler' rxs _ [] = reverse rxs heapGobbler' rxs n (x:xs) = heapGobbler' (x:rxs) (n-1) xs -- Neils O(n) heap version, O(1) stack neilGobbler :: Int -> [x] -> [x] neilGobbler n xs = length res `seq` res where res = take n xs -- Continuation passing O(n) heap version, O(1) stack cpGobbler :: Int -> [x] -> [x] cpGobbler = f id where f c 0 _ = c [] f c _ [] = c [] f c n (x:xs) = f (\xs' -> c (x:xs')) (n-1) xs There are 16 tests for each, parameterised by p=0..15. Each test takes 63*(2^p) elements from a test list of the same length, and is repeated 2^(25-p) times. So in total, 63*(2^25) elements are processed in each case (independent of p). Here are the results in "myCpuTimePrecision = 15625000000" units (the figure exported by System.CPUTime is wrong for me). To convert these to actual time per element figures you need to multiply each by 7.4 pS (I think :-). All tests were run with fixed stack and heap sizes of 16 and 256 MiB respectively. p stack heap neil cp ---------------------------- 0 - 1793 2684 4937 2593 1 - 1860 2673 4897 2584 2 - 1910 2673 4825 2578 3 - 1927 2659 4819 2575 4 - 1946 2657 4813 2574 5 - 1950 2656 5048 2578 6 - 1960 2711 5036 2627 7 - 1976 2730 5126 2643 8 - 2072 2900 5197 2813 9 - 2439 3044 5153 2974 10 - 2685 3275 5371 3199 11 - 2760 3384 5466 3321 12 - 2930 3487 5525 3444 13 - 3181 3648 5813 3698 14 - 3698 3973 6417 4031 15 - 4727 4987 7964 5224 So pretty much as I expected. For smallish lists, stackGobbler is easily the fastest, heapGobbler and cpGobbler are pretty similar, and neilGobbler is the slowest (sorry Neil:-). The performance of all is degraded as p increases. I guess this is not too surprising, but stackGobbler seems to degrade faster so that at p=15 there's not much difference between it and heapGobbler/cpGobbler. I'm not sure what it is that causes stackGobbler to be "unfairly" penalised this way, but I'm reminded of this post from John Meacham.. http://haskell.org/pipermail/glasgow-haskell-users/2007-May/012470.html The other big problem with stackgobbler in practice is the risk of stack overflow. For p=15 it would not work at all for ghc default stack limit. Regards -- Adrian Hey

1 0

what is the fastest way to extract variables from a proposition?
by Cetin Sert 21 Feb '08

21 Feb '08

-- proposition data Prp a = Var a | Not (Prp a) | Or (Prp a) (Prp a) | And (Prp a) (Prp a) | Imp (Prp a) (Prp a) | Xor (Prp a) (Prp a) | Eqv (Prp a) (Prp a) | Cns Bool deriving (Show, Eq) -- Here are to variable extraction methods -- variable extraction reference imp. -- Graham Hutton: Programming in Haskell, 107 vars_ :: Prp a → [a] vars_ (Cns _) = [] vars_ (Var x) = [x] vars_ (Not p) = vars_ p vars_ (Or p q) = vars_ p ++ vars_ q vars_ (And p q) = vars_ p ++ vars_ q vars_ (Imp p q) = vars_ p ++ vars_ q vars_ (Xor p q) = vars_ p ++ vars_ q vars_ (Eqv p q) = vars_ p ++ vars_ q -- variable extraction new * this is faster vars :: Prp a → [a] vars p = evs [p] where evs [] = [] evs (Cns _ :ps) = [] evs (Var x :ps) = x:evs ps evs (Not p :ps) = evs (p:ps) evs (Or p q:ps) = evs (p:q:ps) evs (And p q:ps) = evs (p:q:ps) evs (Imp p q:ps) = evs (p:q:ps) evs (Xor p q:ps) = evs (p:q:ps) evs (Eqv p q:ps) = evs (p:q:ps) -- for : Not (Imp (Or (Var 'p') (Var 'q')) (Var p)) -- vars_: ['p','q','p'] -- vars : ['p','q','p'] -- order and the fact that 'p' appears twice being irrelevant: -- is there an even faster way to do this? -- -- Cetin Sert -- www.corsis.de

4 7

Selecting Array type
by Jeff φ 21 Feb '08

21 Feb '08

I'm trying to create a type called SmartArray. It is a type synonym for an array. If the element type can be unboxed, then SmartArray is an unboxed array. Otherwise, it is a boxed array. For instance, (SmartArray Int Double) is the same as (UArray Int Double) (SmartArray Int String) is the same as (Array Int String) However, my implementation of SmartArray requires me to create an instance of a selector class to tell the compiler wheither the type is boxed or unboxed. I'm hoping to avoid creating instances of the selector class for every possible type. I'd be grateful for any suggestions. Please see my code: {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception -XOverlappingInstances #-} import Data.Ix import Data.Array.Unboxed import Data.Complex type SmartArray i e = (Ix i, SmartArraySelector a e) => (a i e) -- smartArray is similar to array function from Data.Array. But, it -- will return a UArray if e can be unboxed. Otherwise, it returns an Array. smartArray :: (i, i) -> [(i, e)] -> SmartArray i e smartArray bnd eLst = array bnd eLst class (IArray a e) => SmartArraySelector a e | e -> a where arrayType :: Ix i => a i e -> a i e arrayType = id -- SmartArraySelector selects UArray for all types that can be -- unboxed. An instance has to be created for each unboxed type. I'd -- like to avoid listing all unboxed types here. However, since there -- are only a few unboxed types, it's not too burdensome to list them -- all. (For brevity, I didn't create all possible instances.) instance SmartArraySelector UArray Bool where instance SmartArraySelector UArray Char where instance SmartArraySelector UArray Double where instance SmartArraySelector UArray Float where instance SmartArraySelector UArray Int where -- SmartArraySelector selects Array for all types that can't be -- unboxed. An instance has to be created for EVERY possible unboxed -- type that might be used with SmartArray. Since, the list of -- possible types is unlimited, this is pretty annoying. instance SmartArraySelector Array String where instance SmartArraySelector Array (Complex e) where -- I'd like to replace all the boxed instances above with one instance -- like . . . -- -- instance SmartArraySelector Array e where -- -- However, this generates an error even though, -- -XOverlappingInstances turned on. test e = smartArray (0,10) [ (i,e) | i <- [0..10]]

5 5

Re: [Haskell-cafe] Where does ~> come from?
by Wolfgang Jeltsch 21 Feb '08

21 Feb '08

Am Dienstag, 19. Februar 2008 18:26 schrieben Sie: > […] > However, I was told this: ~> a b is a ~> b, but if I write c a b and > wish the effect of a `c` b. This would not work. ~> as an infix operator > has a special place in GHC. It is not "just a type variable". Sorry, but I don’t understand fully what you mean. :-( But nevertheless, a ~> b is not the same as ~> a b but as (~>) a b. It’s just like with ordinary operators where a + b is the same as (+) a b. ~> is not special in GHC. You could use, for example, ### instead of ~> and get the same results. However, GHC accepts type operators only if you tell it to do so. Give GHC the option -XTypeOperators or insert {-# LANGUAGE TypeOperators #-} at the beginning of your source file. > […] Best wishes, Wolfgang

5 4

Haddock documentation of Data.Array.* is confusing
by Alfonso Acosta 21 Feb '08

21 Feb '08

Hi, Excuse me for the subject, but IMHO is absolutely true. Anyhow, the purpose of this message is not merely to rant about it (which I know doesn't help) but to illustrate the possible impression of a Haskell newcomers. It's been a long long time since I last used arrays in Haskell (lists are normally just fine for me) so I checked the docs to refresh my memory. This is the result of my experience: The first thing I checked was Data.Array which ... just shows function names without signatures! OK, I followed the advice shown in "Data.Array" and tried to understand the more generic interface of Data.IArray. Fine, the documentation is much better, however it mentions Data.Array.Base, whose documentation link is missing :S I was suprised to see that even if all the functions of Data.IArray (i.e. array, listArray ... ) are perfectly sensible and generic (which is nice), they are not part of ot the IArray multiparameter class. So I wondered .. how can someone add its own implementation of inmutable arrays to the IArray interface? It was obvious that "bounds" (the only method of the IArray typeclass) was not going to enough, but I tried anyway with a naive example. {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-} data Ix i => LArray i e = LArray [e] (i,i) instance IArray LArray e where -- bounds :: (Ix i, IArray LArray e) => LArray i e -> (i,i) bounds (LArray _ b) = b GHC warned me about missing definitions for some"unsafe" methods of ArrayI which .... as expected, belong to the "phantom" Data.Array.Base module. The sources of Data.Array.Base revealed that the purpose of hiding them was to protect the user. Someone who wants add an array implementation to the IArray interface should use Data.Array.Base but why would it hurt to add a note in IArray mentioning it? and Why is Data.Array.Base hidden for Haddock (especially when there are some broken links pointing to it)? Cheers, Fons

2 2

Broken http://darcs.haskell.org/darcsweb/?
by Dominic Steinitz 20 Feb '08

20 Feb '08

I'm getting errors when I click on any of the links. I'm not sure who administers the site. IOError Python 2.4.4: /usr/bin/python Wed Feb 20 11:41:13 2008 A problem occurred in a Python script. Here is the sequence of function calls leading up to the error, in the order they occurred. /srv/darcsweb/darcsweb.cgi 2248 url_request.sort() 2249 cache = Cache(config.cachedir, url_request) 2250 if cache.open(): 2251 # we have a hit, dump and run 2252 cache.dump() cache = <__main__.Cache instance>, cache.open = <bound method Cache.open of <__main__.Cache instance>> /srv/darcsweb/darcsweb.cgi in open(self=<__main__.Cache instance>) 466 pid = str(os.getpid()) 467 fname = self.basedir + '/.' + self.fname + '-' + pid 468 self.file = open(fname, 'w') 469 self.mode = 'w' 470 self = <__main__.Cache instance>, self.file = None, builtin open = <type 'file'>, fname = '/tmp/darcsweb-cache/.3647210cedbbeff551e4ffe8dac1328a00518335-30974' IOError: [Errno 2] No such file or directory: '/tmp/darcsweb-cache/.3647210cedbbeff551e4ffe8dac1328a00518335-30974' args = (2, 'No such file or directory') errno = 2 filename = '/tmp/darcsweb-cache/.3647210cedbbeff551e4ffe8dac1328a00518335-30974' strerror = 'No such file or directory'

2 1

Exporting Haskell Libraries to C Programmers
by Bruce, Joseph R (Joe) 20 Feb '08

20 Feb '08

Hi, I have a Haskell library that I want to make available via FFI to C programmers on my project team. I read this thread (http://thread.gmane.org/gmane.comp.lang.haskell.cafe/21447) which had some interesting ideas, but they seemed unresolved. Or maybe it answers my question but I don't understand it. Is there a way I can package (ghc-)compiled Haskell code into a statically-linked library and not force the C programmers to include headers and libraries that they have no knowledge of and undefine a seemingly endless list of preprocessor symbols (run ghc with the verbose flag and look at the calls to gcc)? Can this process be automated? Thanks, Joe

2 1