1. 11

I got some great feedback and questions from Lobsters a few weeks back when I posted about a Tree Language, and started compiling common questions into this page.

Would love any feedback! Thank you!


  2. 4

    The contrast on the site is a bit too low for me to read.

    As a parsing geek, I really like how clean and small the design of this is. It looks like a clean spin on a high-level IR. From a syntax UX POV, however, requiring composite expressions (e.g. 1 + 1) to be child nodes doesn’t seem exciting to me. Lisp lets me use parenthesis to avoid the ceremony of a newline + indent, Haskell lets me use $ or parenthesis as well.

    This doesn’t make tree notation bad, but it makes it a harder sell in the PL domain. I’m 100% with you on the power of exponential thinking, but IMO users don’t really care that their favorite PL parser is sometimes an Eldritch abomination.

    I don’t have any good ideas here; using bare words for anything more than a single expression in an infix PL gets quite tricky to parse (dangling if) or read.

    1. 2

      The contrast on the site is a bit too low for me to read.

      Good point! I should probably switch to a different GitHub pages theme.

      Lisp lets me use parenthesis to avoid the ceremony of a newline + indent, Haskell lets me use $ or parenthesis as well.

      Great question that comes up often. I added it to the page.

      Question: Can I do inline Trees?

      Answer: Yes! While not supported at the base Tree Notation level, your individual nodes can certainly have inline trees. Often your Tree Languages will have nodes that contain content written in traditional languages like Javascript, Lisp, or Python. Or you could even have inline trees written in Tree Notation, except using something like the pipe character as YI instead of the newline character.

      1. 3

        If a Tree Language has some nodes whose structure is not expressed in Tree Notation, then a Tree Notation parser doesn’t have access to all the structure of the document. The opposite is also true: Tree Notation doesn’t have any kind of built-in escaping, so if my Tree Language needs nodes that contain YI, I’d have to do something like:

          The Termite
          Ogden Nash
          Some primal termite knocked on wood
          And tasted it, and found it good!
          And that is why your Cousin May
          Fell through the parlor floor today.

        …and now, a Tree Notation parser sees more structure than is actually in the document. Either way, the less the Tree Notation syntax corresponds to the Tree Language semantics, the less useful it is.

        Other light-weight syntaxes like OGDL and BML have more features, which means a notation-level parser can more accurately understand the structure of the document, making the raw notation more useful. There’s definitely a balance between features and flexibility, but I worry that Tree Notation is too flexible.

        1. 3

          Thanks for the feedback! This is a certainly an issue that we should always keep revisiting and see if there’s anything core that should be in Tree Notation versus Tree Languages. So far, nothing has met that threshold. A few years ago I added https://github.com/breck7/jtree/blob/master/zen.mark, which basically says the one rule of Tree Notation is to “Put it in a Tree Language”. But this is always open to change, if we some good data suggesting we should change.

          I took your example and created a Tree Language called Poem in 27 lines in just about 120 seconds (of course, I built the thing so have a huge unfair speed advantage). The “blobNode” attribute tells the Tree Notation implementation not to parse the individual words of those child nodes (this is helpful for one current program which is now over 300k lines of Tree Code with a lot of comments and strings), but that’s just for perf gains. It would be harmless to parse those as strings.

          Thank for the links to OGDL and BML. AFAICT, I haven’t seen those before.

          I definitely think we want to err on the side of too flexible, like binary. I’m still very unsure if we should have the ZI in the base spec of Tree Notation (currently it’s just XI and YI).

    2. 4

      “The Tree Conjecture” is false. There are structures which cannot be represented as trees. If one accepts that anything representable as a finite string (including trees in this format) can be encoded as a natural number; and there are real numbers that cannot be enumerated; and structures might include those, then there are structures not representable as a tree.

      1. 3

        There are not structures that can be represented that cannot be represented by trees.