Search code examples
compiler-constructionclosureslisp

Understanding modeling of recursive closures in compilers

I'm given the description of two ways to model recursive closures for a lisp-like language. Assume I have the following code:

(letrec ((f (fun (l) … (map f l) …)))) …)


 For the closure corresponding to f I could:

  1. Treat f as a free variable, and put it in its own environment which leads to a cyclic closure.
  2. With flat closures, the environment is the closure, and can be reused directly.

I'm using the concept of flat closure that stores in its first cell a pointer to the function and in the rest the free variables. But I get confused with the second option because it seems to me that the first and the second call receive different parameters. How is it possible then that they get the same closure and there is no need to include the recursive call as a free variable to differentiate them?

Maybe you can explain how this is solved in future steps of a typical compiler?

Solution

  • Each invocation of f will create a new closure with a new value for l (assuming lexical scoping). The closure in the body of f generally won't contain f, but the parent will, so you'll end up doing a lookup up the call stack.

    I wrote a post going into this a bit more: http://cinigl.io/posts/nested-variable-scoping