- Haskell-Cafe - Haskell.org

Memory and Threads - MVars or TVars
by Eitan Goldshtrom 29 Jul '10

29 Jul '10

Hi everyone. I was wondering if someone could just guide me toward some good information, but if anyone wants to help with a personal explanation I welcome it. I'm trying to write a threaded program and I'm not sure how to manage my memory. I read up on MVars and they make a lot of sense. My real question is what is "atomic" and how does it apply to TVars? I don't understand what atomic transactions are and I can't seem to find a concise explanation. I also saw some stuff about TMVars? But I can't find much on them either. Any help would be appreciated. -Eitan

6 8

Re: Fun with uu-parsinglib
by S. Doaitse Swierstra 29 Jul '10

29 Jul '10

On 29 jul 2010, at 05:04, David Place wrote: > Hi, Doaitse. > > I am making good progress transcribing my parser to use your library. I think some ways that I have grown accustomed to working with Parsec will not work, though. Now, I am getting the run time error: > >> Result: *** Exception: cannot compute minimal length of right hand side of monadic parser > > Is there an explanation of this error in the documentation? I am trying to combine with alternation some parsers which return the semantic data structures of my program. Perhaps there are restrictions on the kind of parsers that can be combined with alternation. > > Cheers, > David > ____________________ > David Place > Owner, Panpipes Ho! LLC > http://panpipesho.com > d(a)vidplace.com > > > Dear David, I am cc-ing this answer to Haskell-café since the answer may be of a wider interest. Let me first explain a a sequence of design choices I made: 1) my parser combinators perform error correction by trying to insert missing tokens into and to delete superfluous tokens from the input 2) of course there are many possibilities to do so 3) hence I implemented a search process which currently prunes the tree of possible corrective choices up to depth three 4) this process may return several solutions with the same overall cost and I have to pick one of those 5) in case of a draw I give preference to those alternatives which delete something, so progress is guaranteed 6) at the end of the input this does not work, since there is nothing to delete 7) if I pick an arbitrary alternative this may lead to a choice where we get an infinite sequence of insertions; suppose e.g. we want to insert an expression, and the system picks the if_alternative. If it does so it inserts an if-token and then the process starts all over again by trying to insert a conditional expression, which in general will be an expression, which will lead to the insertion of another if-token, etc. 8) in order to prevent this behaviour internally an abstract interpretation is made which computes the minimal number of tokens a parser will recognise (and thus can insert). The recursive alternatives will get an infinite length, and will thus never be chosen unless you grammar is well-formed and all choices only can lead to an infinite sequence of insertions 9) if a choice has to be made for the correction process always a finite alternative is chosen, so the correction process is guaranteed to complete Now the monads come in; they raise the question how to compute the minimal length of a parser WHICH DEPENDS ON A PREVIOUSLY RECOGNISED part of the input. In general this is impossible. So I made the decision to generate an error message in such cases, since I did not expect many people to run into this. But now you, and probably many people used to writing parsers in the monadic (i.e. Parsec) style turn up, and you continue to use the monadic style bacuse you have become accustomed to a different way of writing parsers. Let me give an example, based on the following grammar for well-formed nested parentheses: S -> (S)S ; epsilon. We want to return e.g. the maximal nesting depth. This is one of the functions in the Examples.hs file in the uu-parsinglib. The prototypical way of writing this in applicative style, without using monads is: wfp :: Parser Int wfp = max . (+1) <$> pParens wfp <*> wfp `opt` 0 Now let us take a look at the monadic formulation: wfp = do lt <- pParens wfp rt <- wfp -- < second call to wfp return ((lt + 1) `max` rt) <|> return 0 Now we see that the second call to wfp is within the scope of the binding of lt, and hence may depend on it. In this case it does not, but unfortunately the abstract interpretation cannot see this, and thus cannot do very much. This shows in my view the bad thing about monadic parser combinators: they prohibit the self-analysis of parsers, they inhibit optimisations, and they inhibit feedback based on the analysis. More on this below. Since I assume that the monadic formulation is only used as a last resort, i.e. when a parser REALLY depends on previous input, and that this will in general not be part of an alternative construct, I have decided to generate the above error message. Another solution I could have chosen is to make the choice in the correction process based on the order in which the alternatives occur in the program, but this would create the need to explain to users that the order of their alternatives matters, and it is one of the nice things that thus far it does not. In the old uulib the order even gets completely lost because we internally build tables which assist in speeding up the parsing process. There are several solutions now: a) I just remove the error message and make an educated guess, leading to situations where users might get stuck in an infinite correction process (only at the end of the file; normally in case of a draw preference is given to delete something in order to guarantee progress), and then start to ask questions about what is going on. Notice that they will not get feedback except probably a stack overflow. b) We leave it like this assuming that when people use a monadic style this will not be in the branch of an alternative construct c) We add an extra combinator which removes the error message, and we require the user to indicate that a specific alternative should never be chosen in the insertion process d) Internally I check to see whether more than specific number of insertions occur in a row, and then stop. This will however make parsing a bit more expensive, which I always try to avoid. Let me now come back to explain g further why I think the monadic style should be avoided where-ever possible because they prohibit abstract interpretation. If in the uu-parsinlib you write a parser like: pList (pList (pSym 'a')) you will get an an error message telling that this parser does not make sense, since the outer pList gets as an argument a parser which can accept the empty string. The good news is that this is something we can statically recognise, EVEN IN THE CASE we use monadic parsers. When we have p >>= q then either p is not empty, and if it is we know the value it returns and we can use this to see whether the q part may return empty. Notice that this is an analysis we have to do only once for each parser, and hence costs can be almost neglected. My conclusion is: avoid monadic parsers as much as possible, and only use them where you really want to continue parsing with a parser which really depends on the input, like in: n_as = do n <- pInt pEaxct (pSym 'a') pExact 0 p = pReturn [] pExact n p = (:) <$> p <*> pExact (n-1) p I have explained this observation before in my lecture notes for the Advanced Functional Programming summer school in 1996, section 5.2: @inproceedings{SwieDupo96, Author = {Swierstra, S. D. and Duponcheel, L.}, Booktitle = {Advanced Functional Programming}, Editor = {Launchbury, John and Meijer, Erik and Sheard, Tim}, Pages = {184-207}, Publisher = {Springer-Verlag}, Series = {LNCS-Tutorial}, Title = {Deterministic, Error-Correcting Combinator Parsers}, Urlpdf = {http://www.cs.uu.nl/people/doaitse/Papers/1996/DetErrCorrComPars.pdf}, Volume = {1129}, Year = {1996}} Good luck with your further attempts, and let me know which of the a)-d) you prefer, and do not hesitate to inform me about the next problem you may run into ;-}} Doaitse PS: if you want to do any further semantic processing then you might consider using the uuagc compiler to build te functions which typically arise in from of the <$>'s: http://www.cs.uu.nl/wiki/bin/view/HUT/AttributeGrammarSystem

