Comment by User23
3 years ago
One really interesting development of the Lambda calculus is the De Bruijn index. It does away with variable names altogether. It solves the name collision problem and would be an interesting way to write hygienic macros.
Tromp's binary lambda calculus, which is what Justine is using, is based on de Bruijn indices.
It works, but it's very fiddly. My favourite way of solving the problem of names in the lambda calculus is to use Pitts-Gabbay nominal syntax. Wikipedia has a weak article on them, which I mean someday to fix up: https://en.wikipedia.org/wiki/Nominal_terms_(computer_scienc...
I really like de Bruijn indexes, but whenever alternatives are suggested I always like to mention the paper "I am not a number, I am a free variable", if only for the title ;)
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36...
Interesting! I hadn’t come across this. Thank you!