- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] if-then without -else?
by Rodrigo Stevaux 01 Sep '18

01 Sep '18

> > which cannot be prohibited statically > if we want both the language to be Turing complete, > and type inference to be decidable. > > Could you be so kind as to give a hint on literature that could help me understand this statement?

2 2

Re: [Haskell-cafe] Alternative instance for non-backtracking parsers
by Olaf Klinke 01 Sep '18

01 Sep '18

>Hello, Olaf. I have some distrust of elegant solutions (one of them are >C.P. libs). I am a mathematician, I trust a lot in elegance and beauty. As long as the performance penalty is not prohibitively large, I'd prefer a beautiful implementation over an aggressively optimized one. At least when the code does not live in some real-time system. Certainly there are cases where you absolutely need speed or low memory footprint. > For example, I read that they have problems with memory >consuming (famous article about arrow-based parsers), also your example >(my own experience includes a lot of tricks which I don't like)... So >(but this is my IMHO) for big and serious project with parsing of >something complex I will use bindings to good known parser libraries... I consider Parsec and it descendants good and known. I could not write something like that. Currently I rely on megaparsec because of its informative error messages, knowing that I can switch to one of the siblings without much effort when I need more speed. >Maybe something like this: https://github.com/markwright/antlrc. Btw, >Happy looks still live (https://github.com/simonmar/happy) Have you used any of the above? > >I use "Read"-style parsers for small constructions only, so fail of such >small parser is only case where error is producing and I do it >explicitly (as biggest example: header of Git patch). > >Olaf, what do you think about > 1. http://hackage.haskell.org/package/frisby Frisby looks quite old, as it has idiosyncratic combinators for stuff now in Data.Functor. I've never used it, so I can't tell what its strengths are. Can you? > 2. http://tanakh.github.io/Peggy Notice that in the examples of bothy frisby and peggy, parsing a number only parses a string of digits, then passes it to 'read', i.e. another parser. Is that efficient, elegant parsing? I'm nevertheless intrigued by PEG parsers, because I once read about the connection between grammars and compression: A set of production rules can be quite a bit smaller than the actual text. This turns parsing upside down: The text is constant, the grammar unknown. Olaf

2 1

Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 180, Issue 32
by Michal J Gajda 01 Sep '18

01 Sep '18

