- Haskell-Cafe - Haskell.org

attoparsec and backtracking
by Evan Laforge 17 Mar '13

17 Mar '13

I have a couple of problems with attoparsec which I think are related to its always backtrack nature, but maybe there's some other way to solve the same problems. The first is that it's hard to get the right error msg out. For instance, I have a parser that tries to parse a number with an optional type suffix. It's an error if the suffix is unrecognized: p_num :: A.Parser Score.TypedVal p_num = do num <- p_untyped_num suffix <- A.option "" ((:"") <$> A.letter_ascii) case Score.code_to_type suffix of Nothing -> fail $ "p_num expected suffix in [cdsr]: " ++ show suffix Just typ -> return $ Score.Typed typ num However, which error msg shows up depends on the order of the (<|>) alternatives, and in general the global structure of the entire parser, because I think it just backtracks and then picks the last failing backtrack. Even after carefully rearranging all the parsers it seems impossible to get this particular error to bubble up to the top. The thing is, as soon as I see an unexpected suffix I know I can fail entirely right there, with exactly that error msg, but since there's no way to turn off backtracking I think there's no way to do that. The second thing is that I want to lex a single token. I thought I could just parse a term and then see how far I got and then use that index to splitAt the input. But attoparsec doesn't keep track of the current index, so I wrote ((,) <$> p_term <*> A.takeByteString), and then I can use the length of the left over bytestring. But due to backtracking, that changes what p_term will parse. Since takeByteString always succeeds, it will cause p_term to backtrack until it finds some prefix that will match. The result is that instead of failing to parse, "1." will lex as ("1", "."). Since I integrate lexing and parsing (as is common with combinator parsers), and since it seems I can't keep track of byte position with attoparsec, I think I'm out of luck trying to do this the easy way. I think I have to write a separate lexer that tries to have the same behaviour as the parser, but is all separate code. I know attoparsec was designed for speed, and error reporting and source positions are secondary. Am I simply asking too much of it? I originally used parsec, but parsing speed is my main bottleneck, so I don't want to give ground there. Is there a clever way to get attoparsec to do what I want? Or a ByteString or Text parser out there which is fast, but can not backtrack, or keep track of input position? I've heard some good things about traditional alex+happy... of course it would mean a complete rewrite but might be interesting. Has anyone compared the performance of attoparsec vs. alex+happy?

5 7

ANNOUNCE: Ajhc 0.8.0.2 Release
by Kiwamu Okabe 17 Mar '13

17 Mar '13

We are happy to announce Ajhc 0.8.0.2. It's first release announce for Ajhc. Major change on this release is ability to compile Haskell code for tiny CPU. There is demo on tiny CPU at https://github.com/ajhc/demo-cortex-m3. And you can watch demo movie at http://www.youtube.com/watch?v=bKp-FC0aeFE. Perhaps changes on the announce will be merged to jhc. Ajhc's project web site is found at http://ajhc.masterq.net/. You can get Ajhc 0.8.0.2 source code from https://github.com/ajhc/ajhc/tags. ## Changes * Fix warning messages on compiling. * Ready to compile with GHC 7.6.2. * New RTS for tiny CPU. How to use: https://github.com/ajhc/demo-cortex-m3#porting-the-demo-to-a-new-platform - - - Metasepi team

3 3

ICFP 2013: Second Call for Papers
by David Van Horn 16 Mar '13

16 Mar '13

