Hacker News new | comments | show | ask | jobs | submit login
Why Don't We Have a General-Purpose Tree Editor? (2014) (pcmonk.me)
308 points by networked on Feb 6, 2017 | hide | past | web | favorite | 212 comments



Emacs has ParEdit minor mode which is a general-purpose tree editor.

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


Maybe link to the Emacs Rocks demo in future - just a thought. I share it because I've known about paredit for years and just kind of gone ¯\_(ツ)_/¯ and not bothered - but seeing that demo has sold me on the idea in a super big way, to the extent where it's going to impair my productivity today, or would if we weren't in a post-crunch breather.

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.



Thanks. Added links to paredit demos.


It also has org-mode which seems fairly similar, but offers additional (optional) features for doing things like tables and due dates within the tree.

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.


>indented text trees

You mean points and sub-points?

>all but the most complex parts

And what do you use for those?


Don't forget org mode or mind mapping software. Both are quite able with hierarchical data.


Can you (or anyone) name some good mind mapping software (other than org mode)?


Mind maps are really just nested lists right? https://workflowy.com/ is one of the best nested list (tree) editors I've found for mind-mapping and note-taking.


When I'm not using orgmode I usually use yED[0] for diagrams and graphs. Not specifically mind-mapping software, but close enough for my purposes.

[0]https://www.yworks.com/products/yed


Freemind is alright. Java. Does the basics. Runs everywhere. Open source.


How good is it?

I've never used it and I'm genuinely curious.


Pretty good, it almost make you feel you're working on trees and not text. Takes a few moments to get used to. I recommend what I did: take a bunch of Lisp code, strip it out of parenthesis (M-x replace-string, replace ( and ) with empty strings), and then use Paredit commands to restore the original tree structure. I spent less than an hour simply doing this exercise again and again, and it was enough to become a proficient user.


Good exercise. Thank you!

Also, there are alternatives. What do you think about them?


Don't know of any (could you name them?), so I don't have any opinion.


It depends on your requirements. ParEdit limits you to only perform AST transformations, which could be very good if you edit s-expressions or explicitly tree-like structures.

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.


It is amazing for working with Lisps. I use it for Clojure and it is great -- highly recommend to anyone using a Lisp to learn it. Though you'll miss having it in other languages.

Not sure what it is like for other tree structures.


It's definitely written with the intent of using it to edit Lisp code, and for that it is great. It is now hard for me to imagine writing Lisp by editing S-expressions directly.


I've been thinking about this constantly for the last 2-3 years. I'm working on something which might lead to this.

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.


I've also been thinking about this for about as long (read this same article about 2-3 years ago), and came to pretty much the same conclusion. I actually think defining the grammar for turning text into a tree is likely to be the easy part, compared with building the editor itself.

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...


Back in '84 I was an undergrad at Boston University, doing an independent study with one of the business professors, Dr. Fedoritz, on a "next generation spreadsheet" that was to incorporate a cell-less freeform tree structure to represent Frames of Reference. Operating under the business school, we were working on advanced interfaces for financial professionals. The project was called a Frame Based Knowledge Representation System, with each node being a collection of data, with two special data types, one called a "frame" that contains logic and references to the other fields of the node, and one called a "reference" that pointed to a "frame" of some other node. All very basic, as the end-users were not programmers but financial analysts. Due to the freeform intended usage, the UI was on a vector monitor (like the old Asteroids arcade game), and end-users were trained to use the system as a collection of notes they can freeform write anywhere about their job, with little formulas to calculate things within a note and between other notes. It was explained to be like a combination notepad and spreadsheet. And it made a lot of sense to the end-users; they quickly got elaborate with their logic. The UI got zooming capabilities so actively edited or evaluated nodes would scale up while others shrank down, the end-users kept asking for more sophisticated features, and it really looked like we were on to something BIG. During an evaluation of the project with other professors, one of them asked "Once you've completed these requested features from your financial analysts, haven't you recreated just another programming language? The UI is unique, but I'm just seeing an interpreted language and a metaphor for programming that works with your finance end-users." ...And he was right.


Wow. I hope that didn't kill your project? I wouldn't mind seeing the UI, if you have any pictures, it sounds way ahead of its time!


