Why don't we store the syntax tree instead of the source code?

Question

We have a lot of programming languages. Every language is parsed and syntax checked before being translated into code so an abstract syntax tree (AST) is built.

We have this abstract syntax tree, why don't we store this syntax tree instead of the source code (or next to the source code)?

By using an AST instead of the source code. Every programmer in a team can serialize this tree to any language they want (with the appropriate context free grammar) and parse back to AST when they are finished. So this would eliminate the debate about the coding style questions (where to put the { and }, where to put whitespace, indentation, etc.)

What are the pros and cons of this approach?

Answer 1

Whitespace and Comments

Generally an AST does not include whitespace, line terminators, and comments.

Meaningful Formatting

You are correct that in most cases this is a positive (eliminates formatting holy wars), there are many cases where the formatting of the original code conveys some meaning, such as in multi-line string literals and "code paragraphs" (separating blocks of statements with an empty line).

Code that can't be compiled

While many parsers are very resilient to missing syntax, code with errors often results in a very weird syntax tree, which is fine and dandy up until the point where the user reloads the file. Ever make a mistake in your IDE and then all of a sudden the entire file has "squigglies"? Imagine how that would be reloaded in another language.

Maybe users don't commit unparsable code, but they certainly do have a need to save locally.

No two languages are perfect matches

As others have pointed out, there are almost no two languages that have perfect feature parity. The closest I can think is VB and C#, or JavaScript and CoffeeScript, but even then VB has features like XML Literals that don't quite have equivalents in C#, and the JavaScript to CoffeeScript conversion might result in a lot of JavaScript literals.

Personal Experience:

In a software application I write, we actually need to do this, as the users are expected to enter "plain English" expressions that are converted to JS in the background. We considered only storing the JS version, but found almost no acceptable way to do so that reliably loaded and unloaded, so we ended up always storing both the user text and the JS version, as well as a flag that indicated if the "plain english" version parsed perfectly or not.

Answer 2

Why don't we store this syntax tree instead of the source code? Every programmer in a team can serialize this tree to any language, they want and parse back to AST when they finished.

Indeed, that is a reasonable idea. Microsoft had a research project in the 1990s to do almost exactly that.

Several scenarios come to mind.

The first is rather trivial; as you say, you could have the AST rendered into different views depending on the preferences of different programmers for things like spacing and so on. But storing an AST is overkill for that scenario; just write yourself a pretty-printer. When you load a file into your editor, run the pretty-printer to put it into your preferred format, and back into the original format when you save it.

The second is more interesting. If you can store the abstract syntax tree then code-diffing a change becomes not textual but rather syntactic. Refactorings where code is moved around become much easier to understand. The down side is of course that writing the tree-diff algorithms is not exactly trivial and often has to be done on a per-language basis. Text diff works for almost any langauge.

The third is more like what Simonyi envisioned for Intentional Programming: that the fundamental concepts common to programming languages are what are serialized, and then you have different views of those concepts rendered in different languages. Though a beautiful idea, the ugly fact is that languages are sufficiently different in their details that a lowest-common-denominator approach doesn't really work.

So, in short, it's a lovely idea but it is an enormous amount of extra work for a comparatively small benefit. That's why hardly anyone does it.

Answer 3

You could argue that this is exactly what byte code is in .NET. Infact redgate's reflector program does translate byte code back into a range of .NET programming languages.

However, there are problems. Syntax is language specific in as much as there are things that you can represent on one language that have no representation in other languages. This occurs in .NET with C++ being the only .NET language that has access to all 7 access levels.

Outside of the .NET environment it gets much trickier. Each language then start having their own set of associated libraries. It would not be possible to reflect a generic syntax in both C and Java that reflected the same execution of instructions as they solve simular problems in very different ways.

Answer 4

I sort of like some of your idea, but you're significantly overestimating how easy it is to translate language to language. If it were that easy, you wouldn't even need to store the AST, since you could always parse language X into the AST then go from AST to language Y.

However, I do wish compiler specifications thought a bit more about exposing some of the AST through some kind of API. Things like aspect oriented programming, refactoring, and static program analysis could be implemented through such an API, without the implementer of those capabilities having to redo so much of the work already implemented by compiler writers.

It is strange how often programmer's data structure for representing a program is as a bunch of files containing strings.

Answer 5

I think the most salient points are those:

• There is no benefit. You said that it would mean that everybody could use their pet language. But that’s not true – using a syntax tree representation would elide syntactical differences only, but not semantical ones. It works to some extent for very similar languages – such a VB and C#, or Java and Scala. But not even there completely.

• It’s problematic. You have gained freedom of language, but you’ve lost freedom of tools. You can no longer read and edit the code in a text editor, or even any IDE – you depend on a specific tool that speaks your AST representation for both reading and editing the code. There’s nothing gained here.

  To illustrate this last point, take a look at RealBasic, which is a proprietary implementation of a powerful BASIC dialect. For a time, it almost looked like the language could take off, but it was completely vendor-dependent, to the point that you could only view the code in their IDE since it was saved in a proprietary non-text format. Big mistake.

Answer 6

I think, if you store both the text and the AST, then you haven't really added anything useful, since the text is already there in one language, and the AST can quickly be reconstructed from the text.

On the other hand, if you only store the AST, you lose things like comments which can't be recovered.

Answer 7

I believe the idea is interesting in theory but not very practical since different programming languages support different constructs some which don't have equivalents in other languages.

For example, X++ has a 'while select' statement which couldn't be written in C# without a lot of extra code (extra classes, extra logic, etc). http://msdn.microsoft.com/en-us/library/aa558063.aspx

What I'm saying here is that many languages have syntactic sugars that translate in big blocks of code of the same language or even elements that don't exist at all in others. Here is an example why the AST approach will not work:

Language X has a keyword K that is translated, in AST in 4 statements: S1, S2, S3 and S4. The AST is now translated in language Y and a programmer changes S2. Now what happens with the translation back to X? The code is translated as 4 statements instead of a single keyword...

The last argument against the AST approach are the platform functions: what happens when a function is embedded in the platform? Like .NET's Environment.GetEnvironmentVariable . How do you translate it?

Answer 8

There is a system built around this idea: JetBrains MPS. An editor is a little bit odd, or just different, but in general it is not such a big problem. The biggest problem is, well, that it is not a text any more, so you can't use any of the normal text-based tools - other editors, grep, sed, merge and diff tools, etc.

Answer 9

There are actually several products, generally known as "language workbenches" that store ASTs and present, in their editors, a "projection" of the AST back into a particular language. As @sk-logic said, JetBrains' MPS is one such system. Another is Intentional Software's Intentional Workbench.

The potential for language workbenches seems very high, particularly in the area of domain-specific languages, since you can create a domain-specific projection. For instance, Intentional demos a DSL relating to electricity that projects as a circuit diagram -- much easier and more accurate for a domain expert to discuss and criticize than a circuit described in a text-based programming language.

In practice, language workbenches have been slow to catch on because, aside from DSL work, developers would probably prefer to work in a familiar, general programming language. When compared head-to-head with a text editor or programming IDE, the language workbenches have tons of overhead and their advantages are not nearly as clear. None of the language workbenches that I've seen have boot-strapped themselves to the point where they can easily extend their own IDEs, either -- that is, if language workbenches are great for productivity, why have not the language workbench tools become better-and-better at faster-and-faster rates?

Answer 10

If your intention is to eliminate the debate about formatting styles, then perhaps what you want is an editor that reads in a source file, formats it to your personal preference for display and editing, but when saving it, reformats to the chosen style the team uses.

It's quite easy if you use an editor like Emacs. Changing the formatting style of an entire file is a three command job.

You should also be able to build the hooks to automatically transform a file to your own style on loading, and to transform it to the team style when saving.

Answer 11

it's a nice idea; but each language's AST is different from every other one.

the only exception I know is for VB.NET and C#, where microsoft argues that they're "the exact same language with different syntax". Even other .NET languages (IronPython, F#, whatever) are different at the AST level.

Same thing with JVM languages, they all target the same bytecode, but the language constructs are different, making it different languages and different ASTs.

Even 'thin layer' languages, like CoffeScript and Xtend share a lot of the theory of the underlying languages (JavaScript and Java, respectively); but introduce higher level concepts that are (or should be) retained at the AST level.

if Xtend could be reconstructed from a Java AST, i think it would've been defined as a Java-to-Xtend 'uncompiler' that magically create higher level abstractions from existing Java code, don't you think?

Answer 12

It's difficult to read and modify an AST, instead of source code.

However, some compiler related tools does allow to use the AST. Java bytecode and .NET Intermediate code work similar to an AST.