===================================================================== 18th ACM SIGPLAN International Conference on Functional Programming ICFP 2013 Boston, MA, USA, 25-27 September 2013 http://www.icfpconference.org/icfp2013 ===================================================================== Important Dates ~~~~~~~~~~~~~~~ Submissions due: Thursday, 28 March 2013 23:59 UTC-11 (Pago Pago, American Samoa, time) Author response: Wednesday, 22 May 0:00 UTC-11 Friday, 24 May 2013 23:59 UTC-11 Notification: Friday, 7 June 2013 Final copy due: Friday, 5 July 2013 Scope ~~~~~ ICFP 2013 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, and from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects, concurrency, or parallelism. Topics of interest include (but are not limited to): * Language Design: concurrency and distribution; modules; components and composition; metaprogramming; interoperability; type systems; relations to imperative, object-oriented, or logic programming * Implementation: abstract machines; virtual machines; interpretation; compilation; compile-time and run-time optimization; memory management; multi-threading; exploiting parallel hardware; interfaces to foreign functions, services, components, or low-level machine resources * Software-Development Techniques: algorithms and data structures; design patterns; specification; verification; validation; proof assistants; debugging; testing; tracing; profiling * Foundations: formal semantics; lambda calculus; rewriting; type theory; monads; continuations; control; state; effects; program verification; dependent types * Analysis and Transformation: control-flow; data-flow; abstract interpretation; partial evaluation; program calculation * Applications and Domain-Specific Languages: symbolic computing; formal-methods tools; artificial intelligence; systems programming; distributed-systems and web programming; hardware design; databases; XML processing; scientific and numerical computing; graphical user interfaces; multimedia programming; scripting; system administration; security * Education: teaching introductory programming; parallel programming; mathematical proof; algebra * Functional Pearls: elegant, instructive, and fun essays on functional programming * Experience Reports: short papers that provide evidence that functional programming really works or describe obstacles that have kept it from working If you are concerned about the appropriateness of some topic, do not hesitate to contact the program chair. Abbreviated instructions for authors ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * By Thursday, 28 March 2013, 23:59 UTC-11 (American Samoa time), submit a full paper of at most 12 pages (6 pages for an Experience Report), including bibliography and figures. The deadlines will be strictly enforced and papers exceeding the page limits will be summarily rejected. * Authors have the option to attach supplementary material to a submission, on the understanding that reviewers may choose not to look at it. * Each submission must adhere to SIGPLAN's republication policy, as explained on the web at http://www.sigplan.org/Resources/Policies/Republication * Authors of resubmitted (but previously rejected) papers have the option to attach an annotated copy of the reviews of their previous submission(s), explaining how they have addressed these previous reviews in the present submission. If a reviewer identifies him/herself as a reviewer of this previous submission and wishes to see how his/her comments have been addressed, the program chair will communicate to this reviewer the annotated copy of his/her previous review. Otherwise, no reviewer will read the annotated copies of the previous reviews. Overall, a submission will be evaluated according to its relevance, correctness, significance, originality, and clarity. It should explain its contributions in both general and technical terms, clearly identifying what has been accomplished, explaining why it is significant, and comparing it with previous work. The technical content should be accessible to a broad audience. Functional Pearls and Experience Reports are separate categories of papers that need not report original research results and must be marked as such at the time of submission. Detailed guidelines on both categories are on the conference web site. Proceedings will be published by ACM Press. Authors of accepted submissions are expected to transfer the copyright to the ACM. Presentations will be videotaped and released online if the presenter consents. Formatting: Submissions must be in PDF format printable in black and white on US Letter sized paper and interpretable by Ghostscript. Papers must adhere to the standard ACM conference format: two columns, nine-point font on a ten-point baseline, with columns 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 2pc (0.33in). A suitable document template for LaTeX is available:http://www.acm.org/sigs/sigplan/authorInformation.htm Submission: Submissions will be accepted on the web athttps://www.easychair.org/conferences/?conf=icfp2013 . Improved versions of a paper may be submitted at any point before the submission deadline using the same web interface. Author response: Authors will have a 72-hour period, starting at 0:00 UTC-11 on Wednesday, 22 May 2013, to read reviews and respond to them. Special Journal Issue: There will be a special issue of the Journal of Functional Programming with papers from ICFP 2013. The program committee will invite the authors of select accepted papers to submit a journal version to this issue. General Chair: Greg Morrisett, Harvard University Program Chair: Tarmo Uustalu, Institute of Cybernetics, Tallinn Program Committee: Thorsten Altenkirch, University of Nottingham Olaf Chitil, University of Kent Silvia Ghilezan, University of Novi Sad Michael Hanus, Christian-Albrechts-Universität zu Kiel Fritz Henglein, University of Copenhagen Mauro Jaskelioff, Universidad Nacional de Rosario Alan Jeffrey, Alcatel-Lucent Bell Labs Shin-ya Katsumata, Kyoto University Shriram Krishnamurthi, Brown University John Launchbury, Galois Ryan Newton, Indiana University Sungwoo Park, Pohang University of Science and Technology Sam Staton, University of Cambridge Nikhil Swamy, Microsoft Research, Redmond, WA Dimitrios Vytiniotis, Microsoft Research, Cambridge

1 0

ANNOUNCE: Win32-services
by Michael Steele 16 Mar '13

16 Mar '13