1 0

Fwd: [Haskell-cafe] fine control of bytestring streaming
by Alberto G. Corona 28 Jul '10

28 Jul '10

Thanks Henning , I finally found the problem and an elegant solution (I guess) The problem is not, as I feared, the coalescence of bytestring chunks in more bigger chunks, but the buffering mode of the stream. The stream simply waits until the buffer is full to stream its content. So the solution is either to change the blocking to NoBlocking (with hSetBuffering, and very inefficient) or else to modify Data.BytreString.Lazy.hPut to insert an hFlush after each chunk delivered to the stream: import qualified Data.ByteString as S(hPut) import Data.ByteString.Lazy.Internal(foldrChunks) myhPut :: Handle → ByteString → IO () myhPut h cs = foldrChunks (λc rest → S.hPut h c >> System.IO.hFlush h >> rest) (return ()) cs the original Data.BytreString.Lazy.hPut has not the hFlush step. I had to modify simpleServer to do that and now I control exactly the size of the fragment and the moment when it is delivered, because the mappend instance of ByteString.Lazy respect the chunks created with "pack (String)". I give it to the consideration of the maintainers of Data.ByteString.Lazy (Dons),, because lazy bytestrings, since are a concatenation of user made blocks, have such possibility of controlling precise streaming. Something that neither ordinary strings nor strict bytestring, and I guess nothing else has. Don´t miss out this!. 2010/7/27, Henning Thielemann <lemming(a)henning-thielemann.de>: > > On Tue, 27 Jul 2010, Alberto G. Corona wrote: > >> The question is: are there some way to control bytestring streaming?. >> Can It be done without the stream handler? > > I think there is a function that converts a lazy ByteString to a list of > strict ByteStrings, that should work without copying the chunk data > around. On this chunk list you can do all kind of manipulations, like > merging adjacent small chunks. >