I turned the project into another independent study and created a 3D animation language. About a decade later, I was introduced to the first feature film compositor centered around the GPU, called Shake, and it's node layout looked creepily familiar to how the Frame Knowledge System was when I last used it...


Sounds like your professor invented HyperCard, more or less. Right idea, wrong time/place.


You should look at JetBrains MPS, as should everyone posting on this thread. Because MPS has been in development for over 10 years as far as I know, and has attacked and solved a huge number of the issues you raise here and many more too (e.g. how to integrate non-text based programming with version control).


While we might have some common idea what is text, we definitely not have common semantics! The resulting situation isn't so much different from trees.

And what do you mean by "s-expressions just too simple"? Isn't simplicity something to strive for?


> While we might have some common idea what is text, we definitely not have common semantics!

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).

[1] https://www.mediawiki.org/wiki/2017_wikitext_editor


> And what do you mean by "s-expressions just too simple"? Isn't simplicity something to strive for?

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 have reread your text several times, and don't get it. What do you gain by having no fundamental datatypes, only bits? What syntactical sugar is not expressible by s-expression + transformation rules?

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.


> What do you gain by having no fundamental datatypes, only bits?

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".


You must have read about Urbit, right? Their VM's underlying language/bytecode/thing, Nock, is based on nested pairs of natural numbers, which is perhaps only slightly less unwieldy than operating on single bits.

PS, if you're as enthusiastic about this idea as I am, we should talk, can I email you?


I think it could be neat if the spec of the s-exp was read from local hints rather than top-down prescription. You could show a color picker for color argument to a function etc. clojure.spec seems a cool tool.


>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.

Ummm json??


I was wrong about S-expressions. S-expressions are roughly the right complexity, or even a bit too complex, depending on how you look at it.

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.


JSON is one of the most dominant tree-data formats on the web because of the awesome balance it has between complexity and simplicity. JSON fits the bill nicely.


Actually... it's one of the most dominant tree-data formats on the web because you don't have to bundle a parser with your client and then figure out the idiosyncrasies between your serialisation model and your language's object model, the browser gives you one for free and JSON is your language's object model. It's a lot more fiddly to deal with in languages which don't have a K/V map as the primary object model.


That's quite easy to represent as an editable tree structure.

E.g.

http://jsoneditoronline.org/


I think what you're describing almost exists for C++ in the form of libclang. Editors really prize uniformity and predictability, to give users a comfortable experience, which is why I think libclang is so unwieldy if you try to integrate it into an editor fully—I tried with emacs once. So, despite all the massive effort put into clang, it gets incorporated piecemeal, one IDE feature at a time.


Isn't it only the types of the AST-nodes rather than semantics you need a common representation for?


The key insight of this post for me is this: Code editing is tree editing! The reason why code is edited in text editors, is that tree editing interfaces are fundamentally difficult to do well, and often have to be carefully tuned to the properties of the particular trees and editing tasks. (Simple examples: Huge fanout vs. at most 2 children. Very large information-rich nodes vs. tiny nodes.)

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 f = x = readline; g x

def g x = print x; f


The AST of that would still be a tree. AST does not concern itself with the semantics of the language, only its syntax.


Not 100% sure how to interpret this piece of code, but my naive interpretation gives this AST:

  (def f ()
    (let ((x (readline)))
      (g x)))
  
  (def g (x)
    (print x)
    (f))
Writing in Lisp can open one's eyes about the underlying structure of the code.


My point was that "Code editing is tree editing" sounds a bit like if you can understand the syntax tree, you understand what the code does – which isn't true here. Trees don't show the recursion[1], and a tree-view of code (with e.g. folding) might even give a false impression that what's inside one branch is somehow self-contained. Ie. Turing Machines are more expressive than CFG's :-) Not that tree-view's aren't helpful (indentation is important, and editing Lisp with paredit is a real joy), but there's much more to code-editing than tree-manipulation.

[1] Unless your "tree"-view is actually a lazy call-graph …


I think it's important to distinguish between "tree-structured data" and "tree-structured UI"; many of the suggestions here and in the article's comments mention s-expressions (or alternatives e.g. using indentation or similar); many others mention diagramming/mindmapping tools. I think the real issue is how disconnected such approaches are from each other: why can't I press a key and have my parenthesised expression be expanded into a tree, or press another button to collapse a sub-tree down into a parenthesised expression?

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.