I uploaded a new packaged named Win32-services. This library is a partial binding to the Win32 System Services API. It's now easier to write Windows service applications in Haskell. The hackage page <http://hackage.haskell.org/package/Win32-services> [1] demonstrates simple usage. There are also 2 examples included with the sources. One is a translation of Microsoft's official example. [1]: http://hackage.haskell.org/package/Win32-services -- Michael Steele

2 1

ANN: Monad.Reader Issue 21
by Edward Z. Yang 16 Mar '13

16 Mar '13

I am pleased to announce that Issue 21 of the Monad Reader is now available. http://themonadreader.files.wordpress.com/2013/03/issue21.pdf Issue 21 consists of the following two articles: * "A Functional Approach to Neural Networks" by Amy de Buitléir, Michael Russell, Mark Daly * "Haskell ab initio: the Hartree-Fock Method in Haskell" by Felipe Zapata, Angel J. Alvarez Feel free to browse the source files. You can check out the entire repository using Git: git clone https://github.com/ezyang/tmr-issue21.git If you’d like to write something for Issue 22, please get in touch! Cheers, Edward

1 0

Re: [Haskell-cafe] attoparsec and backtracking
by wren ng thornton 16 Mar '13

16 Mar '13

On 3/15/13 3:29 PM, Evan Laforge wrote: > However, which error msg shows up depends on the order of the (<|>) > alternatives, and in general the global structure of the entire > parser, because I think it just backtracks and then picks the last > failing backtrack. Even after carefully rearranging all the parsers > it seems impossible to get this particular error to bubble up to the > top. The thing is, as soon as I see an unexpected suffix I know I can > fail entirely right there, with exactly that error msg, but since > there's no way to turn off backtracking I think there's no way to do > that. I had some similar issues recently. The trick is figuring out how to convince attoparsec to commit to a particular alternative. For example, consider the grammar: A (B A)* C; where if the B succeeds then we want to commit to parsing an A (and if it fails then return A's error, not C's). To simplify things, let's drop the leading A since it's not part of the problem. And let's try to parse an invalid string like "BX" (or "BABX"). The key point is that, bad = (pB *> pure (:) <*> pA <*> bad) <|> (pC *> pure []) is different than, good = do e <- eitherP pB pC -- (Left <$> pB) <|> (Right <$> pC) case e of Left _ -> (:) <$> pA <*> good Right _ -> pure [] In particular, the first one is bad (for our purposes) because due to hoisting the choice up high, after parsing the B we fail to commit, so when parsing A fails we'll backtrack over the B and try C instead. Assuming C doesn't overlap with B, we'll then report C's error. Whereas the latter is good because due to pushing the choice down, once we've parsed B (or C) we're committed to that choice; so when A fails, we'll report A's error (or backtrack to the lowest choice that dominates the call to good). Attoparsec does indeed just report the failure generated by the final parse, so you'll have to refactor things to recognize which sort of token you're looking for (e.g., p_num vs p_identifier or whatever), and then commit to that choice before actually parsing the token. It's not very modular that way, but I think that's the only option right now. It shouldn't be too hard to design a combinator for doing a hard commit (by discarding the backtrack continuation); but that has modularity issues of its own... Another option, of course, is to drop down to performing lexing on the ByteString itself (e.g., [1]) and then wrap those individual lexers to work as attoparsec Parsers. Even if using attoparsec for the heavy lifting, this is a good approach for maximizing performance of the lexing step. [1] <http://hackage.haskell.org/package/bytestring-lexing> -- Live well, ~wren

1 0

Open-source projects for beginning Haskell students?
by Brent Yorgey 15 Mar '13

15 Mar '13

Hi everyone, I am currently teaching a half-credit introductory Haskell class for undergraduates. This is the third time I've taught it. Both of the previous times, for their final project I gave them the option of contributing to an open-source project; a couple groups/individuals took me up on it and I think it ended up being a modest success. So I'd like to do it again this time around, and am looking for particular projects I can suggest to them. Do you have an open-source project with a few well-specified tasks that a relative beginner (see below) could reasonably make a contribution towards in the space of about four weeks? I'm aware that most tasks don't fit that profile, but even complex projects usually have a few "simple-ish" tasks that haven't yet been done just because "no one has gotten around to it yet". If you have any such projects, I'd love to hear about it! Just send me a paragraph or so describing your project and explaining what task(s) you could use help with --- something that I could put on the course website for students to look at. Here are a few more details: * The students will be working on the projects from approximately the end of this month through the end of April. During the next two weeks they would be contacting you to discuss the possibility of working on your project. * By "relative beginner" I mean someone familiar with the material listed here: http://www.cis.upenn.edu/~cis194/lectures.html and just trying to come to terms with Applicative and Monad. They definitely do not know much if anything about optimization/profiling, GADTs, the mtl, or Haskell-programming-in-the-large. (Although part of the point of the project is to teach them a bit about programming-in-the-(medium/large)). * What I would hope from you is a willingness to exchange email and/or chat with the student(s) over the course of the project, to give them a bit of guidance/mentoring. I am certainly willing to help on that front, but of course I probably don't know much about your particular project. Thanks! -Brent

