Join Newsletter

Trees That Grow

YOW! Lambda Jam 2019

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.