> The challenge is getting this to be a useable way of entering programs.
Well exactly.
When the path between Program A and Program B can only be valid programs, you are going to end up with either a much longer, less intuitive path, or deleting everything and starting again. It can also be quite possible to invent structures which are valid but have no valid path to creating them.
Well, I think most common transformations work reasonably well. One usually doesn't want to do things completely contrary to the AST, such as convert "while a<b" to "whilea = b".
And it's certainly possible to create any valid AST in the editor I describe. The set of valid trees is extended to those with "holes" in places, which one fills in when entering a program, and it's always possible to do this.
The challenge is one of finding an intuitive user interface, not whether it's possible at all. One issue is that infix notation is unnatural for entering trees (prefix is more natural).
> It can also be quite possible to invent structures which are valid but have no valid path to creating them.
I'm curious if you have an example of such a structure?
Pedantically: if, for every valid tree, there exists a bidirectional path to the empty root node, there's always at least one path between all given pairs of valid trees ... albeit one that no developer would ever take.
You are quite right to call this out - and quite right in general. With AST verification alone your statement holds strongly.
I was remembering a professor I had who was very into formal verification and had an IDE that would only accept valid programs - however his validity checks were more than just tree based, they involved passing a type check. Which now you've called me on it, is quite definitely beyond valid AST editing.
The base case: if you have a structure with a mandated cyclical reference that doesn't accept a second (e.g. nil) type, you cannot construct it without creating an intermediate invalid program. This doesn't tend to show up if the cyclical reference is all the same type (A1 -> A2 -> A1) because you can often cheat and self reference, but it does if it is different types (A1 -> B1 -> A1). You can't construct an A without a B, which cannot be constructed without an A.
But that's still not a problem you cry! And quite right, you can edit the type itself to remove and re-add the reference.
That is until the type is built into the language, or a library.
OP clarified, but I understood that as a valid tree without a path to empty node. I don't have an example, but with grammar weird enough it sounds plausible. Especially if some form of type checking is involved, as OP mentioned.
Well exactly.
When the path between Program A and Program B can only be valid programs, you are going to end up with either a much longer, less intuitive path, or deleting everything and starting again. It can also be quite possible to invent structures which are valid but have no valid path to creating them.