> Fold/unfold terms/trees (code folding, but for expressions rather than lines)

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...).


> Emacs can hide/show blocks in Lisp expressions (and others). Install HideShow (https://www.emacswiki.org/emacs/HideShow).

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 :(


Trees are graphs with out cycles but you always end up adding cycles. Code is no exception. There have been endless attempts to create coding systems based on graphs. These systems promise extraordinary modularity and reusability and an ease of programming which will allow anyone to construct complex software with a few clicks and drags. So far everyone of these systems that I have seen in the last 25 years has fallen short of its promises.

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.


How do you feel about tools like Reaktor, which I assure you works very well indeed?


Reaktor is a audio program. There is actually a long history of this type of app working well. PD is an early example. This is indeed a limited type of programming.

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.


That's not very responsive. Reaktor's primary purpose is to produce audio, but it also allows one to build sequencers, user interfaces, graphics (eg spectrograms, from DSP primitives by build your own FFT modules) and all sorts of other tools. Besides, why is audio somehow an inferior sort of data processing?


Sometimes not being able to add cycles is a design goal. For example if you're exposing a user-facing DSL and it's in the shared interest of the users and the backend that their scripts always terminate, perhaps even in a bounded amount of time/cycle.

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.


Unreal Engine 4 has Blueprint, which is a powerful node graph programming system. It works great and it's very popular. It's definitely worth looking at for anyone interested in this sort of thing. The "bi-directional flow" (exec nodes "push", data nodes "pull") makes it very flexible for almost any kind of task.


One huge question to ask is why you need an editor specifically for a tree. Do you want a gui, or a format? If you need a gui, you are automatically in domain-specific territory. If you only need a format, maybe you don't need a tree editor at all.

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.


> If you need a gui, you are automatically in domain-specific territory.

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.


I appreciate the reply, but I humbly suggest that nothing is solved by saying "just use plugins". You can't build a good plugin architecture in the first place without understanding the problem domain & workflow.

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.


Yes, it seems like something like Naked Objects[0] combined with domain-specific plugins / components could do quite nicely.

0: https://en.wikipedia.org/wiki/Naked_objects



The third screenshot [here][1] is hilarious :)

[1]: http://strlen.com/treesheets/docs/screenshots.html



You can also create a slideshow from it:

https://github.com/YaakovDavis/TreeSlides


I should take a look at that, in case there are features there that org-mode doesn't already have and are worth stealing.

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?


Never mind Emacs, Emacs is easy.

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.


As somebody who only makes a pretty basic use of org-mode I disagree.

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.


It depends what you mean by "good use", I suppose; I started out with just the very basic outliner and checklist features, and expanded from there. It didn't take much more than knowing those features existed, and what they looked like, to start using them. You do need to refer heavily to documentation when getting started with more complex features, but that seems like a fair tradeoff to me.

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?


Seems like a enhanced personal wiki and away from PIM style and more added MindMap style. I would say this is not a tree editor.


It allows you to edit a tree structure. Unlike most tree editors, which lay out the tree in one dimension, this uses 2 dimensions. How is that not a tree editor other than it looking unfamiliar to you?


what features/behavior would you want to have it qualify as such?


TreeSheets is really awesome, and I say this after having tried my own share of outliners and mind-mapping tools.


I just tried this on macOS. I really like the concept but: It does not conform to macOS UI standards (I could live with that), and it is very slow (I cannot live with that).


It uses wxWidgets for UI, which does a poor job on OS X. What actions are slow? I have it here on a MBP and it appears to work just fine.


We do, it's called "the file system". Folders and directories galore. If you dont like folder icons and rectangular windows, navigate with MC.

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.


I think we don't have a general-purpose tree editor for two reasons:

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.


FWIW the editor in Chromium's and Firefox's developer tools are pretty good. I'd really like to see something like that as a standalone tool for both trees and XML and see how far it can be taken.


The inspector? I've seen and worked with similar tools for XML, too, though not recently. They're very good for small, constrained hand-editing, but I find them to scale extremely poorly.


For XML you may want to take a closer look at XML Marker 1.1 (it's old, freeware and Windows but still better than many other tools) and maybe Eclipse.


I think that sums it up. We really can't top crufty old Windows freeware?

There is a gaping hole in the market.


The last time I worked on complex XML I even used XML Marker with WINE... it works there. If you want the Mercedes of XML editors you should take a look at Oxygen XML editor (this is not free but runs on more platforms than Windows).


+1 for OxygenXML - it is very actively developed and has its own CSS engine that goes above and beyond what browsers can do. So you can style your tree with CSS.


Or the market is smaller than it might seem.


For the programming use case there is also Leo.

http://leoeditor.com/

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-...


Leo is fairly cool. Been around forever, but not many people know about it.

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.


FWIW, comparing my experiences with several different "graphical equation editors" (fundamentally a flavor of tree-editor) versus editing LaTeX code directly, the tree editor loses every time. Yes, the tree editor is capable of providing an amazingly efficient interface for modifying parts of an existing expression - but when you start restructuring the whole expression things get messy fast. The plain code method is a bit rougher to read / enter in simple cases, but since it's just text in a text editor it doesn't have the same complexity escalation when doing unusual reorganizations.


This sounds like something that can only be true for equations below some size. If you're trying to manipulate a sufficiently large equation, it has to be automated, so directly editing text is bound to lose (however clunky the automated method may be). So maybe your experience is just that equations rarely get large enough to make it worth it to use a graphical editor?

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


I regularly edit large equations in LaTeX. I don't see how it's not manageable, just break your equations into multiple lines.

  \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}
> 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?

I use Mathematica, and I just use the plaintext Mathematica syntax for large equations too. I also break these into multiple lines.


> regularly edit large equations in LaTeX. I don't see how it's not manageable, just break your equations 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.


But is this due to text being the most efficient way of editing or are our tools simply inadequate?

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.


Based on Paredit keybindings, I don't think 'sibling', 'union' and 'splice' would be enough for convenient editing; you'd at least need a set of keys to move nodes (with their subtrees) around.


I'm thinking it would if you also had good selection keybindings.

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.


This reminded me of Leslie Lamport's (of LaTeX fame) paper "How to write a 21st century proof" [0], where he argues that we should explicitly structure proofs as trees.

[0]: http://lamport.azurewebsites.net/pubs/proof.pdf


See to me the problem is the notion of tree structure itself. Forgive me because I don't know the correct mathematical way to talk about this: a tree is a particular type of network in which nodes can have only one direct parent and thus only share siblings with the descendants of that single parent. What we are really lacking is a good network editor, which would encompass not only trees but also more complex rhizomatic network structures.

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.


There's a core abstraction lurking behind tools like ZigZag, the Leo editor, hashtags, and C pointers/linked structures.

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. ;-)


