17 ms·

Where is the CRDT for syntax trees

161 points by lewisjoe 5y ago

slaymaker1907 5y ago
Sort of related, but I was having to do some nasty merges and even if you have a human doing the merging, having a solid diff algorithm is still extremely important. My favorite thus far has been the recursive git strategy with histogram as the diff algorithm with regards to merging.
thomasikzelf 5y ago
We are almost there, for lists and structs there are CDRT's but a move operation across the data structure is missing. Martin Kleppman (from automerge) talks about this in his talk "CRDTs: the hard parts"[0]. I also think a range move or range delete is missing from many of these algorithms. A submission here on HN did implement a range delete on rich text (but I forgot what the name was). [0]: https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw EDIT: Ah actually Peritext (which you linked to) was the article I was thinking of. I think the range delete would be useful for regular lists as well.
- dmulligan 5y ago
  See our latest paper [0] for an atomic move operation on replicated trees. [0]: https://dominicpm.github.io/publications/kleppmann-highly-available.pdf https://dominicpm.github.io/publications/kleppmann-highly-av...
  - eternalban 5y ago
    Thank you for the paper. I have a peripheral question that’s been bugging me for a while and hopefully you can answer it: why aren’t the CS papers dated? If you hadn’t mentioned latest paper I would have to do footnote archeology to guess the general timeline.
    - dmulligan 5y ago
      Ha, I'm not sure! I just write papers, the vagaries of how and why journals and conference proceedings are published the way that they are is beyond my ken. Looking back through some of my other papers it seems that there's a mix --- some styles do include a date, especially those provided by the ACM, whilst others don't, including IEEE TPDS which is where the paper above is published. Who knows?
- kazinator 5y ago
  Syntax trees are lists and structs that have semantics. Conflict-free means that there is no conflict in the semantics, not just that the operations on a syntax tree shape result in a valid syntax tree shape. If we pass a syntax tree node with 12 children to two different servers which each add a node, we can easily resolve the structural conflict by adding both nodes, so now we have 14, and that may be a valid syntax tree. However, that 12-child node could be, say, a call to a function that takes 12 arguments. (So 11 are being passed, and one is defaulted). Adding one argument is semantically valid. Adding two means the call is bad.
  - dnautics 5y ago
    > Conflict-free means that there is no conflict in the semantics, If you start with an incorrect premise you will wind up in a strange place. Conflict free has a specific meaning, and "semantics" can have multiple layers. If your threshold is perfect conflict free semantics at all levels, then you are indeed doomed. But a CRDT can provide a distributed, conflict-free canonical source substrate, with a specific semantic meaning at a minimally useful lowest semantic level. The challenge is to find transformations that are "good enough" to minimize conflicts at the higher semantic levels that you care about.
  - monocasa 5y ago
    Practically, I don't think we're there yet. Yes, you can probably make a lisp-like that evals a currently existing crdt tree. The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. I don't want a partial update causing the execution of gods knows what. And if we get real strictly transactional with the code tree updates, what's the point of the crdt in the first place? I'm not sure these issues can't be overcome, but it's admittedly still an open problem.
    - infogulch 5y ago
      > The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. The real problem is that we're trying to solve this problem at the wrong level of abstraction. I think CRDTs can be reformulated as a subset of a larger replicated data type model that explicitly includes conflicts as part of the model, that any chosen set of transformations can be programmatically projected into a corresponding set of conflicts, that the choices of resolutions to those conflicts can be pre-packaged and composable, that some of those resolutions may need to be 'add a new transformation that choses between conflicts created by two other conflicting transformations' (basically exposing the problem up into the model of the data type), and that a composition of chosen resolutions can be proved to be fully conflict-free. The biggest benefits of this approach are: 1. It enables modeling domains where conflicts are an unavoidable part of the domain itself. 2. It allows tuning an initially pessimistic model where all conflicts are exposed to the user by gradually adjusting the conflict resolution choices so that it becomes more conflict-free over time; especially by composing known conflict-free subsets of the model into larger conflict-free subsets.
