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.
|