> 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.

Have you seen DDD (the Data Display Debugger) ? It's a graphical shell around gdb, and can help visualizing data structures.


Yes, that's the kind of user interface that I believe should be the basis for modern programming environments. It's also the example I was thinking of when I said that linked structures are difficult to navigate beyond the few first nodes; a "boxes+arrows" representation just doesn't scale well without a way to structure nodes hierarchically and summarize the state of whole groups of objects.

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).


Can I email you? I'm working on similar ideas. I can't find an email address. My email address is in my profile.


Sure! I've just emailed you from my personal mail account.


The author does mention such networks (AKA "graphs"), and there's a lot of discussion in the article's comments.

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
How do we handle the order of these nodes and edges, e.g. for display or for serialising/deserialising? If we parse the graph from the text above, would we get an identical value to a parse of the following?

    B -> C
    ^    |
    |    V
    A <- D
If yes, would the user be upset that we've discarded the order? If no, then what is the form/structure of this extra information? Can it be represented as a specialisation/generalisation of a graph, or do we need something fundamentally different (a string, a parse tree, a partial-ordering, etc.)?

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
We can't write the following DAG just by using parentheses: should we put "C" inside the parentheses for "B", or for "A", or for both?

    C <-- B <-- A --> D
    ^           |
    |           |
    \-----------/


What's wrong with (A (B C) C D) ?

For circular structures, you could also have:

    '#1=(A . #1#)
Which is:

     (A A A A A A A ....)


> What's wrong with (A (B C) C D) ?

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".


> That's a different structure: it has two Cs in it.

It has two occurrences of the same C (but maybe I did not get your example).


https://github.com/gephi/gephi

> Gephi is an award-winning open-source platform for visualizing and manipulating large graphs.