I got 4.7s for similar amount of data in 2013. However I was pretty sure that fully inlined implementation could potentially go 5x faster. http://hackage.haskell.org/package/hPDB Please check xeno XML parser benchmarks for another example. https://hackage.haskell.org/package/xeno On Fri, 31 Aug 2018 at 14:41, <haskell-cafe-request(a)haskell.org> wrote: > Send Haskell-Cafe mailing list submissions to > haskell-cafe(a)haskell.org > > To subscribe or unsubscribe via the World Wide Web, visit > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > or, via email, send a message with subject or body 'help' to > haskell-cafe-request(a)haskell.org > > You can reach the person managing the list at > haskell-cafe-owner(a)haskell.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Haskell-Cafe digest..." > Today's Topics: > > 1. Re: HDBC packages looking for maintainer (Tobias Dammers) > 2. Re: Alternative instance for non-backtracking parsers > (Olaf Klinke) > 3. Re: Alternative instance for non-backtracking parsers > (Bardur Arantsson) > > > > ---------- Forwarded message ---------- > From: Tobias Dammers <tdammers(a)gmail.com> > To: haskell-cafe(a)haskell.org > Cc: > Bcc: > Date: Thu, 30 Aug 2018 15:24:04 +0200 > Subject: Re: [Haskell-cafe] HDBC packages looking for maintainer > Hi, > > I'd be interested. I've used HDBC on a few projects, and my yeshql > library was originally built with HDBC as the only backend. It would be > a terrible shame to see this bitrot. > > Cheers, > > Tobias (tdammers on github etc.) > > On Mon, Aug 13, 2018 at 12:07:38PM +0200, Erik Hesselink wrote: > > Hi all, > > > > I've been the maintainer for some of the HDBC packages for a while now. > > Sadly, I've mostly neglected them due to lack of time and usage. While > the > > packages mostly work, there are occasional pull requests and updates for > > new compiler versions. > > > > Because of this I'm looking for someone who wants to take over HDBC and > > related packages [1]. If you use HDBC and would like to take over > > maintainership, please let me know and we can get things set up. > > > > Regards, > > > > Erik > > > > [1] https://github.com/hdbc > > > _______________________________________________ > > Haskell-Cafe mailing list > > To (un)subscribe, modify options or view archives go to: > > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > > Only members subscribed via the mailman list are allowed to post. > > > -- > Tobias Dammers - tdammers(a)gmail.com > > > > > ---------- Forwarded message ---------- > From: Olaf Klinke <olf(a)aatal-apotheke.de> > To: PY <aquagnu(a)gmail.com> > Cc: haskell-cafe <haskell-cafe(a)haskell.org> > Bcc: > Date: Thu, 30 Aug 2018 20:21:07 +0200 > Subject: Re: [Haskell-cafe] Alternative instance for non-backtracking > parsers > > Hello, Olaf. I have some distrust of elegant solutions (one of them are > > C.P. libs). > > I have a program that parses several CSV files, one of them 50MB in size, > and writes its result as HTML. When I started optimizing, the execution > time was 144 seconds. Profiling (thanks to Jasper Van der Jeugt for writing > profiteur!) revealed that most of the time was spent parsing and > postprocessing the 50MB CSV file. Changing the data structure of the > postprocessing stage cut down the execution time to 32 seconds, but still > the majority is spent on parsing. > Then I realized that (StateT String Maybe) is a parser which conveniently > has all the class instances one needs, most notably its Alternative > instance make it a backtracking parser. After defining a few combinators I > was able to swap out my megaparsec parser against the new parser, which > slashed execution time in half. Now most of the parsing time is dedicated > to transforming text to numbers and dates. I doubt that parsing time can be > reduced much further [*]. The new parser was identical to the old parser, > only the combinators now come from another module. That is the elegant > thing about monadic parser libraries. > I will now use the fast parser by default, and if it returns a Nothing, > the program will suggest a command line flag that switches to the original > megaparsec parser, exactly telling the user where the parse failed and why. > I am not sure whether there is another family of parsers that have > interfaces so similar that switching from one package to another is as > effortless as monadic parsers. > > Cheers > Olaf > > [*] To the parser experts on this list: How much time should a parser take > that processes a 50MB, 130000-line text file, extracting 5 values (String, > UTCTime, Int, Double) from each line? > > > > ---------- Forwarded message ---------- > From: Bardur Arantsson <spam(a)scientician.net> > To: haskell-cafe(a)haskell.org > Cc: > Bcc: > Date: Thu, 30 Aug 2018 21:43:55 +0200 > Subject: Re: [Haskell-cafe] Alternative instance for non-backtracking > parsers > On 30/08/2018 20.21, Olaf Klinke wrote: > >> Hello, Olaf. I have some distrust of elegant solutions (one of them are > >> C.P. libs). > > > > [*] To the parser experts on this list: How much time should a parser > take that processes a 50MB, 130000-line text file, extracting 5 values > (String, UTCTime, Int, Double) from each line? > > Not an expert, but for something as (relatively!) standard as CSV, I'd > probably go for a specialized solution like 'cassava', which seems like > it does quite well according to https://github.com/haskell-perf/csv > > Based purely the lines/second numbers on that page and the number you've > given, I'd guesstimate that your parsing could potentially be as fast as > (3.185ms / 1000 lines) * 130000 lines = 414.05ms = 0.4 s. > > (Of coure that still doesn't account for extracting the Int, Double, > etc., but there are also specialized solutions for that which should be > pretty hard to beat, see e.g. bytestring-lexing.) > > It's also probably a bit less elegant than a generic parsec-like thing, > but that's to be expected for a more special-case solution. > > Regards, > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >

2 1

Installing hsdev on windows
by Yotam Ohad 01 Sep '18

01 Sep '18

Hi cafe, I installed haskell platform for windows 10 and then ran `cabal install hsdev` I got the following error: Resolving dependencies... cabal: Could not resolve dependencies: [__0] trying: hsdev-0.3.1.4 (user goal) [__1] trying: hlint-2.1.10 (dependency of hsdev) [__2] trying: haskell-src-exts-1.20.2 (dependency of hsdev) [__3] next goal: ghc-syb-utils (dependency of hsdev) [__3] rejecting: ghc-syb-utils-0.3.0.0 (conflict: hsdev => ghc-syb-utils>=0.2.3 && <0.3) [__3] trying: ghc-syb-utils-0.2.3.3 [__4] next goal: ghc (dependency of hsdev) [__4] rejecting: ghc-8.4.3/installed-8.4..., ghc-8.4.3, ghc-8.4.1 (conflict: ghc-syb-utils => ghc>=7.0 && <8.4) [__4] rejecting: ghc-8.2.2, ghc-8.2.1 (conflict: hsdev => ghc==8.4.*) After searching the rest of the dependency tree exhaustively, these were the goals I've had most trouble fulfilling: hsdev, haskell-src-exts, ghc-mod, hlint, base, ghc, ghc-syb-utils Any Ideas on how to solve this? I'm clueless thanks