17 20

PPDP 2013: Call for Papers
by Tom Schrijvers 15 Mar '13

15 Mar '13

===================================================================== Call for papers 15th International Symposium on Principles and Practice of Declarative Programming PPDP 2013 Special Issue of Science of Computer Programming (SCP) Madrid, Spain, September 16-18, 2013 (co-located with LOPSTR 2013) http://users.ugent.be/~tschrijv/PPDP2013/ ====================================================================== PPDP 2013 is a forum that brings together researchers from the declarative programming communities, including those working in the logic, constraint and functional programming paradigms, but also embracing a variety of other paradigms such as visual programming, executable specification languages, database languages, and knowledge representation languages. The goal is to stimulate research in the use of logical formalisms and methods for specifying, performing, and analysing computations, including mechanisms for mobility, modularity, concurrency, object-orientation, security, verification and static analysis. Papers related to the use of declarative paradigms and tools in industry and education are especially solicited. Topics of interest include, but are not limited to: * Functional programming * Logic programming * Answer-set programming * Functional-logic programming * Declarative visual languages * Constraint Handling Rules * Parallel implementation and concurrency * Monads, type classes and dependent type systems * Declarative domain-specific languages * Termination, resource analysis and the verification of declarative programs * Transformation and partial evaluation of declarative languages * Language extensions for security and tabulation * Probabilistic modelling in a declarative language and modelling reactivity * Memory management and the implementation of declarative systems * Practical experiences and industrial application This year the conference will be co-located with the 23nd International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2013) and held in cooperation with ACM SIGPLAN. The conference will be held in Madrid, Spain. Previous symposia were held at Leuven (Belgium), Odense (Denmark), Hagenberg (Austria), Coimbra (Portugal), Valencia (Spain), Wroclaw (Poland), Venice (Italy), Lisboa (Portugal), Verona (Italy), Uppsala (Sweden), Pittsburgh (USA), Florence (Italy), Montreal (Canada), and Paris (France). Papers must describe original work, be written and presented in English, and must not substantially overlap with papers that have been published or that are simultaneously submitted to a journal, conference, or workshop with refereed proceedings. Work that already appeared in unpublished or informally published workshop proceedings may be submitted (please contact the PC chair in case of questions). Proceedings will be published by ACM Press* After the symposium, a selection of the best papers will be invited to extend their submissions in the light of the feedback solicited at the symposium. The papers are expected to include at least 30% extra material over and above the PPDP version. Then, after another round of reviewing, these revised papers will be published in a special issue of SCP with a target publication date by Elsevier of 2014. Important Dates Abstract Submission: May 27, 2013 Paper submission: May 30, 2013 Notification: July 4, 2013 Camera-ready: July 21, 2013 Symposium: September 16-18, 2013 Invites for SCP: October 2, 2013 Submission of SCP: December 11, 2013 Notification from SCP: February 22, 2014 Camera-ready for SCP: March 14, 2014 Authors should submit an electronic copy of the paper (written in English) in PDF. Each submission must include on its first page the paper title; authors and their affiliations; abstract; and three to four keywords. The keywords will be used to assist us in selecting appropriate reviewers for the paper. Papers should consist of no more than 12 pages, formatted following the ACM SIG proceedings template (option 1). The 12 page limit must include references but excludes well-marked appendices not intended for publication. Referees are not required to read the appendices, and thus papers should be intelligible without them. Program Committee Sergio Antoy Portland State University, USA Manuel Carro IMDEA Software Institute, Spain Iliano Cervesato Carnegie Mellon University, Qatar Agostino Dovier Universita degli Studi di Udine, Italy Maria Garcia de la Banda Monash University, Australia Ralf Hinze University of Oxford, UK Yukiyoshi Kameyama University of Tsukuba, Japan Oleg Kiselyov USA Yanhong Annie Liu State University of New York at Stony Brook, USA Stefan Monnier Universite de Montreal, Canada Alan Mycroft University of Cambrige, UK Bruno C. d. S. Oliveira National University of Singapore, Singapore Alberto Pettorossi Universita di Roma Tor Vergata, Italy Enrico Pontelli New Mexico State University, USA Kristoffer Rose IBM Research, USA Sukyoung Ryu KAIST, South Korea Vitor Santos Costa University of Porto, Portugal Torsten Schaub University Potsdam, Germany Tom Schrijvers Ghent University, Belgium Martin Sulzmann Hochschule Karlsruhe, Germany Wouter Swierstra Universiteit Utrecht, The Netherlands Tarmo Uustalu Institute of Cybernetics, Estonia Janis Voigtlaender University of Bonn, Germany Meng Wang Chalmers University of Technology, Sweden Jan Wielemaker Universiteit van Amsterdam, The Netherlands Program Chair Tom Schrijvers Department of Applied Mathematics and Computer Science Ghent University 9000 Gent, Belgium General Chair Ricardo Pena Facultad de Informatica Universidad Complutense de Madrid 28040 Madrid, Spain * Confirmation pending

