• Naming is hard: It's one of the two hard problems in computer science along with cache invalidation and off by one errors. Humans and computers struggle with coming up with good names. Compilers often need to generate names for variables and function parameters.
• We want Names: Compilers need names to represent programs in memory and determine equality. An AST with named variables is used to understand the naming dilemma. Equality and substitution are two properties needed in the AST. All nontrivial compilers equate ASTs for internment and optimization passes.
• Inlining Names: Substitution is the process of inlining function parameters. Inlining is important for optimization. Examples show how naming can make inlining hard and change the meaning of an AST. Tracking used names can be expensive and hinder equality.
• More Names, More Problems: Different names for similar AST terms can cause problems. The computer lacks the ability to pattern match and see the equality. Names get in the way of the computer's understanding.
• Inlining Issues: Bad names can cause inlining to change the meaning of an AST. The compiler struggles to see these issues on larger ASTs. It's possible to track used names, but it can be expensive and hinder equality.
• Picking Better Names: Functions can be thought of as an array of names for bound variables. Indexing can be used instead of names to represent variables. This makes it easier to compare ASTs for equality.
• Achieving Equality for All: Systematically selecting indices using DeBruijn Levels makes it easy to compare ASTs for equality. However, it can cause problems with substitution.
• Trouble in Paradise: DeBruijn Levels can lead to incorrect indices when substituting. DeBruijn Indices solve this problem by building a stack of names bottom to top and indexing into it.
• Turning around our Troubles: DeBruijn Indices make it easy to work with bound variables and substitution. They are easier to work with than DeBruijn Levels. A hybrid approach can be used to combine the benefits of both.
• Pick the Right Name for the Job: DeBruijn Indices are better for dealing with bound variables, while DeBruijn Levels are better for free variables. A hybrid approach can be used to achieve both equality and substitution while maintaining legibility.