Initially, I plan to concentrate my efforts on one such optimization called Lambda Lifting. Lambda lifting is a technique for transforming a functional program with local function definitions, possibly with free variables in function definitions, into a program consisting only of global function definitions which can be used as rewrite rules. [3]
The idea is to eliminate free variables by making them arguments to the procedure. Eliminating free variables from the procedure not only reduces the overhead of using higher order procedures and the closure allocation cost of packaging up code and environment but it also cuts down on the cost of dereferencing those free variables.
For example:
(let ((x 3))
(let ((f (lambda () x)))
(f)))
after lambda-lifting will be transformed into :
(let ((x 3))
(let ((f (lambda (x') x')))
(f x')))
As long as the free variable is not assigned or its respective procedure does not escape, it is always beneficial to lambda-lift, as the cost of packaging will remain the same - whether it is one closure or one free variable.
For example:
(let ((x 3))
(let ((f (lambda () x)))
(let ((g f))
(g))))
Here, f has only one free variable and would have been an ideal candidate for lambda lifting if it did not escape. f is said to escape because it is not possible to clearly find all of f's call-sites. Therefore, in order to lambda-lift f correctly it will become necessary to remember information about f's new argument and propagate it throughout the program.
Moreover, to produce correct code at all times one has to keep in mind that a free variable may also be settable. A lambda expression in which any of the free variables is settable, should not be lifted.
For example:
(let ((x 3))
(let ((f (lambda (y) (+ x y)))
(g (lambda (v) (set! x v))))
(begin
(g 4)
(f 2))))
after lambda-lifting, will be transformed to :
(let ((x 3))
(let ((f (lambda (y x') (+ x' y)))
(g (lambda (v x'') (set! x'' v))))
(begin
(g 4 x)
(f 2 x))))
Lifting x in procedure f or procedure g will result in incorrect output. The above example which returned the value 6 will return 5 after f and g have been lifted.
Besides abiding by the restrictions it is also essential to look at some heuristics if we want lambda-lifting to be not only successful but also a profitable endeavor. Although lambda-lifting of a procedure is most profitable when there are many references to free variables, it is not wise to lambda-lift a procedure which is called in a nontail position and has more than one free variable.
For example:
(let ((x 3)(y 4))
(let ((f (lambda () (* x y))))
(cons 2 (f))))
In the above case, the cost of saving and restoring registers proves to be detrimental to the whole effort.
Most of the information for checking the above mentioned restrictions can be obtained by syntactically analyzing the source program. And, if we treat the lambda-lifting as an 'all-or-none' procedure, then even the heuristics described above can easily be determined statically from the given source code. However, it is often helpful to find a compromise between lifting all the free variables and not lifting any of them. It would be ideal to be able to find the optimal combination of free variables to lift for better overall performance. Developing heuristics for such a purpose will not be as direct and will depend on more dynamic features of the program accessible only at run-time like whether these free variables were dereferenced many times, once or never.