From: Pascal J.B. <pj...@in...> - 2003-12-04 21:53:19
|
Sam Steingold writes: > > * Szymon <kh...@jc...> [2003-12-04 20:28:49 +0100]: > > > >> >> > Does clisp have tail recursion optimization to prevent stack overflows > >> >> > on deep recursions? > >> >> no. > > "no" ---> both interpreted & compiled code? > yes. > > >> > why ? > >> debuggability > > Thanks. > > > > Does compilation (in clisp) transform tail-recursion to loops? > > no. patches that optionally optimize tail calls (not necessarily > recursive) are welcome. > > > For example: before compilation I can execute tail-rec fuction ~3000 > > times (clisp -m2MB), after compile '... 30000+ (no time to test it > > longer). > > compiled code uses less stack. I'm sorry Sam but you're wrong. CLISP reduces tail-recursion in compiled code: [31]> (defun fact (n &optional (r 1)) (if (> n 1) (fact (1- n) (* r n)) r)) FACT [32]> (disassemble 'fact) Disassembly of function FACT (CONST 0) = 1 1 required argument 1 optional argument No rest parameter No keyword parameters 16 byte-code instructions: 0 L0 0 (JMPIFBOUNDP 1 L5) 3 (CONST 0) ; 1 4 (STORE 1) 5 L5 5 (LOAD&PUSH 2) 6 (CONST&PUSH 0) ; 1 7 (CALLSR&JMPIF 1 49 L14) ; > 11 (LOAD 1) 12 (SKIP&RET 3) 14 L14 14 (LOAD&DEC&PUSH 2) 16 (LOAD&PUSH 2) 17 (LOAD&PUSH 4) 18 (CALLSR&PUSH 2 56) ; * 21 (JMPTAIL 2 5 L0) <========================= HERE =================== #<COMPILED-CLOSURE FACT> [35]> (defun fact2 (n &optional (r 1)) (cond ((<= n 1) r) ((evenp n) (fact2 (- n 2) (* r n (1- n)))) (t (fact2 (1- n) (* r n))))) FACT2 [36]> (disassemble 'fact2) Disassembly of function FACT2 (CONST 0) = 1 (CONST 1) = -2 1 required argument 1 optional argument No rest parameter No keyword parameters 27 byte-code instructions: 0 L0 0 (JMPIFBOUNDP 1 L5) 3 (CONST 0) ; 1 4 (STORE 1) 5 L5 5 (LOAD&PUSH 2) 6 (CONST&PUSH 0) ; 1 7 (CALLSR&JMPIF 1 50 L26) ; <= 11 (LOAD&PUSH 2) 12 (CALLS2&JMPIF 148 L29) ; EVENP 15 (LOAD&DEC&PUSH 2) 17 (LOAD&PUSH 2) 18 (LOAD&PUSH 4) 19 (CALLSR&PUSH 2 56) ; * 22 (JMPTAIL 2 5 L0) <========================= HERE =================== 26 L26 26 (LOAD 1) 27 (SKIP&RET 3) 29 L29 29 (CONST&PUSH 1) ; -2 30 (LOAD&PUSH 3) 31 (CALLSR&PUSH 2 54) ; + 34 (LOAD&PUSH 2) 35 (LOAD&PUSH 4) 36 (LOAD&DEC&PUSH 5) 38 (CALLSR&PUSH 3 56) ; * 41 (JMPTAIL 2 5 L0) <========================= HERE =================== #<COMPILED-CLOSURE FACT2> Why do you think there is a JMPTAIL instruction in the virtual machine? -- __Pascal_Bourguignon__ http://www.informatimago.com/ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Living free in Alaska or in Siberia, a grizzli's life expectancy is 35 years, but no more than 8 years in captivity. http://www.theadvocates.org/ |