5 ms·

TL;DR CRDT is completely irrelevant to any of the highlighting/etc stuff Most highlighters are lexers. Advanced highlighters/folders are parsers. The lexing/p

TL;DR CRDT is completely irrelevant to any of the highlighting/etc stuff Most highlighters are lexers. Advanced highlighters/folders are parsers. The lexing/parsing that is required for highlighting is easy to make incremental for all sane programming languages. for LL(star) grammars, adding incrementality is completely trivial (i sent patches to ANTLR4 to do this) for LR(k) grammars, it's more annoying but possible (tree-sitter does this) For lexing, doing it optimally is annoying, doing it near optimally is very easy. optimal incremental lexing requires tracking, on a per token basis, how far ahead in the character stream the recognizer looked (easy), and computing the affected sets (annoying) Most real programming languages have a lookahead of 1 or 2. Near-optimally requires tracking only the max lookahead used, and assuming all tokens need that max-lookahead. In a world where min token length is 1, that means you only need to re-lex an additional (max lookahead) tokens before the changed range. In a world where min token length is 0, it's all zero length tokens + (max lookahead) tokens before the changed range. This does not require any explicit per-token computation. Again for basically all programming languages, this ends up re-lexing 1 or 2 more tokens total than strictly necessary. Tree-sitter does context-aware on-demand lexing. i have patches on the way for ANTLR to do the same. The only thing CRDT helps with in this equation at all is knowing what changed and producing the sequence of tree-edits for the lexer/parser. The lexer only cares about knowing what character ranges changed, which does not require CRDT. The typical model for this kind of edit is what vscode's document text changes provide (IE For a given text edit, old start , old end, new start , new end) The parser only cares about what token ranges changed, which does not require CRDT.

munificent 7y ago
This is a great comment!
chubot 7y ago
Yeah I think I get what you're saying -- basically that if you have incremental algorithms then you don't need to take a dependency on CRDT or OT to make the UI updates fast? In other words, you can do things synchronously BUT still quickly, since you have an incremental algorithm. In any case, I basically asked that same question here: https://lobste.rs/s/jembrx/thoughts_on_why_crdt_didn_t_work_out_as_well#c_d57eds https://lobste.rs/s/jembrx/thoughts_on_why_crdt_didn_t_work_... I've seen Treesitter and am impressed by it, which I wrote a little about in that comment. ----- Since you speak of "sane" languages, I wrote a parser for an "insane" language by hand, with a principled regex-based lexer: How to Parse Shell Like a Programming Language http://www.oilshell.org/blog/2019/02/07.html http://www.oilshell.org/blog/2019/02/07.html In fact the first thing I tried was to use ANTLR to translate the POSIX shell grammar (which only covers about 1/4 of the shell language). This drove home the limitations of grammar-based approaches. I found its model of lexing to be very limited (along with insisting on materializing a parser tree rather than providing semantic actions in ANTLR v4). So it's good to hear that it's being updated for "context-aware lexing", and incremental lexing. Are you using ANTLR for IDE-like tools? I wasn't aware that it was good or commonly used for that kind of use case. ----- I briefly talked with the author of Treesitter on Github about his bash syntax highlighter with Treesitter, which is of course a parser and not just a lexer, and can be made incremental. I wasn't sure if the context-aware lexing mechanisms here could really handle the shell language: https://tree-sitter.github.io/tree-sitter/creating-parsers#lexical-analysis https://tree-sitter.github.io/tree-sitter/creating-parsers#l... I think his response was basically that it doesn't have to be 100% correct, which I agree with for an editor. Trading off some corner cases for speed is probably the right thing. But I have thought about what it would take make a parser for a "crazy" language incremental and 100% correct (which you would want for further semantic analysis). I wonder if you can write recursive descent parser in the Skip language and then get incrementality for free? The language is designed so that every algorithm can be made incremental, and it's not limited to pure functional constructs like other systems. Supposedly it goes to some lengths to provide you with a more imperative / mutable state modelk, so it should be able to express an "arbitrary" parser. http://skiplang.com/ http://skiplang.com/ In other words, instead of having different algorithms for making LL(star) and GLR parsing incremental, Skip might give you a more expressive model for the parser. A bunch of my blog posts are about the limitations of grammar-based approaches. ----- FWIW the style of context-aware lexing I use is explained here: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html And the other post lists the 14 different modes or contexts that the shell front end has: http://www.oilshell.org/blog/2019/02/07.html#toc_7 http://www.oilshell.org/blog/2019/02/07.html#toc_7 It's a very simple and powerful mechanism, but my parser only cares about batch mode for now. It's not clear to me how it differs in expressiveness from what Treesitter offers (or ANTLR). The current lexer mode basically depends on the control flow of the parser.
josephg 7y ago
Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed it up. I agree - CRDT / OT / whatever is sort of orthogonal, although its really nice being able to feed the parser with the same operation format, and have it update its output. https://home.seph.codes/public/miniohm/ https://home.seph.codes/public/miniohm/ / https://github.com/josephg/miniohm https://github.com/josephg/miniohm if you're curious. I'd love to see this sort of thing applied at a larger scale in a compiler. For example, I could imagine editing a C program with a compiler running live. Instead of batch compiling artifacts to disk like its 1970, instead as I type each character the compiler recompiles just the parts of my program that could be affected by my change. The compiler passes code changes to the linker (maybe with a function level granularity). And the linker could then (live) manage writes to an executable, allocating new byte ranges for changed functions and updating references on the fly. Even on very large C++ project like Chrome, there's no reason why incremental updates should take more than 1-2ms. If all you're doing is changing a single function in the binary file, why do our linkers rewrite the whole thing?
- wpietri 7y ago
  > Instead of batch compiling artifacts to disk like its 1970 [...] I am delighted to see people discussing this. Batch orientation made sense in a very resource-constrained era. But at this point we have more RAM and CPU than we know what to do with. It seems so obvious to me that the correct solution is to prioritize developer experience and keep everything hot. My single biggest barrier to developing faster is the latency between making a change and seeing what that does to the test results. I would like that to be well under a second. Given the cost of programmer time, I could happily throw money at RAM and CPU. But standard, batch-oriented tools won't take advantage of it 99% of the time. I think there's a revolution in developer experience out there, and I really want to see it happen.
  - afiori 7y ago