- josephg 5y ago
  Martin Kleppman has proposed using range deletes for all deletes in automerge[1]. In diamond types (my own CRDT) I'm still on the fence about whether or not this is a good idea. The downside is if you select & delete two functions, and I concurrently insert a new function in the middle of that range, then the merged result will delete my function. Thats a really bad outcome - but its pretty rare in practice. A much more common case is, I deleted 2 lines of code and you modify a parameter in one of those function calls. In this case, using range deletes your edits will also be deleted (which is what we want). Using individual deletes, the result will end up with some random junk left behind, in the form of whichever characters I typed. When we're editing code as plain text, I don't think there's any such thing as perfect here. For asyncronous collaborative editing (like git), I think generating conflict markers & human supervision for merging might be the best answer. I'd love to see someone make a prototype editor which can do AST-level concurrent editing. That would be super interesting in a bunch of ways - like, you could use the AST to do syntax highlighting in any editor too. But I'm not sure how it'd merge code when the parse tree is invalid - like, if I remove a closing brace (}) early in the function, what happens? There's a lot of cool ideas in this space. I'm excited to see people explore them as CRDTs get more popular and more mature. [1] https://github.com/automerge/automerge/issues/401 https://github.com/automerge/automerge/issues/401
  - lewisjoe 5y ago
    Makes sense. Ranged deletes might be key to handle rich-text table mutations. Seph, thanks for showing up. Author here. This write-up is just a generalization I've landed on, while thinking about the nature of another problem: handling block elements in rich text in Peritext - a project you've collaborated with I guess. Here's the link - https://github.com/inkandswitch/peritext/issues/27 https://github.com/inkandswitch/peritext/issues/27 Do throw your thoughts too. I'd be happy pick your brain on this :)
    - josephg 5y ago
      Commented in the github thread :)
  - thomasikzelf 5y ago
octopoc 5y ago
Sounds similar to what Semantic Merge[1] does. Of course it would also have to handle syntax errors. For that it could fall back to the current crop of text CRDTs. [1] https://www.semanticmerge.com/ https://www.semanticmerge.com/
dnautics 5y ago
We just got CRDTs for generic textual documents! yeesh. Patience! code has generic textual components -- like comments -- plus tree-like elements -- so it's arguably more complex. Furthermore, one expects automatically merging conflicting content to often have to be resolved because even a merge + a sophisticated node-based merging strategy will fail to capture effectful intents. However, i am excited to see tooling where, for example competing merges get run through a trichotomy (A only, B only, A + B) to see which branch satisfies the most number of tests... And then suggests the resolution accordingly.
- rackjack 5y ago
  In terms of generic textual documents, do you have a link? The only thing that comes to mind is Pijul: https://pijul.org/ https://pijul.org/ I also found peritext: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
  - ath92 5y ago
    There's also yjs: https://github.com/yjs/yjs https://github.com/yjs/yjs
  - dnautics 5y ago
    oh I think peritext is "automerge" with formatting? which is referenced by OP. OP calls it a "json-based CRDT", which is true for automerge, but that description may be confusing: JSON is the "storage/(transport?) datastructure", the "materialized datastructure" for automerge is plain text. Note that one of the creators of peritext (martin kleppmann) is also creator of automerge.
- LAC-Tech 5y ago
  We just got CRDTs for generic textual documents! yeesh. Patience! Really? Link?
  - dnautics 5y ago
    automerge? it's in OP
pshc 5y ago
Dear zohopublic.com: please use real <a> anchor tags for hyperlinks instead of restyled <span>s, thank you
- remram 5y ago
  Oh my that's awful! I thought you had encountered some sort of accessibility issue (which are serious on their own) but middle-click and right-click don't even work. How could they ship this?
