November 2008 - Haskell-Cafe

streaming translation using monads
by Warren Harris 19 Nov '08

19 Nov '08

I am working on a query language translator, and although I feel that a monadic formulation would work well for this application, I've stumbled on a number of questions and difficulties that I thought the knowledgeable people here might be able to help me with. As a translator, there's a source language and a target language, and both of these are specified as a grammar of nested expressions. My first thought was to formulate the target language as an embedded language where each clause expression is represented as a monad operation, so that the bind operator can join the pieces together, e.g.: (clause1, clause2 ...) could be specified as an embedded language as: clause1 >>= \ v1 -> clause2 >>= \ v2 -> ... However, each of the clauses is actually an output routine to send the expression that it denotes to a remote server, and a parser for receiving the results. Since a clause is really a pair of operations, it doesn't seem possible to formulate a monad that will compose all the output routines together and compose all the input routines together in one shot. (Note that the variables in the above code (v1, v2) represent inputs to be received from the remote server -- all outputs are packaged into the clause expressions themselves and are effectively literals.) A naive formulation of a monad to implement the above as "output -> input v" might appear to work, but has the ill-effect of interleaving the output and input statements for each clause rather than composing something that can send the entire request, and then receive the entire result. This forces me to use "output * input v" as the type of each clause expression, but now it is not possible to write a monad with a bind operation that will compose pieces in terms of input variables. Instead I have had to resort to using a set of combinators that thread a continuation function through each clause and accumulate inputs as they are received: clause1 ==> (\ k v1 -> k (trans1 v1)) ++ clause2 ==> (\ k v2 -> k (trans2 v2)) ++ ... This threading is necessary in that I want to stream the translation back to the client requesting the translation rather than building up the (possibly large) results in memory. This formulation has proven to be quite cumbersome in practice, as the resulting continuation types reflect the depth-first traversal of the nested query expressions, and type errors can be quite unintuitive. (It is quite interesting though that each continuation/transformation function can receive not only receive the input from the immediately preceding clause, but from any of the preceding clauses, and also return more or fewer results. However getting anything wrong can be very problematic in that it can lead to either downstream *or* upstream errors depending on how the clauses are composed into an overall query expression.) An alternative to all this would be to use an algebraic datatype to specify the target language (with separate routines for the output and input operations), but that would appear to require another sum type to express the values to be received. I'd like to avoid that if possible since the projection of those values back into my program could lead to dynamic type errors, and also causes seemingly needless memory allocations. There must be another technique for this sort of streaming translation out there... I welcome any suggestions you might have! Warren Harris

4 7

Fwd: [Haskell-cafe] implementing python-style dictionary in Haskell
by Alberto G. Corona 19 Nov '08

19 Nov '08

sorry, Dons, ---------- Forwarded message ---------- From: Alberto G. Corona <agocorona(a)gmail.com> Date: 2008/11/18 Subject: Re: [Haskell-cafe] implementing python-style dictionary in Haskell To: Don Stewart <dons(a)galois.com> By the way byteStrings are wonderful, but, it isn´t true that byteStrings are not so fast for managing short strings, for example keys ? 2008/11/18 Don Stewart <dons(a)galois.com> dave: > > 2008/11/18 kenny lu <haskellmail(a)gmail.com>: > > > Here is a comparison of memory usage > > > > > > Map : 345 MB > > > IntMap : 146 MB > > > Trie : 282 MB > > > Python : 94 MB > > > > > > Here is a comparison of execution time (on an intel dual core 2.0G) > > > > > > Map: 26 sec > > > IntMap: 9 sec > > > Trie: 12 sec > > > Python: 2.24 sec > > > > > > > > > The above number shows that my implementations of python style > dictionary > > > are space/time in-efficient as compared to python. > > > > > > Can some one point out what's wrong with my implementations? > > > > This isn't really a fair comparison. Map, IntMap, and Trie are > > persistent data structures, and Python dictionaries are ephemeral. > > (That is, when you "add" a key to a Map, you actually create a new one > > that shares structure with the old one, and both can be used in > > subsequent code. In Python, you would have to copy the dictionary.) > > > > Strings, not ByteStrings. that's the difference. > > -- Don > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

UArray Word16 Word32 uses twice as much memory as it should?
by Arne Dehli Halvorsen 19 Nov '08

19 Nov '08

Hello, I am having an issue with these unboxed arrays. I have some code that creates this structure:: (Array Word16 (UArray Int Word32), Array Word16 (UArray Int Word8)), and I am finding that it uses about twice as much memory as I had anticipated. This tuple is returned strict, and I think I haven't left much room for other data remaining in memory. It should hold one Word8 and one Word32 for a data set of 100 million records, and it uses around 1 gigabyte. By my calculations, it should be half that. So I was wondering if I might have hit upon a 64-bit vs 32-bit issue. I compile with: ghc --make load05 -O1 -funbox-strict-fields -XBangPatterns -fvia-C (also tried with -O2, and without the -fvia-C) using the packaged version of ghc 6.10.1 on MacOSX 10.5.5 Grateful for any pointers, Arne D Halvorsen