1 0

ANN: syz-0.2.0.0
by Michael D. Adams 28 Jul '10

28 Jul '10

Hi all, This years Workshop on Generic Programming includes a generic zipper for Haskell that defines a Zipper type permitting zipper traversals over arbitrary instances of Data. A Haskell library based on those ideas is now available from Hackage at: http://hackage.haskell.org/package/syz Right now the documentation is very minimal so the best guide would be to have a look at the paper which includes a small tutorial. A pre-print is available at: http://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ Bug reports as well as suggestions, feedback or contributions to the library or the documentation are most welcome and should be sent to me at adamsmd-AT-cs-DOT-indiana-DOT-edu. Michael D. Adams Ph.D. Student Indiana University http://www.cs.indiana.edu/~adamsmd/

1 0

Lists and monads
by Kevin Jardine 28 Jul '10

28 Jul '10

As a Haskell neophyte, one of the things I find confusing is the way that the usual list functions (map, fold, ++, etc.) often cannot be used directly with monadic lists (m [a] or [m a]) but seem to require special purpose functions like ap, mapM etc. I get the idea of separating pure and impure code but am constantly frustrated by the fact that stuff that would be easy outside a monad seems to get more difficult inside, especially list manipulation. As a result I tend to write ugly recursive list functions that would be more appropriate with Python, say. I suspect that things are not quite as difficult as they appear, however, but cannot find any tutorials on monadic list manipulation. Any suggestions for resources in that area? Kevin

6 13

Parsec "Best Practices" examples
by David Place 28 Jul '10

28 Jul '10

Hi, All. I have a compiler written in Parsec and Haskell for a DSL. It's quite rudimentary since I made it for my own use only. I would like to make it useable by a slightly wider circle. For this, I need better error reporting. Currently, it terminates after finding one syntax error. I would like to detect as many syntax errors as possible and report them before terminating. Are there any "best practices" examples of how to do this available? It seems like something many people would have solved already. Cheers, David ____________________ David F. Place Owner, Panpipes Ho! LLC http://panpipesho.com d(a)vidplace.com

2 2

Template Haskell sees into abstract data types
by Serguey Zefirov 28 Jul '10

28 Jul '10

Data.Map.Map and Data.Set.Set are exported abstractly, without exposing knowledge about their internal structure. I cannot directly create my own class instances for them because of that. But I found that I can write Template Haskell code that could do that - those data types could be reified just fine. This is somewhat strange situation. Was it a design decision?

7 13

Class instances on class constraints
by Dušan Kolář 28 Jul '10

28 Jul '10

Hello all, For school purposes, I would like to define something like this: module SetOverList( SetFromList , SetOL(..) ) where type SetFromList a = [a] addEq :: Eq a => a -> SetFromList a -> SetFromList a addEq v [] = [v] addEq v l@(x:xs) = if x==v then l else x : addEq v xs addOrd :: Ord a => a -> SetFromList a -> SetFromList a addOrd v [] = [v] addOrd v l@(x:xs) = case compare x v of GT -> v : l EQ -> l LT -> x : addOrd v xs class SetOL a where addElem :: a -> SetFromList a -> SetFromList a instance (Eq a) => SetOL a where addElem = addEq instance (Ord a) => SetOL a where addElem = addOrd which does not work, of course (Flexible or Undecidable instances won't help). The aim is to have addElem function that works differently according to situation whether a type, which is base of the list/set, is a member of class Eq or Ord. Could you point me or hint me how to get as close as possible to the required solution? Maybe I'm not able to see an obvious way... Thanks, Dušan

2 2

Haskell Forum
by Daniel Díaz 28 Jul '10

28 Jul '10

Hi all, I want to open a Haskell forum based on phpBB, but I need some collaborators for organize its content, and moderate its use. When we have finished, I will open this forum for the entire community of Haskell! If you are interested, mail me: danieldiaz(a)asofilak.es Thanks in advance.

21 39

Int and ByteStrings
by wren ng thornton 28 Jul '10

28 Jul '10

Hey all, Is there a library function (f :: [Int] -> ByteString) such that it's prefix-preserving, and platform independent? GHC-only is fine for now. There are a bunch of functions of that type, but I need those guarantees and I'm hoping someone else has already done it. If there isn't one for Int, has someone already made a package that offers IntMap on Word32, Word64, etc? -- Live well, ~wren

2 2