awinter-py 5y ago
critical for version control, esp if you believe git history is important for long-term software maintainability -- smarter transplantation tracking leads to history 'surviving for longer' even as things jump context
blueprint 5y ago
what if automerge added a generalization of the 'Text' object's features like 'insertAt' etc which reflect the set of operations a programmer does in changing an AST during development?
nawgz 5y ago
There is this really beautiful algorithm implemented behind really oldschool JS that I have seen used a couple times: WebGME. https://github.com/webgme/webgme https://github.com/webgme/webgme It is a Model-Based-Systems-Engineering tool, as far as I can tell, and it lets you create "metamodels" (SysML diagrams / rules essentially) and then collaboratively author some model graph, giving you a "commit" for every action, a version history, a git-like branching and merging model, and more. The collaborative aspect is pretty strong in their own UI, I've tried to build my own and couldn't get it as easily, but I guess my question is: has anyone ever used this tool as well?
dan-robertson 5y ago
I was just talking about this problem yesterday (only to say that it is a problem. I don’t have any solutions). I was thinking in the context of a pijul/categorical theory of patches model rather than a CRDT that resolves conflicts deterministically (in the pijul model all merges are successful and well-behaved in that the order of mergin doesn’t matter but your data structure may contain representations of merge conflicts). Fundamentally, I think the problem is that for a good AST model, you want to be able to handle transformations of the following forms: e <-> (e) if(e) {f; g} <- if(e) f -> if(e) {h; f} a (b c) d <-> a b c d (a b) (c d) <-> (a b c d) The second line is meant to ask: how would you merge people independently making the middle-to-left and middle-to-right changes with your CRDT. I would like to point out particularly the changes of nesting depth and the merging and splitting of subsequences. Let me briefly describe the pijul/CToP model. You start with a simple model of files: each file is a totally ordered set of lines, and a model of patches: a patch is an injection taking the lines of one file to equal lines in another file (i.e. it isn’t changing the contents of the line) and furthermore it is increasing which means the relative order is maintained. New lines are points not in the image of the function and deleted lines are represented by pseudo-lines in the new file with a “deleted” tag. This then forms a category with possible files being the objects and patches the morphisms. You then do some magic to figure out how to add all push outs to the category. Push outs correspond to merges (more formally, the push out of the span B <-f- A -g-> C is an object P with morphisms p: B->P, q: C->P such that the compositions fp and gq are equal and the universal property that for any other object Q and morphisms rs satisfying the same properties there is a unique morphism u: P->Q such that fpu = fr = gs = gqu, which in our case means that the merge is fair in the sense that it hasn’t accidentally resolved a conflict that was ambiguous). The result is a model where files are partially ordered sets of lines and patches are just (strictly) increasing functions. If two lines do not have an order relative to each other, that is the representation of a merge conflict. I don’t have a good model for how that sort of thinking could extend to ASTs. Possibly an OT-in-CRDT model could cope with Emacs paredit style transformations of the tree better than this. I’m also unconvinced that solving tables would solve ASTs or vice versa. The constraints on tables feel different to me (no nesting but global constraints on the length of each row or column. Maybe allowing irregular tables where some cells are merged makes it harder). And a regular table feels like it could better fit into a set-with-extra-structure model (like total orders for each row and column or something somehow like that). Anyway, I’ll be curious to see if someone ever comes up with a really good model to this and, if so, how heuristic-heavy it needs to be (either in the merging or the choice of diff representation) to get good results.
WhatIsDukkha 5y ago
I ask myself - "Why is it that almost all programming environments work in plain text buffers and not syntax trees?" (there are several strong answers to this) Adding a crdt on top of that... But I'll go have a noodle about what this would be good for anyway, thanks :)
dataflow 5y ago
Sounds nice in theory. But how is syntax based version control ever supposed to work when we have so many languages that literally parse differently depending on dependencies that aren't even in the codebase? Let alone ones that easily take hours to compile even when they are in the codebase? Sounds impossible in practice unless we restrict ourselves to sufficiently context free languages.
- int0x80 5y ago
  Do you have an example of a language that parses different because of dependencies?
  - dataflow 5y ago
    Sure, just plain C can wreck any kind of parsing with its macros.
    - int0x80 5y ago
      Technically the parsing itself and the grammar are the same, they don't depend on defined macros. Yes, defining a macro in an included file can make the resulting AST change, but the parsing algorithm doesn't really care about it.
    - chriswarbo 5y ago
      Unfortunately, text-substitution macros (like CPP) pretty much force a source file to be treated as a stream of bytes. They can be handy, but delimited macros (e.g. like Lisps) are much less invasive.
      - dataflow 5y ago
        Yeah that's kind of my point. The idea of syntax based source control is nice in theory but in reality it's just wishful thinking with the kinds of languages we use.
  - layer8 5y ago
__MatrixMan__ 5y ago
It would be interesting to examine how often the syntactically correct merge solution is also deemed to be semantically correct by both authors involved. Imagine a list of emoji below the question: "How would you rate this merge?" And then behind the scenes:some AI trickery profiling the way any pair of users are likely to conflict/agree. The future is looking... high contrast.
kazinator 5y ago
Where is the Conflict-Free Replicated Data Type for syntax trees? It seems instantly obvious to me (which is a disclaimer encouraging you to be suspicious) that the answer is: exactly nowhere. Syntax trees have conflicts. If you and I have the same syntax tree, and then change the syntax independently, the results have to be merged, which may be semantically impossible. The kinds of operations you'd like to have on a syntax tree data type are not conflict-free.
- layer8 5y ago
  I'm getting flashbacks to SVN tree conflicts.
- dnautics 5y ago
  You could say that about free text too. You and I could edit the same word and then have a semantic conflict. Arguably the situation with code is better since some things like tests are less likely to conflict so you can have automated flagging of spots that have caused problems.
  - kazinator 5y ago
    > You could say that about free text too. Not only can, but did: about 15 minutes ago in another subthread under this submission.
    - deleted 5y ago
      [deleted]
- speed_spread 5y ago
  Would it be possible to design a constrained syntax that would guarantee mergeability while preserving decent expressivity?

161 points by lewisjoe 5y ago

slaymaker1907 5y ago

Sort of related, but I was having to do some nasty merges and even if you have a human doing the merging, having a solid diff algorithm is still extremely important. My favorite thus far has been the recursive git strategy with histogram as the diff algorithm with regards to merging.

thomasikzelf 5y ago

We are almost there, for lists and structs there are CDRT's but a move operation across the data structure is missing. Martin Kleppman (from automerge) talks about this in his talk "CRDTs: the hard parts"[0]. I also think a range move or range delete is missing from many of these algorithms. A submission here on HN did implement a range delete on rich text (but I forgot what the name was). [0]: https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw EDIT: Ah actually Peritext (which you linked to) was the article I was thinking of. I think the range delete would be useful for regular lists as well.

dmulligan 5y ago
See our latest paper [0] for an atomic move operation on replicated trees. [0]: https://dominicpm.github.io/publications/kleppmann-highly-available.pdf https://dominicpm.github.io/publications/kleppmann-highly-av...
- eternalban 5y ago
  Thank you for the paper. I have a peripheral question that’s been bugging me for a while and hopefully you can answer it: why aren’t the CS papers dated? If you hadn’t mentioned latest paper I would have to do footnote archeology to guess the general timeline.
  - dmulligan 5y ago
    Ha, I'm not sure! I just write papers, the vagaries of how and why journals and conference proceedings are published the way that they are is beyond my ken. Looking back through some of my other papers it seems that there's a mix --- some styles do include a date, especially those provided by the ACM, whilst others don't, including IEEE TPDS which is where the paper above is published. Who knows?
kazinator 5y ago
Syntax trees are lists and structs that have semantics. Conflict-free means that there is no conflict in the semantics, not just that the operations on a syntax tree shape result in a valid syntax tree shape. If we pass a syntax tree node with 12 children to two different servers which each add a node, we can easily resolve the structural conflict by adding both nodes, so now we have 14, and that may be a valid syntax tree. However, that 12-child node could be, say, a call to a function that takes 12 arguments. (So 11 are being passed, and one is defaulted). Adding one argument is semantically valid. Adding two means the call is bad.
- dnautics 5y ago
  > Conflict-free means that there is no conflict in the semantics, If you start with an incorrect premise you will wind up in a strange place. Conflict free has a specific meaning, and "semantics" can have multiple layers. If your threshold is perfect conflict free semantics at all levels, then you are indeed doomed. But a CRDT can provide a distributed, conflict-free canonical source substrate, with a specific semantic meaning at a minimally useful lowest semantic level. The challenge is to find transformations that are "good enough" to minimize conflicts at the higher semantic levels that you care about.
- monocasa 5y ago
  Practically, I don't think we're there yet. Yes, you can probably make a lisp-like that evals a currently existing crdt tree. The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. I don't want a partial update causing the execution of gods knows what. And if we get real strictly transactional with the code tree updates, what's the point of the crdt in the first place? I'm not sure these issues can't be overcome, but it's admittedly still an open problem.
  - infogulch 5y ago
    > The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. The real problem is that we're trying to solve this problem at the wrong level of abstraction. I think CRDTs can be reformulated as a subset of a larger replicated data type model that explicitly includes conflicts as part of the model, that any chosen set of transformations can be programmatically projected into a corresponding set of conflicts, that the choices of resolutions to those conflicts can be pre-packaged and composable, that some of those resolutions may need to be 'add a new transformation that choses between conflicts created by two other conflicting transformations' (basically exposing the problem up into the model of the data type), and that a composition of chosen resolutions can be proved to be fully conflict-free. The biggest benefits of this approach are: 1. It enables modeling domains where conflicts are an unavoidable part of the domain itself. 2. It allows tuning an initially pessimistic model where all conflicts are exposed to the user by gradually adjusting the conflict resolution choices so that it becomes more conflict-free over time; especially by composing known conflict-free subsets of the model into larger conflict-free subsets.
josephg 5y ago
Martin Kleppman has proposed using range deletes for all deletes in automerge[1]. In diamond types (my own CRDT) I'm still on the fence about whether or not this is a good idea. The downside is if you select & delete two functions, and I concurrently insert a new function in the middle of that range, then the merged result will delete my function. Thats a really bad outcome - but its pretty rare in practice. A much more common case is, I deleted 2 lines of code and you modify a parameter in one of those function calls. In this case, using range deletes your edits will also be deleted (which is what we want). Using individual deletes, the result will end up with some random junk left behind, in the form of whichever characters I typed. When we're editing code as plain text, I don't think there's any such thing as perfect here. For asyncronous collaborative editing (like git), I think generating conflict markers & human supervision for merging might be the best answer. I'd love to see someone make a prototype editor which can do AST-level concurrent editing. That would be super interesting in a bunch of ways - like, you could use the AST to do syntax highlighting in any editor too. But I'm not sure how it'd merge code when the parse tree is invalid - like, if I remove a closing brace (}) early in the function, what happens? There's a lot of cool ideas in this space. I'm excited to see people explore them as CRDTs get more popular and more mature. [1] https://github.com/automerge/automerge/issues/401 https://github.com/automerge/automerge/issues/401
- lewisjoe 5y ago
  Makes sense. Ranged deletes might be key to handle rich-text table mutations. Seph, thanks for showing up. Author here. This write-up is just a generalization I've landed on, while thinking about the nature of another problem: handling block elements in rich text in Peritext - a project you've collaborated with I guess. Here's the link - https://github.com/inkandswitch/peritext/issues/27 https://github.com/inkandswitch/peritext/issues/27 Do throw your thoughts too. I'd be happy pick your brain on this :)
  - josephg 5y ago
    Commented in the github thread :)
- thomasikzelf 5y ago

octopoc 5y ago