2 2

Monadic bind with associated types + PHOAS?
by Ryan Ingram 19 Nov '08

19 Nov '08

This is an idea that has been bouncing around in my head for a while, having to do with embedded languages. A few of the talks at CUFP this year mentioned using Haskell to embed a DSL that gets compiled into the output of the program; the hydraulic engine talk embedded the code for the real-time safety computation in the trucks, and one of the finance talks embedded a language for designing Excel spreadsheets. One thing that often comes up is a desire to do a pass on the resultant code to optimize it, but it's pretty difficult with the standard monadic formulation because of embedded functions. You can't do introspection on functions in Haskell; they aren't elements of Eq or Show. This has caused, for example, some implementations of FRP to switch to using arrows instead. However, I find the arrow syntax cumbersome and I feel it tends to obfuscate what is actually going on in the code. An earlier talk at ICFP mentioned using PHOAS instead of HOAS to encode expressions. In HOAS, a lambda expression in the target language is represented by a function in the source language: > data ExpE t where > ApE :: ExpE (a -> b) -> ExpE a -> ExpE b > LamE :: (ExpE a -> ExpE b) -> ExpE (a -> b) But without a way to inspect the function inside LamE, you can't get back to the "source code". You end up adding special constructors for "Primitive" or "Variable" to let you do something with the resultant structure, which leads to the expression language containing "unsafe" constructors which need to be hidden. PHOAS makes a small change to make many of these things possible without compromising safety: > data ExpP v t where > VarP :: v t -> ExpP v t > ApP :: ExpP v (a -> b) -> ExpP v a -> ExpP v b > LamP :: (v a -> ExpP v b) -> ExpP v (a -> b) > > newtype Exp t = Exp (forall v. ExpP v t) Now, by parametricity, if you are constructing an Exp t, the only useful thing you can do with the variable passed to LamP is give it to VarP. This means the code using it is basically the same as the HOAS code, except a couple of extra "VarP" constructors inserted, but you gain the ability to inspect inside the lambda and extract the code it generates! An couple of examples, from a PHOAS test I wrote up: 1) An evaluator > eval :: Exp t -> t > eval (Exp e) = evalP e > > newtype Prim a = Prim a > evalP :: ExpP Prim t -> t > evalP (VarP (Prim a)) = a > evalP (ApP e1 e2) = evalPrim e1 $ evalPrim e2 > evalP (LamP f) = evalPrim . f . VarP . Prim 2) using "show" to peek inside functions! ] -- implementation is an exercise for the reader ] -- you'll learn a lot! :) ] ] newtype Var a = Var String ] showExp :: ExpP Var a -> ShowS ghci> let test = Exp $ Lam $ \a -> Lam $ \b -> Var a ghci> :t test test :: Exp (t -> t1 -> t) ghci> print test \x y -> x It seems to me this exact transformation could be useful to express "variable binding" in embedded languages! > type family Primitive m a > type family BoundVar m a > class PMonad m where > preturn :: Primitive m a -> m a > pbind :: m a -> (BoundVar m a -> m b) -> m b Now, this strictly generalizes regular monads: > newtype Wrap m a = Wrap (m a) > unwrap (Wrap m) = m > type instance Primitive (Wrap m) a = a > type instance BoundVar (Wrap m) a = a > instance Monad m => PMonad (Wrap m) where > preturn x = WM (return x) > pbind m f = WM (unwrap m >>= unwrap . f) So, it seems like the do-notation should work on this type, although you lose pattern matching ([x] <- getArgs). And you can use PHOAS techniques to build up a structure that you can introspect and optimize. Does anyone think this is a direction worth pursuing? It seems to me like a point where the current syntax of Haskell could mesh well with the new type-system technology that we keep getting from GHC HQ. -- ryan

3 3

Re: [Haskell-cafe] Re: FFI and returning structs
by Donn Cave 19 Nov '08

19 Nov '08

Quoth Maurcio <briqueabraque(a)yahoo.com>: |> (...) Ironically, that's actually just what the original |> function is doing - cf. "struct return convention", where the |> caller allocates space and passes a pointer as a hidden |> parameter. (...) | | Can I be sure things always goes like that? I remember reading | somewhere that if, for instance, a struct is smaller in size than | a pointer (like a struct made of three chars), the struct could be | returned by itself. I think you can be reasonably sure it doesn't always work that way! But if you're interested, you can see what the compiler does with that smaller struct, looking at the assembly code it generates. I'm no Intel programmer, but if my test function uses a parameter, I can see that the parameter is found at an offset, compared to the same function returning a plain scalar value. So - yes, the struct value is returned in a register - but the convention is also observed, with the hidden parameter. Using gcc for Intel 80386 family CPU. Maybe later I will see how it works on AMD64. | Also, why Haskell FFI do not automate that? As long as it is | Storable data, can't it get the pointer and 'peek' it for me? I can't speak for the FFI authors, and note that I'm not even saying that it can't do this. Your inquiry was rather short on details about what happened, and anyway it's only convenient for me to try it with NHC, which may not be the compiler you're using. But if it were up to me, I doubt that I would support this (struct return), since it's rare, at best it adds to the difficulty of supporting different hardware platforms and compilers, and it's easy to work around. Donn

