Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
24  
Lisp is normally written as an abstract syntax tree. It didn't catch on as much as more Algol-like languages. –  David Thornley Nov 10 '11 at 22:18
2  
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 '11 at 23:58
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 '11 at 3:29
1  
Even two different implementations of the same programming language may use different AST's for the same source file. So the idea of reusing AST's wouldn't work. –  Giorgio Nov 11 '11 at 18:44
1  
There are much bigger differences between languages than just their syntax for simple constructs. –  Thomas Ahle Dec 7 '11 at 11:29
show 6 more comments

12 Answers

up vote 49 down vote accepted

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.

share|improve this answer
7  
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 '11 at 3:25
1  
There's actually a tool that converts Javascript to CoffeeScript, so I think JavaScript and CoffeScript are mutually translatable without Javascript literals. –  Peter Olson Nov 11 '11 at 20:40
    
Interesting tool, Peter, I was not aware of it. –  Kevin McCormick Nov 14 '11 at 15:06
add comment

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.

share|improve this answer
    
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 '11 at 3:13
    
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... –  romkyns Mar 12 '12 at 20:13
add comment

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.

share|improve this answer
1  
+1, I was about to ask "so, what about MSIL" –  Wyatt Barnett Nov 10 '11 at 22:47
3  
Ever tried decompiling MSIL produced by F#? –  SK-logic Nov 11 '11 at 13:02
add comment

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.

share|improve this answer
4  
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. –  Carson63000 Nov 11 '11 at 4:24
add comment

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.

share|improve this answer
2  
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 '11 at 14:08
1  
@nikie True but you can already do this using reformatting tools – like astyle or UnniversalIndent. No need for arcane binary formats. –  Konrad Rudolph Nov 11 '11 at 14:35
    
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. –  Peter Taylor Nov 11 '11 at 18:03
    
If you think "There is no benefit," then you have not seen Intentional Software's Domain Workbench. –  Craig Stuntz Nov 11 '11 at 19:18
    
@Craig Very right. And since it seems to be pretty arcane, care to give a concise explanation of what it offers? But just to make this clear, I was addressing the “benefit” which the OP outlined here, and explain why this doesn’t work. There may well be other benefits, but I fail to see them so far (except for what Peter wrote). –  Konrad Rudolph Nov 12 '11 at 15:35
show 1 more comment

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.

share|improve this answer
3  
and if you make the comments part of the syntax tree (with comment nodes that can be a child of anything)? –  ratchet freak Nov 10 '11 at 23:28
    
Our tools do exactly that. See my other comments in this thread. –  Ira Baxter Nov 11 '11 at 3:27
add comment

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?

share|improve this answer
add comment

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.

share|improve this answer
    
... 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. –  Steven Jeuris Nov 11 '11 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 '11 at 22:58
    
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 '11 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 '11 at 13:09
add comment

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?

share|improve this answer
    
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 '11 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 –  Larry OBrien Nov 13 '11 at 1:10
    
interesting, I'll try that one as well. –  SK-logic Nov 13 '11 at 9:50
add comment

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.

share|improve this answer
    
Then you'll still need a semantic diff and merge (i.e., again, AST-level). –  SK-logic Nov 11 '11 at 15:41
    
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. –  Gustav Bertram Nov 11 '11 at 15:44
    
a good point, a single normalised representation solves all the problems –  SK-logic Nov 11 '11 at 15:49
    
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 '11 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. –  Gustav Bertram Nov 12 '11 at 8:33
add comment

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?

share|improve this answer
1  
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. –  Eric Lippert Nov 11 '11 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 '11 at 18:42
add comment

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.

share|improve this answer
    
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 '11 at 3:32
2  
Tell this to the LISPers now... –  missingno Nov 11 '11 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 '11 at 18:57
    
@umlcat, can you tell me more about your work on a visual tool for ASTs? –  Daniel Albuschat Oct 21 '13 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 '13 at 3:33
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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