June 2021 - Haskell-Cafe

Pearl! I just proved theorem about impossibility of monad transformer for parsing with (1) unbiased choice and (2) ambiguity checking before running embedded monadic action (also, I THREAT I will create another parsing lib)
by Askar Safin 18 Jun '21

18 Jun '21

Hi. I hope people here, at haskell-cafe, like various theorem, pearls on parsing, monads, monad transformers and anything like that, right? So, I just proved something interesting for you! Theorem about impossibility of monad transformer for parsing with (1) unbiased choice and (2) ambiguity checking before running embedded monadic action. I already presented it on #haskell in Libera chat, now let me send it here. This is not quite theorem, i. e. I would not say that it keeps with mathematical standards of rigor. --------------------------- I want monad transformer (let's name it ParserT) with following properties (hint: I proved such transformer doesn't exist): - it has unbiased choice (i. e. (<|>) :: ParserT m a -> ParserT m a -> ParserT m a) (this means running parser can give you multiple results) - you can run parser without executing embedded monadic actions. i. e. "run" function should look like this: run :: ParserT m a -> String -> [m a] {- Not m [a] -} I want such function, because I want to do this: run parser, then count number of possible parses, then (if count is equal to one) actually execute embedded monadic action. I. e. I want something like this: parser :: ParserT (Either String) () parser = ..... main :: IO () main = do { input <- ....; case run parser input of { [res] -> do { -- Cool! we got exactly one result! Let's run it case res of { Left e -> putStr $ "Parsing succeed, but we have semantic error: " ++ e; Right () -> putStr "Everything OK"; }; }; _ -> putStr "Cannot parse. 0 parse trees or >1 parse trees"; }; } Now let me state theorem. Theorem. Such transformer doesn't exist. Moreover, even if I replace arbitrary monad "m" with particular monad "Maybe" (or "Either String") the task is still unsolvable. But the task seems achievable using arrows ------------------------------------- Proof. Let's imagine such "ParsecT Maybe" exists. Let's imagine we have such function: char :: Char -> ParserT Maybe Char {- matches supplied char -} Also, keep in mind we have "lift": lift :: Maybe a -> ParserT Maybe a Now let's write this: parseA = char 'a' parseAorA = char 'a' <|> char 'a' contr = do { a <- lift $ Nothing; if a > 5 then parseA else parseAorA; return (); } Now, please, say, what is (run contr "a")? How many elements will (run contr "a") have? If "a > 5", then (run contr "a") will contain one element. If "a <= 5", then (run contr "a") will contain two elements. But we cannot know whether "a > 5", because we cannot extract "a" from "Nothing". So, we got contradiction. QED ----------------- In other words, function "run" with type "ParserT m a -> String -> [m a]" means that we should somehow be able to know count of parses before executing monadic action. But this is impossible, because our parser can contain code like this: (do { a <- lift $ ...; if a then ... else ...; }). I. e. count of parses can depend on value, embedded in inner monad, so we cannot know count of parses before we run embedded inner monadic action. This theorem is not simply out of curiosity. I actually need parsing lib with this properties. 1. I need unbiased choice, because it is compatible with CFGs, and I love CFGs (as opposed to PEG) 2. I need embedding monads, because this allows me to check semantic errors (such as "type mismatch") in time of parsing. I. e. I can simply embed (Either String) monad into parsing monad, and use this (Either String) monad for checking semantic errors 3. I need to know number of parse trees before executing monadic actions (i. e. i need ([m a]) as opposed to (m [a])), because I want to check that number of parses is equal to 1 (if not, then print error), and then extract inner monad (which will contain information about semantic errors). In other words, I want check the input for ambiguity (and print error if it is ambiguous), and if it is not ambiguous, then print possible semantic errors (if any). The possibility of ambiguity detection is whole point of using CFGs as opposed to PEGs (which are always unambiguous, but this unambiguity is simply trick). 4. Every terminal and nonterminal should carry location info (i. e. begin and end of this string). And this location info should be passed implicitly. And it should not be embedded deeply in ASTs I will use. (This means that "happy" is not for me. As well as I understand it cannot implicitly pass location info. In https://github.com/ghc/ghc/blob/master/compiler/GHC/Parser.y I see explicit location management all the time.) 5. Left recursion is not needed So, does such lib exist? Well, I already know such lib should be arrow based (as opposed to monad). So, is there such arrow parsing lib? Embedding arbitrary inner monad is not needed, just embedding (Either String) will go. If there is no such lib, I plan to create my own. This is threat! :) Also, I wrote letter long ago asking for parsing lib with different properties. I included desire for reversibility, among others. Well, this was other task. For my current task I don't need reversibility. == Askar Safin http://safinaskar.com https://sr.ht/~safinaskar https://github.com/safinaskar

