When implementing programming languages, we usually represent computer programs as abstract syntax trees. With this representation we need to be especially careful when representing bound variables, because the implementations of variable renaming and substitution are error-prone. Naive implementations can result in poor performance.
In this work, this problem is explored using the lambda calculus, which is a simple programming language of functions. Three representations of bound variables are presented: the naive approach, de Bruijn indices, and higher-order abstract syntax.
The OCaml library Bindlib is also presented, as it makes working with bound variables simple, safe and efficient.
Finally, the use of the Bindlib library is demonstrated with the example of the Millet programming language, which is used as a base when prototyping programming languages.
The differences in the efficiency of bound variable representations are demonstrated by an experiment in which we measure the execution time of four implementations of the lambda calculus.
|