amelius 7y ago
Very interesting and informative. But I suppose what the user really wants is the next step: not just incremental parsing, but also incremental compilation (or at least the error-checking part of the compilation process).
- DannyBee 7y ago
  The basic error checking comes with incremental parsing. A lot of semantic error checking is also not that bad to make incremental (though some languages are just really really bad here). Incremental compilation depends on the constraints on environment (IE are you trying to incrementally produce normal object files or what) The more you relax the environmental constraints the easier it gets. It also depends on just how non-local an effect the programming language allows. For most programming language, general incremental compilation requires either strongly overestimating possibly-modified sets, or global interprocedural dataflow + pointer analysis. Most choose the former, or don't do general incremental, but instead something like "edits to functions are incremental, edits to global data/types/etc are not" (This is even without compiler optimization on).
- chubot 7y ago
  The Skip language (which I mentioned in another comment) is a language based entirely on incremental computation. Every piece of code you write in it becomes incremental, as far as I know. AND the compiler is self-hosted!!! So that means they have a fully incremental compiler. Although there is an LLVM back end, so maybe only the front end of the compiler is incremental? That's still important. It comes from the same people as the Hack language, which I believe has a fast "online" typechecker -- which I think is incremental (?) I believe you could write a C compiler in Skip the same way? If you peek at the source code, it has a 6000 line recursive descent parser, and 6000 line type checker, much in the style of OCaml (but in Skip). I think this deserves a blog post because it's not clear to me that the message of Skip got through (7 months ago on HN). Their website has some examples, but not too many. Of course, I haven't tried it yet, and it's a super ambitious project, so there could be some big problem with it. But if the goal is to make an entire suite of compiler and devtools that are incremental, then Skip seems like it's ahead of the state of the art and something to borrow from. Salsa was also mentioned, and I believe it's based on some of the same academic work like Adapton. But I don't know if they have an entire self-hosted compiler as a demo like Skip does. It seems to be "query-oriented" rather than supporting arbitrary code, which is what I would expect for most incremental computing frameworks. Skip seems to be more ambitious. https://github.com/salsa-rs/salsa https://github.com/salsa-rs/salsa I believe that the Skip language does this, because it's compiler is self-hosted. It's http://skiplang.com/blog/2017/01/04/how-memoization-works.html http://skiplang.com/blog/2017/01/04/how-memoization-works.ht... https://github.com/skiplang/skip/tree/master/src/frontend https://github.com/skiplang/skip/tree/master/src/frontend Skip – A programming language to skip the things you have already computed https://news.ycombinator.com/item?id=18077612 https://news.ycombinator.com/item?id=18077612 https://github.com/skiplang/skip/blob/master/src/frontend/skipTyping.sk https://github.com/skiplang/skip/blob/master/src/frontend/sk...