3 5

ICFP 2021 Student Research Competition: Call for Submissions
by Sam Tobin-Hochstadt 17 Jun '21

17 Jun '21

ICFP 2021 Student Research Competition Call for Submissions ICFP invites students to participate in the Student Research Competition, which will be held virtually alongside the main conference, in order to present their research and receive feedback from prominent members of the programming language research community. As usual, the SRC consists of three rounds: * Extended abstract * Poster session at ICFP 2021 * ICFP presentation To make the virtual competition fruitful, we will make sure that every student will have an "invited audience" during the poster session. We are also planning to organize a social event for the students. Please visit the SRC website for updates. ### Important Dates Submissions due: 2 July 2021 (Friday) https://icfp21src.hotcrp.com Notification: 16 July 2021 (Friday) Conference: 22 August (Sunday) - 27 August (Friday) ### Submission Details Each submission (referred to as "abstract" below) should include the student author’s name and e-mail address; institutional affiliation; research advisor’s name; ACM student member number; category (undergraduate or graduate); research title; and an extended abstract addressing the following: * Problem and Motivation: Clearly state the problem being addressed and explain the reasons for seeking a solution to this problem. * Background and Related Work: Describe the specialized (but pertinent) background necessary to appreciate the work in the context of ICFP areas of interest. Include references to the literature where appropriate, and briefly explain where your work departs from that done by others. * Approach and Uniqueness: Describe your approach in addressing the problem and clearly state how your approach is novel. * Results and Contributions: Clearly show how the results of your work contribute to programming language design and implementation in particular and to computer science in general; explain the significance of those results. * Submissions must be original research that is not already published at ICFP or another conference or journal. One of the goals of the SRC is to give students feedback on ongoing, unpublished work. Furthermore, the abstract must be authored solely by the student. If the work is collaborative with others and*or part of a larger group project, the abstract should make clear what the student’s role was and should focus on that portion of the work. * Formatting: Submissions must be in PDF format, printable in black and white on US Letter sized paper, and interpretable by common PDF tools. All submissions must adhere to the "ACM Small" template that is available (in both LaTeX and Word formats) from https://www.acm.org/publications/authors/submissions. For authors using LaTeX, a lighter-weight package, including only the essential files, is available from http://sigplan.org/Resources/Author/#acmart-format. The submission must not exceed 3 pages in PDF format. Reference lists do not count towards the 3-page limit. Further information is available at the ICFP SRC website: https://icfp21.sigplan.org/track/icfp-2021-Student-Research-Competition Program Committee: Chair: Anders Miltner (UT Austin) Andreea Costea (NUS Singapore) Andrew Hirsch (MPI-SWS) Liam O'Connor (University of Edinburgh) Lionel Parreaux (HKUST) Daming Zou (ETH Zurich)

1 0

An emotional retrospective on my Haskell journey so far
by Chris Smith 17 Jun '21

17 Jun '21

Hi everyone, I started out writing a blog post about why I chose to become a contributor to the Haskell Foundation. It ended up being a bit of a bigger picture recap of my whole Haskell journey. I would like to share it with you, since many of the people here have been really influential to me over the past 15 years. Thank you all so much. Link: https://cdsmithus.medium.com/why-i-support-the-haskell-foundation-1ac3cda1f… Yes, it's Medium, but it isn't part of their soft paywall, so please don't be afraid to click on it. Cheers, Chris Smith

1 0

Fwd: Haskell grammar ambiguity
by Jon Purdy 17 Jun '21

17 Jun '21