3 2

Parsing Haskell with Layout
by Benjamin Redelings 30 Aug '18

30 Aug '18

Hi, Section 10.3 of the Haskell 2010 report describes the layout rule for Haskell in terms of rules for inserting curly braces and semicolons into the token stream. I'm not sure of the theory behind implementing Note 5 in section 10.3. This says roughly that we insert a "}" token after token t[n] if the tokens t[1]...t[n+1] have no valid parses, and the sequence of tokens t[1] ... t[n] followed by "}" DO have a valid parse. I think this allows you to write f z = let x=2;y=3 in x+y+z However, except for Note 5, it seems like you could do a simple preprocessing step on the token stream to insert "{", ";", and "}" before parsing. Note 5 seems more complicated. (I feel like I read a note somewhere that said "read this and weep" and then failed to implement Note 5. But now I can't remember where I read this.) In simple explanations like Write you a haskell (http://dev.stephendiehl.com/fun/008_extended_parser.html) it seems that the approach is simply to ignore Note 5. Can anyone fill me in on (a) what concepts are assumed by the report that would make it "obvious" how Note 5 is supposed to be implemented? (b) a simple (hopefully) implementation strategy for implementing it? I'm looking for a language-independent approach for parsing. I did see some mention of error-correcting parsers in the Parsec paper, which might allow adding the "}" at a parse error. But I see there is a paper called " An error correcting parser for context free grammars that takes less than cubic time". The "less than cubic time" seems rather worrisome, so I don't know if this is the right approach. Also, when using parsec, it seems that you might get an idea how many tokens are a valid prefix of the grammer when the token stream fails to parse. Hence, you could try inserting a "}" into the token stream at the point of a parse error. However, a naive approach would then require re-parsing the whole stream from the beginning until each parse error, which seems very expensive. Thanks for any help! -BenRI

3 3

Dependent types, weak references, and stable names
by David Feuer 29 Aug '18

29 Aug '18

I just realized that dependent types should let us do some things with weak references and stable names less awkwardly. In particular, there are two invariants that are not (and cannot be) expressed in the type system at present: 1. If two stable names are equal, then their underlying objects are equal. 2. If a weak reference was built using a key and a value, and the key is alive, then the value is also alive. I hope we'll be able to express these with Dependent Haskell, using whatever the real syntax will be. data Weak :: k -> Type -> Type mkWeak :: (key :: k) -> v -> IO () -> IO (Weak key v) deRefWeakSurely :: (key :: k) -> Weak key v -> IO v -- Intentionally omitted: finalize data StableName :: k -> Type makeStableName :: (key :: k) -> IO (StableName key) eqStableName :: StableName x -> StableName y -> Maybe (x :~: y) The idea is that we can calculate the StableName of a key, look for that that in a hash table of weak pointers, and if we find it, we get evidence that we can use to dereference the weak pointer (deRefWeakSurely would use touch# under the hood, but that's not our concern).

2 1

Setting RTS thread names useful?
by Viktor Dukhovni 29 Aug '18

29 Aug '18

