Trees That Grow
Trees That Grow *(Najd, Shayan and Peyton-Jones, Simon, 2016)* is proposed as a solution to a problem that regularly affects authors of deep and detailed algebraic structures. A data structure denoting a syntax tree for a programming language is typically very intricate and a small alteration deep in the tree can affect all siblings and parents of that tree. For example, adding a minor language feature to a syntax tree can have flow-on effects for the remainder of the tree. Classy lenses & prisms are a very powerful tool to overcome this common issue, which we will look at in this talk, but we will primarily look at another more recent proposal in Trees That Grow (TTG) to contrast and explore.
Although this general problem is canonically explained in terms of a programming language syntax tree (such as lambda calculus), we will also look at another application in aviation where TTG has been used to implement a flexible data structure tree in aviation documentation. The outcome of the talk is to provoke a discussion about this common programming problem, and the methods and trade-offs by which it might be overcome. TTG is also proposed as a solution to extending the Haskell programming language in the Glasgow Haskell Compiler (GHC).
Overall, the audience will get a good feel for the details of the problem that we are dealing with, then we explore some of the methods by which we can mitigate the problem, with an emphasis on gaining an understanding for Trees That Grow.
Outline/Structure of the Talk
- State the problem that is addressed by Trees That Grow
- Give the definition of Trees That Grow as a technique
- Explore how Trees That Grow addresses the problem
- Discuss trade-offs involved with the technique, compared to others
Familiarity with Trees That Grow as a technique in data structure design.
An audience interested in exploring solutions to common problems in data structure design
Prerequisites for Attendees
Familiarity with algebraic data types and the subsequent design problems involved.