[Openmcl-devel] destructuring-bind breaks tail-recursion optimization

[Gary Byers]

? (pprint (macroexpand-1 '(destructuring-bind (x) (list n)
                             (if (< x 0) t (foo (1- x))))))

;;; I'll wait while anyone interested in this does so.   What ?
;;; You want me to do this for you ?  How will you learn to do
;;; this for yourself if I do it for you ?
;;; Everyone ready ?  Good.

Let's start with the assertion that some primitive operations
on an object of type CCL::DESTRUCTURE-STATE can be more concise
than the equivalent inline expansion and may make it easier to
generate higher-level error messages.  (The inline expansion
would involve lots of CARs and CDRs and NULL checks and error
signaling of various flavors of PROGRAM-ERROR.)

There are various tradeoffs involved:

1) whether it is "better" (by some metrics) to generate this concise
    sort of expansion for various flavors of destructuring
    (including DESTRUCTURING-BIND)
2) if one concludes that it's better to generate a more concise
    expansion (by keeping state info in one of these objects), it's
    "better" to stack-cons the object than it would be to heap-cons
    it.  (This kind of tradeoff involves the "howling factor" : would
    people be more likely to howl if DESTRUCTURING-BIND consed unnecessarily
    or if it did stack allocation that interfered with tail-recursion
    optimization ?)

One can make different decisions than those that we/I made (and they'd
be "defensible", too!), but the decisions that were made were made
intentionally and interfere with tail-recursion optimization.

In general, DYNAMIC-EXTENT on a variable binding means that the lifetime
of the initial value of the variable is no greater than the scope of the
variable.  In some cases, the lifetime of the value could be made shorter
than that; in the expansion of DESTRUCTURING-BIND, the stack-consed
object can't be referenced after the lambda list has been processed and
isn't aliased in any way, so it -could- be popped off the stack earlier
(and the function call in the body would then be tail-recursive.)  Without
doing this kind of analysis, the compiler has to assume that the called
function -could- somehow reference the stack-allocated object, and can't
safely deallocate the object until that function returns.

On Tue, 9 Feb 2010, Ron Garret wrote:

> SLSIA.  Is this intentional, or is it a bug?
>
> ? (defun baz (n)
>  (let ((x n))
>    (if (< x 0) t (baz (1- x)))))
> BAZ
> ? (defun foo (n)
>  (destructuring-bind (x) (list n)
>    (if (< x 0) t (foo (1- x)))))
> FOO
> ? (baz 100000)
> T
> ? (foo 100000)
>> Error: Stack overflow on temp stack.
>> While executing: FOO, in process Listener(7).
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>