The RTS sets thread names on Linux, but not other POSIX platforms. FreeBSD has the requesite functionality, and the patch below can enable it. Not sure whether this is in fact useful, since all threads would get the same name ("ghc_worker"): diff --git a/rts/posix/OSThreads.c b/rts/posix/OSThreads.c index 7dcf0eed15..9d2d9a897e 100644 --- a/rts/posix/OSThreads.c +++ b/rts/posix/OSThreads.c @@ -139,6 +139,9 @@ createOSThread (OSThreadId* pId, char *name STG_UNUSED, pthread_detach(*pId); #if defined(HAVE_PTHREAD_SETNAME_NP) pthread_setname_np(*pId, name); +#elif defined(freebsd_HOST_OS) + /* Since FreeBSD 5.1 */ + pthread_set_name_np(*pId, name); #endif } return result; On Linux the thread name is taken from the static variable "program_invocation_short_name", which is again the same for all threads of each program, but is not globally the same. FreeBSD could get the same result with getprogname(3). The question still remains as to whether setting such thread names is useful or pointless... -- Viktor.

2 1

Re: [Haskell-cafe] Ghc error messages on Windows
by Olaf Klinke 29 Aug '18

29 Aug '18

Kees, the strange symbols are escape codes for coloring the output. Newer GHCs color the error messages, and what you see is when GHC thinks it prints to a color terminal but the terminal can not handle colors. I don't know how to switch that off, though. Olaf

1 0

Mapping of async tasks to threads?
by Viktor Dukhovni 29 Aug '18

29 Aug '18

I have an application that is largely latency-bound, it operates on hundreds of concurrent DNS lookup tasks, to process workloads of millions to tens of millions such tasks. Each task is spawned via Control.Concurrent.Async.async, and the code is compiled with "-threaded", and runs with the "capability" count set to 4: $ ps -o command= -p $(pgrep -x danescan) danescan ... +RTS -N4 ... The main task collects batches of outputs from the worker tasks and stores the results in a database. With the worker count set to 350, looking at per-thread "ps" output on FreeBSD, I see 24 threads of which 3 look idle, 20 seem to be doing the DNS work (with a few noticeably less than the rest), and one is the main thread doing the database updates: $ ps -o pid,lwp,time,mwchan,msgrcv,msgsnd,state -H -p $(pgrep -x danescan) | sort -k5n PID LWP TIME MWCHAN MSGRCV MSGSND STAT 38083 100763 0:00.00 uwait 0 0 I+ 38083 101152 0:00.00 uwait 0 0 I+ 38083 101922 0:00.00 uwait 0 0 I+ 38083 101343 0:02.29 uwait 27194 27627 I+ 38083 101335 0:04.30 uwait 51689 52517 I+ 38083 101391 0:13.33 uwait 173618 177160 S+ 38083 101917 0:22.63 kqread 295420 300894 S+ 38083 101362 0:28.73 uwait 371419 378350 I+ 38083 101349 0:46.11 uwait 594307 604816 I+ 38083 101352 0:49.65 uwait 641703 653557 S+ 38083 101370 0:53.93 select 699057 712217 S+ 38083 101358 0:58.15 uwait 757636 771437 S+ 38083 101376 1:00.84 kqread 794335 809328 S+ 38083 101375 1:02.31 uwait 806276 821284 S+ 38083 101342 1:02.34 uwait 809367 823963 S+ 38083 101244 1:03.26 select 812395 827329 S+ 38083 101360 1:03.47 uwait 815955 831710 S+ 38083 101356 1:03.03 uwait 818215 833649 I+ 38083 101364 1:03.54 uwait 825807 841300 S+ 38083 101347 1:03.89 uwait 832981 848893 S+ 38083 101334 1:04.42 kqread 836132 851386 S+ 38083 101357 1:06.04 uwait 859308 875754 S+ 38083 101134 1:06.67 kqread 859410 875176 S+ 38083 100655 5:36.98 uwait 11780649 11780685 S+ The number of open UDP DNS query sockets matches what I expect (each active query uses a fresh socket, closing it when the results arrive): $ lsof -n -P -i -a -p $(pgrep -x danescan) | egrep -c '(TCP|UDP).*:53$' 349 How is the actual thread count related to the RTS "-N" option? I did not expect to see 20 threads... -- Viktor.

1 0

Re: [Haskell-cafe] Alternative instance for non-backtracking parsers
by Olaf Klinke 28 Aug '18

28 Aug '18

Thanks to Doaitse for the example. I yet have to wrap my head around it (since I don't know how pChainr is related to <|>) but playing with q parsing the empty string is a good start. When you said > One might expect <|> to be associative, but even that is in no way guaranteed. I suppose you meant that type class laws can not be enforced, because the documentation of Alternative states that <|> should be associative. It would be quite horrible if the Alternative instances of parsers weren't. @Paul: I think that parser combinator libraries are one of the most wonderful things functional programming has given us. How else would you parse your input data? Anything cobbled together manually with the help of some Read instances is bound to be unmaintainable and does not yield good error messages. What would you suggest as a replacement? How would you write composable parsers for a complicated file type? Today I added a 'try' method to my MonadParse type class. This lets me write (try p <|> q) generically. An instance for Attoparsec would declare try=id, since it always backtracks. We'll see how this goes. What I learned form this thread is: * arrange your usages of <|> so that both sides can never share a common prefix, then no backtracking will be necessary * for that reason, some parsers like Megaparsec define their Alternative instances the way they do, without backtracking. Please allow one more question: Is the backtracking performance penalty linear in the amount of backtracking? That is, suppose that p = char '-' >> someHugeParser q = char '-' >> anotherHugeParser Could (try p <|> q) decide after seeing two characters that p fails and commit to the second branch, freeing memory? Thanks, Olaf

3 2