munificent 7y ago

This is a great comment!

chubot 7y ago

Yeah I think I get what you're saying -- basically that if you have incremental algorithms then you don't need to take a dependency on CRDT or OT to make the UI updates fast? In other words, you can do things synchronously BUT still quickly, since you have an incremental algorithm. In any case, I basically asked that same question here: https://lobste.rs/s/jembrx/thoughts_on_why_crdt_didn_t_work_out_as_well#c_d57eds https://lobste.rs/s/jembrx/thoughts_on_why_crdt_didn_t_work_... I've seen Treesitter and am impressed by it, which I wrote a little about in that comment. ----- Since you speak of "sane" languages, I wrote a parser for an "insane" language by hand, with a principled regex-based lexer: How to Parse Shell Like a Programming Language http://www.oilshell.org/blog/2019/02/07.html http://www.oilshell.org/blog/2019/02/07.html In fact the first thing I tried was to use ANTLR to translate the POSIX shell grammar (which only covers about 1/4 of the shell language). This drove home the limitations of grammar-based approaches. I found its model of lexing to be very limited (along with insisting on materializing a parser tree rather than providing semantic actions in ANTLR v4). So it's good to hear that it's being updated for "context-aware lexing", and incremental lexing. Are you using ANTLR for IDE-like tools? I wasn't aware that it was good or commonly used for that kind of use case. ----- I briefly talked with the author of Treesitter on Github about his bash syntax highlighter with Treesitter, which is of course a parser and not just a lexer, and can be made incremental. I wasn't sure if the context-aware lexing mechanisms here could really handle the shell language: https://tree-sitter.github.io/tree-sitter/creating-parsers#lexical-analysis https://tree-sitter.github.io/tree-sitter/creating-parsers#l... I think his response was basically that it doesn't have to be 100% correct, which I agree with for an editor. Trading off some corner cases for speed is probably the right thing. But I have thought about what it would take make a parser for a "crazy" language incremental and 100% correct (which you would want for further semantic analysis). I wonder if you can write recursive descent parser in the Skip language and then get incrementality for free? The language is designed so that every algorithm can be made incremental, and it's not limited to pure functional constructs like other systems. Supposedly it goes to some lengths to provide you with a more imperative / mutable state modelk, so it should be able to express an "arbitrary" parser. http://skiplang.com/ http://skiplang.com/ In other words, instead of having different algorithms for making LL(star) and GLR parsing incremental, Skip might give you a more expressive model for the parser. A bunch of my blog posts are about the limitations of grammar-based approaches. ----- FWIW the style of context-aware lexing I use is explained here: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html And the other post lists the 14 different modes or contexts that the shell front end has: http://www.oilshell.org/blog/2019/02/07.html#toc_7 http://www.oilshell.org/blog/2019/02/07.html#toc_7 It's a very simple and powerful mechanism, but my parser only cares about batch mode for now. It's not clear to me how it differs in expressiveness from what Treesitter offers (or ANTLR). The current lexer mode basically depends on the control flow of the parser.

