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