Abstract Syntax Trees

The data structure we're using in this example is called an abstract syntax tree. In the last exercise you wrote a function that takes an abstract syntax tree as input and returns a new abstract syntax tree that does something slightly different (playing an extra note). Your code transformed the input program into a new output program in the same musical language. Your function computed a program transformation.

There are different ways to represent abstract syntax trees in JavaScript. The method we use is to create objects that have a field tag that says which type of expression it is. Each different type of tag can have its own unique set of fields that make sense for that tag. So a 'note' expression has a pitch and dur, while a 'seq' expression has a left and a right.

Here's our example abstract syntax tree again.

Let's do another more interesting program transformation.

This time write a function reverse that takes a music expression as input and returns a new music expression that plays the notes in the reverse order. Your function shouldn't modify the input, it should just return a new reversed expression.


You probably want to use recursion for this one. What's the base case?

The reverse of ABC+DEF is not DEF+ABC. It's FED+CBA.

Prev Next