josephg 7y ago

Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed it up. I agree - CRDT / OT / whatever is sort of orthogonal, although its really nice being able to feed the parser with the same operation format, and have it update its output. https://home.seph.codes/public/miniohm/ https://home.seph.codes/public/miniohm/ / https://github.com/josephg/miniohm https://github.com/josephg/miniohm if you're curious. I'd love to see this sort of thing applied at a larger scale in a compiler. For example, I could imagine editing a C program with a compiler running live. Instead of batch compiling artifacts to disk like its 1970, instead as I type each character the compiler recompiles just the parts of my program that could be affected by my change. The compiler passes code changes to the linker (maybe with a function level granularity). And the linker could then (live) manage writes to an executable, allocating new byte ranges for changed functions and updating references on the fly. Even on very large C++ project like Chrome, there's no reason why incremental updates should take more than 1-2ms. If all you're doing is changing a single function in the binary file, why do our linkers rewrite the whole thing?

wpietri 7y ago
> Instead of batch compiling artifacts to disk like its 1970 [...] I am delighted to see people discussing this. Batch orientation made sense in a very resource-constrained era. But at this point we have more RAM and CPU than we know what to do with. It seems so obvious to me that the correct solution is to prioritize developer experience and keep everything hot. My single biggest barrier to developing faster is the latency between making a change and seeing what that does to the test results. I would like that to be well under a second. Given the cost of programmer time, I could happily throw money at RAM and CPU. But standard, batch-oriented tools won't take advantage of it 99% of the time. I think there's a revolution in developer experience out there, and I really want to see it happen.
- afiori 7y ago

amelius 7y ago

Very interesting and informative. But I suppose what the user really wants is the next step: not just incremental parsing, but also incremental compilation (or at least the error-checking part of the compilation process).

DannyBee 7y ago
The basic error checking comes with incremental parsing. A lot of semantic error checking is also not that bad to make incremental (though some languages are just really really bad here). Incremental compilation depends on the constraints on environment (IE are you trying to incrementally produce normal object files or what) The more you relax the environmental constraints the easier it gets. It also depends on just how non-local an effect the programming language allows. For most programming language, general incremental compilation requires either strongly overestimating possibly-modified sets, or global interprocedural dataflow + pointer analysis. Most choose the former, or don't do general incremental, but instead something like "edits to functions are incremental, edits to global data/types/etc are not" (This is even without compiler optimization on).
chubot 7y ago
The Skip language (which I mentioned in another comment) is a language based entirely on incremental computation. Every piece of code you write in it becomes incremental, as far as I know. AND the compiler is self-hosted!!! So that means they have a fully incremental compiler. Although there is an LLVM back end, so maybe only the front end of the compiler is incremental? That's still important. It comes from the same people as the Hack language, which I believe has a fast "online" typechecker -- which I think is incremental (?) I believe you could write a C compiler in Skip the same way? If you peek at the source code, it has a 6000 line recursive descent parser, and 6000 line type checker, much in the style of OCaml (but in Skip). I think this deserves a blog post because it's not clear to me that the message of Skip got through (7 months ago on HN). Their website has some examples, but not too many. Of course, I haven't tried it yet, and it's a super ambitious project, so there could be some big problem with it. But if the goal is to make an entire suite of compiler and devtools that are incremental, then Skip seems like it's ahead of the state of the art and something to borrow from. Salsa was also mentioned, and I believe it's based on some of the same academic work like Adapton. But I don't know if they have an entire self-hosted compiler as a demo like Skip does. It seems to be "query-oriented" rather than supporting arbitrary code, which is what I would expect for most incremental computing frameworks. Skip seems to be more ambitious. https://github.com/salsa-rs/salsa https://github.com/salsa-rs/salsa I believe that the Skip language does this, because it's compiler is self-hosted. It's http://skiplang.com/blog/2017/01/04/how-memoization-works.html http://skiplang.com/blog/2017/01/04/how-memoization-works.ht... https://github.com/skiplang/skip/tree/master/src/frontend https://github.com/skiplang/skip/tree/master/src/frontend Skip – A programming language to skip the things you have already computed https://news.ycombinator.com/item?id=18077612 https://news.ycombinator.com/item?id=18077612 https://github.com/skiplang/skip/blob/master/src/frontend/skipTyping.sk https://github.com/skiplang/skip/blob/master/src/frontend/sk...