Why is the tracer in CMUCL 19a ignoring nested calls?
(defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
(trace fac)
response is:
0: (FAC 3)
0: FAC returned 6
6
expected response (available using CMUCL 18e, but not with 19a).
0: (FAC 3)
1: (FAC 2)
2: (FAC 1)
2: FAC returned 1
1: FAC returned 2
0: FAC returned 6
6
Thanks in advance.
Joerg Behrend wrote:
> Why is the tracer in CMUCL 19a ignoring nested calls?
>
> (defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
> (trace fac)
>
> response is:
>
> 0: (FAC 3)
> 0: FAC returned 6
> 6
>
>
> expected response (available using CMUCL 18e, but not with 19a).
> 0: (FAC 3)
> 1: (FAC 2)
> 2: (FAC 1)
> 2: FAC returned 1
> 1: FAC returned 2
> 0: FAC returned 6
> 6
What optimizations do you have DECLAIMed on CMUCL 19a? Try evaluating
(declaim (optimize (speed 0) (debug 3)))
and redefining FACT with these new optimizations. On SBCL 0.8.19.22,
(declaim (optimize (speed 0) (debug 3)))
(defun fact (n) (if (> n 1) (* n (fac (1- n))) 1))
outputs each call, but
(declaim (optimize (speed 3) (debug 0)))
(defun fact (n) (if (> n 1) (* n (fac (1- n))) 1))
only outputs the call with n=3.
-- MJF
···@math.uni-koeln.de (Joerg Behrend) writes:
> Why is the tracer in CMUCL 19a ignoring nested calls?
>
> (defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
> (trace fac)
>
> response is:
>
> 0: (FAC 3)
> 0: FAC returned 6
> 6
Presumably because it's optimizing away the recursion. With
appropriate NOTINLINE and DEBUG declarations you can probably get it
to stop doing that.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
+ Peter Seibel <·····@javamonkey.com>:
| ···@math.uni-koeln.de (Joerg Behrend) writes:
|
| > Why is the tracer in CMUCL 19a ignoring nested calls?
| >
| > (defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
| > (trace fac)
| >
| > response is:
| >
| > 0: (FAC 3)
| > 0: FAC returned 6
| > 6
|
| Presumably because it's optimizing away the recursion. With
| appropriate NOTINLINE and DEBUG declarations you can probably get it
| to stop doing that.
Doesn't look like that helps. And if you insert an error at the
bottom of the recursion, the backtrace shows all the calls, so no
optimizing away or inlining has (apparently) taken place.
Maybe this question is better asked on the cmucl-help mailing list.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
In article <···············@shuttle.math.ntnu.no>,
Harald Hanche-Olsen <······@math.ntnu.no> wrote:
> + Peter Seibel <·····@javamonkey.com>:
>
> | ···@math.uni-koeln.de (Joerg Behrend) writes:
> |
> | > Why is the tracer in CMUCL 19a ignoring nested calls?
> | >
> | > (defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
> | > (trace fac)
> | >
> | > response is:
> | >
> | > 0: (FAC 3)
> | > 0: FAC returned 6
> | > 6
> |
> | Presumably because it's optimizing away the recursion. With
> | appropriate NOTINLINE and DEBUG declarations you can probably get it
> | to stop doing that.
>
> Doesn't look like that helps. And if you insert an error at the
> bottom of the recursion, the backtrace shows all the calls, so no
> optimizing away or inlining has (apparently) taken place.
CMUCL probably optimizes self-recursion, by not going through the
symbol's function cell. But the NOTINLINE declaration is supposed to
disable this type of optimization.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
On Sat, 12 Feb 2005 22:23:38 -0500, Barry Margolin <······@alum.mit.edu>
wrote:
> In article <···············@shuttle.math.ntnu.no>,
> Harald Hanche-Olsen <······@math.ntnu.no> wrote:
>
>> + Peter Seibel <·····@javamonkey.com>:
>>
>> | ···@math.uni-koeln.de (Joerg Behrend) writes:
>> |
>> | > Why is the tracer in CMUCL 19a ignoring nested calls?
>> | >
>> | > (defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
>> | > (trace fac)
>> | >
>> | > response is:
>> | >
>> | > 0: (FAC 3)
>> | > 0: FAC returned 6
>> | > 6
>> |
>> | Presumably because it's optimizing away the recursion. With
>> | appropriate NOTINLINE and DEBUG declarations you can probably get it
>> | to stop doing that.
>>
>> Doesn't look like that helps. And if you insert an error at the
>> bottom of the recursion, the backtrace shows all the calls, so no
>> optimizing away or inlining has (apparently) taken place.
>
> CMUCL probably optimizes self-recursion, by not going through the
> symbol's function cell. But the NOTINLINE declaration is supposed to
> disable this type of optimization.
>
funny.. tail optimation in LispWoks happens on the form
(defun fac (n)
(declare (optimize (speed 3) (debug 0)))
(labels ((fac-intern (n sum)
(if (> n 1)
(fac-intern (1- n) (* sum n))
sum)))
(fac-intern n 1)))
Which is equivalent of
(defun fac (n)
(loop with sum = 1
for i from n downto 1 do
(setf sum (* sum i))
finally return sum))
But I've never seen you stack optimation before.
Have I missed something?
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> + Peter Seibel <·····@javamonkey.com>:
>
> | ···@math.uni-koeln.de (Joerg Behrend) writes:
> |
> | > Why is the tracer in CMUCL 19a ignoring nested calls?
> | >
> | > (defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
> | > (trace fac)
> | >
> | > response is:
> | >
> | > 0: (FAC 3)
> | > 0: FAC returned 6
> | > 6
> |
> | Presumably because it's optimizing away the recursion. With
> | appropriate NOTINLINE and DEBUG declarations you can probably get it
> | to stop doing that.
>
> Doesn't look like that helps. And if you insert an error at the
> bottom of the recursion, the backtrace shows all the calls, so no
> optimizing away or inlining has (apparently) taken place.
And the trace still doesn't work?
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
+ Peter Seibel <·····@javamonkey.com>:
| > Doesn't look like that helps. And if you insert an error at the
| > bottom of the recursion, the backtrace shows all the calls, so no
| > optimizing away or inlining has (apparently) taken place.
|
| And the trace still doesn't work?
That's right. I usually run with slime. At first I though maybe
slime had installed its own function tracer, and that this was the
reason for the problem. So I tried it again, in plain cmucl 19a:
;;; COMMON-LISP-USER:
(declaim (notinline fac) (optimize (speed 0) (debug 3)))
nil
;;; COMMON-LISP-USER:
(defun fac (n) (if (> n 1) (* n (fac (1- n))) 1))
fac
;;; COMMON-LISP-USER:
(trace fac)
(fac)
;;; COMMON-LISP-USER:
(fac 3)
0: (fac 3)
0: fac returned 6
6
;;; COMMON-LISP-USER:
(defun fac (n) (if (> n 1) (* n (fac (1- n))) (error "Oops")))
fac
;;; COMMON-LISP-USER:
(fac 3)
0: (fac 3)
Error in function fac: Oops
[Condition of type simple-error]
Restarts:
0: [abort] Return to Top-Level.
Debug (type H for help)
(fac 1)
Source: (error "Oops")
0] :back
0: (fac 1)
1: (fac 1 1)[:external]
2: (fac 2)
3: (fac 1 2)[:external]
4: (fac 3)
5: (fac 1 3)[:external]
6: ("DEFINE-FWRAPPER TRACE-FWRAPPER" 3)
7: (interactive-eval (fac 3))
8: (lisp::%top-level)
9: ((labels lisp::restart-lisp
save-lisp))
0] q
;;; COMMON-LISP-USER:
There may be a hint in those :external entries, though I am not sure
what. Need to spend some more time delving into the documentation.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
From: Christophe Rhodes
Subject: Re: Function tracing in CMUCL
Date:
Message-ID: <sqmzu8n4pz.fsf@cam.ac.uk>
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> + Peter Seibel <·····@javamonkey.com>:
>
> | > Doesn't look like that helps. And if you insert an error at the
> | > bottom of the recursion, the backtrace shows all the calls, so no
> | > optimizing away or inlining has (apparently) taken place.
> |
> | And the trace still doesn't work?
>
> That's right. I usually run with slime. At first I though maybe
> slime had installed its own function tracer, and that this was the
> reason for the problem. So I tried it again, in plain cmucl 19a:
>
> 6: ("DEFINE-FWRAPPER TRACE-FWRAPPER" 3)
Here's the clue.
> There may be a hint in those :external entries, though I am not sure
> what. Need to spend some more time delving into the documentation.
I believe the default tracer in cmucl 19 is breakpoint-based, which
interacts with self recursion and tail call elimination. Try
(trace :encapsulate t foo)
and see if that helps.
Christophe
+ Christophe Rhodes <·····@cam.ac.uk>:
| I believe the default tracer in cmucl 19 is breakpoint-based, which
| interacts with self recursion and tail call elimination. Try
| (trace :encapsulate t foo)
| and see if that helps.
Nope, it didn't.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
>>>>> "Christophe" == Christophe Rhodes <·····@cam.ac.uk> writes:
Christophe> Harald Hanche-Olsen <······@math.ntnu.no> writes:
>> + Peter Seibel <·····@javamonkey.com>:
>>
>> | > Doesn't look like that helps. And if you insert an error at the
>> | > bottom of the recursion, the backtrace shows all the calls, so no
>> | > optimizing away or inlining has (apparently) taken place.
>> |
>> | And the trace still doesn't work?
>>
>> That's right. I usually run with slime. At first I though maybe
>> slime had installed its own function tracer, and that this was the
>> reason for the problem. So I tried it again, in plain cmucl 19a:
>>
>> 6: ("DEFINE-FWRAPPER TRACE-FWRAPPER" 3)
Christophe> Here's the clue.
>> There may be a hint in those :external entries, though I am not sure
>> what. Need to spend some more time delving into the documentation.
Christophe> I believe the default tracer in cmucl 19 is breakpoint-based, which
Christophe> interacts with self recursion and tail call elimination. Try
Christophe> (trace :encapsulate t foo)
Christophe> and see if that helps.
It's a known bug. I assume it's caused by cmucl 19a changing how
tracing is done, using the fwrapper stuff. I don't understand the
causes of this.
Ray
Jan Gregor <··········@NOSPAMquick.cz> wrote:
+---------------
| I tried all advices but none help. Does somebody have tested solution ?
+---------------
Oddly enough, a combination of compiling and rewriting (FAC arg)
as (FUNCALL 'FAC arg) seemed to do the trick, though neither one
alone did:
> (lisp-implementation-type)
"CMU Common Lisp"
> (lisp-implementation-version)
"19a"
> (defun fac (n)
(if (<= n 1)
1
(* n (funcall 'fac (1- n)))))
FAC
> (compile 'fac)
; Compiling LAMBDA (N):
; Compiling Top-Level Form:
FAC
NIL
NIL
> (trace fac)
(FAC)
> (fac 5)
0: (FAC 5)
1: (FAC 4)
2: (FAC 3)
3: (FAC 2)
4: (FAC 1)
4: FAC returned 1
3: FAC returned 2
2: FAC returned 6
1: FAC returned 24
0: FAC returned 120
120
>
But you don't want to have to rewrite everything all time, so
thankfully there's a better way. Look in the "CMUCL User's Manual",
Chapter 5 "Advanced Compiler Use and Efficiency Hints", section
5.6.1 "Self-Recursive Calls", and you'll find this little note:
Local call is used when a function defined by defun calls itself.
For example:
(defun fact (n)
(if (zerop n)
1
(* n (fact (1- n)))))
This use of local call speeds recursion, but can also complicate
debugging, since trace will only show the first call to fact,
and not the recursive calls. This is because the recursive calls
directly jump to the start of the function, and don't indirect
through the symbol-function. Self-recursive local call is inhibited
when the :block-compile argument to compile-file is nil (see section
5.7.3.)
And, indeed:
$ cat fac.lisp
(defun fac (n)
(if (<= n 1)
1
(* n (fac (1- n)))))
$ cmu
> (load "fac.lisp")
; Loading #p"/usr/u/rpw3/fac.lisp".
T
> (trace fac)
(FAC)
> (fac 5)
0: (FAC 5)
0: FAC returned 120
120
> (untrace)
> (compile-file "fac" :block-compile nil)
; Python version 1.1, VM version Intel x86 on 15 FEB 05 03:30:22 am.
; Compiling: /usr/u/rpw3/fac.lisp 15 FEB 05 03:21:00 am
; Converted FAC.
; Compiling DEFUN FAC:
; Byte Compiling Top-Level Form:
; fac.x86f written.
; Compilation finished in 0:00:00.
#p"/usr/u/rpw3/fac.x86f"
NIL
NIL
> (load *)
; Loading #p"/usr/u/rpw3/fac.x86f".
T
> (trace fac)
(FAC)
> (fac 5)
0: (FAC 5)
1: (FAC 4)
2: (FAC 3)
3: (FAC 2)
4: (FAC 1)
4: FAC returned 1
3: FAC returned 2
2: FAC returned 6
1: FAC returned 24
0: FAC returned 120
120
>
Hope that helps,
-Rob
p.s. Note that there is a significant performance penalty to turning
off block-compilation, though if it helps debugging...
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607