ORIGINAL: I am programming a functional compiler and found out about locally nameless representation (using de brujin indeces for bound variables and names for free variables). I just don't understand what the advantages of locally nameless are?
In uni we made an example language in kotlin with hashmaps as closures. In these hashmaps the variables were stored. In the end we integrated a lexer. I don't understand when locally nameless would even be nessecary, if you wouldnt even be able to get through the lexer when calling something like:
lambda (a) => lambda (a) => a + a
Am I missing something or misunderstanding something?
EDIT: I now understand what it's for and how and when variable capture with named variables happens. I am currently working on an interpreter in kotlin wich takes lambda input and uses locally nameless representation to avoid name capture. I am planning to implement it like this:
- TEXTINPUT -> Lexer (function definitions with parameters and lambdas)
- -> Parser (creates the AST of function definitions using de brujin indeces and leaves the parameters as named variables until the function is called)
- -> Beta reduction(substitute every bound variable and leave the named ones as is)
- -> function call (Evaluation)
What is your opinion on this sequence?