Sounds similar to what Semantic Merge[1] does. Of course it would also have to handle syntax errors. For that it could fall back to the current crop of text CRDTs. [1] https://www.semanticmerge.com/ https://www.semanticmerge.com/

dnautics 5y ago

We just got CRDTs for generic textual documents! yeesh. Patience! code has generic textual components -- like comments -- plus tree-like elements -- so it's arguably more complex. Furthermore, one expects automatically merging conflicting content to often have to be resolved because even a merge + a sophisticated node-based merging strategy will fail to capture effectful intents. However, i am excited to see tooling where, for example competing merges get run through a trichotomy (A only, B only, A + B) to see which branch satisfies the most number of tests... And then suggests the resolution accordingly.

rackjack 5y ago
In terms of generic textual documents, do you have a link? The only thing that comes to mind is Pijul: https://pijul.org/ https://pijul.org/ I also found peritext: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
- ath92 5y ago
  There's also yjs: https://github.com/yjs/yjs https://github.com/yjs/yjs
- dnautics 5y ago
  oh I think peritext is "automerge" with formatting? which is referenced by OP. OP calls it a "json-based CRDT", which is true for automerge, but that description may be confusing: JSON is the "storage/(transport?) datastructure", the "materialized datastructure" for automerge is plain text. Note that one of the creators of peritext (martin kleppmann) is also creator of automerge.
LAC-Tech 5y ago
We just got CRDTs for generic textual documents! yeesh. Patience! Really? Link?
- dnautics 5y ago
  automerge? it's in OP

pshc 5y ago

Dear zohopublic.com: please use real <a> anchor tags for hyperlinks instead of restyled <span>s, thank you

remram 5y ago
Oh my that's awful! I thought you had encountered some sort of accessibility issue (which are serious on their own) but middle-click and right-click don't even work. How could they ship this?

awinter-py 5y ago

critical for version control, esp if you believe git history is important for long-term software maintainability -- smarter transplantation tracking leads to history 'surviving for longer' even as things jump context

blueprint 5y ago

what if automerge added a generalization of the 'Text' object's features like 'insertAt' etc which reflect the set of operations a programmer does in changing an AST during development?

nawgz 5y ago

There is this really beautiful algorithm implemented behind really oldschool JS that I have seen used a couple times: WebGME. https://github.com/webgme/webgme https://github.com/webgme/webgme It is a Model-Based-Systems-Engineering tool, as far as I can tell, and it lets you create "metamodels" (SysML diagrams / rules essentially) and then collaboratively author some model graph, giving you a "commit" for every action, a version history, a git-like branching and merging model, and more. The collaborative aspect is pretty strong in their own UI, I've tried to build my own and couldn't get it as easily, but I guess my question is: has anyone ever used this tool as well?

dan-robertson 5y ago

