Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2014-09-09

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

All times shown according to UTC.

Time Nick Message
00:23 jeffreykegler ronsavage: I'm very pleased with what you've done with the website.
01:36 ronsavage Marpa's gaining some serious traction :-)
01:37 Aria Yaaay!
05:04 aredridel joined #marpa
05:09 ronsavage joined #marpa
05:58 ilbot3 joined #marpa
05:58 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
08:32 rns joined #marpa
10:55 Torsten_ joined #marpa
10:57 Torsten_ hi, I've been lurking in the irc logs from time to time and came across yesterdays posts by sivoais regarding "Standard Flavored Markdown"
10:58 Torsten_ I just wanted to share a link to the relevant "spec" discussion on the official commonmark discussion page: http://talk.commonmark.org/t/​commonmark-formal-grammar/46
11:00 Torsten_ I am in no way competent to join the discussion there (no parsing theory education on my side), but it sounds like Marpa might be a solution to there parsing problem
11:01 Torsten_ at least, once they do have an ABNF for their markdown flavour
15:32 Aria Yeah, it could implement it well. If only we had a marpa port for other popular languages. Sigh!
16:13 jeffreykegler joined #marpa
17:33 lwa joined #marpa
18:27 lwa joined #marpa
19:11 lwa joined #marpa
20:14 daxim joined #marpa
20:39 jeffreykegler joined #marpa
20:51 jeffreykegler My last blog post seems to have been a hit -- I was hoping putting things together as a narrative would help focus the issues, and that seems to be the case.
20:51 Aria Indeed. The questions about 'how do PEG and all that fit into the timeline and things' are interesting
20:51 jeffreykegler Yes, and also the seeming omission of yacc
20:52 Aria Yeah.
20:52 jeffreykegler I say seeming because of course I am talking about algorithms and I talk about LALR *a lot*
20:52 Aria Though interestingly you mention nearly no tools -- just what people have done with them, and what their basis is.
20:53 jeffreykegler Right.  I did that for compression -- I'm all about algorithms but I want to relate them to applications.
20:54 jeffreykegler So I omitted most discussion of tools -- yacc would be useful to include, though ...
20:54 jeffreykegler I think there'll be a revision, and I'll add an entry for yacc, mentioning that yacc == LALR so folks can connect the dots.
20:56 Aria Makes sense.
20:57 jeffreykegler PEG is also an interesting story -- it goes back much further than people think, but it's one of a long list of semi-syntax-driven left parsers.  So if PEG, why not mention ANTLR?
20:58 Aria Yeah, for sure.
20:58 jeffreykegler And also Perl 6 grammars which also fall into this school of semi-syntax-driven left parsers -- attempts to get the best of syntax driven, together with the best of recursive descent.
20:59 Aria My mental highlights go something like "LR, LL, Earley, theory, LALR, yacc, bison, ANTLR, GLR, bison, PEG, Today!"
20:59 jeffreykegler Huh?
21:00 Aria Just my mental timeline reads something like that. IF you put one-word labels on everything.
21:00 jeffreykegler OK
21:02 jeffreykegler There's a Hacker News discussion going which is quite interesting.
21:02 jeffreykegler I may respond to several points via the Google group -- for example, why I ommitted yacc and tools in general
21:07 jeffreykegler The Hacker news discussion seems to have forked over to reddit, but I cannot find where.  reddit is hard to search.
21:08 Aria Ugh, yeah.
21:08 Aria Loathesome for programming discussions
21:08 Aria http://www.reddit.com/submit?url=http%3A%2F%2​Fjeffreykegler.github.io%2FOcean-of-Awareness​-blog%2Findividual%2F2014%2F09%2Fchron.html
21:14 jeffreykegler I have jumped into the reddit discussion: http://www.reddit.com/r/programming/com​ments/2fxkr7/parsing_a_timeline/ckdsa26
21:18 jeffreykegler In these discussions, I bear in mind a prior go-around with my "Perl syntax is undecidable" results.  The discussions, even on Lambda the Ultimate, were so confused I frankly despaired.
21:18 jeffreykegler But now my result is on Wikipedia, and the writeup is quite concise and correct.
21:18 daxim joined #marpa
21:19 Aria Nice!
21:20 jeffreykegler These current discussions seem far more rational and better informed than those about the decidability of Perl parsing.
21:22 Aria Heh, yeah.
21:23 jeffreykegler Another note, why don't I mention LL parsing.  I do, repeatedly, calling it left parsing.  Perhaps the solution to this is a glossary at the end.
21:23 Aria Yeah, maybe.
21:24 jeffreykegler By the way, recursive descent is a strange beast in this context -- it's not really an algorithm -- it's an approach to writing LL parsers.
21:24 Aria Yeah.
21:24 jeffreykegler That distinction may seem a bit too semantic ...
21:24 Aria Yeah. Lots of people refer to the algorithm by the code to implement it.
21:24 Aria Hence LL -> RecDescent, LALR -> yacc.
21:24 jeffreykegler but the difference is in making theoretical statements -- I can characterize the time complexity of LL(k) ...
21:25 jeffreykegler but to talk about whether RecDescent is O(n) or whatever, I have to assume equivalence to LL(k) for some k.
21:26 Aria Yeah.
21:27 Aria "Can I break your stuff by handing it weird input?" is a real thing, especially these days.
21:27 Aria Sending node.js into swap with JSON that's too deep, for one.
21:28 jeffreykegler Re RecDescent: strictly speaking, RecDescent could use Marpa for lookahead.  What would be it's power and complexity then?
21:29 jeffreykegler That's why RecDescent is tricky to describe in theoretical terms.
21:29 jeffreykegler I note bison and GLR mentioned a bit.
21:31 Aria Heh, yeah.
21:31 jeffreykegler I could go into theoretical differences, but in fact I don't really see GLR used very much.
21:32 jeffreykegler Could you create something like the SLIF DSL in bison GLR without going exponential?  (Not to mention mixing it with procedural parsing.)
21:32 Aria I don't think you could.
21:32 Aria I think it's just "LALR with the edges sawn off"
21:32 jeffreykegler :-)
21:33 Aria A little nicer to use. Some of the conflicts made all better.
21:33 Aria Slows down parsing a little, but whatever, CPU is cheap.
21:33 Aria A pragmatic tool for people who don't care anyawy.
21:36 jeffreykegler GLR is one of a large class of approaches to general parsing.
21:37 jeffreykegler The recipe goes like this:
21:37 Aria Yep.
21:37 jeffreykegler 1. Take call algorithm X, one with a lot of nice properties.
21:37 jeffreykegler 2. When it fails, backtrack. (GLR does *not* backtrack, but bear with me.)
21:38 jeffreykegler The result of these two step is an algorithm that you hope will be combine the best of both world -- the benefits of X, without the exponential time of backtracking.
21:38 jeffreykegler And in some cases that will happen.
21:39 Aria yep.
21:40 jeffreykegler GLR, as I said does, not backtrack, but it does fork the stack, which may trade space for time, thought I wonder about even that.
21:40 jeffreykegler It's kind of like an Earley non-deterministic strategy, but without using Earley's tables.
21:40 Aria Yeah.
21:50 jeffreykegler Btw, I thought thechao's point on reddit was excellent -- it's become the trend in parsing to make complexity claims without the supporting math ...
21:50 Aria True. But are they wrong?
21:51 jeffreykegler this is a trend I did *not* follow.
21:51 Aria So far I've found them borne out when I checked.
21:51 jeffreykegler Are the claims wrong?  Worse, they are usually phrased so they're not really falsifiable.
21:51 Aria Heh, now there's that.
21:52 Aria Mostly I want to answer a more specific question: given arbitrary input, can I make this go pear-shaped?
21:52 Aria Not "what kind of pear shape?", just "does it go significantly nonlinear?"
21:53 jeffreykegler Aria: consider that it took a generation for yacc's pear-shaped-ness to emerge.
21:53 Aria Heh, true.
21:53 Aria Though I'm not sure anyone was looking before.
21:53 Aria After, I'm not sure they bothered writing down when they found it.
21:54 jeffreykegler For example, suppose you're rewriting Scala, and decide to go face-first for Marpa.
21:54 jeffreykegler What assurance do you have that it will be fast enough, when you've the implementation 3/4 done?
21:54 jeffreykegler and after many person-years of work?
21:55 jeffreykegler That's why precise claims and math to support them are important.
21:56 Aria Mmm. Yeah. Or at least finding a counterexample that makes something go pear-shaped, so you can discard it and move on.
21:56 Aria But that does take at least a passing understanding of the algorithm.
22:00 ronsavage What's the Wikipedia link. I searched for Marpa, and then for Kegler. The latter redirects to 10 pin bowling. Is that some sort of joke, Jeffey, that you've bowled the opposition out :-)).
22:02 jeffreykegler ronsavage: the last name reflects the kind of hard-working lineage I come from. :-)  It is in fact the same word -- a German last name which is also a word in German.
22:03 jeffreykegler Marpa does not have a Wikipedia link.  Perhaps more important the Earley page has some issues -- particular it does not clearly distinguish between properties of Earley's original algorithm ...
22:04 jeffreykegler and properties of later algorithms in the Earley family.
22:05 jeffreykegler re bison GLR: https://www.gnu.org/software/bison/man​ual/html_node/Simple-GLR-Parsers.html
22:06 jeffreykegler The last two grafs are pretty forthright about the issues.  Note that none of those issues exists with Marpa.
22:09 jeffreykegler Changing topic: I like the comment in https://news.ycombinator.com/item?id=8292365  "I think Marpa is only the beginning."
22:16 ronsavage OK. Thanx.
22:18 jeffreykegler ronsavage: btw.  Just checked to see if the IRC log is on the web site.  And, yes, you'd already taken care of it.  Thanks.
22:30 ronsavage German, eh? Some of my relatives came to Australia from Greuβen in Thuringia about 150 years ago. I know that β isn't quite right, but via Unicode I could not find a better one.

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