Re: Common Lisp vs. Scheme
>>>> "Karl" == Karl M Hegbloom
<karlheg(a)inetarena.com> writes:
Karl> (defun fact (n)
Karl> (labels ((fact-it (n acc)
Karl> (if (< n 2)
Karl> acc
Karl> (fact-it (- n 1) (* n acc)))))
Karl> (fact-it n 1)))
Karl> ... tells me that the interpreter does NOT do tail call elimination,
Karl> but the *compiler* does.
From byte-optimize.el:
;; Tail-recursion elimination is not really possible in Emacs Lisp.
;; Tail-recursion elimination is almost always impossible when all variables
;; have dynamic scope, but given that the "return" byteop requires the
;; binding stack to be empty (rather than emptying it itself), there can be
;; no truly tail-recursive Emacs Lisp functions that take any arguments or
;; make any bindings.
;;
;; Here is an example of an Emacs Lisp function which could safely be
;; byte-compiled tail-recursively:
;;
;; (defun tail-map (fn list)
;; (cond (list
;; (funcall fn (car list))
;; (tail-map fn (cdr list)))))
;;
;; However, if there was even a single let-binding around the COND,
;; it could not be byte-compiled, because there would be an "unbind"
;; byte-op between the final "call" and "return." Adding a
;; Bunbind_all byteop would fix this.
;;
;; (defun foo (x y z) ... (foo a b c))
;; ... (const foo) (varref a) (varref b) (varref c) (call 3) END: (return)
;; ... (varref a) (varbind x) (varref b) (varbind y) (varref c) (varbind z) (goto 0)
END: (unbind-all) (return)
;; ... (varref a) (varset x) (varref b) (varset y) (varref c) (varset z) (goto 0) END:
(return)
;;
;; this also can be considered tail recursion:
;;
;; ... (const foo) (varref a) (call 1) (goto X) ... X: (return)
;; could generalize this by doing the optimization
;; (goto X) ... X: (return) --> (return)
;;
;; But this doesn't solve all of the problems: although by doing tail-
;; recursion elimination in this way, the call-stack does not grow, the
;; binding-stack would grow with each recursive step, and would eventually
;; overflow. I don't believe there is any way around this without lexical
;; scope.
;;
;; Wouldn't it be nice if Emacs Lisp had lexical scope.
;;
;; Idea: the form (lexical-scope) in a file means that the file may be
;; compiled lexically. This proclamation is file-local. Then, within
;; that file, "let" would establish lexical bindings, and
"let-dynamic"
;; would do things the old way. (Or we could use CL "declare" forms.)
;; We'd have to notice defvars and defconsts, since those variables should
;; always be dynamic, and attempting to do a lexical binding of them
;; should simply do a dynamic binding instead.
;; But! We need to know about variables that were not necessarily defvarred
;; in the file being compiled (doing a boundp check isn't good enough.)
;; Fdefvar() would have to be modified to add something to the plist.
;;
;; A major disadvantage of this scheme is that the interpreter and compiler
;; would have different semantics for files compiled with (dynamic-scope).
;; Since this would be a file-local optimization, there would be no way to
;; modify the interpreter to obey this (unless the loader was hacked
;; in some grody way, but that's a really bad idea.)
;;
;; HA! RMS removed the following paragraph from his version of
;; byte-opt.el.
;;
;; Really the Right Thing is to make lexical scope the default across
;; the board, in the interpreter and compiler, and just FIX all of
;; the code that relies on dynamic scope of non-defvarred variables.