What is an AST transformation?

Question

What is an AST transformation in general? I came across these words when reading Groovy blog's. But what it is in general?

Raleigh

Answer 1

AST means Abstract Syntax Tree, which is basically an abstract representation of code / any syntactic structure. A transformation is an action modifying this tree (i.e. transforming the existing AST to a new AST). For more information have a look here: http://en.wikipedia.org/wiki/Abstract_syntax_tree

Carcassonne

Never heard of that before, thanks for the education :) – Comprehensive

Answer 2

In addition to what have been mentioned already, you might also be interested in a broader and more fundamental concept of Term rewriting.

Buchner

Answer 3

The simple answer is any function that converts one AST, into another AST.

A more sophisticated view can be found in my SO answer on Model-driven development: What is a transform?

Atonic

Downvoter/Flagger: given that other folks think my answer is pretty good, it seems only reasonable that you should note your objection here instead of simply flagging this and running. – Atonic

Ira, can you tell what can AST Transformations achieve that Mixins can't? – Kesley

Mixins are a runtime scheme for adjusting a baseline behavior f by allowing additional behaviors b ("before") and a ("after"). Your resulting behavior is b dot f dot a (composition of behaviors). The range of behaviors you can get is obviously restricted by how f processes its input. Program transformations (PT) take an arbitrary specification f and applies transformations to generate another specification f' with the same abstract behavior as f. ... – Atonic

... One can use PT to implement mixins (just apply transformations that insert b and a around a realization of f), so PT is at least as powerful as Mixins. But Mixins are restricted to a specific programming language in which f, a and b must be coded; PT systems done right have no such restrictions. So Mixins are strictly less powerful than PT. (In fact, PT can realize arbitrary computations on f to produce a result, which is much more thatn Mixins can restricted to "compose f with b and a"). PTs are also valuable in allowing one to work with abstractions rather than just code. ... – Atonic

... To get a real sense of the practical differences, consider how you might tackle the problem of converting the mission software for the B-2 Stealth Bomber, coded in JOVIAL, into C, with "Mixins". It should be blindingly obviously that Mixins cannot approach such a problem, yet PT can do this in a "technically easy" way (my company has actually done this). Or consider converting C++ code operating on std::vectors into mixed C++ and SIMD machine instructions for high performance execution; again, mixins cannot approach this, and again my company has done this with PTs. – Atonic

... Both of the above tasks were done using PT implemented as AST transformations, with admittedly extra capabilities provided by the tool we use (see my bio for more details on the tool). – Atonic

Answer 4

AST is a tree representation of the abstract syntactic structure of source code written in a programming language.

When there is a need to transform code changing it parts usually transformer operates with tree representation of source code to find the node which requires changes using Visitor Pattern and to apply this changes.

For example putout code transformer for JavaScript supports direct manipulation with AST tree this way:

const putout = require('putout');

const removeDebugger = {
    report: () => 'debugger should not be used',
    fix: (path) => {
        path.remove();
    },
    traverse: ({push}) = ({
        'DebuggerStatement': (path) => {
            push(path);
        }
    }),
};

putout('const a = 5; debugger', {
    fix: true,
    plugins: [
        ['remove-debugger', removeDebugger]
    ]
});
// returns
({
    code: 'const a = 5;',
    places: [],
});

Anyways there is much simpler way to manipulate with AST used in @putout/plugin-remove-debugger:

const removeDebugger = {
    report: () => 'debugger should not be used',
    replace: () = ({
        'debugger': ''
    }),
};

In this example one expression replaced with another using templates language of @putout/engine-runner that helps to write simple code transformation without touching AST at all.

Worth mention that inside of replace transformation anyways used AST because it's the most powerful way of manipulation with source code.

Course