Email Archive: sbcl-help (read-only)

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: DS - 2011-07-15 18:31 ``` On 13 Jul 2011, at 19:38, Teemu Likonen wrote: > See the following toy example. It is > recursive but, if I understand correctly, there is no tail-call. > > (defun sum (numbers) > (declare (optimize (speed 0) (debug 0))) > (if numbers > (+ (first numbers) (sum (rest numbers))) > 0)) That call to sum is not in a tail position, its result is passed to #'+. Tail-merging is not possible here. You should use an accumulator. (defun sum (numbers &optional (accum 0)) (if numbers (sum (rest numbers) (+ accum (first numbers))) accum)) Regards. -Daniel ```

[Sbcl-help] More question about SBCL regarding tail recursion Cheung, Matthew G <mgcheung@hr...>
 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Nikodemus Siivola - 2011-06-14 16:53 ```On 14 June 2011 19:38, Cheung, Matthew G wrote: > One thing that has never been clear to me was whether SBCL will by > default use tail recursion optimisations.  I wrote a general "repeated Tail-merging is done if (> SPACE DEBUG) or (> SPEED DEBUG) -- not by default. > This question is probably more general lisp, but is it considered a > better practice when writing a function using tail recursion to use a > local function to do the actual tail recursion?  Is it a bad idea to use Depends on the case, but if eg. floating point arguments are involved a local call may be more efficient. > an optional or keyword parameter to store the results of the > intermediate calculations?  In this case it seemed like it was a good Stylistically it's fine. >From micro-efficiency POV it is less than ideal. &OPTIONAL is pretty cheap, but unless the function is inlined &KEY incurs a runtime cost for keyword parsing. Cheers, -- nikodemus ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Jim Wise - 2011-06-14 18:30 Attachments: Message as HTML ```"Cheung, Matthew G" writes: > One thing that has never been clear to me was whether SBCL will by default > use tail recursion optimisations. I wrote a general "repeated squaring" > function that takes as it's arguments a "squaring" function a "multiply" > function, the base and the exponent and I wrote it tail recursively. This > was to be used for both modular exponentiation and point multiplication on > an elliptic curve. So can I assume SBCL will optimise by default? Nikodemus pointed out the combination of optimization vs. debug declarations you need to make TCO happen. Beyond that, TCO has behaved very well for me -- I have a largish hardware simulator (a (currently subset of a) simulator of Knuth's MIX) that I've used for testing, written entirely in CPS, and I've left it running a loop for a large number of iterations without seeing stack growth. -- Jim Wise jwise@... ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Faré - 2011-06-14 21:31 ```On 14 June 2011 14:30, Jim Wise wrote: > "Cheung, Matthew G" writes: > >> One thing that has never been clear to me was whether SBCL will by default >> use tail recursion optimisations.  I wrote a general "repeated squaring" >> function that takes as it's arguments a "squaring" function a "multiply" >> function, the base and the exponent and I wrote it tail recursively.  This >> was to be used for both modular exponentiation and point multiplication on >> an elliptic curve.  So can I assume SBCL will optimise by default? > > Nikodemus pointed out the combination of optimization vs. debug > declarations you need to make TCO happen. > > Beyond that, TCO has behaved very well for me -- I have a largish > hardware simulator (a (currently subset of a) simulator of Knuth's MIX) > that I've used for testing, written entirely in CPS, and I've left it > running a loop for a large number of iterations without seeing stack > growth. > jsnell once gave me this recipe to ensure that SBCL will do TCO is: (declaim (optimize #+sbcl (sb-c::merge-tail-calls 3) #+sbcl (sb-c::insert-debug-catch 0)) More generally, I've created a library ptc on common-lisp.net to let people semi-portably declare their code to require proper tail-calls. git clone http://common-lisp.net/~frideau/git/ptc.git Patches welcome. —♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• http://fare.tunes.org I'd rather write programs that write programs than write programs — Dick Sites ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Teemu Likonen - 2011-07-13 17:38 ```* 2011-06-14T19:53:36+03:00 * Nikodemus Siivola wrote: > On 14 June 2011 19:38, Cheung, Matthew G wrote: >> One thing that has never been clear to me was whether SBCL will by >> default use tail recursion optimisations.  I wrote a general >> "repeated > > Tail-merging is done if (> SPACE DEBUG) or (> SPEED DEBUG) -- not by > default. Is the TRACE output a reliable way to tell whether optimization on recursive calls has occurred? See the following toy example. It is recursive but, if I understand correctly, there is no tail-call. Without much speed optimization: (defun sum (numbers) (declare (optimize (speed 0) (debug 0))) (if numbers (+ (first numbers) (sum (rest numbers))) 0)) CL-USER> (trace sum) (SUM) CL-USER> (sum '(1 2 3 4)) 0: (SUM (1 2 3 4)) 1: (SUM (2 3 4)) 2: (SUM (3 4)) 3: (SUM (4)) 4: (SUM NIL) 4: SUM returned 0 3: SUM returned 4 2: SUM returned 7 1: SUM returned 9 0: SUM returned 10 10 Now the same thing with more speed: (defun sum (numbers) (declare (optimize (speed 3) (debug 0))) (if numbers (+ (first numbers) (sum (rest numbers))) 0)) CL-USER> (sum '(1 2 3 4)) 0: (SUM (1 2 3 4)) 0: SUM returned 10 10 It seems that the was only one call to SUM so either there is some optimization or TRACE couldn't track what's really happening. ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Nikodemus Siivola - 2011-07-13 17:55 ```On 13 July 2011 20:38, Teemu Likonen wrote: > Is the TRACE output a reliable way to tell whether optimization on > recursive calls has occurred? See the following toy example. It is > recursive but, if I understand correctly, there is no tail-call. Nope. Tail-merging has no effect on whether TRACE shows the call or not. What you're seeing is the effect of self-calls being optimized to local calls, instead of going through the FDEFINITION -- which TRACE has instrumented. Cheers, -- nikodemus ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Teemu Likonen - 2011-07-13 18:13 ```* 2011-07-13T20:55:29+03:00 * Nikodemus Siivola wrote: > Tail-merging has no effect on whether TRACE shows the call or not. > What you're seeing is the effect of self-calls being optimized to > local calls, instead of going through the FDEFINITION -- which TRACE > has instrumented. Thanks. I suspected something like that. TRACE couldn't see those local calls. ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Gabriel Dos Reis - 2011-07-13 19:25 ```On Wed, Jul 13, 2011 at 12:55 PM, Nikodemus Siivola wrote: > Tail-merging has no effect on whether TRACE shows the call or not. > What you're seeing is the effect of self-calls being optimized to > local calls, instead of going through the FDEFINITION -- which TRACE > has instrumented. Does this mean SBCL functions defined with FLET or LABELS? Or, from SBCL point of view, there is no effect, it is just stylistic? -- Gaby ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Nikodemus Siivola - 2011-07-14 13:22 ```On 13 July 2011 22:25, Gabriel Dos Reis wrote: >> Tail-merging has no effect on whether TRACE shows the call or not. >> What you're seeing is the effect of self-calls being optimized to >> local calls, instead of going through the FDEFINITION -- which TRACE >> has instrumented. > > Does this mean SBCL functions defined with FLET or LABELS? > Or, from SBCL point of view, there is no effect, it is just > stylistic? I'm not sure I understand the question, but I'll try to answer anyways. If SPEED or SPACE is > DEBUG, and FOO calls itself (tail or non-tail call doesn't come into it) (defun foo (...) ...) is compiled approximately as if you had written (defun foo (...) (labels ((foo (...) ...)) (foo ...))) instead. When you do (TRACE FOO) something along the lines of (let ((orig (fdefinition 'foo))) (setf (fdefinition 'foo) (lambda (&rest args) (trace-call 'foo args) (let ((values (multiple-value-list (apply orig args)))) (trace-return 'foo values) (values-list values))))) takes place. Put these two together, and it should be fairly obvious why the optimization in question makes trace miss the self-calls. Cheers, -- nikodemus ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: DS - 2011-07-15 18:31 ```On 13 Jul 2011, at 19:38, Teemu Likonen wrote: > See the following toy example. It is > recursive but, if I understand correctly, there is no tail-call. > > (defun sum (numbers) > (declare (optimize (speed 0) (debug 0))) > (if numbers > (+ (first numbers) (sum (rest numbers))) > 0)) That call to sum is not in a tail position, its result is passed to #'+. Tail-merging is not possible here. You should use an accumulator. (defun sum (numbers &optional (accum 0)) (if numbers (sum (rest numbers) (+ accum (first numbers))) accum)) Regards. -Daniel ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Teemu Likonen - 2011-07-15 18:52 ```* 2011-07-15T20:02:50+02:00 * DS wrote: > That call to sum is not in a tail position, its result is passed to > #'+. Tail-merging is not possible here. I know. My point was that TRACE output for that function shows a single call to the function and then I asked if there was some optimization done even for this kind non-tail-call recursion. The answer was "no". The call was just short-circuited so that TRACE couldn't see the calls. > You should use an accumulator. That's what I do when I want one. :-) ```

 Re: [Sbcl-help] More question about SBCL regarding tail recursion From: Gabriel Dos Reis - 2011-07-19 07:49 ```On Thu, Jul 14, 2011 at 8:22 AM, Nikodemus Siivola wrote: > On 13 July 2011 22:25, Gabriel Dos Reis wrote: > >>> Tail-merging has no effect on whether TRACE shows the call or not. >>> What you're seeing is the effect of self-calls being optimized to >>> local calls, instead of going through the FDEFINITION -- which TRACE >>> has instrumented. >> >> Does this mean SBCL functions defined with FLET or LABELS? >> Or, from SBCL point of view, there is no effect, it is just >> stylistic? > > I'm not sure I understand the question, but I'll try to answer anyways. > > If SPEED or SPACE is > DEBUG, and FOO calls itself (tail or non-tail > call doesn't come into it) > > (defun foo (...) >  ...) > > is compiled approximately as if you had written > > (defun foo (...) >  (labels ((foo (...) >              ...)) >     (foo ...))) > > instead. > > When you do > >  (TRACE FOO) > > something along the lines of > >  (let ((orig (fdefinition 'foo))) >   (setf (fdefinition 'foo) (lambda (&rest args) >                              (trace-call 'foo args) >                              (let ((values (multiple-value-list >                                              (apply orig args)))) >                                (trace-return 'foo values) >                                (values-list values))))) > > takes place. That answers the question. Thanks. ```