Why Don't We Have a General-Purpose Tree Editor? (2014)
pcmonk.me
pcmonk.me
https://www.emacswiki.org/emacs/ParEdit
edit: paredit demos:
Productive Emacs: Paredit https://www.youtube.com/watch?v=T1WBsI3gdDE
Emacs Rocks! Episode 14: Paredit: https://www.youtube.com/watch?v=D6h5dFyyUX0
By comparison, the Emacs Wiki article is a poor introduction, because introduction is not its purpose; it's there to collect resources for people who already use paredit, and a good introduction answers the question of why someonr would want to start.
That said, thanks so much for posting about it here! I'm really looking forward to learning it today.
I've never used it and I'm genuinely curious.
If I was working on lisp-like languages, I would definitely use it. But ParEdit didn't stick to me, even after a few attempts. I didn't like the key bindings, and I think that the interface is too complex for me.
Also, there are alternatives. What do you think about them?
Not sure what it is like for other tree structures.
I pretty much just use indented text trees for all but the most complex parts of software design and I find it works very well.
You mean points and sub-points?
>all but the most complex parts
And what do you use for those?
What I've concluded, is that we don't have a good representation for a general purpose tree editor to work on. Roughly speaking, S-expressions are just a bit too simple, and XML is way too complicated.
General purpose plain text editors work so well because we've agreed on a common representation (more or less), which is easy for text. But as soon as you want to move to useful, common tree-structures, you have to agree on both representation and semantics, which makes it much harder.
One challenge we need to solve is - what level do you want to work on? Let's say you're working on some code. You may want to treat functions and blocks as a tree structure, but you want to treat simple mathematical expressions as text. Where this threshold is, is entirely context-dependent. The editor needs to understand the language and be able to expand text into its tree structure, or collapse the tree into its text representation, at any node in the tree.
This implies that we need to agree on a common format for defining the conversion (parsing and generating) between text and trees. We'd probably also need a package system which contains common definitions for all major languages.
That said, during my research I ran across an ancient Usenet thread from 1989[1]. In it, the OP asks:
> Should the language designers be making work for the language-oriented editor designers or should the language-oriented editor designers be making work for the language designers?
(The thread rapidly devolves into an all out flame war about whether or not C can be considered to be context-free)
Lisp feels like a language designed specifically to make a language-oriented editor designer happy, but most other popular languages fail the context-free test one way or another, thus making them difficult to define good grammars for. The problem seems to be that historically the language designers have far outnumbered the language-oriented editor designers.
[1] https://groups.google.com/d/msg/comp.lang.misc/MCZmQv56--Q/O...
And what do you mean by "s-expressions just too simple"? Isn't simplicity something to strive for?
Funny, that makes me think of the new Wikitext editor that the Wikimedia Foundation is developing. [1]
They are using the previous Visual editor infrastructure, and they are having problems because features that make sense for a rich text editor are creeping into the plain-text code editor (such as unwanted copy-pasting of styling code).
I should stress "a bit". Actually, looking closer at s-expressions right now (I was writing based on what I remembered), I'd like to flip that statement. S-expressions are just a bit more complex than what I have in mind. Or alternately: they're equivalent under some trivial transformation.
It depends on how you look at things - there are supposedly many different implementations of s-expressions, which support different fundamental data types. The basic idea is simpler. There are no fundamental data types, just nodes. For example a 'bit' is a node which can contain one of two child nodes ('one' or 'zero'). Any tree which represents data in memory on a computer can be expanded down to a collection of bits. Though in a text representation or tree editor the user will generally have collapsed the tree such that they don't see individual bits.
What I have in mind could look more complex than s-expression in a different context though: the text file representation of the trees may have more syntactic sugar than s-expressions in lisp.
The representation isn't significantly different, but the focus is. I'm focusing more on things related to type theory, schemas, how to represent patches/diffs, standardizing parsing/generation and other transforms, etc.
I am working on something like that too, and I'm completely fine with symbols (with their arbitrary definition by lisp and user) being the fundamental elements.
I'd say what you gain is reusability, mostly. When you impose a datatype on data, it comes with a series of constraints and expectations, so you can only use the data in the ways prescribed by its type.
If the data doesn't have attached a type of is own, you can use it in different ways at different contexts - this can be valuable for data transformation processes, such as compilation or system interfaces. I suppose you could get the same effect by casting the data to a new type when you change it to a new context.
I've read a bunch about applying semiotics theory to programming, and changing the meaning of the symbols "on the go" is closer to the way we think (inferring meanings from the signs adequate to the current context) than the old mathematical approach of "every datum has one well-defined type, and only one".
PS, if you're as enthusiastic about this idea as I am, we should talk, can I email you?
Ummm json??
JSON is way too complex. JSONS assumes that you have an object/record structure (labels and values), and gives you both objects and arrays with which to build tree structures.
E.g.
In the early days of programming text editors, we dealt with this difficulty by exploiting the human brain's mechanisms for dealing with serialized trees -- which is to say the human brain's facilities for processing language and reading and writing text. By doing this, we could represent all kinds of hierarchically structured code, and let the human brain process it. But even in these early days, we started bringing in visual aids for reading structure: indentation and braces.
Now, if you look at modern IDEs, you'll find even more geometric/visual representation of the tree structure of code, in the form of collapsible tree controls operating on the code. This isn't to naively say that graphical programming is the way to go, since the potential for interrelation and complexity of structure in code is far too high to comfortably represent in 2 or even 3 dimensions. The way forward is to be able to dynamically visualize very specific contexts. (One example I can think of of the top of my head, would be to quickly visualize all "subscribers" of an Observer, then be able to visualize the 2nd order "users" of those subscribers. Another would be to visualize patterns in code supporting dataflows as an explicit flow graph.)
def g x = print x; f
(def f ()
(let ((x (readline)))
(g x)))
(def g (x)
(print x)
(f))
[1] Unless your "tree"-view is actually a lazy call-graph …
I imagine a decent tree editor would let me:
- Navigate and edit the structure and its contents in a linear representation, like using paredit on an s-expression.
- Navigate and edit the structure and its contents in a more "tree-like" representation, e.g. as boxes+arrows, or nested boxes.
- Toggle between display modes on a per-term basis, e.g. using boxes+arrows for the top-level (say, function definitions in a Lisp file) and s-expressions for the contents.
- Fold/unfold terms/trees (code folding, but for expressions rather than lines)
- Allow plugins/preferences tailored for particular trees, e.g. syntax colouring for programming language parse trees.
As a more elaborate idea, we could allow plugins to extend the tree/graph structure with "virtual" nodes, e.g. linking names to their definitions, documentation, tests, etc. as if they were code-folded parts of the source code.
Emacs can hide/show blocks in Lisp expressions (and others). Install HideShow (https://www.emacswiki.org/emacs/HideShow). I personally never use it, generally the right solution is to refactor (but there might be good use cases too).
> As a more elaborate idea, we could allow plugins to extend the tree/graph structure with "virtual" nodes, e.g. linking names to their definitions, documentation, tests, etc. as if they were code-folded parts of the source code.
Basically, when working from Emacs through Slime, the Common Lisp backend (called Swank) injects such metadata to the runtime objects (source file if a file exists, original code, documentation). You could define your very own properties if you want, like how a particular form should be displayed to the user. What already exists, for example, is a way to define custom indentation rules for macros, which are used on the Emacs side to indent your code as you wish.
Slime also decorates values in the buffer so that they act as "presentation" objects (https://www.common-lisp.net/project/slime/doc/html/Presentat...).
Yes, I've used it before and it's quite nice.
I've not used Slime, or done any Common Lisp programming for that matter.
I do love Emacs, and calling out to a sub/inferior-process for language-specific info is a good idea; it can just be frustrating to actually get the darn things to work though. After failing to get Geiser to work for Racket, or ghc-mod || intero || dante for Haskell, I've resigned myself to being happy with just syntax colouring :(
If you pay attention to these characteristics you will begin to notice the regularity with which such systems crop up and die. In my experience there's no use trying to talk enthusiasts out of this idea. I even attempted such a system myself many years ago. It's almost a rite of passage.
The reason tree editors (aka graph editors with out cycles, yet) don't work is similar to why we use relational DBs, instead of more the natural interpretation of data as graphs, boils down to, graph algorithms are slow and complex. In practice the added complexity outweighs the perceived benefits. The way people currently edit code, although not perfect, actually works really well. You have to weigh the costs of moving away from a simple system that works against the benefits and complexity of the new system.
Above I was referring to attempts to apply this idea to general programming. I'm not saying such systems are impossible just that it's a bad idea to assume it will make the programmer's life easier.
Just because a tool can't solve all problems in their generality doesn't make it automatically worthless, there are situations where less is truly more.
Excel is a great tool for making trees; just add a column that names your parent. I used Excel to create a prototype of an event driven animation sequencing engine for a Disney game. It was more of a state machine / directed graph than a tree, but the only constraint there is data, not the editor. The prototype was later replaced (after the game using Excel shipped) with a gui based tree editor, but not something that could be called "general purpose".
I've long thought that hierarchical file formats come with some pretty bad downsides, from both sides, usage and implementation. You don't need a hierarchical format as long as you are willing to name all nodes and not allow anonymous nodes. Once you do that, you can have a flat file structure with fields that reference other nodes. Once you do that, XML feels crazy. Easier to implement parsers that don't have to do overblown amounts of dynamic memory allocation, easier for humans to read & follow, easier to share references or allow non-tree structures, etc. etc.
The author specifically describes a platform in which domain specific concerns are facilitated by plugins, so I don't see why we are "automatically in domain-specific territory". One could easily envision classes of plugins for drawing nodes and edges (perhaps a canvas DSL), plugins for enforcing the domain's specific rules, etc.
This is not a new idea, people have tried it before. If there was a decent solution it would already exist. People have tried to make general purpose graph editors & tree GUIs & layout engines, and there have been a bunch of people that thought they were being smart by architecting it to accept plugins. There's a reason you've never heard of any of them; nothing was general purpose enough to stick around, and applications that didn't try to be "general purpose" have vastly superior UI/UX.
I spent several years building a tree editor (the animation sequencing project I mentioned earlier). I've also used well known tree editors in node-based gui apps for decades. (Check out programs for film & game production like Nuke, Maya & Houdini -- they are tree editors.) Simply put, there are not enough commonalities between applications in different domains to make it worth building a shared "general purpose" editor. The workflows, problems, and schemas are too distinct. The tree isn't even close to the hard part anyway.
More seriously, that looks like at least a sizable subset of org-mode's capabilities, implemented in a way that doesn't require clearing the hurdle that getting comfortable with Emacs tends to be. How is it on the import/export/interop side?
Org-mode itself seems like a tool where you have to read fifty pages of documentation to make good use of it. Maybe I'm exaggerating, but I've tried it a couple of times, and it never seems to be worth the complexity penalty vs. using a plain text file.
I'm also not sure what you mean by "complexity penalty vs. using a plain text file", since Org files are plain text files, with all the magic implemented in the UI layer - I regularly edit Org files on my phone with Editorial, and while the UI is obviously rudimentary by comparison, such editing is not actually difficult to do. Will you elaborate on what you mean here?
Without having to read anything you just have to remember to use * to mark sections and * * for subsections and so on. Then you use tab to expand/collapse the sections. That's rather intuitive, not more complicated than a plain text file and already you have better highlighting and additional functionality.
Then sometimes I wonder "hey, I'd like to have a link to this URL in this file" or "I'd like to export this to HTML or PDF so that I can send it to my friend who doesn't use org-mode without losing the formatting". And then you look in the manual and you (generally) find what you're looking for.
Sure if you want to be an org-mode wizard you'll have to learn quite a bit but I really don't see "the complexity penalty vs. using a plain text file". The complexity is only here if you want it.
Edit: also the array auto-formatting is a godsend. Doing it by hand in text files is tedious.
The problem is not trees, they are readily available in many formats. The problem is schemas. If there are no rules on the branches everything becomes "Old_stuff" or "important_work" or whatever people do to their document folders as the tide turns.
You need trees layered over trees to provide some structure and get that sweet workflow QC. Graph-homomorphisms between trees that is, or slice categories over whatever structure you need to maintain. Trees (or graphs) in semantic/syntactic relationships stacked as high as you can muster. Usually this is presented as a two-layered structure-tree+data-tree system in end user applications, with a fixed semantic tree depending on the domain in application. The trick is finding the balance between end-user configurability of layers n+1 and the required knowledge to design useful structures. People who edit layer 2 should probably be domain experts, and layers 3 and above are best left to programmers and computer scientists. If this was a solved problem, nobody would buy CRUD-software, and a good half of us would be looking for work.
1. Nobody knows what it should look like.
2. Nobody knows how it should work.
I fear this article has left me as much in the dark on these points as I was before I read it. Perhaps someone else here will find something in it I missed.
There is a gaping hole in the market.
Leo is of particular interest because it automatically syncs between the tree and code files: http://leoeditor.com/tutorial-programming.html
The approach is documented here: http://leoeditor.com/appendices.html#the-mulder-ream-update-...
I'm a heavy Emacs and Org mode user. But at this time I've given up on being proficient in Emacs-Lisp and how it ties to the whole Emacs ecosystem.
So I searched for a self-extensible editor in Python, and find Leo.
I haven't taken the time to learn it really well, but I did fiddle with some tree editing in Python with it, and it works as advertised. If I didn't have to work for a living, I'd spend most of my time porting over the cool aspects of Emacs to Leo.
Unfortunately, the documentation/web site is very opaque. Not so bad that it's useless, but bad enough that if anyone wants to learn it well they'll have to do a lot of Google searching (in the mailing list) or code browsing.
Also, to be frank, it's not a great editor compared to Vim/Emacs. But that should be easily fixable with scripting/code changes.
For instance, doesn't the fact that people do pure algebra with Mathematica (forgetting about all the numerics, integrals, etc.) demonstrate that TeX loses for sufficiently large equations? Even if one only needs to use one or two functions with a very obvious tree interpretation (e.g., distributing multiplication over addition), Mathematica beats TeX for large enough equations.
What graphical equation editors have you used? This was what turned up when I searched google: http://equalx.sourceforge.net
\begin{equation}
H_n(i) =
\begin{cases}
\left(
H_{n-1}(i)_2,
H_{n-1}(i)_1
\right) &
0 \le i < 2^{2(n-1)}
\\
\left(
H_{n-1}(i-2^{2(n-1)})_1,
H_{n-1}(i-2^{2(n-1)})_2 + 2^{n-1}
\right) &
2^{2(n-1)} \le i < 2 \cdot 2^{2(n-1)}
\\
\left(
H_{n-1}(i-2\cdot2^{2(n-1)})_1 + 2^{n-1},
H_{n-1}(i-2\cdot2^{2(n-1)})_2 + 2^{n-1}
\right) &
2 \cdot 2^{2(n-1)} \le i < 3 \cdot 2^{2(n-1)}
\\
\left(
- H_{n-1}(i-3\cdot2^{2(n-1)})_2 + 2^{n}-1,
- H_{n-1}(i-3\cdot2^{2(n-1)})_1 + 2^{n-1}-1
\right) &
3 \cdot 2^{2(n-1)} \le i < 4 \cdot 2^{2(n-1)}
\\
\end{cases}
\end{equation}
I use Mathematica, and I just use the plaintext Mathematica syntax for large equations too. I also break these into multiple lines.
I understand how to indent TeX, but when you have a hundred algebraic terms it's very unwieldly, and Mathematica becomes clearly superior (for me) just to visualize it.
Anyways, it sounds like you're just saying you haven't found the graphical visualization for equation trees to be useful, so you stick with the linear representation, but the manipulations of those trees (by mathematica, or some other dedicated editor) is still useful.
In this case I would add that we would probably still need some sort of visualization aid for sufficiently large equations, and that the tools are just not good right now. After all, much/most code is written in normal (linear) text editors, but some people still do find it useful to "collapse" sections of code, corresponding to branches of the tree structure induced by indentation. Many people don't bother with this right now because it can cause headaches that simple scrolling does not, but better tools may change this.
Let's imagine a world that has standardized on certain UIs - just like TextMate/sublime style hotkeys are common in graphical editors, let's say we had iWorks[1] style table editing hotkeys everywhere and a TBD standard for tree operations that you could learn once and then apply everywhere. Basically you need 'sibling', 'union' and 'splice', right? That really wouldn't be more difficult than text operations IMO. I could see this for all sorts of purposes, starting with a standard configuration GUI for json / xml config files.
[1] because damnit these are still the only sane and consistent table hotkeys.
click on node -> select-family -> command-x (family gets highlighted similar to Excel) -> select target node -> use sibling or append-child (implicitely moves the family in the clipboard)
The only other special move you need is a switch-position between siblings. for the insert actions it would be best to have next-sibling and previous-sibling (alt-arrow left/right like iWorks tables?) and last/first child.
As a person interested in programming language design, that makes me wonder if visual programming might be the sort of thing that we as programmers don't use because it is, in some sense, "beneath us". You can argue that the complexity of a standard Max patch is much lower than your production system, but many production systems are "render database to JSON", which seems far less complex than, say, a feature film, many of which are made almost entirely in Houdini.
I think Ted Nelson's ZigZag structure is the closest anyone has come as yet, but manipulating those is NOT user friendly (to say the least). Visualization of multidimensional networks is difficult on many levels, particularly UI. At a certain point you probably come up against hard cognitive limits of human thought.
Whilst networks/graphs in general are very expressive, they can also be tricky to manage in some situations; e.g. think of a graph containing a cycle:
A -> B
^ |
| V
D <- C
B -> C
^ |
| V
A <- D
If we forbid cycles, we get a "directed acyclic graph" (DAG); it's like a tree, but multiple parents are allowed. DAGs are nice since we can do things like topologically sort them.
If we only allow nodes to have a single incoming edge, we get trees. The nice thing about trees is that they can be represented without any notion of "references" or "arrows". For example, we can write trees by nesting parentheses: (A (B C) D) is the tree:
C <-- B <-- A --> D
C <-- B <-- A --> D
^ |
| |
\-----------/For circular structures, you could also have:
'#1=(A . #1#)
(A A A A A A A ....)That's a different structure: it has two Cs in it.
> For circular structures, you could also have: '#1=(A . #1#)
That's what I meant by "references".
It has two occurrences of the same C (but maybe I did not get your example).
The hyperlink as the base abstraction allowed us to store and navigate individual nodes in a hypertext, but it doesn't work well for collections - thus it provides limited support for programmatic access.
Conversely, pointers & references in programming languages allow for easy handling/transformation of large structures (either loops or recursive traversal), but there have never been a really good visual representation beyond a few nodes, and are difficult to navigate.
A good tool should be based on an abstraction that worked well for linking information at separate places in the data space, and for retrieving collections as a whole. I have my ideas for how that abstraction should work, and even may develop a product around it eventually. ;-)
Have you seen DDD (the Data Display Debugger) ? It's a graphical shell around gdb, and can help visualizing data structures.
It's been many years since I used it, so it may have evolved to include features for displaying large datasets; however what is needed is something akin to Bret Victor's "Learnable programming" principles, which is more powerful than simply tracing a single deterministic execution path (which is what classic "debugging" is).
> Gephi is an award-winning open-source platform for visualizing and manipulating large graphs.
https://news.ycombinator.com/item?id=7511979
It's an unresolved problem as far as I know. Lots of partial solutions. I ran into this again recently because I use tree editors extensively (mostly leo) for my daily routine and was searching for a better (more structured) replacement but I haven't found anything yet that beats leo.
Emacs org mode is reportedly extremely powerful as well but I have yet to invest significant time into it (there is only so much time...).
Emacs with IMHO better keybindings, lots of integrated packages which can be switched on/off as functionally related "layers".
For vim users has of course evil package.
http://flyinglogic.com/ is on the right track. JVM cross platform and commercial.
Curious how jetbrains MPS could improve on something like that.
Joke aside, graphs are far from being trivial to represent as a data structure, and their use are so various that you can hardly edit a graph using text alone. Even a visual editor would require to be tailored to different work you do with graphs.
I also like mermaid (https://github.com/knsv/mermaid), so I created a small rails app (https://github.com/juliend2/metaglue) that uses mermaid as the graph language, and it generates an SVG graph in realtime. I really like it and use it as a kind of brain dump for various subjects. The idea behind it is to collect any kind of data (bits of knowledge) and mash them all together inside a common graph.
Gingko provide templates for Timelines, Screenplays, GTD and Academic papers, but I can imagine using it for complex formal proofs — I mostly use it for Microscope[2] and worldbuilding[3].
Right now it doesn't have any programmatic/computing capacity, but Gingko is eminently user friendly, so if Adriano[4] ever implemented a plugin system (or if someone wrote a Gingko-node-crunching chrome extension) I would imagine it to be a very enjoyable interface for editing trees.
1. https://gingkoapp.com/?ref=f32636d1
2. http://www.lamemage.com/microscope/
3. https://www.reddit.com/r/worldbuilding
4. https://twitter.com/adrianoferrari
Disclosure: I don't have any affiliation with Gingko, but that is my referral link. ;)
I'm using yEd a lot, and I especially like layouting functions like hierarchical layout. I often use it to plan interdependent tasks. I just start with tasks I know are required and the thing of their prerequisites. Quite fast this gives a big graph structure. Then I run a hierarchical layout on this and suddenly I have a very clear structure of tasks. Their hierarchical layouting algorithm is great. I suspect it may be based on GraphViz dot's algorithm (http://www.graphviz.org/Documentation/TSE93.pdf) as it produces results of similar high quality.
I also love the UI of yEd. Zooming in and out, creating nodes and dependencies/edges feels just great.
There don't seem to be tree-oriented editors for XML. Or HTML. Or even JSON. That would be useful. At least the tree structure would always be correct. More effort is going into figuring out how to parse "bad JSON" than into writing editors for it.
And keeping HTML "well formed" is a battle that lost hard with xhtml. Further, any "rich" editor likely kept the tree structure well formed. It did little to keep it manageable, though.
And I wager that most "bad JSON" is programmatically generated. This is literally a problem with countless solutions today. But, it is almost always quicker to println something out that you are certain you know the structure of, than it is to use a library. So, people don't. :(
Isn't that a pretty basic refactoring feature of most IDEs?
Also, I've been impressed with a lot of the invention that has happened around Grasshopper's UX + UI. I've been really surprised to see the design community emerge with the best graph programming editor, as opposed to something much more developer focused.
It is of course not general purpose because you have to have Rhino to use it, but it can be used for general purpose programming since you can create custom components with .NET, ignoring most of the pre-built ones that are focused on parameterized geometry.
We're imagining the idea that your whole development flow is expressible in terms of trees and expressions that we can use to navigate those trees. Say for example a webhook pushes a commit event. We can navigate from that commit, into the chat channel associated with it. Find the repo that contains it. Associate it with the build and link the two together in chat or, most relevant to this article, navigate into the code itself and perform an action such as changing the code or opening a PR with a suggested edit and comment.
The interesting thing is that it's trees the whole way down. We can use the same expression to reach across all all kinds of events or to pick out individual tokens or structures inside the code.
There's lots of information on our blog: https://the-composition.com/
We've open sourced a lot of our core work at: https://github.com/atomist and are also interested in talking to teams about joining out alpha (see atomist.com)
It's a really interesting problem to be working on.
practical purposes abound, sure, but I'd just like to see the intermediate notation that pops out if someone were to attempt to design one. I don't think it'd be like graphviz..
Blockly ( https://developers.google.com/blockly ) is also similar, but I think it's a bit too specific:
- Only one type of block is needed, to represent a generic "node" in the tree. Distinctions can be added by plugins, if desired for some particular language.
- The idea of "interlocking" can be discarded, since a general tree editor should allow arbitrary edits to arbitrary trees (in the same way that a general text editor should allow any text to be inserted anywhere in a file/buffer). Plugins can add it back for particular languages.
- Nesting should be the only relationship; it subsumes "sitting beside" (like Blockly assignments) or "wrapping around" (blockly loops).
- No need to distinguish between editable/immutable values; everything is editable.
As a baby step towards the author's goal, how about an s-expression editor which displays boxes-in-boxes instead of parentheses? The editing commands could be exactly the same as e.g. Emacs+paredit, the only difference would be that indentation begins at the left edge of the current box, rather than at the left edge of the screen. For example, we would have to discard the indentation of an expression like:
(foo (bar baz) (quux
foobar))
+-------------------------+
| +-------+ +---------+|
|foo |bar baz| |quux ||
| +-------+ | foobar||
| +---------+|
+-------------------------+
More radical extensions can then support pulling the boxes out into a more traditional tree structure.
Maybe this could be combined with https://github.com/jacksonrayhamilton/context-coloring and either https://en.wikipedia.org/wiki/Semigraphics or the new cairo support for drawing pretty borders?
Even a basic tree editor would be very powerful. Especially if you could run code from a repl that would change the tree (I know, that's no longer basic ... but it would let the graphical portion be basic, which might help it be bootstrapped into existence).
Heavy user of outline view in MS-word here, which is basically a tree editor for text documents.
I might be misunderstanding this but a "tree" is a graph, so formally a tuple G = {V,E} where V a set of vertices {a,b,c,....} and E a set of tuples: {{a,b}, {b,c},...} so that each a,b,c,... are vertices in V.
So for instance, the graph:
a
|
/ \
b c
| |
d e
That's a simple, intuitive, light-weight notation that is very easy to manipulate in a text editor, so that's probably why nobody has bothered to write a special-purpose program for it.
And if you want a graphical representation there's always tools like graphviz, so our graph can be written in dot-language as:
digraph{
a->b
a->c
b->d
c->e
}
From a math notation point of view, this statement is not needed. If your edges are directed, denote your edges not as sets (which are always unordered in math), but as ordered pairs instead:
{{V,E}: V = {a,b,c,d,e}, E = {(a,b),(a,c),(b,d),(c,e)}}
(1) The notation a->b was defined as a simple shorthand, i.e. a->b := (a,b).
(2) The notation a->b was defined to be the graph consisting of just a, b and the edge, i.e. a->b := ({a,b}, {(a,b)}) ... this may be followed by some algebraic rules about how to combine small graphs to build larger graphs.
(3) The notation a->b may be a somewhat misused notation for functions, meaning the only possible function from set {a} to set {b}, i.e. the function that maps a to b. If you define a function to be a relation (i.e. a set of pairs) where the first elements are unique, then this is acually equal to {(a,b)}, i.e. the set containing exactly this one pair.
Interpretation (3) might look somewhat contrieved, but it actually isn't that much of a stretch, given the connections between graph theory and function structures through category theory.
I guess it's convenient notation for a typical step in those algorithms, where two edges are oriented towards a common vertex- shown as A -> B <- C or similar. That's a little more concise than {(A,B),(C,B)} but also more intuitive when the intention is to show how to (re)construct a graph from dependence relations, as those algorithms usually do.
___________________
[1] Causality; models, reasoning and inference:
http://bayes.cs.ucla.edu/BOOK-2K/
[2] A Fast Algorithm for Discovering Sparse Causal Graphs; Peter Spirtes & Clark Glymour:
http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&c...
A UI, now that's a different issue but I don't see why you need a special UI there. It just sounds like a bit of a gimmick to me, to be honest. Or probably it's just that the OP wants to use graphs (trees) for something that doesn't really need graphs? As in, yeah, you can represent computation using graphs -you can represent all sorts of formal stuff with graphs- but that's an implementation detail.
Like, why have a GUI to an AST and not a GUI to your computer's 1s and 0s, in RAM? Or a GUI to your processor's registers? It's just a very unnatural way to program, really.
For example, imagine representing the HTML of this Hacker News page in your format; it would be completely unwieldy, and Hacker News is notoriously simple as far as HTML goes.
It's clear that this representation is massively space inefficient, since it repeats the vertex labels over and over. It's also massively time inefficient for common operations, like finding the incoming/outgoing edges of a node; these can be seen "at a glance" in some representations, like boxes + arrows, whilst your representation requires traversing the entire set of edges looking for matches. In fact, I can't figure out a sensible way to even write down the vertices in such an example! Even if we invented some arbitrary labelling scheme, e.g. labelling nodes based on their path from the root, or based on their position in a post-order traversal, such labelling schemes would be enough to define the tree on their own!
Unfortunately I think this is another case of trying to shoehorn sets into places where they don't belong for no particular reason, as if trees are somehow "less mathematical" than sets. It didn't work for Bertrand Russell, and it doesn't work here ;)
> if you want a graphical representation there's always tools like graphviz
Graphviz is notoriously messy when it comes to graphs of any nontrivial size, and the existing tooling makes interaction less than ideal (e.g. using home-grown scripts on top of image canvases and hotspots, rather than established interaction methods like a widget toolkit).
> Also, I don't understand why a tool to manipulate graphs, rather than just represent them, would be any different than a proof assistant or a theorem prover.
I don't see the connection myself. Proof assistants are incredibly picky about what they allow (that's kind of the point ;) ); on the other hand, a tree editor would be used for "fast and loose" cutting, pasting, duplicating, rotating, swapping, etc. of arbitrary sub-trees in arbitrary structures. How would tooling like, say, Coq, help with that?
Well yes, but that's because HTML is a mess, not because graph notation is unwieldy.
In any case I don't think it's a good idea to try to program in graph notation, or anything like it. Actually, I think it's a terrible idea. Unless you want to create some kind of help tool for graph theory, I guess.
>> Proof assistants are incredibly picky about what they allow (that's kind of the point ;)
As are all programming languages. Manipulating graphs, er, graphically, will not give you some sort of magical get-out-of-jail-free card against syntax errors or undefinable behaviour etc.
Like, I'm not even sure what the point is here, with the OP. Is it along the lines of "hey, look at graphs, graphs are cool, let's make coding cool with cool graphs"? Or is there some sort of benefit, like expressive power or syntactic clarity, that you don't have with high-level languages already? Why do you need a GUI to an AST? To be honest, the OP looks like a bit of a muddle to me.
It does prevent some errors, like malformed structures. For example, the following Lisp:
(defun (square x (* x x))
void square(int x {
return x * x;
while $i < $num do
puts "Inside the loop i = #$i)
$i +=1
The idea of a general tree editor is not to prevent syntax errors, undefined behaviour, etc. because those are properties of specific trees, e.g. the parse trees of C programs. A tree editor just edits trees; it doesn't care what those trees represent (that's why the author mentions a plugin mechanism, like Emacs has different modes for editing files written in different languages).
Manipulating programs at the level of parse trees can also be more efficient, less tedious and prevent errors, e.g. see the paredit videos linked in other comments. By analogy, what's the point of a general text editor, when our CPU can already perform arithmetic on bytes? A general text editor doesn't prevent syntax errors, undefined behaviour, etc. Does editing strings of text, rather than numerical bytes, provide expressive power or syntactic clarity that we don't have with high-level languages already?
I also don't think the author was asking for something "graphical" or "GUI" per se; their analogy is with text editors (e.g. Emacs and Vi), which are efficient both in their display and their interaction. A general tree editor wouldn't be based around e.g. drag'n'drop of nodes/edges, in the same way that general text editors aren't based around drag'n'drop of glyphs in a grid.
General text editors have features for moving to the start/end of a line, for cut/paste up to the next space or linefeed, for highlighting parentheses, for folding/unfolding between sentinel characters, etc. General tree editors would instead have features to move to the root/leaf of a tree, cut/paste sub-terms, fold/unfold expressions, etc. No need to care about the existence of whitespace, linefeeds, indentation, parentheses/delimiters, etc. they can all be handled mechanically.
A trivial example of this are input fields which enforce a lexical format. For instance, we can implement an input field for a floating-point number where you simply cannot type some garbage like "1.E". What happens is that you type "1" (so far so good), then then "1." (still good) and then "1.E" (good prefix, but bad). Since it is a good prefix, the "E" is allowed, but the validator automatically inserts some suffix to make it valid, like 0. So you see "E0". The 0 is selected so that the next thing you type will replace it. But if you type some garbage like Z, it will be rejected; at that point you may only type a + or - sign, or a decimal digit.
Your example doesn't work very well, since it's very specific (the author wants "general-purpose"), and I would say it's not actually a "character-based editing method": it has a keyboard-driven UI and a character-based display, but so does NetHack. Instead I'd say your example is a float editor, rather than a 'text editor with syntax rules'.
In any case, there is an example which is close to a general-purpose tree editor that's is keyboard-driven with a character-based display: paredit mode in Emacs, as mentioned by other comments. It's implemented exactly like you describe: many keypresses correspond to the insertion of their respective characters, but when that would invalidate the tree structure (e.g. '(' and ')' keys), different actions are taken instead. For example, '(' inserts '()', whilst ')' "steps over" existing ')' characters rather than inserting extra ones.
My issues with paredit, as I've written in other comments, are that it's stuck with a single representation of trees as parenthesised s-expressions: there's no way to alter the "view" of a tree, e.g. to a boxes-on-sticks view or a nested-boxes view (whether they're displayed using ASCII art or GUI widgets). It also leaks implementation details, e.g. altering the alignment or indentation of expressions will cause the file contents to change, despite having nothing to do with a tree.
When you have text, you can interpret the string as a number and you can count the possible files: "0x01", "0x02", ... "0x0101", "0x0102", ... "0x010101", ... -- all of the possible files are enumerated by a single increasing sequence. This corresponds to the ordinal "omega-0".
When you have a table, you can interpret each row as a number and now you have an arbitrary number of infinite increasing sequences, but you can imagine a transfinite "sequence of sequences" that counts the tables with 1 row, then the tables with 2 rows, and so forth. This is a single infinite increasing sequence of infinite increasing sequences, which corresponds to the ordinal "omega-0 squared".
But when you have a tree, there's an infinite increasing sequence corresponding to... every single finite tree! In fact, there are multiple increasing sequences corresponding to every finite tree, and infinite sequences associated to those sequences, and... anyway, tree-counting functions are very hard to define at all, but with a little bit of work in combinatorics you'll find something called a "Veblen function" which is defined so that the parameter of the function is the number of levels of recursion of infinitary functions applied to themselves, and then the fixpoint of the Veblen function itself is the Feferman-Schutte ordinal, which cannot even be defined in first-order logic! One example of the horror that results from counting trees is Kruskal's theorem:
http://en.wikipedia.org/wiki/Kruskal's_tree_theorem
In other words, trees, which can encode arbitrary structure, are much more difficult to do math on than tables and flat files, which can only encode simple structures.
Not the most complex solution but also super easy to use. Tab to indent, shift-tab to unindent. Select-drag-and-drop... etc.
Also you can use Ranger[1] or Finder or NERDTree with Vim/Nvim to utilize your file system as a tree structure and afterwards "extract" it with tree[2]
But I don't need a UI oriented around visually displaying tree-like things. Expanding / collapsing nodes is very meh. Moving / splitting / joining nodes is much more interesting and useful.
As a simple concrete example: changing the order of the parameters (and their type) in a function definition. Wouldn't it be great to 'swap-with-prev-node' or 'swap-with-next-node' rather than copy/paste and dealing with commas? The same operations could swap the order of two fields in a struct or two functions or two classes or any pair of adjacent nodes in a tree.
Or how about moving an 'if' block inside the 'for' block that follows it? Just execute the 'move-node-inside-next-node' (or whatever) command.
This only requires editors that (indirectly) understand the semantics of the text you're editing. Thus far the biggest barrier is all wheel re-invention needed for the cartesian product of all editors and all languages. But that's the wrong approach. We need each language to provide a tool that each editor can use via a common protocol.
This is precisely the point of the LSP. The functionality only needs to be written once per language and per editor. This is totally tractable. I don't know if LSP currently supports the specific tree-manipulation functionality I mentioned, but I'm confident it could.
Does anyone knowledgeable about LSP know if this is already possible, feasible, and/or generally desirable? Are there deal breakers that make this hard / not worthwhile?
Note that you don't need a fleshed-out, implementation-friendly abstract syntax tree (e.g. "(definition (name foo) (type (function int int)) (arguments ((name x) (type int))) (body ...))"); you just need a parse tree of the tokens (e.g. (def foo ((int x)) ...)).
I agree that the existing silos of VisualStudio, Eclipse, Netbeans, jEdit, Emacs, Vi, etc. is a bad thing, and initiatives like LSP are is a step in the right direction.
Another nice approach that I came across recently is https://github.com/CarlOlson/structured-editing . This also uses a separate process to get information about code, but uses "spans" (start position, end position, label, extra info) which seem to be in between strings and syntax trees. For example a span might encompass a class definition; another span covers a method inside that class; another covers a statement in that method; another covers a function call in that statement; another covers the function name in that call, and it's extra info includes the location where that function is defined, its type, etc.
I represent the web by a tree, every node has metadata (id, type, title) and data. Nodes can be persisted (ie. as json text files, or in database table) and browsed (parent to children and back). Admin UI is very simple: in the left pane there is the tree browser, works like filesystem browser - you can open "folders" (nodes with subnodes) and "files" (leaf nodes). Each node shows specific editor for it's type, that usually consist of few form fields.
I couldn't get the full 14 level tree to fit on my screen.
You can build your own admin UI, if you want as it's all done with the same API you use to build your sites.
- Update your profile.
- Post Tweets for you.
That's not cool.
It saves a single document in your browser's local storage.
Good stuff.
More than tree structured XML, this also provides node graph XML visual editing.
Like OP mentions Excel for instance, for editing tabular data, which isn't quite a standard file format, and in any case supports many different formats for tabular data.
I can't help but wonder if OP is focusing on "format" rather than the structure of the data itself. There's plenty of editors for these well known formats. Perhaps he just needs to restructure his problem to use one of these?
In XML for instance, it's fairly straightforward to implement a "plugin" such as he describes, using python or ruby and a DOM parser, which could amongst other things provide the different renderings described.
I remember using XML Spy a long time back which seemed to do this quite well, as an ever expanding grid of cells, click into a cell, and it would expand showing its constituent cells. There were different tree representations available as well.
I mean, I like the idea a lot! Used MindNode, but I found it very bound to specific type of problems. It is visualization tool. And Emacs is just too much. I use it from time to time, but I would like nice native general purpose text editor with Tree capability and Markdown support.
Whilst a cool idea, and a nice foundation for actions, it certainly suffers from being clunky UI-wise, so doesn't solve the author's problem directly.
The "list of trees" part is what's constant about trees; the value is what makes it hard. What's a value? A name? A string? A text? Either a text, or a name and a map of strings to strings (simplified HTML)? A General Purpose Tree Editor would have to handle all those cases, and a whole lot more.
I'm asking this on the perspective of someone who is about to teach model-driven software engineering for a semester but cannot find much pratical use for it..
[1] can anyone help me with clarity here as to why triple stores failed? Is it because no :db/retract and no time axis so cache consistency problems? or a deeper reason?
Looking back at my history this topic hits me right in the feels...
And we get stuck on that and say "Let's have a syntax." And then we're back to text again.
It's surely funny if there can be so many comments and nobody even ran the program.
It's only for JSON but you can write a small script to convert it to whatever format you want.
Not to mention that "jump to source", et al. depend on particular semantics of the code. So by itself, those features don't make a general-purpose tree editor.
If he is asking for away to organize various bits of text etc, is that not basically a directory tree stuffed with files?
https://play.google.com/store/apps/details?id=com.orgzly&hl=...
For simplicity, let me start with just trees. What kind of trees have we got?
Well, we've got programming language ASTs. In these trees, nodes tend to have only two or three children, each of which is probably a short word or a number, but they can easily extend hundreds of levels deep, or even thousands. (Before you disagree with this, go take a look at the dump of the AST of a modestly complicated Python function or something. Many programming language grammars are not optimized for this representation and end up with way more intermediate grammar nodes than you'd expect, which all seem like they'd be really easy to "just" collapse, but that causes its own problems.) The naive and obvious representations of all of this are difficult to navigate and consume the vast majority of the screen with whitespace. It rapidly becomes clear you need a specialized mechanism for dealing with this... then after a few iterations, if you do it right, you discover that you've reinvented... the original textual representation.
(This is not proof that textual representation is optimal in general. You can correctly argue that you end up there because the entire language was designed with that in mind in the first place, and that a language designed to be graph-based in the first place may work better. However, your tree viewer doesn't have any of the latter that doesn't already have a special-purpose viewer built for it, which your putatively generic code isn't going to compete with.)
Database rows are just a graph, right? Well, that's one top-level node for the result that contains the rows, and then, oh, let's say 25,000 identically-structured children. How are you going to navigate that? Are you going to introduce a "paging" concept? If so, you're going to complicate the other uses of this generic editor that don't need it.
How about rich text? Rich text is just a tree. But is your generic tree editor going to require sub nodes for "bold"? For that matter, how does your generic editor handle either of "text <b>bold</b> more text" or "text <span class='arbitrary_class'>span</span> more text"? There's a lot of different rules that people may want to apply to tree nodes; do those look like one, two, or three nodes in your editor? I can make a case for all three, for instance, for the first one (imagine the word bold is bold in the first one, it's a rich text display):
* text bold more text
* text
(bold) bold
more text
* text
(bold) bold
* more text
Speaking of RDF... have you considered the visual differences between ordered trees and unordered trees? Box & line graphs naturally represent unordered children, outline views impose a view of order even if one doesn't exist, other layouts may have other consequences. You can't just let the decision about outline vs. box & line be determined by the orderedness of the nodes either, because there may be other properties of the graph that may be unsuitable for.
And then, of course, there's the graphs that you want to view as box & line diagrams, the ones you want to have fully manual layout for vs. the ones you want some degree of automation. And you've to deal with the boxes that are way too big for the display because they contain several dozen kilobytes of plain text. Can your boxes contain subgraphs within them? And under any display methodology (graphs, outlines, whatever), what does it look like when you have a node with 25,000 incoming links? Does that work well with graphs that have only a few nodes like that? What about graphs like friend networks on Facebook that consist almost entirely of nodes that have hundreds of links? Note that when you've seen graphs of Facebook, they never much resemble, say, LabView diagrams, they're always these very zoomed-out representations with only entire regions colored and being discussed. How is your generic graph editor suitable for use on programming languages doing with this graph?
The theme here is not "unsolvable problem". The theme here is "unresolvable conflicts between different use cases". In an individual context, these issues are solvable, and have been reasonably solved. But trying to create a generic "graph" editor is, well, given the genericness of the term "graph" basically trying to create a generic "editor".
Used it at university for notes, and is great for quick revisions before the exams too!
Also, supports LaTeX.
Yeah, Gingko is really phenomenal, especially for multiplayer!