3 ms·

Sure, you can do that. Besides the closure allocation cost you have to be careful if your Lisp supports setting variables directly: (define x 2) (defin

by jules 14y ago

Sure, you can do that. Besides the closure allocation cost you have to be careful if your Lisp supports setting variables directly: (define x 2) (define y (lambda (z) (+ x z)) (set! x 3) Now you want the `x` referenced inside the lambda to refer to the new value of `x`. So if closure creation copies bindings in the parent scope then you have to introduce an extra indirection for mutable variables. This is called "assignment conversion". (define x (make-ref 2)) (define y (lambda (z) (+ (read-ref x) z)) (set-ref! x 3) Note also that it is unnecessary to store the number of bindings in the environment, because this number is implied by the lambda associated with the closure.

DanWaterworth 14y ago
Awesome, that's exactly the answer I was hoping for. Is this a common way of compiling lisp or does it actually make things slower in the general case?
- jules 14y ago
  Both methods have pros and cons, and the most advanced implementations use a hybrid method. The copying method is probably the best to start with. It may make things slower in special circumstances, but in the common case it is faster because lambdas tend to have a small number of free variables. It is also way simpler, because linked environments have a tendency to retain garbage if you are not careful. For example: (let ((x 1) (y 2)) (lambda (z) (+ x z)) If you use linked closures naively then the closure will keep `y` in memory even though it's garbage. However, keep in mind that what you usually not think of as free variables are free variables. For example if you have this: (let ((y 4)) (map (lambda (x) (factorial (+ x y))) xs)) Then not only `y` but also `factorial` and `+` are free variables. With some work you can avoid storing those references in the closure. I believe that the state of the art is described in this paper: ftp://ftp.ecn.purdue.edu/qobi/99-105.pdf
  - DanWaterworth 14y ago
    All good points. I will surely read that paper, thanks for all your help.

by jules 14y ago

DanWaterworth 14y ago

Awesome, that's exactly the answer I was hoping for. Is this a common way of compiling lisp or does it actually make things slower in the general case?

jules 14y ago
Both methods have pros and cons, and the most advanced implementations use a hybrid method. The copying method is probably the best to start with. It may make things slower in special circumstances, but in the common case it is faster because lambdas tend to have a small number of free variables. It is also way simpler, because linked environments have a tendency to retain garbage if you are not careful. For example: (let ((x 1) (y 2)) (lambda (z) (+ x z)) If you use linked closures naively then the closure will keep `y` in memory even though it's garbage. However, keep in mind that what you usually not think of as free variables are free variables. For example if you have this: (let ((y 4)) (map (lambda (x) (factorial (+ x y))) xs)) Then not only `y` but also `factorial` and `+` are free variables. With some work you can avoid storing those references in the closure. I believe that the state of the art is described in this paper: ftp://ftp.ecn.purdue.edu/qobi/99-105.pdf
- DanWaterworth 14y ago
  All good points. I will surely read that paper, thanks for all your help.