Email fail, pardon the noise; original message below. ---------- Forwarded message --------- From: Jon Purdy <evincarofautumn(a)gmail.com> Date: Wed, Jun 16, 2021 at 1:35 PM Subject: Re: [Haskell-cafe] Haskell grammar ambiguity To: Sven Panne <svenpanne(a)gmail.com> On Wed, Jun 16, 2021 at 12:49 AM Sven Panne <svenpanne(a)gmail.com> wrote: > I consider ambiguous grammars a serious usability bug. > I agree. I always make a point of telling ‘%expect 0’ to Happy. (“More often than not the grammar you write will have conflicts”? Excuse you!) > The BlockArguments proposal introduced lots of additional ambiguities, and > that's the reason why I'm still opposed to it. > I consider BlockArguments a fix for a bug in the Haskell grammar, namely, a redundant production, requiring an unnecessary operator, which causes confusion for some people coming from other languages. In being fixed, however, it exposed other serious grammar issues. So I’d be strongly in favour of fixing those unclear/ambiguous parses by further (incremental) simplification of the grammar. It would be very nice if the extent of lambda/if/&c. were unambiguous, so I think this idea is a step in the right direction. I would also be very pleased if the layout rule were reformulated as a simpler desugaring step, from a token stream annotated with source locations to such a stream with explicit braces and semicolons inserted, rather than being defined in terms of parse errors and papering over edge cases. My ideal would be a simple formal grammar (LALR, PEG, or even operator-precedence) which is machine-validated as unambiguous, with an implementation written by hand to produce nice contextual error messages, which is typed to prove that it accepts the same language as the formal grammar.

1 0

Haskell grammar ambiguity
by Li-yao Xia 17 Jun '21

17 Jun '21

Hello Café, With the BlockArguments proposal[1], the formal grammar of Haskell has become much nicer, with all of the "boring" expression constructs (i.e., other than function or operator application) under one non-terminal: https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0090-b… Its one flaw, inherited from Haskell2010, is ambiguity. I wonder whether that ambiguity is necessary. Currently, a meta-rule fixes that flaw: > The grammar is ambiguous regarding the extent of lambda abstractions, let expressions, and conditionals. The ambiguity is resolved by the meta-rule that each of these constructs extends as far to the right as possible. That is quite informal, so interpreting it takes a bit of thinking. 1. Does the rule make sense? That seems quite likely, but at the same time it seems to depend on some good behavior of the grammar. Like, aren't there grammars where such an "extend far to the right" meta-rule would itself be ambiguous? What's the key criterion for that meta-rule to make sense? 2. How to implement this rule? It might be obvious, with shift-reduce parsing ("shift always"). It also seems feasible with Earley parsing (the only other technique I am familiar with). But, either way, you have to dig into the internals of the chosen parsing method to resolve ambiguities. Instead, what if the grammar were unambiguous to start with? I share an attempt at the bottom of this email. Which brings me to my main two questions: 3. Is this grammar unambiguous? 4. Does it match the meta-rule? I also can't help but think about how it might look like in a hypothetical language report. 5. What are the pros and cons of using a ambiguous or unambiguous grammar for a programming language standard? A plausible starting point is thus: - An ambiguous grammar may be more readable (since there are strictly more choices available), especially if you care more about the AST than the concrete syntax. - An unambiguous grammar is easier to implement: just throw it into an Earley parser. This unambiguous grammar can somewhat easily be "flattened" into the ambiguous one from the report. That challenges the assumption that ambiguous grammars are generally more readable. In fact, the current ambiguous grammar already exposes other concrete syntax concerns (via the distinction between exp, infixexp, fexp, and aexp). In contrast, turning an ambiguous grammar into an unambiguous one takes a bit of effort (when it's possible at all). So if there are ambiguities worth keeping, is there a clear threshold? One other possible issue is that non-ambiguity is a fragile property, so extending the grammar requires extra care. Furthermore, even if the updated grammar is unambiguous, it might not be obvious that it still encodes the intent behind the meta-rule. That meta-rule may still be worth clarifying as a requirement for language extensions at least. Haskell syntax can be pretty, but the process behind it is a wee bit complicated. Regards, Li-yao --- # Unambiguous grammar for expressions (some rules omitted for brevity) # Compared to Haskell2010+BlockArguments, we move the rules for if, lambdas and lets into their own non-terminal rexp, and add four extra rules in exp, ensuring that rexp occurs only to the right end of function/operator applications. # Possibly simplifiable more # * and + represent repetition. # Expressions. exp -> iexp "::" type | iexp # EXTRA RULES with rexp | rexp | iexp qop rexp | iexp qop frexp | frexp # EXTRA SYMBOL rexp # Expressions with right-recursive syntax. rexp -> "if" exp "then" exp "else" exp | "\\" var "->" exp | "let" decls "in" exp # EXTRA (AUXILIARY) SYMBOL frexp # Function application with a trailing block argument. frexp -> aexp aexp* rexp # Infix expression (was infixexp). OLD iexp -> fexp (qop fexp)* # Optional function applications. OLD fexp -> aexp | aexp aexp+ # Atomic expressions. OLD with removed if/lambda/let aexp -> qvar | "[" "]" | "(" ")" | qcon | "(" exp ")" | "do" "{" stmts "}" | "case" exp "of" "{" alts "}"

