3 ms·

The Informal Description section on Wikipedia is good for more background on Lambda Calculus: https://en.m.wikipedia.org/wiki/Lambda_calculus https://en.m.wiki

• User23 5y 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. [1] https://en.m.wikipedia.org/wiki/De_Bruijn_index https://en.m.wikipedia.org/wiki/De_Bruijn_index
  • chalst 5y ago
    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_science) https://en.wikipedia.org/wiki/Nominal_terms_(computer_scienc...
    • User23 5y ago
      Interesting! I hadn’t come across this. Thank you!
    • chriswarbo 5y ago
      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.365.2479&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36...