I use Gephi quite frequently, it's interface leaves a bit to be desired but I've quite often quickly dumped some data into it and come up with some interesting relationships I wouldn't have thought of until it was visualised in Gephi.


It would be quite possible to develop a plugin that provides a user input oriented editing experience.


This has been here before:

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...).


I use org mode every day. It actually is a tree editor. You can fold and unfold entries, move whole subtrees into deeper/higher levels, etc. The tree editor however is just one of many org features.


Try spacemacs [0].

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.

[0] http://spacemacs.org/


Interestingly, visual programming and tree-editing has actually gained a lot of traction with non-programmers. Tons of the big video and audio production suites (off the top of my head: Houdini, Max MSP, Grasshopper, Nuke, Blender's node editor) are DAG-based authoring tools, and are a joy to use.

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.


A lot of tree editors aren't sufficient because he's asking about DAGs. Most tree-editing software only lets you have multiple children per parent, but you also need to allow multiple parents per child.

http://flyinglogic.com/ is on the right track. JVM cross platform and commercial.

Curious how jetbrains MPS could improve on something like that.


Isn't XML already a tree?

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.


Workflowy is pretty nice, it exports to plain text and xml.

https://workflowy.com/


I tend to use https://www.omnigroup.com/omnioutliner/, but workflowy is especially useful when I need a list to be shared.

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.


I'm a fan of workflowy too. As a vim user I was also very pleased to discover that vimflowy [https://vimflowy.bitballoon.com/] also exists.


I wish for something more sophisticated than workflowy, but I can't stop using it!



Workflowy is a list manager or am I missing something?


Nested lists == trees


that's an excellent option


And then there is Gingko[1], a beautiful, keyboard-shortcutted, markdown-enabled tree editor that exports to html, markdown, LaTeX, docx, impress.js, and json.

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 second this.

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.


yed is the best tool for the job I've used so far, so I'm glad someone already mentioned it.


I have found it most handy for visualising data that I've dumped elsewhere in a simple format such as .tgf (generated dependency diagrams etc).


There have been pure S-expression editors in LISP. INTERLISP worked that way. Yet EMACS, which is a text editor which knows a little about S-expressions, won out. INTERLISP's LISP editor had features never seen since, such as "Make this code subexpression a standalone function". This would pull the subexpression out and make it a named function, inserting the correct calls with the correct arguments in the original code. The inverse operation, "expand this function here", was also available. This eased refactoring.

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.


>features never seen since, such as "Make this code subexpression a standalone function". This would pull the subexpression out and make it a named function, inserting the correct calls with the correct arguments in the original code.

Isn't that a pretty basic refactoring feature of most IDEs?


This doesn't sound like a difficult macro/function to write. More, this has been replicated in other languages, now. These refactoring capabilities are considered a hallmark of the popular IDEs that people point to.

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. :(


Architects and the like already work with a really great tree editor called Grasshopper. Easy to see cross sections through your tree as you are arranging components and relationships L->R or T->B, so there is potential to have very clear hierarchies depending on the style of the user.

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.


I found myself thinking of something like Treeline when he describes what he wants. http://treeline.bellz.org/


Don't we have various LISP editors that are basically just that?


This is a part of what we're working on at atomist - https://www.atomist.com/

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.


honestly, let's go a step further and make it a general purpose graph editor!

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..


Surprised nobody's mentioned Boxer, or some other boxes-in-boxes representation http://web.media.mit.edu/~mres/papers/boxer.pdf

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))
Instead we would align "foobar" to be in the same box as "quux", e.g.

    +-------------------------+
    |    +-------+ +---------+|
    |foo |bar baz| |quux     ||
    |    +-------+ |   foobar||
    |              +---------+|
    +-------------------------+
Note that I don't recommend using ASCII to draw the boxes (except maybe as a proof-of-concept). Once we have such an editor, we could start to extend it with features like coloured boxes for syntax colouring, structure-checkers (e.g. "if" should have 3 children, etc.).

More radical extensions can then support pulling the boxes out into a more traditional tree structure.


After some Googling I've come across http://foldr.org/~michaelw/emacs/ which includes a hack for giving nested s-expressions different colours and hiding the parentheses. This sort of "tree view", combined with paredit's "tree editing", might go some way towards faking a tree editor.

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?


It's funny how bad I really want to go to the foobar line and hit Tab (or M-q near it).