1 0

The Monad.Reader - Issue 12: SoC Special
by Wouter Swierstra 19 Nov '08

19 Nov '08

I am pleased to announce that a new issue of The Monad.Reader is now available: http://www.haskell.org/haskellwiki/The_Monad.Reader Issue 12 is another Summer of Code special and consists of the following three articles: * Max Bolingbroke Compiler Development Made Easy * Roman Cheplyaka How to Build a Physics Engine * Neil Mitchell Hoogle Overview The Monad.Reader is a quarterly magazine about functional programming. It is less formal than a journal, but more enduring than a wiki page or blog post. If you'd like to write something for the next issue of The Monad.Reader, please get in touch. The deadline for the next issue will be February 13th. Looking forward to your submissions, Wouter This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

1 0

Automatic parallelism in Haskell, similar to "make -j4"?
by T Willingham 19 Nov '08

19 Nov '08

I was surprised when I read the multi-core section of Real World Haskell which explains the use of par, seq, and force to achieve parallelism. While it's obvious a programmer could provide useful parallelism hints to the compiler, given the nature of the language I would have thought Haskell could do a significant amount of parallelism itself without any hints or code changes at all. I am thinking of our troglodytic friend 'make', which will run (for example) 4 parallel jobs when given the option "make -j4". Even 'rake', the ruby version of make, now has a branch (called drake) which does the parallel -j option. Since much of Haskell code is free of side effects, it would seem that it can be analyzed in similar manner to Makefile dependencies in order to find sections which can be run in parallel. What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? Thanks, TW

9 12

Can't figure out source of race condition when using System.Process
by Rafal Kolanski 19 Nov '08

19 Nov '08

Greetings Gentlemen (and Ladies), As part of my small and simple framework for making presentations in Haskell I have a module which, given some text, makes a .tex file and then converts it to .svg for loading into a cairo canvas. It features simple caching (performs md5 on the contents of the .tex file and uses that as the file name... if an .svg by that name exists, it'll get loaded rather than regenerated). Unfortunately, it also segfaults once in a while, probably indicating I have some kind of race condition ... but I can't figure out why. This is the only point in my code that I think I'm using any concurrency, although I'm compiling with ghc --make -threaded. Compiling without -threaded results in a deadlock. Ubuntu 8.10, 64-bit, GHC 6.8.2. Any advice? I'm attaching the module in question (79 lines). Sincerely, Rafal Kolanski.

6 7

Re: [Haskell-cafe] FFI and returning structs
by Donn Cave 19 Nov '08

19 Nov '08

Quoth Maurcio <briqueabraque(a)yahoo.com>: | I have not found examples of this in documentation | or hackage packages: how can I deal with funcions | returning not pointers to structs but structs | thenselves? | | struct example {... | | example function_name (... | | My intuition said I could try a data declaration | that is a properly done instance of Storable, and | then use that. | | data Example = ... | | instance Storable Example where ... | | But it seems I was wrong. Eh! probably not wrong - the problem is not how the data looks, but where it is. If it were my problem, I would try a wrapper function that returns the same value as an argument - e.g., if you have struct X f(), then void f_(struct X *x) { *x = f(); } ... so your wrapper will look like ccall "f_" f :: Ptr X -> IO () instead of ccall "f" f :: IO X Ironically, that's actually just what the original function is doing - cf. "struct return convention", where the caller allocates space and passes a pointer as a hidden parameter. But you can't just declare it that way, because the original f bumps the stack pointer on return (you may see "ret $4" in the assembly code, on Intel hardware) Try to compile the wrapper with the same compiler that compiled the original function. I'm really just guessing that your Haskell compiler doesn't understand or perfectly handle this particular C wart. If my suggestion doesn't work, I may have guessed wrong. Donn

2 1

Pattern matching on numbers?
by Ryan Ingram 19 Nov '08

19 Nov '08

How does this work? > fac n = case n of > 0 -> 1 > _ -> n * fac (n-1) ghci> :t fac fac :: (Num t) => t -> t The first line of "fac" pattern matches on 0. So how does this work over any value of the Num typeclass? I know that the "1" on the rhs of fac are replaced with (fromInteger 1), but what about numeric literals in patterns? Does it turn into a call to (==)? Should whatever technique is used be extended to other typeclasses too? -- ryan

4 3