| blob | efb9d061b5cfcef77b1e916c1764979cc05c0b95 |
1 ;;; cconv.el --- Closure conversion for statically scoped Emacs lisp. -*- lexical-binding: nil -*-
3 ;; Copyright (C) 2011 Free Software Foundation, Inc.
5 ;; Author: Igor Kuzmin <kzuminig@iro.umontreal.ca>
6 ;; Maintainer: FSF
7 ;; Keywords: lisp
8 ;; Package: emacs
10 ;; This file is part of GNU Emacs.
12 ;; GNU Emacs is free software: you can redistribute it and/or modify
13 ;; it under the terms of the GNU General Public License as published by
14 ;; the Free Software Foundation, either version 3 of the License, or
15 ;; (at your option) any later version.
17 ;; GNU Emacs is distributed in the hope that it will be useful,
18 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
19 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 ;; GNU General Public License for more details.
22 ;; You should have received a copy of the GNU General Public License
23 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
25 ;;; Commentary:
27 ;; This takes a piece of Elisp code, and eliminates all free variables from
28 ;; lambda expressions. The user entry points are cconv-closure-convert and
29 ;; cconv-closure-convert-toplevel(for toplevel forms).
30 ;; All macros should be expanded beforehand.
31 ;;
32 ;; Here is a brief explanation how this code works.
33 ;; Firstly, we analyse the tree by calling cconv-analyse-form.
34 ;; This function finds all mutated variables, all functions that are suitable
35 ;; for lambda lifting and all variables captured by closure. It passes the tree
36 ;; once, returning a list of three lists.
37 ;;
38 ;; Then we calculate the intersection of first and third lists returned by
39 ;; cconv-analyse form to find all mutated variables that are captured by
40 ;; closure.
42 ;; Armed with this data, we call cconv-closure-convert-rec, that rewrites the
43 ;; tree recursivly, lifting lambdas where possible, building closures where it
44 ;; is needed and eliminating mutable variables used in closure.
45 ;;
46 ;; We do following replacements :
47 ;; (lambda (v1 ...) ... fv1 fv2 ...) => (lambda (v1 ... fv1 fv2 ) ... fv1 fv2 .)
48 ;; if the function is suitable for lambda lifting (if all calls are known)
49 ;;
50 ;; (lambda (v1 ...) ... fv ...) =>
51 ;; (curry (lambda (env v1 ...) ... env ...) env)
52 ;; if the function has only 1 free variable
53 ;;
54 ;; and finally
55 ;; (lambda (v1 ...) ... fv1 fv2 ...) =>
56 ;; (curry (lambda (env v1 ..) .. (aref env 0) (aref env 1) ..) (vector fv1 fv2))
57 ;; if the function has 2 or more free variables.
58 ;;
59 ;; If the function has no free variables, we don't do anything.
60 ;;
61 ;; If a variable is mutated (updated by setq), and it is used in a closure
62 ;; we wrap it's definition with list: (list val) and we also replace
63 ;; var => (car var) wherever this variable is used, and also
64 ;; (setq var value) => (setcar var value) where it is updated.
65 ;;
66 ;; If defun argument is closure mutable, we letbind it and wrap it's
67 ;; definition with list.
68 ;; (defun foo (... mutable-arg ...) ...) =>
69 ;; (defun foo (... m-arg ...) (let ((m-arg (list m-arg))) ...))
70 ;;
71 ;;; Code:
76 "Try to do lambda lifting if the number of arguments + free variables
85 "List of candidates for lambda lifting.
93 ;; byte-compile-bound-variables normally holds both the
94 ;; dynamic and lexical vars, but the bytecomp.el should
95 ;; only call us at the top-level so there shouldn't be
96 ;; any lexical vars in it here.
102 "Find all free variables of given form.
103 Arguments:
104 -- FORM is a piece of Elisp code after macroexpansion.
105 -- FVRS(optional) is a list of variables already found. Used for recursive tree
106 traversal
108 Returns a list of free variables."
109 ;; If a leaf in the tree is a symbol, but it is not a global variable, not a
110 ;; keyword, not 'nil or 't we consider this leaf as a variable.
111 ;; Free variables are the variables that are not declared above in this tree.
112 ;; For example free variables of (lambda (a1 a2 ..) body-forms) are
113 ;; free variables of body-forms excluding a1, a2 ..
114 ;; Free variables of (let ((v1 ..) (v2) ..)) body-forms) are
115 ;; free variables of body-forms excluding v1, v2 ...
116 ;; and so on.
118 ;; A list of free variables already found(FVRS) is passed in parameter
119 ;; to try to use cons or push where possible, and to minimize the usage
120 ;; of append.
122 ;; This function can return duplicates (because we use 'append instead
123 ;; of union of two sets - for performance reasons).
134 fvrs))
172 ;condition-case
182 ;; We call cconv-freevars only for functions(lambdas)
183 ;; defun, defconst, defvar are not allowed to be inside
184 ;; a function (lambda).
185 ;; FIXME: should be a byte-compile-report-error!
193 fvrs
196 ;;;###autoload
198 "Main entry point for closure conversion.
199 -- FORM is a piece of Elisp code after macroexpansion.
200 -- TOPLEVEL(optional) is a boolean variable, true if we are at the root of AST
202 Returns a form where all lambdas don't have any free variables."
208 ;; Analyse form - fill these variables with new information
210 ;; Calculate an intersection of cconv-mutated and cconv-captured
215 form ; the tree
219 '()
220 )))
229 res))
235 ;; This function actually rewrites the tree.
236 "Eliminates all free variables of all lambdas in given forms.
237 Arguments:
238 -- FORM is a piece of Elisp code after macroexpansion.
239 -- LMENVS is a list of environments used for lambda-lifting. Initially empty.
240 -- EMVRS is a list that contains mutated variables that are visible
241 within current environment.
242 -- ENVS is an environment(list of free variables) of current closure.
243 Initially empty.
244 -- FVRS is a list of variables to substitute in each context.
245 Initially empty.
247 Returns a form where all lambdas don't have any free variables."
248 ;; What's the difference between fvrs and envs?
249 ;; Suppose that we have the code
250 ;; (lambda (..) fvr (let ((fvr 1)) (+ fvr 1)))
251 ;; only the first occurrence of fvr should be replaced by
252 ;; (aref env ...).
253 ;; So initially envs and fvrs are the same thing, but when we descend to
254 ;; the 'let, we delete fvr from fvrs. Why we don't delete fvr from envs?
255 ;; Because in envs the order of variables is important. We use this list
256 ;; to find the number of a specific variable in the environment vector,
257 ;; so we never touch it(unless we enter to the other closure).
258 ;;(if (listp form) (print (car form)) form)
262 ; let and let* special forms
265 ;; next for variables needed for delayed push
266 ;; because we should process <value(s)>
267 ;; before we change any arguments
276 binder
281 ;; Check if var is a candidate for lambda lifting.
289 ; lambda lifting condition
291 ; do not lift
293 value emvrs fvrs envs lmenvs)
294 ; lift
299 elm2 emvrs nil envs lmenvs)
300 funcbodies-new))
304 ; push lifted function
310 ;; Check if it needs to be turned into a "ref-cell".
312 ;; Declared variable is mutated and captured.
315 value emvrs
316 fvrs envs lmenvs))
321 ;; Normal default case.
324 value emvrs fvrs envs lmenvs)))))
326 ;; this piece of code below letbinds free
327 ;; variables of a lambda lifted function
328 ;; if they are redefined in this let
329 ;; example:
330 ;; (let* ((fun (lambda (x) (+ x y))) (y 1)) (funcall fun 1))
331 ;; Here we can not pass y as parameter because it is
332 ;; redefined. We add a (closed-y y) declaration.
333 ;; We do that even if the function is not used inside
334 ;; this let(*). The reason why we ignore this case is
335 ;; that we can't "look forward" to see if the function
336 ;; is called there or not. To treat well this case we
337 ;; need to traverse the tree one more time to collect this
338 ;; data, and I think that it's not worth it.
359 ;; we push the element after redefined free variables
360 ;; are processes. this is important to avoid the bug
361 ;; when free variable and the function have the same
362 ;; name
383 ;; Here we update emvrs, fvrs and lmenvs lists
385 ; safely remove
389 ; safely remove
392 ; push new
399 ;; Here we do the same letbinding as for let* above
400 ;; to avoid situation when a free variable of a lambda lifted
401 ;; function got redefined.
425 ))))
430 elm emvrs fvrs envs lmenvs)
431 body-forms-new))
433 ;end of let let* forms
435 ; first element is lambda expression
441 elm emvrs fvrs envs lmenvs)
442 other-body-forms-new))
455 elm-2 emvrs fvrs envs lmenvs)
456 elm-new))
458 cond-forms-new))
477 ;; Here we form our environment vector.
478 ;; If outer closure contains all
479 ;; free variables of this function(and nothing else)
480 ;; then we use the same environment vector as for outer closure,
481 ;; i.e. we leave the environment vector unchanged
482 ;; otherwise we build a new environmet vector
502 ;; the difference between envs and fvrs is explained
503 ;; in comment in the beginning of the function
511 elm emvrs fvrs envs lmenvs)
512 body-forms-new))
519 ;if no freevars - do nothing
522 ; 1 free variable - do not build vector
527 ; >=2 free variables - build vector
535 ;defconst, defvar
541 elm emvrs fvrs envs lmenvs)
542 body-forms-new))
546 ;defun, defmacro
552 ; find mutable arguments
564 ;transform body-forms
571 emvrs fvrs envs lmenvs)
572 body-new)
577 elm emvrs fvrs envs lmenvs)
578 body-forms-new))
582 ; letbind mutable arguments
585 binders-new))
593 ;condition-case
598 emvrs fvrs envs lmenvs)))
605 emvrs fvrs envs lmenvs))
606 handlers-new))
612 :fun-body
614 emvrs fvrs envs lmenvs)))
617 `(,head
618 :fun-body
620 emvrs fvrs envs lmenvs)))
627 sym
643 ; funcall is not a special form
644 ; but we treat it separately
645 ; for the needs of lambda lifting
650 ;; All args (free variables and actual arguments)
651 ;; should be processed, because they can be fvrs
652 ;; (free variables of another closure)
656 fvrs envs lmenvs)
657 processed-fv))
661 elm emvrs fvrs envs lmenvs)
662 args-new))
665 fun emvrs fvrs envs lmenvs))
670 elm emvrs fvrs envs lmenvs)
671 cdr-new))
675 ; function-like forms are:
676 ; or, and, if, progn, prog1, prog2,
677 ; while, until
681 elm emvrs fvrs envs lmenvs)
682 body-forms-new))
694 ;replace form =>
695 ;(aref env #)
699 var))
702 form))))))
716 "Find mutated variables and variables captured by closure. Analyse
717 lambdas if they are suitable for lambda lifting.
718 -- FORM is a piece of Elisp code after macroexpansion.
719 -- ENV is a list of variables visible in current lexical environment.
720 Each entry has the form (VAR INCLOSURE BINDER PARENTFORM)
721 for let-bound vars and (VAR INCLOSURE PARENTFORM) for function arguments.
722 -- INCLOSURE is the nesting level within lambdas."
724 ; let special form
739 inclosure))
747 ;; If var is a function push it to lambda list.
753 ; defun special form
766 ;; If a local variable (member of env) is modified by setq then
767 ;; it is a mutated variable.
772 ;; Delete from candidate list for lambda lifting.
792 ;; FIXME: The bytecode for condition-case forces us to wrap the
793 ;; form and handlers in closures (for handlers, it's probably
794 ;; unavoidable, but not for the protected form).
802 ;; FIXME: The bytecode for catch forces us to wrap the body.
809 ;; FIXME: The bytecode for save-window-excursion and the lack of
810 ;; bytecode for track-mouse forces us to wrap the body.
821 ;; Here we ignore fun because funcall and apply are the only two
822 ;; functions where we can pass a candidate for lambda lifting as
823 ;; argument. So, if we see fun elsewhere, we'll delete it from
824 ;; lambda candidate list.
830 ;; If this funcall and the definition of fun are in
831 ;; different closures - we delete fun from candidate
832 ;; list, because it is too complicated to manage free
833 ;; variables in this case.
849 ;; Delete lambda if it is found here, since it escapes.
854 ;;; cconv.el ends here