Lambda the Ultimate

The limitation is with git, not with structural editing. Structural editing will lead to better version control. Versioning lines of flat text is not the right way to handle version control of programs.

There were many attempts at structural editors in history, but none got much popularity. I hope the tide is finally changing.

Post reply below

Fluidity (constrained input order) is the enemy of structural editing; if they can nip that problem then maybe...it will be popular.

But frankly, language-aware editing isn't that hard, and there is no good reason we can't store/version trees rather than flat lines of text. Dammit, incremental parsing and type checking are easy problems.

how they handle git merge where you are bound to get inconsistent code sooner or later (and which requires transitions through invalid states to get code right)

If I understand correctly (though I haven't found much details beyond the 'About' page), the idea is that multiple versions of the same code can (temporarily) exist side-by-side.

For example, consider the situation where method 'A' uses method 'B'. In one branch, method 'C' is introduced that also uses method 'B'. In another branch, 'B' is changed and 'A' is updated accordingly.

When merging these 2 branches, my understanding is that the original 'B' and the updated 'B' will both be available under different hashes. 'A' will have been updated to point to the hash of the updated 'B', where 'C' still points to hash of the original 'B'.

Obviously this is an undesirable situation, so you'll have to do some work to resolve the naming overlap between the original 'B' and the new 'B' - but it'll typecheck fine.

(I think this is a very interesting approach, but would love to see more details on how it's actually designed and what the implications are: for example, when 'B' takes a parameter of type 'T', and this type is changed, does that mean the update to 'T' also forces a new hash for 'B'?)

The author has detailed how he envisions version control here - my take above seems like a reasonable summary.

What about multiple simultaneous editing like google docs, where you can see each others cursors, and leave margin notes everyone can read? If there was live type inference/checking it could work quite well. This could also use the same kind of track-changes as google docs instead of version control. It would seem to solve versioning and merging in a way that moves towards the extreme, but in line with ideas like continuous integration and continuous deployment.

A version control system should be able to merge different files types with plugins. Merge for programs is indeed an AI-complete problem, but that does not mean that nothing can be done automatically. A structured program format can track edits semantically, which would allow for better automated merging than a merge based on plain text. An automatic plain text merge can result in code that's not even syntactically correct. Beyond syntax errors the main problem in merging is determining where code came from. If you have some ancestor C and two derivatives A,B of C, then to perform a good automated merge we need to know to which part of C the code in A,B corresponds, and which code is new. For example if the order of two definitions is changed in A, and in B one of those definitions is edited, then the merge should change the order of the definitions and edit one of them. Text based merge necessarily has to use heuristics based on the final program text to determine this, but a structural editor can just keep track of where code came from.

This is a very common theme. Plain text IDEs have to use a lot of heuristics where in a structural editor you can just do the right thing. Think about code completion while editing. While editing plain text the file is in a syntactically incorrect state, but we still want to autocomplete code based on definitions in that file. So you need to write a parser that has some heuristics to extract those definitions despite syntax errors, and possibly using an older version of the file. But then what if the programmer puts the file in a syntactically incorrect state, and then renames one of the functions in the file. Do we get autocomplete for the new function name? All these issues strongly indicate that plain text is not the right representation for code. The only reason this is not obvious to everyone is because of cultural baggage. Nobody would write an optimizing compiler which internally uses the plain text representation of code, and then transforms that with some crazy text mangling. An IDE is not any different.

Text based merge necessarily has to use heuristics based on the final program text to determine this, but a structural editor can just keep track of where code came from.

The text based editor could do that too, but I suspect it's not even a good idea. It's actually a nice property of the current state of affairs that merge behavior depends only on the states of A, B and C and not on the path from C to A and C to B, because that path is invisible. Your 'ideal' requires keeping track of a transformation that the programmer can't see and using it to merge. What if the programmer decides half way through an edit that he should have e.g. renamed a symbol instead of deleting a symbol and introducing a new one? Are we going to have a way to edit the edit-history? Or do we just decide that merge behavior isn't something the programmer needs to have full control over?

Don't get me wrong; I think better understanding of the structure of a program by the IDE during editing will be a good thing. But I don't think there's usually a "right thing" when dealing with programs under construction.

Even if it isn't a good idea, then merging ASTs still works better than merging a program as if it is a homogeneous array of characters.

But I do think it's a good idea. There doesn't need to be any complicated change tracking. You just give each location in the tree an identity, and doing an edit is assigning a new subexpression to a location. If Joe swaps the order of function definitions foo and bar, and Mary changes a subexpression of foo it all works out automatically. There is a merge conflict if both people changed the same location concurrently, or if there is a reference to a deleted symbol, or if there is a type error, or if a unit test fails. (perhaps you signal a warning if two people changed two different subexpressions of the same function concurrently, even if it did not cause a merge conflict)