tail-recursion woes on acl 7.0

David Tolpin <[email protected]> Wed, 8 Feb 2006 02:13:36 +0400
Newsgroups gmane.lisp.allegro
Message-ID <[email protected]>
Hi,

I've tried my code with ACL 7.0 (I don't use ACL for development or  
production, but decided to try it just to make sure I remain  
compatible), and a function that is obviously tail-recursive is not  
optimized as such. An extremely simplified version of the function is

> (defun LINK-FLOW (flow)
>   (declare (optimize (speed 3)))
>   (let ((addresses (make-hash-table))
>         (fctls nil))
>     (labels ((COLLECT (wolf flow bubbles)
>                "recursive step through flow and exit"
>                (cond
>                  ((null wolf)
>                   t)
>                  (t
>                   (let ((item (pop wolf)))
>                         (case (floor item 13)
>                           (2
>                            (collect wolf (cons item flow) bubbles))
>                           (3
>                            (collect wolf flow (cons item bubbles)))
>                           (t
>                            (collect wolf (cons item flow)  
> bubbles))))))))
>       (collect flow nil nil))))
>
> (defun test-link-flow (n)
>   (let (flow)
>     (dotimes (i n)
>       (push i flow))
>     (link-flow flow)))

And when I compile and call it, I get

> CL-USER(3): (declaim (optimize (speed 3)))
> CL-USER(4): (progn (compile-file "test") (load "test"))
> ....
> CL-USER(5): (explain-compiler-settings)
> ;; COMPILER:COMPILE-FORMAT-STRINGS-SWITCH               T
> ;; COMPILER:DECLARED-FIXNUMS-REMAIN-FIXNUMS-SWITCH      NIL
> ;; COMPILER:GENERATE-INLINE-CALL-TESTS-SWITCH           T
> ;; COMPILER:GENERATE-INTERRUPT-CHECKS-SWITCH            T
> ;; COMPILER:INTERNAL-OPTIMIZE-SWITCH                    T
> ;; COMPILER:OPTIMIZE-FSLOT-VALUE-SWITCH                 T
> ;; COMPILER:PEEPHOLE-OPTIMIZE-SWITCH                    T
> ;; COMPILER:SAVE-ARGLIST-SWITCH                         T
> ;; COMPILER:SAVE-LOCAL-NAMES-SWITCH                     T
> ;; COMPILER:SAVE-LOCAL-SCOPES-SWITCH                    NIL
> ;; COMPILER:TAIL-CALL-NON-SELF-MERGE-SWITCH             NIL
> ;; COMPILER:TAIL-CALL-SELF-MERGE-SWITCH                 T
> ;; COMPILER:TRUST-DECLARATIONS-SWITCH                   T
> ;; COMPILER:TRUST-DYNAMIC-EXTENT-DECLARATIONS-SWITCH    T
> ;; COMPILER:VERIFY-ARGUMENT-COUNT-SWITCH                T
> ;; COMPILER:VERIFY-CAR-CDR-SWITCH                       NIL
> ;; COMPILER:VERIFY-NON-GENERIC-SWITCH                   NIL
> ;; COMPILER:VERIFY-SYMBOL-VALUE-IS-BOUND-SWITCH         NIL
> ...
> CL-USER(5): (test-link-flow 100000)
> Error: Stack overflow (signal 1000)
>   [condition type: SYNCHRONOUS-OPERATING-SYSTEM-SIGNAL]
>
> Restart actions (select using :continue):
> 0: continue computation
> 1: Return to Top Level (an "abort" restart).
> 2: Abort entirely from this (lisp) process.

And then the stack shows

> [1c] CL-USER(9): :bt
> Evaluation stack:
>
> (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT) <- (LABELS LINK-FLOW COLLECT) <-
>   (LABELS LINK-FLOW COLLECT)(LABELS LINK-FLOW COLLECT) <-  ...
>


What's wrong?

David