1 0

Lazy object deserialization
by Scott Lawrence 15 Mar '13

15 Mar '13

Hey all, All the object serialization/deserialization libraries I could find (pretty much just binary and cereal) seem to be strict with respect to the actual data being serialized. In particular, if I've serialized a large [Int] to a file, and I want to get the first element, it seems I have no choice but to deserialize the entire data structure. This is obviously an issue for large data sets. There are obvious workarounds (explicitly fetch elements from the "database" instead of relying on unsafeInterleaveIO to deal with it all magically), but it seems like it should be possible to build a cereal-like library that allows proper lazy deserialization. Does it exist, and I've just missed it? Thanks, -- Scott Lawrence Linux baidar 3.7.10-1-ARCH #1 SMP PREEMPT Thu Feb 28 09:50:17 CET 2013 x86_64 GNU/Linux

4 5

Where's the case? or The difference between simpl and prep
by Tom Ellis 15 Mar '13

15 Mar '13

The -ddump-simpl output below doesn't contain a case corresponding to the seq in sum', but the -ddump-prep does. Isn't the output from simpl the input to prep? If so, where does the case reappear from? If not, how are simpl and prep related? It seems to have something to do with "Str=DmdType SS" but I don't understand. This seems to come from the IdInfo on the Id which is the binder "Test.sum'" but [1] says that this information is optional so it seems strange that such crucial information would be encoded there. Thanks, Tom [1] http://www.haskell.org/ghc/docs/7.6.2/html/libraries/ghc-7.6.2/IdInfo.html#… % cat Test.hs module Test where sum' :: [Integer] -> Integer -> Integer sum' [] n = n sum' (x:xs) n = n `seq` sum' xs (n + x) % ghc -fforce-recomp -ddump-simpl -O2 Test.hs [1 of 1] Compiling Test ( Test.hs, Test.o ) ==================== Tidy Core ==================== Result size = 14 Rec { Test.sum' [Occ=LoopBreaker] :: [GHC.Integer.Type.Integer] -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer [GblId, Arity=2, Caf=NoCafRefs, Str=DmdType SS] Test.sum' = \ (ds_daw :: [GHC.Integer.Type.Integer]) (n_a9J :: GHC.Integer.Type.Integer) -> case ds_daw of _ { [] -> n_a9J; : x_a9K xs_a9L -> Test.sum' xs_a9L (GHC.Integer.Type.plusInteger n_a9J x_a9K) } end Rec } % ghc -fforce-recomp -ddump-prep -O2 Test.hs [1 of 1] Compiling Test ( Test.hs, Test.o ) ==================== CorePrep ==================== Result size = 17 Rec { Test.sum' [Occ=LoopBreaker] :: [GHC.Integer.Type.Integer] -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer [GblId, Arity=2, Caf=NoCafRefs, Str=DmdType SS, Unf=OtherCon []] Test.sum' = \ (ds_saQ :: [GHC.Integer.Type.Integer]) (n_saS :: GHC.Integer.Type.Integer) -> case ds_saQ of _ { [] -> n_saS; : x_saW xs_saV -> case GHC.Integer.Type.plusInteger n_saS x_saW of sat_saZ { __DEFAULT -> Test.sum' xs_saV sat_saZ } } end Rec }

2 2