5 8

IFL2021 second call for papers
by Pieter Koopman 16 Jun '21

16 Jun '21

================================================================================ IFL 2021 33rd Symposium on Implementation and Application of Functional Languages venue: online 1 - 3 September 2021 https://ifl21.cs.ru.nl <https://ifl21-publicity-dot-yamm-track.appspot.com/Redirect?ukey=1NdKhGOLpm…> ================================================================================ News - Paper submission is now open: https://easychair.org/conferences/?conf=ifl21 <https://ifl21-publicity-dot-yamm-track.appspot.com/Redirect?ukey=1NdKhGOLpm…> . - Invited speakers are added: Stephanie Weirich and John Hughes - Sponsor added: Facebook Research <https://ifl21-publicity-dot-yamm-track.appspot.com/Redirect?ukey=1NdKhGOLpm…> Scope The goal of the IFL symposia is to bring together researchers actively engaged in the implementation and application of functional and function-based programming languages. IFL 2021 will be a venue for researchers to present and discuss new ideas and concepts, work in progress, and publication-ripe results related to the implementation and application of functional languages and function-based programming. Industrial track and topics of interest This year's edition of IFL explicitly solicits original work concerning *applications* of functional programming in industry and academia. These contributions will be reviewed by experts with an industrial background. Topics of interest to IFL include, but are not limited to: * language concepts * type systems, type checking, type inferencing * compilation techniques * staged compilation * run-time function specialisation * run-time code generation * partial evaluation * (abstract) interpretation * meta-programming * generic programming * automatic program generation * array processing * concurrent/parallel programming * concurrent/parallel program execution * embedded systems * web applications * (embedded) domain-specific languages * security * novel memory management techniques * run-time profiling performance measurements * debugging and tracing * testing and proofing * virtual/abstract machine architectures * validation, verification of functional programs * tools and programming techniques * applications of functional programming in the industry, including ** functional programming techniques for large applications ** successes of the application functional programming ** challenges for functional programming encountered ** any topic related to the application of functional programming that is interesting for the IFL community Post-symposium peer-review Following IFL tradition, IFL 2021 will use a post-symposium review process to produce the formal proceedings. Before the symposium authors submit draft papers. These draft papers will be screened by the program chairs to make sure that they are within the scope of IFL. The draft papers will be made available to all participants at the symposium. Each draft paper is presented by one of the authors at the symposium. After the symposium every presenter is invited to submit a full paper, incorporating feedback from discussions at the symposium. Work submitted to IFL may not be simultaneously submitted to other venues; submissions must adhere to ACM SIGPLAN's republication policy. The program committee will evaluate these submissions according to their correctness, novelty, originality, relevance, significance, and clarity, and will thereby determine whether the paper is accepted or rejected for the formal proceedings. We plan to publish these proceedings in the International Conference Proceedings Series of the ACM Digital Library, as in previous years. Moreover, the proceedings will also be made publicly available as open access. Important dates Submission deadline of draft papers: 17 August 2021 Notification of acceptance for presentation: 19 August 2021 Registration deadline: 30 August 2021 IFL Symposium: 1-3 September 2021 Submission of papers for proceedings: 6 December 2021 Notification of acceptance: 3 February 2022 Camera-ready version: 15 March 2022 Submission details All contributions must be written in English. Papers must use the ACM two columns conference format, which can be found at: http://www.acm.org/publications/proceedings-template <https://ifl21-publicity-dot-yamm-track.appspot.com/Redirect?ukey=1NdKhGOLpm…> The submission Web page for IFL21 is https://easychair.org/conferences/?conf=ifl21 <https://ifl21-publicity-dot-yamm-track.appspot.com/Redirect?ukey=1NdKhGOLpm…> . Peter Landin Prize The Peter Landin Prize is awarded to the best paper presented at the symposium every year. The honoured article is selected by the program committee based on the submissions received for the formal review process. The prize carries a cash award equivalent to 150 Euros. Organisation IFL 2021 Chairs: Pieter Koopman and Peter Achten, Radboud University, The Netherlands IFL Publicity chair: Pieter Koopman, Radboud University, The Netherlands PC: Peter Achten (co-chair) - Radboud University, Netherlands Thomas van Binsbergen - University of Amsterdam, Netherlands Edwin Brady - University of St. Andrews, Scotland Laura Castro - University of A Coruña, Spain Youyou Cong - Tokyo Institute of Technology, Japan Olaf Chitil - University of Kent, England Andy Gill - University of Kansas, USA Clemens Grelck - University of Amsterdam, Netherlands John Hughes - Chalmers University, Sweden Pieter Koopman (co-chair) - Radboud University, Netherlands Cynthia Kop - Radboud University, Netherlands Jay McCarthey - University of Massachussetts Lowell, USA Neil Mitchell - Facebook, England Jan De Muijnck-Hughes - Glasgow University, Scotland Keiko Nakata - SAP Innovation Center Potsdam, Germany Jurriën Stutterheim - Standard Chartered, Singapore Simon Thompson - University of Kent, England Melinda Tóth - Eötvos Loránd University, Hungary Phil Trinder - Glasgow University, Scotland Meng Wang - University of Bristol, England Viktória Zsók - Eötvos Loránd University, Hungary Virtual symposium Because of the Covid-19 pandemic, this year IFL 2021 will be an online event, consisting of paper presentations, discussions and virtual social gatherings. Registered participants can take part from anywhere in the world. [image: beacon]