I have wondered this exact same thing! I assumed tree editors did exist, and I was excited that all I needed to do was go find them. But Google did not come through for me.

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).


Outliners? (https://en.wikipedia.org/wiki/Outliner)

Heavy user of outline view in MS-word here, which is basically a tree editor for text documents.


>> We need a solid, simple program that can simply edit trees.

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
Would be written as {{V,E}: V = {a,b,c,d,e}, E = {{a,b},{a,c},{b,d},{c,e}}} possibly accompanied by a statement as to whether edges are directed or not.

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
   }
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.


> {{V,E}: V = {a,b,c,d,e}, E = {{a,b},{a,c},{b,d},{c,e}}} possibly accompanied by a statement as to whether edges are directed or not.

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)}}


Thanks. Or you can always use what I think is slightly informal notation, where a directed edge is notated as a -> b (I've seen that in textbooks, but I'm not sure where it's coming from).


Haven't seen this notation in text books so far, but I guess one of the following 3 things happened:

(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 believe it's (1) and I think it might originate in Judea Pearl's textbook on causality [1], particularly the section on the IC algorithm. I've also encountered it in a bunch of papers on graph reconstruction, by Wermuth, Lauritzen, Spirtes and Glymour (not all in one go, I don't think). For instance, see [2].

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...


Your representation is certainly valid, but I think those properties (light-weight, intuitive, etc.) apply to your example rather than your representation.

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?


>> 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.

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.


> 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.

It does prevent some errors, like malformed structures. For example, the following Lisp:

    (defun (square x (* x x))
Or the following C:

    void square(int x {
      return x * x;
Or the following Ruby:

    while $i < $num  do
        puts "Inside the loop i = #$i)
        $i +=1
    
These sorts of things can occur when manipulating programs at the character level, but they're inexpressible at the level of parse trees/graphs. Balancing parentheses, braces, quotation marks, begin/end, etc. is exactly the sort of task that machines can automate away.

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.


We can have editing methods that are character-based, yet which make those kinds of syntax errors impossible.

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.


> We can have editing methods that are character-based, yet which make those kinds of syntax errors impossible.

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.


Would that support an edge between b and e? That's what determines whether something like an outliner would be a good UI for it. If you need that support, then the UI becomes more difficult - you either have to "draw" the graph visually, or have a continually adapting approximation.


Why wouldn't it? You just add an edge: {b, e}.

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.


Is it me or is this article reposted every four months? Does it show that there is a fundamental need that is still unmet?


Think of this in terms of ordinal numbers.

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.


There is the Dot language: https://en.wikipedia.org/wiki/DOT_(graph_description_languag... The files can be viewed with Graphviz.


Take a look at Parinfer[0]. It's for Lisp editing, but S-expressions are as general as it gets.

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]

[0] https://shaunlebron.github.io/parinfer/#introduction

[1] http://ranger.nongnu.org/

[2] http://mama.indstate.edu/users/ice/tree/


Honestly, if I'm trying to organize some concepts into a tree, I'll go into Word, open a blank document, and switch to Outline mode.

Not the most complex solution but also super easy to use. Tab to indent, shift-tab to unindent. Select-drag-and-drop... etc.


I don't want a general purpose tree editor. I want a general purpose text editor that understands the semantics of the text I'm editing. One that understands all the various not-necessarily-sexp-based code I'm editing is a tree and supports (ParEdit style) operations on that tree. Especially with languages in the Algol/C family. I think this can be accomplished (eventually) via language servers and editors that speak the Language Server Protocol (LSP) [0].

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?

[0] http://langserver.org/


Keep in mind that it's pretty trivial (if laborious) to make parsers/pretty-printers between your language of choice and s-expressions, which would allow a generic tree editor to work on your language.

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.


Somewhat related: I was overwhelmed by complexity of web CMS solutions. I needed something very very simple, that gets the task done (user-editable webpage content).

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.


If I understand you correctly, ProcessWire has such an admin UI out of the box: https://processwire.com/

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.


I had to work with Pimcore CMS recently (https://www.pimcore.org/en) and was pleasantly surprised. It works like you describe, the data is organised very developer friendly (classes and collections of data a tree structure for organisation). I am not sure how regular people would get along with this but knowing only bloated, slow and clumsy wordpress in that space it was surprisingly efficient.


Ca. 15 years ago, I used WebSiteBaker [0]. The website survives happily without any maintenance from my side. Only non-technical users changing content. There are a few minor things to do (e.g. CSS for mobile users), but I have no access anymore. I have no idea, how it has changed, but I would definitely try it again today.

[0] http://websitebaker.org/


I'm not sure how you'd get that simple enough for users? For example if you do inspect element in Chrome it shows the page as a tree structure and it's not simple. Here's some of it for your post http://imgur.com/a/svB4J

I couldn't get the full 14 level tree to fit on my screen.


Author of code2flow here (https://code2flow.com) - I think you could use my tool to easily create many types of trees. It's not generic, as in, it is focused on charting programs/algorithms and workflows but I've seen people (ab)use it for many different use cases, like so: https://code2flow.com/fRRlCK


Little Outliner 2 is pretty good. http://littleoutliner.com/ Made by Dave @ scripting.com


Went to try it out but it requires signing into your twitter account and they get access to:

- Update your profile.

- Post Tweets for you.

That's not cool.


Version 1 doesn't require you to sign in:

http://littleoutliner.com/v1/

It saves a single document in your browser's local storage.


OWL is a nifty fork of Dave Winer's work that stores all data locally and doesn't require a Twitter account.

https://github.com/interstar/OWL


That looks interesting. It also has a web.py server that can be used to store data on a server somewhere.

Good stuff.


I'll second LO2. I use it to keep notes of what I do every day.


We have it. It's called JetBrains MPS: https://www.jetbrains.com/mps/


Because we don't have a general-purpose tree file format.


I'm not being facetious here ... but aren't XML, Json and Yaml popular tree-structured formats?

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.


XML?


http://rupy.se/logic.jar

More than tree structured XML, this also provides node graph XML visual editing.


This certainly is good question. But, the fact that we don't have one yet maybe tells us that we haven't defined what it should be and what kind of problem it should solve.

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.


This may sound cruel, but you can use OmniOutliner as a tree editor and transform the XML to your target with your favorite xml transformation method.


I have a startup called Wizely, which is a social wisdom network. The iOS (phone) app (in development) will have a tree editor. I'm also developing a tablet version that would be bigger and more "touch-friendly". A full browser/desktop version isn't in the works, but if things roll out according to plan, it would be an important addition to our process.


Something slightly more hardcode: http://hazelgrove.org - structured editing via a formal calculus of actions which provably maintains correctness.

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 author's use of "sufficient cause" brought to mind Sciral's Flying logic[0] which does some basic logic and sufficient cause in terms of Goldratt's Theory of Constraints. It's also useful for a number of other logical structures, like trees.

[0] http://flyinglogic.com


A tree is a pair of a value and a list of trees.

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.


imagine you had about ten excel tables linked in a graph, any interesting visualization or analysis involves querying it like a database, and many databases are very rigid in terms what they can store, not flexible like excel. Semantic web stores (triple stores) are mostly schemaless and solve the rigidity but they had their own problems [1], datomic's 5-store model maybe fixes them? So maybe we will see an excel-for-graphs based on datomic someday soon. I'm working on this problem so if anyone has any interest in discussing this you should email me! It's a really interesting problem because excel-for-graphs would be an amazing starting point for building CRUD apps.

[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?


What comes to my mind is the Eclipse Modeling Framework. It's not exactly light-weight, but it always worked pretty well for my use cases. Throw a model at it (XML schema, annotated Java, ...) and it generates a Java implementation including a tree-based editor; certainly good enough for prototyping purposes.


I'm curious about your use cases, as I do not seem to find much information about model-driven development out there. Can you elaborate a little bit more about what you do with EMF?

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..


I've brought up this issue before in the context of GraphQL's declarative data: https://github.com/facebook/graphql/issues/237#issuecomment-...


If you can do queries AND have a GUI option that seems logical to me.

Looking back at my history this topic hits me right in the feels...

http://birdhouse.org/beos/byte/25-formula_queries/


Trees are not all alike and I think this stops most such plans. Some trees have types and tags, quoting of other trees, container patterns that are representable as a tree but unpleasant to edit.

And we get stuck on that and say "Let's have a syntax." And then we're back to text again.


Did anybody get the source code to run? I've been trying to test it out for a long time but never really gotten anywhere. Is there anybody that is good at functional programming that could help me out?

It's surely funny if there can be so many comments and nobody even ran the program.


http://jsoneditoronline.org/

It's only for JSON but you can write a small script to convert it to whatever format you want.


I'd even be happy to have just a simple general-purpose text-ui tree viewer. There's tree(1) and ncdu(2) but they doesn't really work for anything except directory trees.


I think this problem is closely related to the perennial "optimal to-do list" problem. A to-do list is a tree. If you have a good tree editor, you have a good to-do list app.


Pretty much any code editor with a jump to source, is a user friendly graph editor. And with refactoring tools, a good debugger and compiler I can't see what is missing


Not all graphs are expressed as code, or should be.


Also, code in most languages is pretty far from being a tree on the surface.

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.


I must admit i have no clue what the author is actually asking for.

If he is asking for away to organize various bits of text etc, is that not basically a directory tree stuffed with files?


Isn't this just what's known as an Outliner (e.g. OmniOutliner, but various other programs exist)?


orgzly (open outliner saves in org mode for Android)

https://play.google.com/store/apps/details?id=com.orgzly&hl=...


Because the use case of "edit all graphs" is too divergent to be solved by one program.

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
(Note the new asterisk on the third line of the last one; it's a new node. In the first one, we have "special" nodes that can be embedded, whereas others probably can't be; that's a heck of a concept to write into your generic editor and will have huge ramifications in all sorts of other places, not least of which is the graph data representation and API. In the second one we somehow have "embedded" nodes, which has the same problems, except it has different massive effects on the graph data structure and API. The third is conceptually simplest in a lot of ways, but maps neither to HTML nor to the human's internal representation very well.) Now, how do your choices that you made for this rich text application map back to the other types of graphs you may want to support? Because each of those three choices will have different implications if you then try to support RDF graphs in the same visual layout.

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".


seems like the next trello can be trello with graphs, diagrams and trees


Thanks to this post I found out about TreeSheets. Looks interesting.


Check out Freemind. It's been collecting dust on the shelves.


Joe Celko's Trees and Hierarchies in SQL for Smarties (book) is a good start for better understanding/defining trees. http://a.co/9eVzvji


There's a very useful chapter in Karwin's SQL Antipatterns on this topic too.


Lisp Machines had general tree editing facilities.


Isn't that called Outliner?


Check out Freemind


Freeplane?


Check gingko, which is more focussed on docs, but is a tree editor at its core.

https://gingkoapp.com/

Used it at university for notes, and is great for quick revisions before the exams too!


Gingko is phenomenal, heavy use of it will alter how you think and work, Sapir-Whorf style. Developer seems like a good guy who cares intensely. Happy to pay for this tool.


Looks great but it only does text. The link speaks of beyond ASCII. For this the old school PIM were better at storage of thoughts.


"old school PIM"? Wikipedia and I find this ambiguous [1].

1. https://en.wikipedia.org/wiki/PIM


Actually, it does Markdown, which includes images, and anything you can embed as HTML.

Also, supports LaTeX.


Whoops, I am a bad community member and posted before seeing this.

Yeah, Gingko is really phenomenal, especially for multiplayer!


+1 for gingko -- it's especially great when starting a big document from scratch as it allows you to move and restructure entire documents, something that would be a lot of trouble with copy paste.


To me it's shocking that there's nothing for editing XML that equates to an editable tree GUI interface where nodes and properties can be rendered onto something resembling a document but yet browsable (by expanding and collapsing node) with the same paradigm of a file-system browser gui. I'm working on this myself actually, in meta64.com (see it on github, because the site is not always live, and is experimental). I am using JCR as the back end data storage but seriously considering adding a feature so support direct XML editing. XML and also REST are highly structural, and yet everyone seems to just use syntax-highlighting text editors to edit them rather than something more akin to a tree-based browser, that would render something more friendly looking (with expand/collapse capability). Think of it like this, you have seen RSS XML before right? You have also seen web sites that RENDER the RSS feed into a document-looking thing. That's what i'm getting at. Going from editing this stuff as a text file, to something much more advanced, like a tree-browser. Maybe there are some things i'm not aware of, like perhaps even an Atom Editor plugin or whatever, but I don't think there's anything in wide use or i'd know about it, having been a web developer for 25yrs now.


Blasphemy: All xml editors are General Purpose Tree Editors




Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: