Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-06-14

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

All times shown according to UTC.

Time Nick Message
02:37 jeffreykegler joined #marpa
03:31 ceridwen jeffreykegler, A question about something I keep hearing: I've talked to a number of people who seem to believe that GLR is faster than Earley, but I've never seen a citation for it outside the latest ANTLR paper, which just cites one of Tomita's GLR publications.  There are good reasons for thinking that whatever tests or analysis Tomita did in 1985 no longer apply, because they happened before Leo's mo
03:31 ceridwen difications to the algorithm.
03:32 ceridwen Not to mention bug fixes in both Earley and GLR and the enormous changes in hardware performance since then.
03:32 jeffreykegler *LR* is faster than Earley
03:33 jeffreykegler and GLR is just as fast as LR if you don't use the "G" part.
03:33 jeffreykegler That's a bit snarky ...
03:33 ceridwen Have you heard anyone assert this?  Do you have any evidence pointing one direction or the either?  My *suspicion* is that this one of those urban myths that get repeated in the community by people who've forgotten the original reasoning.
03:34 ceridwen But I don't have a disproof either.
03:34 jeffreykegler More seriously, if you're lucky in your choice of grammar, and you don't go much beyond LR, GLR will be fast.
03:35 jeffreykegler ... faster than Earley's
03:35 jeffreykegler If you aren't lucky, speed drops off a cliff.
03:36 jeffreykegler I think the class GLR parses in linear time is LR(1)\
03:36 jeffreykegler and GLR will be faster in those cases.
03:37 jeffreykegler But I don't think Marpa is losing any applications to GLR, because GLR is so much harder to use, has no hope of allowing "events" or other procedural logic ...
03:38 jeffreykegler and, to boot is linear for a far smaller class of grammars.
03:38 jeffreykegler Marpa is linear for a superset of LR-regular, which includes *every* deterministic grammar.
03:39 jeffreykegler But is it possible to put together a timing which shows GLR beating Marpa ... yes, sure.
03:40 ceridwen My understanding is that GLR depends on what table's used, so if you use an LR(1) table, you get linear performance on LR(1) grammars?
03:41 jeffreykegler GLR will go beyond LR(1), but it ceases to be linear after that.
03:41 ceridwen Yeah.
03:41 jeffreykegler And wrt the changes in hardware performance you mentioned, yes very good point ...
03:42 ceridwen I'm mostly curious about the question with respect to GLL.  I've already ruled out GLR based on the reasons you mentioned.
03:42 jeffreykegler because while GLR will be linear with a faster constant than Marpa, the difference would be hard to notice on modern hardware.
03:42 ceridwen Yes.
03:42 ceridwen Though, for instance if the Earley tables get large enough, it's possible that the fact that fast memory hasn't gotten much bigger lately might hurt Earley.  There's almost certainly more going on since 1985, so much has changed.
03:43 jeffreykegler When I say linear, I include space bounds for both algorithms.
03:44 ceridwen But isn't there a constant factor in there too?
03:44 jeffreykegler Yes, and one to Marpa's disadvantage
03:45 jeffreykegler When it comes to Marpa and space, the thing is that while in theory you are parsing just to parse ...
03:45 jeffreykegler in real life you are creating an AST or doing something with the parse, and the data structure you need to do something is large and linear anyway.
03:46 jeffreykegler That is, you are going to use the space anyway in many/most applications.
03:47 jeffreykegler If you are doing something like just scanning for a pattern, then Marpa is at a disadvantage ...
03:47 jeffreykegler but then GLR is at a disadvantage usually compared to recursive descent or regexes.
03:48 jeffreykegler That is, GLR fills a middle ground which does not really exist.
03:48 jeffreykegler IMHO
03:49 jeffreykegler For sure, however, there are lots of applications where Marpa will never beat regexes.
03:50 ceridwen Yeah.
03:51 ceridwen I'd suspect that the size of the parse forest would completely dominate the Earley items or GSS.
04:04 jeffreykegler Btw, I am curious about others perceptions.  In terms of actual usage, and not counting regexes, I think Marpa's main competitors are
04:04 jeffreykegler recursive descent, and
04:04 jeffreykegler PEG
04:05 jeffreykegler My guess is that yacc/LALR/bison gets academic attention, and folks recommend them to other people, but nobody actually implements with them any more.
04:12 ceridwen There are still LALR parsers out there in actual use, I can name a couple in Python.  Many of them are old, now, by software standards though.
04:13 ceridwen I think it depends to an extent on the availability of good parsing tools in a given language.
04:15 ceridwen PEG-based parsers are very popular, but they seem to be mostly recursive-descent, not packrat parsers.
04:16 ceridwen I would say that LALR and its cousins are slowly dying.
04:27 jeffreykegler Good night, all!  AFK
05:15 RichardMichaels joined #marpa
07:19 lwa joined #marpa
08:09 ernimril_ left #marpa
08:09 ernimril joined #marpa
10:47 koo5 joined #marpa
12:20 koo5 joined #marpa
12:56 Cheery jeffreykegler: if GLR has as bad 'wakeup time' as what constructing canonical parsing tables produce
12:56 Cheery then I don't think it's in any way practical, for example to what I'm about to do
12:57 Cheery equally cool thing in here is that the parser farts up immediately from the syntax file.
12:59 Cheery and really, compared to PEG the context free grammars form modular
13:01 Cheery that meaning: if you remove rule that constructs conditional clauses in my language, then you no longer have conditionals
13:01 Cheery that doesn't cause the parser to suddenly exhibit alternative behavior because there is no ambiguous rule shadowed by the conditionals
13:32 RichardMichaels hi
15:20 jeffreykegler joined #marpa
15:25 jeffreykegler RichardMichaels: hi
15:54 Cheery it's hours from since I wrote a file format.
15:56 Cheery There's one thing that just bothers me.
15:56 Cheery the reading and writing are duals.
16:04 Cheery https://bpaste.net/show/81edc2acb53e
16:04 Cheery But I have no idea how to represent it in a way that these two functions could be derived from it
16:15 jeffreykegler joined #marpa
16:15 jeffreykegler From this conversation: http://www.reddit.com/r/lisp/comments/39mngt/successor_for_lisp_syntax/, a reaction to my PEG blog post
16:16 jeffreykegler "Jeffrey Kegler's take on PEG can be aggravating to read, but there's some point to what he says about the subject."
16:16 jeffreykegler Off to run errands.  AFK
16:21 Cheery https://bpaste.net/show/9590165b430a
16:21 Cheery this kind of representation might allow to derive the both.
16:22 Cheery but it's darn complex to handle right :)
16:22 Cheery the trick by how this would work, would be to interpret the same input into their duals.
16:23 Cheery x=value < 128 :7:8
16:23 Cheery on writing, the x captures the condition.
16:23 Cheery on reading the x retrieves the bit.
16:25 Cheery the block.bytes would work similarly. the 'bytes' would dump its output on writing, on reading it'd read in its length.
17:32 koo5 joined #marpa
17:35 lwa joined #marpa
18:22 Cheery Progress: https://bpaste.net/show/90a89eef0beb
18:24 Cheery I removed my handwritten parser today
19:28 koo5 joined #marpa
19:53 koo5 Cheery, working on a structural editor? me kinda too, tell me more
19:53 koo5 yeah marpa is a good demotivator but not good enough
19:57 koo5 another evil thing is http://grammaticalframework.org/
20:00 Cheery is it really not good enough?
20:00 Cheery I'm in middle of writing code that parses my grammar filess
20:03 Cheery file => notation(op lhs rhs): lhs=symbol binary_spacing(op) rhs=symbol
20:05 koo5 well, i dont know, it makes it a non-critical component, thats for sure, depends how much energy there is to pursue things
20:05 koo5 youre dealing with some binary formats?
20:06 Cheery I was working on my languages bytecode just while ago
20:06 koo5 ah
20:06 Cheery occassionally doing it if I need. but .json is usually perfectly sufficient
20:07 Cheery I made bytecode format now because it's relatively low level part that has to read it.
20:07 Cheery implementing json and reading it would represent about same amount of effort.
20:10 Cheery 9~anyway. that grammar is almost like something a noob would write into his sketchbook
20:12 Cheery it's also first language ever, that I've designed along the system that interprets the results
20:13 koo5 can i see it?
20:13 koo5 im a noob too
20:14 Cheery I'm still working on it. But I can write production rules such as this one: file => symbol colon:":" symbol
20:16 Cheery although the parser got indentation sensitivity builtin and I'm not using it here, it doesn't interfere on parsing multi-line expressions
20:18 Cheery https://bpaste.net/show/2f97ccffdf6a
20:18 Cheery it looks like that
20:20 Cheery I'm later pushing out more code into pyllisp repository
20:20 koo5 neat, i should steal that
20:22 Cheery so about structure editor.. I've written several that failed
20:23 Cheery the key component that I think I lacked is effective parsing. if you don't have superb input, it sucks more than it is worth
20:24 Cheery also, if you get the mechanics right, the next thing you need to get right is the display.
20:25 Cheery fortunately, with good parsing and good use of parsing, and some insights from TeX, it shouldn't be troubling
20:27 koo5 looking thru your repos
20:30 koo5 my last attempt was primarily structural, https://github.com/koo5/new_shit , new i want to try starting out with a text editor
20:32 koo5 and yeah discovering marpa changed a lot, i will only be adding structuralness as necessary
20:35 koo5 but..lets see what you have there..
20:41 koo5 you took a stab at a rich text editor, awesome
20:42 koo5 and cyk, wow, and everything..
20:51 koo5 yeah, youre miles ahead of me
21:01 koo5 https://docs.google.com/document/d/1NQCoEghY5rGyEx9tRulQlPz8Do1JPA8O-uoLq3tpTJk/pub#h.21il84y3uzy0
21:02 koo5 +- my current idea about enriching a text editor
21:08 Cheery studying
21:11 koo5 most of my notes are outdated
21:14 Cheery you could bring this to test drive: https://github.com/cheery/little_list_editor
21:14 koo5 im trying textended but it seems the shader text doesnt play well with my gpu and the result is just empty rectangles
21:15 koo5 little_list_editor looks nice but just a toy?
21:15 Cheery well textended not being complete, that is not much better.
21:16 Cheery it's got a layout engine, but it's unproven that it works because I didn't get to work on large enough files
21:16 Cheery but little_list_editor is based on what I learned about marpa
21:17 Cheery I'm impressed how well it works, though I noticed it's got problems on ambiguous inputs.
21:18 koo5 so little_list_editor is your focus now?
21:18 Cheery it's a small experiment behind 3 days, which happened to show lot of promise
21:19 Cheery I'm not focused on structure editing right now.
21:19 Cheery my current goal is to use the same parser in that little_list_editor, and create language for pyllisp using it
21:21 Cheery that is. I'll make a plaintext programming language with as good syntax as I can create
21:22 koo5 yeah
21:22 koo5 + incremental parsing
21:22 koo5 you dont want to use marpa tho?
21:23 koo5 my idea now is to get rid of an ast as a standalone thingy, and only keep it as metadata in the textt
21:23 koo5 text
21:23 Cheery I don't know. I might, but I wanted to understand the algorithm too.
21:23 koo5 i see
21:24 Cheery it's bit apparent that every marpa user do not need to do that.
21:27 Cheery koo5: anyway, the editor shouldn't be hard to understand. But it gives a platform to try things out
21:28 Cheery specifically the critical part that must be solved is to get it run on ambiguous grammars
21:29 Cheery and, of course, to somehow formalize what it does so the user understands it.
21:33 Cheery koo5: I've given up three or four times when I've hit a wall in this subject.
21:33 koo5 in user accessibility?
21:33 Cheery yeah. that's the missing piece
21:34 koo5 of what tho? does it behave like a text editor?
21:35 koo5 let me scale the font and play with it..
21:36 Cheery internally it's handling structures, but I noticed long while ago that it's convenient if main commands affect the text elements.
21:40 Cheery btw. it's probably not coincidence that text editors are still an important interface to computers.
21:41 Cheery you've got computer memory that's sequence of characters. Well today that's not entirely true because text encodings developed.
21:42 koo5 its a ton of work to implement smooth text editing over ast, i know, as i said, i think starting with a text area is the way to go
21:43 Cheery text area or graphical element of some sort, where you can move in screen coordinates
21:43 Cheery you need clear cues on where the action happens if you do something.
21:44 koo5 in new_shit i have contextual help in sidebar, each element has keypress handlers
21:44 koo5 but hmm..
21:44 koo5 i dont want to think about this old stuff
21:46 koo5 display was done by generating a stream of marked-up chars from the ast
21:47 Cheery hmmm
21:47 Cheery thinking about this, I'm getting ideas of things to try
21:49 Cheery basically when you got good parser, this problem opens up in the interface.
21:50 Cheery I dare to say that parsing is an UI concept entirely
21:50 Cheery treat it as such
22:37 ronsavage joined #marpa
23:34 ronsavage jk: Re http://irclog.perlgeek.de/marpa/2015-06-13#i_10744030. I didn't see any takers on the backlog. Everyone is obviously too busy having fun with Marpa, so I'll do it.
23:42 jeffreykegler joined #marpa
23:42 jeffreykegler ronsavage: Thanks!
23:47 Cheery http://boxbase.org/entries/2015/jun/15/marpa-parsing-revolution/

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