1 0

ccall vs capi
by Julian Ospald 14 Jun '21

14 Jun '21

Hi, recently during a ghcup release, we stumbled over yet another `ccall` bug on Darwin: https://github.com/biegunka/terminal-size/pull/16 This took Ben some time to debug (thanks again) and it isn't always clear with such bugs whether something is wrong with GHC/RTS/GC or a library, so this can be a time-sink. It's also not the first time it happened: * https://github.com/haskell/unix/pull/110#issuecomment-613384845 * https://github.com/hasufell/hpath/commit/74d686547e67da3eeae327c84c63f83833… I can't say that I fully understood what the exact difference here is and why it seems to matter much more on Darwin than on other systems. So I think it would be helpful if we could come up with: 1. a clear description of the differences of ccall vs capi 2. an explanation why ccall can lead to terrible bugs on darwin 3. a guideline of when using one over the other is appropriate Not everyone deals with ffi on a regular basis, so I hope the experts here can shed some light! Cheers, Julian

3 2

Need advise with using Quickcheck
by Han Joosten 13 Jun '21

13 Jun '21

Dear café, I want to implement a roundtrip test for a parser/prettyprinter combination. Let me try to explain what I am struggling with. I start with some type definitions of functions I have *data Guarded a =* * Errors (NE.NonEmpty CtxError) | Checked a [Warning]* *parseFoo :: Text -> Guarded Foo* *prettyFoo :: Foo -> Text* The idea is that for all foo :: Foo, the following holds: *parseFoo . prettyFoo $ foo* should be equal to *Checked foo []* Now, if there is a counterexample, I would like to see prettyFoo foo as output, folowed by the show of the Errors part. I have been struggling to get this working, but without luck so far. I am not very familiar with Quickcheck, so that could be the problem too. Any help would be appreciated! Thanks Han

5 6

ZuriHac 2021 is happening in a week!
by Jasper Van der Jeugt 12 Jun '21

12 Jun '21

Hey folks, This is a final reminder that ZuriHac is taking place next weekend, Friday 18 June - Sunday 20 June 2021. Here are a couple of things to know: - You can register and join the Discord server through the following link: https://zureg.zfoh.ch/register/ - There will be the traditional pre-event socializing on Thursday, starting at 19:00 CEST. - We finalised the schedule, and there have been a couple of really cool additions. You can seee the calendar at https://zfoh.ch/zurihac2021/#schedule If you submitted a project, please ping us anytime on Discord in the #helpdesk channel, and we'll set up text and video channels for you. Happy hacking! The Zurich Friends of Haskell - https://zfoh.ch/

1 0

Optimizing Eq instances with reallyUnsafePtrEquality#
by Simon Jakobi 12 Jun '21

12 Jun '21

Hi everyone! In https://github.com/haskell-unordered-containers/unordered-containers/issues… we're wondering whether certain Eq instances, for example record types or strings, could be optimized by including a pointer equality check that detects when an object is compared with itself. Does anyone here have experience with such an optimization? Has this been considered before, for example in GHC's deriving machinery? One complication seems to be the correct handling of fields with irreflexive instances, for example Float and Double. In such a case, pointer equality doesn't imply "==-equality". I'm looking forward to hearing your thoughts on this! :) Cheers, Simon

6 7