July 2010 - Haskell-Cafe

ANN: weighted-regexp-0.1.0.0
by Sebastian Fischer 29 Jul '10

29 Jul '10

Hello, this year's ICFP features A Play on Regular Expressions where two Haskell programmers and an automata theory guru develop an efficient purely functional algorithm for matching regular expressions. A Haskell library based on their ideas is now available from Hackage. For more information (and a link to the play) visit: http://sebfisch.github.com/haskell-regexp/ Cheers, Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

8 26

data.binary get reading beyond end of input bytestring?
by Conrad Parker 29 Jul '10

29 Jul '10

Hi, I am reading data from a file as strict bytestrings and processing them in an iteratee. As the parsing code uses Data.Binary, the strict bytestrings are then converted to lazy bytestrings (using fromWrap which Gregory Collins posted here in January: -- | wrapped bytestring -> lazy bytestring fromWrap :: I.WrappedByteString Word8 -> L.ByteString fromWrap = L.fromChunks . (:[]) . I.unWrap ). The parsing is then done with the library function Data.Binary.Get.runGetState: -- | Run the Get monad applies a 'get'-based parser on the input -- ByteString. Additional to the result of get it returns the number of -- consumed bytes and the rest of the input. runGetState :: Get a -> L.ByteString -> Int64 -> (a, L.ByteString, Int64) The issue I am seeing is that runGetState consumes more bytes than the length of the input bytestring, while reporting an apparently successful get (ie. it does not call error/fail). I was able to work around this by checking if the bytes consumed > input length, and if so to ignore the result of get and simply prepend the input bytestring to the next chunk in the continuation. However I am curious as to why this apparent lack of bounds checking happens. My guess is that Get does not check the length of the input bytestring, perhaps to avoid forcing lazy bytestring inputs; does that make sense? Would a better long-term solution be to use a strict-bytestring binary parser (like cereal)? So far I've avoided that as there is not yet a corresponding ieee754 parser. Conrad.

7 13

Announce snm-0.0.2: The Simple Nice-Looking Manual Generator
by Johnny Morrice 29 Jul '10

29 Jul '10

Hi list, Recently, I've been working on a compiler/programming language project.[2] I became rather unstuck when I started spending more time documenting the semantics instead of actually getting to work on the implementation. Hence this program! snm allows you to write clean, web-friendly reports, user guides and manuals without having to edit fickle html. snm allows you to structure your document in a modular fashion. snm document sections are written in yaml and are easy to write and understand. snm is a generator of small, valid xhtml files. Read the snm user guide here: http://www.killersmurf.com/static/snm_help.html snm uses Yaml and generates XHTML, so it's a little like John MacFarlane's yst[1], but yst is for making websites, while snm is exclusively for creating structured reports. It still has a lot of problems, not to mention no support for images, or multiple pages, but I'm finding it usable (enough to document itself!) so I thought it best to share :) Sorry if I have left typos, it's very late Have fun, Johnny [1] John MacFarlane's yst: http://hackage.haskell.org/package/yst [2] Yon aforementioned programming language project, in case anyone fancies a peep. Demoted to reference #2, on account of it not yet compiling code :) http://github.com/elginer/Obelisk

2 1

Search for documentation as data fails with Haskell Platform on Windows 7
by John D. Ramsdell 29 Jul '10

29 Jul '10

I contributed the CPSA package to Hackage, and tried using it on a PC running Windows 7. The package installs six executables and documentation as PDF and XHTML into the package's data directory. Haskell Platform with Cabal installs the package without a problem. It was actually quite smooth and simple. So far so good. The trouble came when I tried to locate the documentation. The XHTML document is called cpsauser.html, but the search command on Windows 7 cannot find the document. Is there some way to tell it to try harder? How are users supposed to know how to locate program documentation when using Windows 7? I'm not much of a Windows user, so let me apologize in advance if this is a silly question, and search is, in fact, easy. John

1 0

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