Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-03-10

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
00:55 koo5 joined #marpa
01:10 jeffreykegler http://aredridel.dinhe.net/2015/03/09/why-th​e-quality-of-teaching-programming-is-so-bad/
01:11 jeffreykegler The link is some historical notes on programming (from Aria?)  It is pretty good on a lot of history that I assume Aria is too young to have experienced directly -- about half of it is before *my* time.
01:39 koo7 joined #marpa
02:47 ilbot3 joined #marpa
02:47 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
12:22 koo7 joined #marpa
12:38 lwa joined #marpa
13:53 Aria Hehe, yeah. Definitely before my time; I was born in '81. But my grandfather was an engineer during that era, and ... well, to know unix well, one must know the history of unix.
13:53 Aria And studying how women were pushed out of tech in the 80s is _very_ relevant to my interests.
16:10 koo5 joined #marpa
16:26 jeffreykegler joined #marpa
16:33 jeffreykegler joined #marpa
18:43 jeffreykegler Marpa talkiing points -- I notice in the traffic new interest in Marpa, but some (quite properly!) want confirmation of my complexity claims, which go well beyond the kind of parsers in practical use.
18:44 jeffreykegler There has been a lot of hand-waving in this area, and not a few just-plain-old-false claims, so the skeptics are being reasonable.
18:46 Aria Totally.
18:46 jeffreykegler There is of course my paper -- https://www.academia.edu/10341474/Marpa_A​_practical_general_parser_the_recognizer -- but the proofs are complicated.
18:47 jeffreykegler To the skeptics, I'd first point out that I claim nothing not already in Joop Leo's 1991, which is in the refereed literature.
18:48 jeffreykegler That is, the skeptics do *not* have to believe that I've achieved a new time complexity bound (because I did not)
18:49 jeffreykegler What they have to to believe is that, in improving on and implementing the Leo/Earley algorithm, I did not break anything that would invalidate the previous claims.
18:49 Aria Yup.
18:50 jeffreykegler And when you look at my changes, I think it is intuitively reasonable to believe that I could make those changes without breaking the speed-up in Leo 1991.
18:51 jeffreykegler So actually my time complexity claims should be considered quite uncontroversial.
18:52 jeffreykegler My proofs are routine -- just taking the new algorithm, leveraging the old proofs, all using proof techniques already familiar from the literature.
18:53 jeffreykegler Okay, talking point # 2 re my time complexity claims.
18:53 rns joined #marpa
18:53 jeffreykegler If any doubt remains, you can experiment with expected problematic grammars, and time the results.
18:54 jeffreykegler This is not a proof (although this kind of thing replaces proofs these days in much of the published literature), but ...
18:54 jeffreykegler it should take care of any remaining doubt.
18:54 jeffreykegler I this connection, I'll note ...
18:55 jeffreykegler that a lot of people, including many on this list, have done a lot of things with Marpa at this point, and if Marpa went quadratic on grammars for which I claim linearity ...
18:56 jeffreykegler we'd have probably heard about it by now.
18:57 rns jeffreykegler: re proof of complexity claims – to me, strand (constant-space) parsing would allow parsing inputs of arbitrary lengths and thus facilitate "proof by experiment" -- building a parser and testing how parse time grows with the input size -- for the complexity claims.
18:57 rns I don't know if (and to what extent) this "proof by experiment" has theoretical merit, but it arguably can be more convincing for some audiences.
18:58 rns That's just one point why strand parsing looks very important and interesting to me.
18:59 jeffreykegler rns: In the published literature, "proofs by experiment", often quite arbitrary, are now more common than mathematical proofs.
19:02 rns Alright, then.
19:02 rns Not that I'd be very impressed by a sole "proof by experiment" per se, only as a companion to solid theoretical proof, which Marpa has in its foundations.
19:02 rns But those are good new.
19:02 rns s/good new/good news/
19:05 jeffreykegler Yes, I much prefer the old theoretical proof, and judging from the reception of recent parsing articles, I am not alone in that.
19:06 jeffreykegler Experiments *are* good for catching implementation screwups.
19:07 jeffreykegler I actually had one of those, which Jean-Damien caught -- my transitive closure algorithm.
19:07 jeffreykegler This is not run at parse time, so the screw-up did not affect any of my time complexity claims for parsing.
19:07 jeffreykegler But it *did* making the precomputation of large grammars take an unreasonable amount of time.
19:08 rns I vaguely remember -- when you implemented Warshall?
19:08 jeffreykegler Yes, exactly.
19:08 jeffreykegler A rare mistake in G&J contributed to my problem.
19:09 jeffreykegler G&J say that Warshall is *always* cubic.
19:09 rns Cubic time?
19:10 jeffreykegler A little thought convinced me this was not necessary for a transitive closure so I created my own algorithm which is O(n**2) in practical cases.
19:10 jeffreykegler rns: In this case the "input" is O(n**2) in length, so it's not quite as bad as it sounds.
19:10 jeffreykegler Though it was still plenty bad.
19:11 jeffreykegler As you probably know, usually the "n" in a claim is the length of the input, but sometimes the convention varies.
19:11 Aria I fully intend to instrument my implementation so that I can write test assertions that compare input lengths to iterations of various constructs.
19:12 rns jeffreykegler: yes, can be other size measures.
19:12 rns Aria: Great!
19:13 jeffreykegler The problem with my own algorithm was that I mis-implemented the memory management, and that was hiding a big time complexity cost, which Jean-Damien noticed.
19:14 jeffreykegler And rather than fix my memory management I reinvestigated Warshall's, which, G&J to the contrary notwithstanding ...
19:14 jeffreykegler is the right tool for the job.
19:20 rns Well, even if it never goes higher than cubic for quadratic inputs, looks like it is.
20:09 rns left #marpa

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary