(defmacro tailprog (let-bindings pseudo-funcs &rest forms)
(let (argtags-forms macrolet-elems)
(dolist (pfunc pseudo-funcs)
(destructuring-bind (name vars &rest forms) pfunc
(push `(label ,name ,@vars) argtags-forms)
(push `(return (progn ,@forms)) argtags-forms)
(push `(,name (&rest args) `(goto ,',name ,@args)) macrolet-elems)))
`(macrolet (,.(nreverse macrolet-elems))
(let ,let-bindings
(argtags nil
(return (progn ,@forms))
,.(nreverse argtags-forms))))))
ALL YOUR TAIL RECURSION R BELONG TO US
Name:
122010-02-01 15:25
More detailed explanation of why TCO and optional dynamic scope are conflicting, dynamic binding is usually implemented by such variables being represented using a stack, when you bind a variable, you push the new value to the stack, and then at the end of the block which did the binding, pop the stack. Accessing the value of such a special variable is obviously done by peeking at the top of the variable's value stack. Things get slightly more hairy when multithreading is involved, there are truly global bindings and per-thread bindings in the local thread storage. Now, why does this pose a problem to TCO? You have to pop the value once the binding goes out of scope, which means that there would never be a tail-call, even if it looks like a tail-call. TCO can still be performed in the case you can prove previous bindings won't be needed. Such proving is usually trivial in the case of loops, but may not be trivial in real cases such as mutual tail-recursion.
Here's some code to better explain things:
;;; this proclaims *SOME-SPECIAL* as special
;;; and assigns the symbol NOT-BOUND-FOR-NOW
;;; to this symbol's global value, if the
;;; symbol *SOME-SPECIAL* doesn't exist yet.
(defvar *some-special* 'not-bound-for-now)
(labels ((fn (x)
;; rebinds *some-special* to 1+ it's value
(let ((*some-special* (1+ *some-special*)))
(if (zerop x)
*some-special*
(fn (1- x)))))) ; tail-recursive, but not really
(list
(let ((*some-special* 0))
(fn 100))
*some-special*)) ;=> (101 NOT-BOUND-FOR-NOW)
;;; now let's translate that code into one which
;;; emulates specials clumsily:
(let ((pseudo-special '(not-bound-for-now)))
(labels ((fn (x)
(push (1+ (first pseudo-special)) pseudo-special) ; "binding"
(prog1
(if (zerop x)
(first pseudo-special) ; accessing the value
(fn (1- x)))
(pop pseudo-special)))) ; pop the binding
(list
(progn
(push 0 pseudo-special)
;; more correctly, this should be an UNWIND-PROTECT
;; but PROG1 works for illustrative purposes
(prog1
(fn 100)
(pop pseudo-special)))
(first pseudo-special)))) ;=> (101 NOT-BOUND-FOR-NOW)
;;; As you can see, it's no longer tail-recursive, however
;;; in this specific case, we're dealing with a loop,
;;; which means that we can prove that the previous dynamic
;;; bindings are not used within the loop, so it could
;;; be optimized to:
;;; However, such optimizations can only be performed
;;; if one can prove that certain previous bindings
;;; will not be needed, which is not always the case.
;;; Note that if you actually wanted to emulate special
;;; bindings for some reason in practice, you would use
;;; a symbol-macro for the actual name, so it would point
;;; to the the top of the stack, allowing both accessing
;;; and assignment. Dynamic binding could be done using
;;; a normal macro, for example name it DYNAMIC-LET
;;; which expands to an UNWIND-PROTECT whose protected forms
;;; are a PROGN which first pushes the new binding onto
;;; the var and then executes the actual body of code,
;;; the actual UNWIND-PROTECT cleanup code would pop the
;;; binding and then return the value that PROGN
;;; Obviously, defining new dynamic variables could be
;;; done using a macro which would expand into said
;;; symbol macro. Such an implementation would behave
;;; like real dynamic variables as they are in CL, but
;;; it does miss various subtelties, however I've already
;;; gone in way too much detail about this topic.