124

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?

13
  • 40
    Lisp is normally written as an abstract syntax tree. It didn't catch on as much as more Algol-like languages. Nov 10, 2011 at 22:18
  • 3
    I can't believe that David is the only one to mention that LISP programs are an abstract syntax tree.
    – WuHoUnited
    Nov 10, 2011 at 23:54
  • 3
    In addition to other points: AST is not even the final thing. It also does not take that long to create AST out of code. When I run StyleCop on my small-ish, VS2010 project, it runs dozens of different AST-based rules on thousands of lines of code very fast (sometimes a second or two). It is also fairly easy to extend StyleCop and to write a custom rule. I suspect that parsing of the source code into an AST is a well-understood, and a relatively easy problem. It is coming up with the good language in the first place, and optimization, and all of the libraries that is hard, not parsing.
    – Job
    Nov 10, 2011 at 23:58
  • 3
    Having parsed the code, it is not so easy to generate the code for another language. (How would you translate Prolog's implicit unification into C?). Mostly what you have is an AST for the original program.
    – Ira Baxter
    Nov 11, 2011 at 3:28
  • 3
    The problem of parsing is well understood technically, but it it isnt an easy task to parse C or C++ because they are messy nasty languages. Many compilers parser C or C++ to ASTs: Clang, GCC, ... They aren't intended for program storage, and GCC badly wants to be compiler, not a program analysis tool. Our DMS Software Reengineering Toolkit parses many dialects of C and C++, produces ASTs, symbol tables, and various kinds of flow analysis artifacts. The big Pro of this approach is the abililty to build automated change tools. semanticdesigns.com/Products/DMS/DMSToolkit.html
    – Ira Baxter
    Nov 11, 2011 at 3:29

14 Answers 14

77

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.

4
  • 10
    There are parsers that capture comments and layout in the AST. Our DMS Software Rengineering Toolkit does this just fine. It does have a hard time with illegal code; it has a precise language parser.
    – Ira Baxter
    Nov 11, 2011 at 3:25
  • 2
    There's actually a tool that converts Javascript to CoffeeScript, so I think JavaScript and CoffeScript are mutually translatable without Javascript literals. Nov 11, 2011 at 20:40
  • Interesting tool, Peter, I was not aware of it. Nov 14, 2011 at 15:06
  • +1 for meaningful formatting and the interesting personal experience. -- White spaces aren't important for the question and comments could be kept. Codes with error would be easier to fix anyway and of course the "one language to rule them all" part of the question was unreachable.
    – cregox
    Mar 16, 2015 at 18:17
50

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.

2
  • 5
    Actually, you can do the tree-diff in a language independent way. You do need language specific parsers to build the trees. See our Smart Differencer line of tools, that compare the ASTs for many languages. They all use the same underlying diff engine. semanticdesigns.com/Products/SmartDifferencer
    – Ira Baxter
    Nov 12, 2011 at 3:13
  • 2
    I hope to see the my-style-pretty-print-on-load team-style-pretty-print-on-save in Visual Studio some day... been hoping for years... no luck yet... Mar 12, 2012 at 20:13
21

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.

1
  • 5
    Ever tried decompiling MSIL produced by F#?
    – SK-logic
    Nov 11, 2011 at 13:02
16

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.

6
  • 5
    The potential benefit would be that it could end endless debates like "tabs vs. spaces", "unix vs. windows bracing/indentation", "m_ prefixes in front of members or not", because they could be turned into simple IDE options.
    – nikie
    Nov 11, 2011 at 14:08
  • 2
    @nikie True but you can already do this using reformatting tools – like astyle or UnniversalIndent. No need for arcane binary formats. Nov 11, 2011 at 14:35
  • 2
    The real benefit would be the potential to have diff/patch tools which give you a better understanding of what really changed. But that seems to imply needing an entire new toolchain for version control, which is a serious limitation. Nov 11, 2011 at 18:03
  • 2
    If you think "There is no benefit," then you have not seen Intentional Software's Domain Workbench. Nov 11, 2011 at 19:18
  • 2
    In a nutshell, the same logic can be projected into different representations, not all text based, making the rules accessible to non-programmers. E.g., domain experts like actuaries can write the actuarial parts of an insurance application. Like a DSL except not confined to that representation. This is very much related to the question, though. There's a good demo. Nov 13, 2011 at 3:14
14

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.

1
  • 5
    Have you been following the development of Microsoft's "Roslyn" project to open up the VBc and C# compilers as APIs? There is a preview release available. Nov 11, 2011 at 4:24
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.

2
  • 7
    and if you make the comments part of the syntax tree (with comment nodes that can be a child of anything)? Nov 10, 2011 at 23:28
  • Our tools do exactly that. See my other comments in this thread.
    – Ira Baxter
    Nov 11, 2011 at 3:27
6

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?

3
  • a "language workbench" should not necessarily be based on storing raw ASTs. They can be plain text syntax-oriented as well, see for example meta-alternative.net/pfront.pdf (and this one actually extends Visual Studio and Emacs editor with any eDSL implemented on top of it).
    – SK-logic
    Nov 12, 2011 at 13:13
  • That's an interesting paper; it reminds me (in ambition, not at all in implementation) of a tool called SugarJ which was presented at SPLASH / OOPSLA a few weeks ago: uni-marburg.de/fb12/ps/research/sugarj Nov 13, 2011 at 1:10
  • interesting, I'll try that one as well.
    – SK-logic
    Nov 13, 2011 at 9:50
5

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.

4
  • 3
    ... but you do get a lot of editor features out of the box. Consider expanding this answer a bit, it's a very interesting technology which deserves going a bit more into detail of the advantages of not storing source code as text. E.g. as I answered on this question on tabs vs. spaces. Nov 11, 2011 at 17:24
  • AST could be saved in human readable format and not in binary. can you now with linux tools for example replace every method in code that takes as parameter serializable object? it would be very hard to write, but AST make that very easy.
    – IAdapter
    Nov 11, 2011 at 22:58
  • 2
    People continually make this mistake. The AST makes it easier than if you have just raw text. But for anything interesting, you need a bunch of additonal information: control and data flow, symbol tables, range analysis, ... ASTs help but are only a small part of what is really needed.
    – Ira Baxter
    Nov 12, 2011 at 4:35
  • @Ira Baxter, of course it is easier with AST. But it is much harder to integrate into the existing infrastructure.
    – SK-logic
    Nov 12, 2011 at 13:09
5

You've been reading my mind.

When I took a compilers course, a few years ago, I discovered that if you take an AST and serialize it, with prefix notation instead of the usual infix notation, and use parentheses to delimit entire statements, you get Lisp. While I'd learned about Scheme (a dialect of Lisp) in my undergrad studies, I'd never really gained an appreciation for it. I definitely gained an appreciation for Lisp and its dialects, as a result of that course.

Problems with what you propose:

  1. it's hard/slow to compose an AST in a graphical environment. After all, most of us can type faster than we can move a mouse. And yet, an emerging question is "how do you write program code with a tablet?" Typing on a tablet is slow/cumbersome, compared to a keyboard/laptop with a hardware keyboard. If you could create an AST by dragging and dropping components from a palette onto a canvas on a large, touchscreen device programming on a tablet could become a real thing.

  2. few/none of our existing tools support this. We have decades of development wrapped up in creating increasingly-complex IDEs and increasingly-intelligent editors. We have all these tools for reformatting text, comparing text, searching text. Where are the tools which can do the equivalent of a regular expression search across a tree? Or a diff of two trees? All of these things are easily done with text. But they can only compare the words. Change a variable name, such that the words are different but the semantic meaning is the same, and those diff tools run into trouble. Such tools, developed to operate on ASTs instead of text, would allow you to get closer to comparing the semantic meaning. That would be a Good Thing.

  3. while turning program source code into an AST is relatively well-understood (we have compilers and interpreters, don't we?), turning an AST into program code is not-so-well-understood. Multiplying two prime numbers to get a large, composite number is relatively straightforward but factoring a large, composite number back into primes is much more difficult; that's where we are with parsing vs decompiling ASTs. That's where the differences between languages becomes an issue. Even within a particular language, there are multiple ways to decompile an AST. Iterating through a collection of objects and getting some kind of result, for example. Use a for loop, iterating through an array? That would be compact and fast, but there are limitations. Use an Iterator of some kind, operating on a Collection? That Collection could be variable-sized, which adds flexibility at the (possible) expense of speed. Map/Reduce? More complex, but implicitly parallelizable. And that's just for Java, depending on your preferences.

In time, the development effort will be expended and we will be developing using touchscreens and ASTs. Typing will become less of a necessity. I see that as a logical progression from where we are, looking at how we use computers, today, That will solve #1.

We are already working with trees. Lisp is merely serialized ASTs. XML (and HTML, by extension) is just a serialized tree. To do searching, we already have a couple prototypes: XPath and CSS (for XML and HTML, respectively). When graphical tools are created that allow us to create CSS-style selectors and modifiers, we will have solved part of #2. When those selectors can be extended to support regexes, we'll be closer. Still looking for a good graphical diff tool for comparing two XML or HTML docs. As people develop those tools, #2 will be can be solved. People are already working on such things; they just aren't there, yet.

The only way I can see to be able to decompile those ASTs to programming language text would be something goal-seeking. If I'm modifying existing code, the goal might be achieved by an algorithm which makes my modified code as similar as possible to the starting code (minimal textual diff). If I'm writing code from scratch, the goal might be the smallest, tightest code (likely a for loop). Or it might be code which parallelizes as efficiently as possible (likely a map/reduce or something involving CSP). So, the same AST could result in significantly different code, even in the same language, based on how the goals were set. Developing such a system would solve #3. It would be computationally complex, meaning we'd probably need some kind of client-server arrangement, allowing your handheld tablet to offload a lot of heavy lifting to some cloud-based server.

4

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?

3

Two other interesting projects to note related to coding in Abstract Syntax Tree's is Tree-Sitter which is now a part of the Atom text editor and Github. It parses your code real-time into an AST. This allows you to do some very interesting things, like something the creator of it calls "Extend Selection" where you can continue to click on one word and it will highlight the text related to higher and higher levels of the AST since it understands that structure.:

enter image description here

There is also the Unison programming language which doesn't store source code in text files. Instead, it parses the text files, takes out of all the details so you're left with a highly-abstracted version of your code, and then it hashes that. That "code" is then accessed by using the hash, not the file name. This leads to a lot of interesting benefits like no more builds, no dependency conflicts, and you can easily change names of variables/functions/etc without changing the codebase.

Both of these projects allow you to code at an abstraction level a little further away from the raw text and closer to the AST.

1

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.

6
  • 1
    Then you'll still need a semantic diff and merge (i.e., again, AST-level).
    – SK-logic
    Nov 11, 2011 at 15:41
  • 1
    No, the editor reformats back into the team style for storing the source - so you'd be comparing one source type against the same type. Nov 11, 2011 at 15:44
  • a good point, a single normalised representation solves all the problems
    – SK-logic
    Nov 11, 2011 at 15:49
  • 1
    No, it only solves the problems the problems of comparting two files for identity. If you want to see differences between the files, you ideally need something that understands structure. I love my emacs, but it doesn't understand structure.
    – Ira Baxter
    Nov 12, 2011 at 4:37
  • Emacs is great, but I never use it to diff. To diff my source tree before check-in, I always use meld. It actually understands SVN and git. On Windows, I'd use WinMerge probably in combination with tortoise. Nov 12, 2011 at 8:33
1

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.

9
  • 2
    It is easier to reliably modify an AST with mechanical tools, than to do so with text. You can do this with pattern-directed changes. See semanticdesigns.com/Products/DMS/ProgramTransformation.html
    – Ira Baxter
    Nov 11, 2011 at 3:32
  • 2
    Tell this to the LISPers now...
    – hugomg
    Nov 11, 2011 at 11:48
  • @Ira Baxter. I know, Im actually working on a custom visual tool that works directly with an AST, however, sometimes, developers have to work with text instead of visual. Some AST are also represented as a shorter programming language in text.
    – umlcat
    Nov 11, 2011 at 18:57
  • @umlcat, can you tell me more about your work on a visual tool for ASTs? Oct 21, 2013 at 18:14
  • @Daniel Albuschat I working a pet programming language project.The parser its difficult to implement, so I skip it, for the moment, and made a tool where I show the AST (form with treeview control), & add expressions directly. And can do the opposite, generate the code from the AST.
    – umlcat
    Oct 22, 2013 at 3:33
0

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?

2
  • 2
    As someone intimately familiar with both the C# and VB compilers I can tell you that they are certainly similar but there are a sufficient of important details that differ enough that it is impractical to treat them as "the same language with different syntax". We considered doing that for the Roslyn project; building a single compiler that could compile both languages with equal facility -- and after much debate decided to go with two compilers for two languages. Nov 11, 2011 at 17:47
  • @EricLippert: that's a shame. not that i ever planned learning either language, but it did sound like a nice exception. I think htat leaves lisp-like-Dylan and algol-like-Dylan as the only 'same language with different syntaxes' example.
    – Javier
    Nov 11, 2011 at 18:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.