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.

Tony Morris

Sr. Software Engineer

Queensland FP Lab, Data61


Tony Morris is a software product developer who has deployed functional programming techniques in industry for over 10 years. Tony teaches at the tertiary level and for professional programmers with a view toward producing a viable commercial result. Tony is currently a Senior Software Engineer at NICTA where he is tasked with promoting and educating on functional programming for the benefit of all Australian software developers.

Tony takes a fastidious, principled approach to functional programming both when deployed in practice and when in a learning environment to ensure maximum yield from the effort. Tony believes that exploring principles and the following consequences provides a rewarding experience for all involved.