I'm not extremely familiar with the details of incremental parsing, but I have used Cursorless, a VSCode extension based on tree-sitter for voice controlled structured editing, and it is pretty powerful. You can use the structured editing when you want and also normal editing in between. Occasionally the parser will get things wrong and only change/take/select part of a function or what have you, but in general it's very useful, and I tend to miss it now that I am no longer voice coding much. I seem to remember that there was a similar extension for emacs (sans voice control). treemacs, or something? Anyone used that?
Trying to use any kind of syntax highlighter with TeX is a pain in the butt. I didn't mean LaTeX there. I mean TeX, which can rewrite it's own lexer, and a lot of libraries work by doing so. I move in and out of TeXInfo syntax and it basically just causes most editors to sit there screaming that everything is broken.
Yes its pretty funny when you realise what a tiny corner of the design space of programs most users inhabit that they think things like lsp are an amazing tool instead of a weekend throwaway project.
What's even funnier is how much they attack anyone who points this out.
I think simpler is better when it comes to structured editing. Recursive teXt has the advantage that it proposes a simple block structure built into the text itself [1]. Of course, you will need to design your language to take advantage of this block structure.
I did some work on structural editing a while back, using Tree-sitter to get the AST (abstract syntax tree, the parse tree used for structural edits). I now use the editor as my daily driver but don't use or feel the need for structural editing commands that often - probably partly out of habit and partly because text edits are just better for most editing.
I do miss the "wrap" command when using other editors, but it could be implemented reasonably easily without a parse tree. I found that a lot of the structural edits correspond to indentation levels anyway, but the parse tree definitely helps.
I think almost all of this applies to ordinary word processing as well as computer code. For example, you could have a "block-based" document editor that handles each paragraph of text as a single "entity", like what Jupyter Notebooks does. Documents have major sections, sub sections, sub-sub sections, etc, and so they're also inherently organizable as a "Tree Structure" instead of just a monolighic string of characters. Microsoft hasn't really figured this out yet, but it's the future.
Google just recently figured this out (That Documents need to be Hierarchical):
Also interestingly both Documents and Code will some day be combined. Imagine a big tree structure that contains not only computer code but associated documentation. Again probably Jupyter Notebooks is the closest thing to this we have today, because it does incorporate code and text, but afaik it's not fully "Hierarchical" which is the key.
I'm a bit skeptical because real source can be quite messy. Parsing C source code works because there are neither comments nor preprocessor directives to consider. You have clean input which you can map into an AST using well-defined rules. But source code you edit contain both comments and preprocessor directives. So a parser for structured editing has to acknowledge their existance and can't just ignore them, unlike a parser for a compiler. And that is hard because preprocessor directives and comments can show up almost anywhere. While comments are "mute", directives affect parsing:
#define FOO }
int main() {
FOO
"No one writes code like that!" Actually, they do, and mature C code-bases are full of such preprocessing magic.
> it is now clear to me that there is ongoing work on structured editing which either doesn’t know about incremental parsing in general, or Tim’s algorithms specifically. I hope this post serves as a useful advert to such folk
I'm curious about this unnamed ongoing work (that is unaware of incremental parsing).
I don't know specifically - but even now, i still end up having to explain to people that incremental parsing/lexing (particularly without error recovery) is not hard, it is not really complicated, and as the author here said, Tim (et al) have made beautiful algorithms that make this stuff easy.
Heck, incremental lexing is even easy to explain.
For each token, track where the lexer actually looked in the input stream to make decisions. Any time that part of the input stream changes, every token to actually look at the changed portion of the input stream is re-lexed, and if the result changes, keep re-lexing until the before/after tokenstreams sync up again or you run out of input. That's it.
You can also make a dumber version that statically calculates the maximum lookahead (lookbehind if you support that too) of the entire grammer, or the maximum possible lookahead per token, and uses that instead of tracking the actual lookahead used.
In practice, this is often harder than just tracking the actual lookahead used.
In an LL system like ANTLR, incremental parsing is very similar - since it generates top-down parsers, it's the same basic theory - track what token ranges were looked at as you parse.
During incremental update, only descend into portions of the parse tree where the token ranges looked at contain modified tokens.
Bottom up is trickier.
Error recovery is the meaningfully tricky part in all of this.
Before tree-sitter, I was constantly explaining this stuff to people (I followed the projects that these algorithms came out of - ENSEMBLE, HARMONIA, etc).
After more people get that there are ways of doing this, but you still run into people who are re-creating things we solved in pretty great ways many years ago.
> why structured editors haven’t taken over the world: most programmers find them so annoying to use in some situations that they don’t view the pros as outweighing the cons.
Seems like "annoying" refers to a user interface annoyance.
I'm guessing the following since I couldn't tell what structured editing is like from the article:
Keyboard entry is immediate, but prone to breaking the program structure. Structured editing through specific commands is an abstraction on top of key entry (or mouse), both of which add a layer of resistance. Another layer might come from having to recall the commands, or if recognizing them, having to peruse a list of them, at least while learning it.
What does the developer's experience with incremental parsing feel like?
> What does the developer's experience with incremental parsing feel like?
It's essentially the experience most of us already have when using Visual Studio, IntelliJ, or any modern IDE on a daily basis.
The term "incremental parsing" might be a bit misleading. A more accurate (though wordier) term would be a "stateful parser capable of reparsing the text in parts". The core idea is that you can write text seamlessly while the editor dynamically updates local fragments of its internal representation (usually a syntax tree) in real time around the characters you're typing.
An incremental parser is one of the key components that enable modern code editors to stay responsive. It allows the editor to keep its internal syntax tree synchronized with the user's edits without needing to reparse the entire project on every keystroke. This stateful approach contrasts with stateless compilers that reparse the entire project from scratch.
This continuous (or incremental) patching of the syntax tree is what enables modern IDEs to provide features like real-time code completion, semantic highlighting, and error detection. Essentially, while you focus on writing code, the editor is constantly maintaining and updating a structural representation of your program behind the scenes.
The article's author suggests an alternative idea: instead of reparsing the syntax tree incrementally, the programmer would directly edit the syntax tree itself. In other words, you would be working with the program's structure rather than its raw textual representation.
This approach could simplify the development of code editors. The editor would primarily need to offer a GUI for tree structure editing, which might still appear as flat text for usability but would fundamentally involve structural interactions.
Whether this approach improves the end-user experience is hard to say. It feels akin to graphical programming languages, which already have a niche (e.g., visual scripting in game engines). However, the challenge lies in the interface.
The input device (keyboard) designed for natural text input and have limitations when it comes to efficiently interacting with structural data. In theory, these hurdles could be overcome with time, but for now, the bottleneck is mostly a question of UI/UX design. And as of today, we lack a clear, efficient approach to tackle this problem.
bgoated01|1 year ago
[0] https://www.cursorless.org/
servilio|1 year ago
[1] https://github.com/mickeynp/combobulate
codetrotter|1 year ago
setopt|1 year ago
shakna|1 year ago
llm_trw|1 year ago
What's even funnier is how much they attack anyone who points this out.
practal|1 year ago
[1] http://recursivetext.com
computably|1 year ago
gushogg-blake|1 year ago
I do miss the "wrap" command when using other editors, but it could be implemented reasonably easily without a parse tree. I found that a lot of the structural edits correspond to indentation levels anyway, but the parse tree definitely helps.
HN post: https://news.ycombinator.com/item?id=29787861
quantadev|1 year ago
Google just recently figured this out (That Documents need to be Hierarchical):
https://lifehacker.com/tech/how-to-use-google-docs-tabs
Also interestingly both Documents and Code will some day be combined. Imagine a big tree structure that contains not only computer code but associated documentation. Again probably Jupyter Notebooks is the closest thing to this we have today, because it does incorporate code and text, but afaik it's not fully "Hierarchical" which is the key.
WillAdams|1 year ago
http://literateprogramming.com/
bjourne|1 year ago
sudahtigabulan|1 year ago
I'm curious about this unnamed ongoing work (that is unaware of incremental parsing).
Anyone know what he is referring to?
DannyBee|1 year ago
Heck, incremental lexing is even easy to explain. For each token, track where the lexer actually looked in the input stream to make decisions. Any time that part of the input stream changes, every token to actually look at the changed portion of the input stream is re-lexed, and if the result changes, keep re-lexing until the before/after tokenstreams sync up again or you run out of input. That's it.
You can also make a dumber version that statically calculates the maximum lookahead (lookbehind if you support that too) of the entire grammer, or the maximum possible lookahead per token, and uses that instead of tracking the actual lookahead used. In practice, this is often harder than just tracking the actual lookahead used.
In an LL system like ANTLR, incremental parsing is very similar - since it generates top-down parsers, it's the same basic theory - track what token ranges were looked at as you parse. During incremental update, only descend into portions of the parse tree where the token ranges looked at contain modified tokens.
Bottom up is trickier. Error recovery is the meaningfully tricky part in all of this.
Before tree-sitter, I was constantly explaining this stuff to people (I followed the projects that these algorithms came out of - ENSEMBLE, HARMONIA, etc). After more people get that there are ways of doing this, but you still run into people who are re-creating things we solved in pretty great ways many years ago.
etse|1 year ago
Seems like "annoying" refers to a user interface annoyance.
I'm guessing the following since I couldn't tell what structured editing is like from the article:
Keyboard entry is immediate, but prone to breaking the program structure. Structured editing through specific commands is an abstraction on top of key entry (or mouse), both of which add a layer of resistance. Another layer might come from having to recall the commands, or if recognizing them, having to peruse a list of them, at least while learning it.
What does the developer's experience with incremental parsing feel like?
Eliah_Lakhin|1 year ago
It's essentially the experience most of us already have when using Visual Studio, IntelliJ, or any modern IDE on a daily basis.
The term "incremental parsing" might be a bit misleading. A more accurate (though wordier) term would be a "stateful parser capable of reparsing the text in parts". The core idea is that you can write text seamlessly while the editor dynamically updates local fragments of its internal representation (usually a syntax tree) in real time around the characters you're typing.
An incremental parser is one of the key components that enable modern code editors to stay responsive. It allows the editor to keep its internal syntax tree synchronized with the user's edits without needing to reparse the entire project on every keystroke. This stateful approach contrasts with stateless compilers that reparse the entire project from scratch.
This continuous (or incremental) patching of the syntax tree is what enables modern IDEs to provide features like real-time code completion, semantic highlighting, and error detection. Essentially, while you focus on writing code, the editor is constantly maintaining and updating a structural representation of your program behind the scenes.
The article's author suggests an alternative idea: instead of reparsing the syntax tree incrementally, the programmer would directly edit the syntax tree itself. In other words, you would be working with the program's structure rather than its raw textual representation.
This approach could simplify the development of code editors. The editor would primarily need to offer a GUI for tree structure editing, which might still appear as flat text for usability but would fundamentally involve structural interactions.
Whether this approach improves the end-user experience is hard to say. It feels akin to graphical programming languages, which already have a niche (e.g., visual scripting in game engines). However, the challenge lies in the interface.
The input device (keyboard) designed for natural text input and have limitations when it comes to efficiently interacting with structural data. In theory, these hurdles could be overcome with time, but for now, the bottleneck is mostly a question of UI/UX design. And as of today, we lack a clear, efficient approach to tackle this problem.
unknown|1 year ago
[deleted]