I've seen this on c.l.l. sometime ago: http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/6d41174f80d5427b/
It's an interesting macro, since TCO is supported in most major CL implementations, it's less useful. >>6
Unlike Scheme, CL has many iterative constructs, and they have no need to force what optimizations compilers must make. TCO is a good optimization, and is supported by most real CL implementations, which means that in practice you can write tail-recursive code as much as you'd like.
>>9
Of course not, but iteration is usually defined in a tail-recursive manner in Scheme, which is why having TCO is mandatory there, while having TCO in CL is regarded as optional, but most implementations do it anyway.
Name:
Anonymous2010-02-01 10:01
>>8
It would mean you would have to understand what they meant by "in the tail position." In the loop macro, which is in the tail position? I know how to find out with scheme: I scan a short document.
>>11
LOOP, like all other macros, eventually expand to s-expressions which contain nothing but function calls and special operators. LOOP is nothing more than a simple domain-specific language for purposes of iteration which is compiled to CL. Doing TCO in CL isn't that terribly hard, eventually everything gets compiled down to simple special forms, and then possibly to some even more low-level IR language, where one can perform TCO not that much differently from how you can do it in Scheme, however there are certain language features that can lead to difficulty in performing such optimizations, such as CL's optional dynamic scope (you can declare variables as being ``special'', either locally, or globally. If a name is special within some environment(if local, then there's a corresponding declaration, if global, then the name was proclaimed special(within some package)), then the dynamic binding of that name is accessed). This usually requires a stack to be used to implement dynamic binding, however there are some tricks that allow TCO to be performed in some cases. I've just tested if TCO was performed by a certain decent CL implementation, in one case of dynamic rebinding in a tail-recursive function, and it was not(even at [m](optimize (debug 0) (safety 0) (speed 3))[m/] settings), however in the case of lexical scope, it perfomed quite nicely.
Meh, I didn't mean to say S-Expressions as a textual representation, but as in-memory conses,symbols and other lisp objects, however these objects are almost always printable one way or another, even so-called unprintable objects can be inspected at runtime.
>>12 LOOP, like all other macros, eventually expand to s-expressions which contain nothing but function calls and special operators.
Of course. What I mean is, I know what Scheme implementations are required to consider as in a tail position. (See, e.g., R5RS pages 7 and 8.)
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.
>>14
Oh, so you're saying that in the case of looping constructs which execute some termination/final code, it might not be clear if that's really the final code they'll execute? This would mean the user can't be sure his code is really tail-recursive, even when it appears to be. While, it would be possible to find that out by just doing a macroexpand, the standard doesn't require specific macroexpansions, so behaviours could vary per implementation. In practice, looping constructs in CL almost always use TAGBODY and GO, but I've written tail-recursive implementations of some operators as an exercise when learning CL, and the compiler did do TCO properly, however as I've shown in >>15, TCO may not be always possible in the presence of special variables. While I know Scheme defines (as you've shown) actual positions which must be the tail positions, my understanding of the term is that, a tail-call is a call which is the last call in a function, and its value will be what will be returned, thus the call can be converted to a jump safely. Such an interpretation allows for a general idea of what TCO is supposed to do, however I suppose if you specify the tail positions in a standard, programmers can write tail-recursive programs reliably.
Name:
Anonymous2010-02-01 16:45
>>15 ;;; 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.
If the previous binding is still needed, the new dynamic-let is not in tail position of the previous dynamic-let body. Problem solved, implementation left as an exercise for the reader.