I was just talking about this problem yesterday (only to say that it is a problem. I don’t have any solutions). I was thinking in the context of a pijul/categorical theory of patches model rather than a CRDT that resolves conflicts deterministically (in the pijul model all merges are successful and well-behaved in that the order of mergin doesn’t matter but your data structure may contain representations of merge conflicts). Fundamentally, I think the problem is that for a good AST model, you want to be able to handle transformations of the following forms: e <-> (e) if(e) {f; g} <- if(e) f -> if(e) {h; f} a (b c) d <-> a b c d (a b) (c d) <-> (a b c d) The second line is meant to ask: how would you merge people independently making the middle-to-left and middle-to-right changes with your CRDT. I would like to point out particularly the changes of nesting depth and the merging and splitting of subsequences. Let me briefly describe the pijul/CToP model. You start with a simple model of files: each file is a totally ordered set of lines, and a model of patches: a patch is an injection taking the lines of one file to equal lines in another file (i.e. it isn’t changing the contents of the line) and furthermore it is increasing which means the relative order is maintained. New lines are points not in the image of the function and deleted lines are represented by pseudo-lines in the new file with a “deleted” tag. This then forms a category with possible files being the objects and patches the morphisms. You then do some magic to figure out how to add all push outs to the category. Push outs correspond to merges (more formally, the push out of the span B <-f- A -g-> C is an object P with morphisms p: B->P, q: C->P such that the compositions fp and gq are equal and the universal property that for any other object Q and morphisms rs satisfying the same properties there is a unique morphism u: P->Q such that fpu = fr = gs = gqu, which in our case means that the merge is fair in the sense that it hasn’t accidentally resolved a conflict that was ambiguous). The result is a model where files are partially ordered sets of lines and patches are just (strictly) increasing functions. If two lines do not have an order relative to each other, that is the representation of a merge conflict. I don’t have a good model for how that sort of thinking could extend to ASTs. Possibly an OT-in-CRDT model could cope with Emacs paredit style transformations of the tree better than this. I’m also unconvinced that solving tables would solve ASTs or vice versa. The constraints on tables feel different to me (no nesting but global constraints on the length of each row or column. Maybe allowing irregular tables where some cells are merged makes it harder). And a regular table feels like it could better fit into a set-with-extra-structure model (like total orders for each row and column or something somehow like that). Anyway, I’ll be curious to see if someone ever comes up with a really good model to this and, if so, how heuristic-heavy it needs to be (either in the merging or the choice of diff representation) to get good results.

WhatIsDukkha 5y ago

I ask myself - "Why is it that almost all programming environments work in plain text buffers and not syntax trees?" (there are several strong answers to this) Adding a crdt on top of that... But I'll go have a noodle about what this would be good for anyway, thanks :)

dataflow 5y ago

Sounds nice in theory. But how is syntax based version control ever supposed to work when we have so many languages that literally parse differently depending on dependencies that aren't even in the codebase? Let alone ones that easily take hours to compile even when they are in the codebase? Sounds impossible in practice unless we restrict ourselves to sufficiently context free languages.

int0x80 5y ago
Do you have an example of a language that parses different because of dependencies?
- dataflow 5y ago
  Sure, just plain C can wreck any kind of parsing with its macros.
  - int0x80 5y ago
    Technically the parsing itself and the grammar are the same, they don't depend on defined macros. Yes, defining a macro in an included file can make the resulting AST change, but the parsing algorithm doesn't really care about it.
  - chriswarbo 5y ago
    Unfortunately, text-substitution macros (like CPP) pretty much force a source file to be treated as a stream of bytes. They can be handy, but delimited macros (e.g. like Lisps) are much less invasive.
    - dataflow 5y ago
      Yeah that's kind of my point. The idea of syntax based source control is nice in theory but in reality it's just wishful thinking with the kinds of languages we use.
- layer8 5y ago

__MatrixMan__ 5y ago

It would be interesting to examine how often the syntactically correct merge solution is also deemed to be semantically correct by both authors involved. Imagine a list of emoji below the question: "How would you rate this merge?" And then behind the scenes:some AI trickery profiling the way any pair of users are likely to conflict/agree. The future is looking... high contrast.

kazinator 5y ago

Where is the Conflict-Free Replicated Data Type for syntax trees? It seems instantly obvious to me (which is a disclaimer encouraging you to be suspicious) that the answer is: exactly nowhere. Syntax trees have conflicts. If you and I have the same syntax tree, and then change the syntax independently, the results have to be merged, which may be semantically impossible. The kinds of operations you'd like to have on a syntax tree data type are not conflict-free.

layer8 5y ago
I'm getting flashbacks to SVN tree conflicts.
dnautics 5y ago
You could say that about free text too. You and I could edit the same word and then have a semantic conflict. Arguably the situation with code is better since some things like tests are less likely to conflict so you can have automated flagging of spots that have caused problems.
- kazinator 5y ago
  > You could say that about free text too. Not only can, but did: about 15 minutes ago in another subthread under this submission.
  - deleted 5y ago
    [deleted]
speed_spread 5y ago
Would it be possible to design a constrained syntax that would guarantee mergeability while preserving decent expressivity?