I never cared for the function trace. I just find it confusing and
almost never tells me clearly how the function i'm tracing is really
working inside. See for example this:
(defun fibonacci (n)
(if (<= n 1) n
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
(trace fibonacci) ;;ecl or sbcl
(fibonacci 7)
With the output of trace, I'm no wiser how this recursion worked, if
anything I'm more confused. Is there anything clearer? (mind you, I am
not excluding the possibility that I'm not as bright as some of you
who *do* find the trace function very helpful and clear).
On 14 abr, 17:21, Francogrex <······@grex.org> wrote:
> I never cared for the function trace. I just find it confusing and
> almost never tells me clearly how the function i'm tracing is really
> working inside. See for example this:
> (defun fibonacci (n)
> (if (<= n 1) n
> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
>
> (trace fibonacci) ;;ecl or sbcl
>
> (fibonacci 7)
>
> With the output of trace, I'm no wiser how this recursion worked, if
> anything I'm more confused. Is there anything clearer? (mind you, I am
> not excluding the possibility that I'm not as bright as some of you
> who *do* find the trace function very helpful and clear).
There is nothing special in this function. It just computes the nth
element of the Fibonacci's famous sequence using its definition.
F_0 = F_1 = 1
F_n = F_(n-1) + F(n-2) for n>=2
So, the sequence is 1, 1, 2, 3, 5, 8, 13, ...
By the way, I don't think it is possible to simplify "trace" for this
case. The problem is that this function uses double recursion. To
follow the trace output correctly you need to follow the numbers to
the left.
For instance, to see where this (fibonacci 3) returns:
...
4: (fibonacci 3)
5: (fibonacci 2)
6: (fibonacci 1)
6: fibonacci returned 1
...
You need to search the next line starting with the number 4, here:
4: fibonacci returned 2
All lines starting with a 5 between these two lines are called
directly for calculating the value of (fibonacci 3); lines starting
with a 6 are the functions called directly by the functions called in
the 5th level; and so on.
Francogrex <······@grex.org> writes:
> I never cared for the function trace. I just find it confusing and
> almost never tells me clearly how the function i'm tracing is really
> working inside. See for example this:
> (defun fibonacci (n)
> (if (<= n 1) n
> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
>
> (trace fibonacci) ;;ecl or sbcl
>
> (fibonacci 7)
>
> With the output of trace, I'm no wiser how this recursion worked, if
> anything I'm more confused.
Well, you have to interpret the output of trace with the help of the
function definition and a knowledge of the argument evaluation rules of
Lisp. The output alone won't tell you much.
CL-USER> (fibonacci 7)
0[1]: (FIBONACCI 7)
1[1]: (FIBONACCI 6)
2[1]: (FIBONACCI 5)
3[1]: (FIBONACCI 4)
4[1]: (FIBONACCI 3)
5[1]: (FIBONACCI 2)
6[1]: (FIBONACCI 1)
6[1]: returned 1
6[1]: (FIBONACCI 0)
6[1]: returned 0
5[1]: returned 1
5[1]: (FIBONACCI 1)
5[1]: returned 1
4[1]: returned 2
4[1]: (FIBONACCI 2)
5[1]: (FIBONACCI 1)
5[1]: returned 1
5[1]: (FIBONACCI 0)
5[1]: returned 0
4[1]: returned 1
From this, it seems reasonably clear to me what is happening. After the
top level call, you end up descending via the first argument to the
addition step until you get to level 6, where you have two successive
recursive calls from the same level which are handled by the first of
the IF clauses.
At level 4, our second call goes again to (FIBONACCI 2) which we can
actually skip the details of because we know how it goes already.
> Is there anything clearer? (mind you, I am
> not excluding the possibility that I'm not as bright as some of you
> who *do* find the trace function very helpful and clear).
Well, that's the question for you, really.
What would you like to see that would be clearer? What would the ideal
presentation look like?
And then we can think about how one would go about providing that for an
arbitrary function. Of if that is too tough, at least provide some
guidance on how to manually insert trace statements that would do what
you need.
--
Thomas A. Russ, USC/Information Sciences Institute
On Apr 14, 11:31 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> What would you like to see that would be clearer? What would the ideal
> presentation look like?
Maybe it's too simplistic or optimistic but would have liked to see
something such as=
0+1=1
1+1=2
1+2=3
2+3=5
3+5=8
... etc
On Apr 15, 3:35 pm, Francogrex <······@grex.org> wrote:
> On Apr 14, 11:31 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
>
> > What would you like to see that would be clearer? What would the ideal
> > presentation look like?
>
> Maybe it's too simplistic or optimistic but would have liked to see
> something such as=
> 0+1=1
> 1+1=2
> 1+2=3
> 2+3=5
> 3+5=8
> ... etc
(defun fibonacci (n)
(loop
for x from 0 to 1 do
(format t
"the ~:r fibonacci number by definition is ~a ~%"
x x))
(if (< n 3) (return-from fibonacci)
(loop for i from 2 to n
for 2back = 0 then last
for last = 1 then lastemp
for lastemp = last then (+ 2back lastemp)
do
(format t
"the ~:r fibonacci number is ~a + ~a = ~a~%"
i 2back last (+ 2back last)))))
:^)
On Apr 16, 1:26 am, Raffael Cavallaro <················@gmail.com>
wrote:
> (defun fibonacci (n)
> (loop
> for x from 0 to 1 do
> (format t
> "the ~:r fibonacci number by definition is ~a ~%"
> x x))
> (if (< n 3) (return-from fibonacci)
> (loop for i from 2 to n
> for 2back = 0 then last
> for last = 1 then lastemp
> for lastemp = last then (+ 2back lastemp)
> do
> (format t
> "the ~:r fibonacci number is ~a + ~a = ~a~%"
> i 2back last (+ 2back last)))))
>
> :^)
That's beautiful; thanks.
>>>>> "Francogrex" == Francogrex <······@grex.org> writes:
Francogrex> On Apr 14, 11:31�pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
>> What would you like to see that would be clearer? �What would the ideal
>> presentation look like?
Francogrex> Maybe it's too simplistic or optimistic but would have liked to see
Francogrex> something such as=
Francogrex> 0+1=1
Francogrex> 1+1=2
Francogrex> 1+2=3
Francogrex> 2+3=5
Francogrex> 3+5=8
How would a general trace facility possibly know that?
Ray
On 15 abr, 18:05, Raymond Toy <···········@stericsson.com> wrote:
> >>>>> "Francogrex" == Francogrex <······@grex.org> writes:
>
> Francogrex> On Apr 14, 11:31 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> >> What would you like to see that would be clearer? What would the ideal
> >> presentation look like?
>
> Francogrex> Maybe it's too simplistic or optimistic but would have liked to see
> Francogrex> something such as=
> Francogrex> 0+1=1
> Francogrex> 1+1=2
> Francogrex> 1+2=3
> Francogrex> 2+3=5
> Francogrex> 3+5=8
>
> How would a general trace facility possibly know that?
>
> Ray
A trace of the function + :)
On Apr 15, 2:35 pm, Francogrex <······@grex.org> wrote:
> On Apr 14, 11:31 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
>
> > What would you like to see that would be clearer? What would the ideal
> > presentation look like?
>
> Maybe it's too simplistic or optimistic but would have liked to see
> something such as=
> 0+1=1
> 1+1=2
> 1+2=3
> 2+3=5
> 3+5=8
> ... etc
Yeah, that's not what TRACE is intended to do. It's not meant to
somehow divine the internal structure of a program, but rather to let
you see the overall 'shape' of a recursive call. And it's pretty
decent at that - I've used it plenty to do precisely that.
However, what you're looking for can, in fact, be roughly achieved by
TRACE, you just have to target a different thing - in this case, the +
function. After all, you're not interested in the fib calls at all;
you only want to see when an addition takes place.
Note: my Lisp dies when I try to (trace +), as + is used inside of
TRACE. So I had to define a wrapper function that I could then trace.
(defun my+ (&rest nums) (reduce '+ nums))
(defun fib (n) (if (< n 3) 1 (my+ (fib (- n 1)) (fib (- n 2)))))
(trace my+)
(fib 6)
Entering function MY+ with params (1 1)
Function MY+ returned value(s) (2)
Entering function MY+ with params (2 1)
Function MY+ returned value(s) (3)
Entering function MY+ with params (1 1)
Function MY+ returned value(s) (2)
Entering function MY+ with params (3 2)
Function MY+ returned value(s) (5)
Entering function MY+ with params (1 1)
Function MY+ returned value(s) (2)
Entering function MY+ with params (2 1)
Function MY+ returned value(s) (3)
Entering function MY+ with params (5 3)
Function MY+ returned value(s) (8)
8
~TJ
On Apr 16, 1:57 pm, TJ Atkins <··········@gmail.com> wrote:
> However, what you're looking for can, in fact, be roughly achieved by
> TRACE, you just have to target a different thing - in this case, the +
> function. After all, you're not interested in the fib calls at all;
> you only want to see when an addition takes place.
>
> Note: my Lisp dies when I try to (trace +), as + is used inside of
> TRACE. So I had to define a wrapper function that I could then trace.
>
> (defun my+ (&rest nums) (reduce '+ nums))
> (defun fib (n) (if (< n 3) 1 (my+ (fib (- n 1)) (fib (- n 2)))))
> (trace my+)
> (fib 6)
> Entering function MY+ with params (1 1)
> Function MY+ returned value(s) (2)
> Entering function MY+ with params (2 1)
> Function MY+ returned value(s) (3)
> Entering function MY+ with params (1 1)
> Function MY+ returned value(s) (2)
> Entering function MY+ with params (3 2)
> Function MY+ returned value(s) (5)
> Entering function MY+ with params (1 1)
> Function MY+ returned value(s) (2)
> Entering function MY+ with params (2 1)
> Function MY+ returned value(s) (3)
> Entering function MY+ with params (5 3)
> Function MY+ returned value(s) (8)
> 8
Perfect! that's exactly what i needed.
Francogrex <······@grex.org> writes:
> I never cared for the function trace. I just find it confusing and
> almost never tells me clearly how the function i'm tracing is really
> working inside. See for example this:
> (defun fibonacci (n)
> (if (<= n 1) n
> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
>
> (trace fibonacci) ;;ecl or sbcl
>
> (fibonacci 7)
>
> With the output of trace, I'm no wiser how this recursion worked, if
> anything I'm more confused. Is there anything clearer? (mind you, I am
> not excluding the possibility that I'm not as bright as some of you
> who *do* find the trace function very helpful and clear).
Perhaps tracing two different (and simplier) calls would be more
telling? But it's true that fibinacci is not so interesting. It is
more interesting to use TRACE when you have several functions calling
each others and you reach a point where you don't know how a given
function is called.
C/USER[17]> (defun fibonacci (n)
(if (<= n 1) n
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
FIBONACCI
C/USER[18]> (trace FIBONACCI)
;; Tracing function FIBONACCI.
(FIBONACCI)
C/USER[19]> (FIBONACCI 4)
1. Trace: (FIBONACCI '4)
2. Trace: (FIBONACCI '3)
3. Trace: (FIBONACCI '2)
4. Trace: (FIBONACCI '1)
4. Trace: FIBONACCI ==> 1
4. Trace: (FIBONACCI '0)
4. Trace: FIBONACCI ==> 0
3. Trace: FIBONACCI ==> 1
3. Trace: (FIBONACCI '1)
3. Trace: FIBONACCI ==> 1
2. Trace: FIBONACCI ==> 2
2. Trace: (FIBONACCI '2)
3. Trace: (FIBONACCI '1)
3. Trace: FIBONACCI ==> 1
3. Trace: (FIBONACCI '0)
3. Trace: FIBONACCI ==> 0
2. Trace: FIBONACCI ==> 1
1. Trace: FIBONACCI ==> 3
3
C/USER[20]> (FIBONACCI 5)
1. Trace: (FIBONACCI '5)
2. Trace: (FIBONACCI '4)
3. Trace: (FIBONACCI '3)
4. Trace: (FIBONACCI '2)
5. Trace: (FIBONACCI '1)
5. Trace: FIBONACCI ==> 1
5. Trace: (FIBONACCI '0)
5. Trace: FIBONACCI ==> 0
4. Trace: FIBONACCI ==> 1
4. Trace: (FIBONACCI '1)
4. Trace: FIBONACCI ==> 1
3. Trace: FIBONACCI ==> 2
3. Trace: (FIBONACCI '2)
4. Trace: (FIBONACCI '1)
4. Trace: FIBONACCI ==> 1
4. Trace: (FIBONACCI '0)
4. Trace: FIBONACCI ==> 0
3. Trace: FIBONACCI ==> 1
2. Trace: FIBONACCI ==> 3
2. Trace: (FIBONACCI '3)
3. Trace: (FIBONACCI '2)
4. Trace: (FIBONACCI '1)
4. Trace: FIBONACCI ==> 1
4. Trace: (FIBONACCI '0)
4. Trace: FIBONACCI ==> 0
3. Trace: FIBONACCI ==> 1
3. Trace: (FIBONACCI '1)
3. Trace: FIBONACCI ==> 1
2. Trace: FIBONACCI ==> 2
1. Trace: FIBONACCI ==> 5
5
C/USER[21]>
--
__Pascal Bourguignon__
On Tue, 14 Apr 2009 22:21:45 +0200, Francogrex <······@grex.org> wrote:
>
> With the output of trace, I'm no wiser how this recursion worked, if
> anything I'm more confused. Is there anything clearer? (mind you, I am
> not excluding the possibility that I'm not as bright as some of you
> who *do* find the trace function very helpful and clear).
>
Trace is typically not really good designed. I
developed this one in Newlisp:
;----------------8<--------------------------------------
(load "http://www.instprog.com/Instprog.default-library.lsp")
(set 'fibo (lambda(x)(if (>= x 3)
(+ (fibo (- x 1))
(fibo (- x 2)))
1)))
(println "debug-wrap test --------------------------------------")
(debug-wrap fibo)
(fibo 7)
(exit)
;---------------8<----------------------------------------
Output:
debug-wrap test --------------------------------------
(fibo (in 7)
(fibo (in 6)
(fibo (in 5)
(fibo (in 4)
(fibo (in 3)
(fibo (in 2)
(out 1)); t=0, mem=2
(fibo (in 1)
(out 1)); t=0, mem=2
(out 2)); t=18, mem=2
(fibo (in 2)
(out 1)); t=0, mem=2
(out 3)); t=39, mem=2
(fibo (in 3)
(fibo (in 2)
(out 1)); t=0, mem=2
(fibo (in 1)
(out 1)); t=0, mem=2
(out 2)); t=18, mem=2
(out 5)); t=78, mem=2
(fibo (in 4)
(fibo (in 3)
(fibo (in 2)
(out 1)); t=0, mem=2
(fibo (in 1)
(out 1)); t=0, mem=2
(out 2)); t=19, mem=2
(fibo (in 2)
(out 1)); t=0, mem=2
(out 3)); t=37, mem=2
(out 8)); t=134, mem=2
(fibo (in 5)
(fibo (in 4)
(fibo (in 3)
(fibo (in 2)
(out 1)); t=0, mem=2
(fibo (in 1)
(out 1)); t=0, mem=2
(out 2)); t=19, mem=2
(fibo (in 2)
(out 1)); t=0, mem=2
(out 3)); t=41, mem=2
(fibo (in 3)
(fibo (in 2)
(out 1)); t=0, mem=2
(fibo (in 1)
(out 1)); t=0, mem=2
(out 2)); t=19, mem=2
(out 5)); t=77, mem=2
(out 13)); t=229, mem=2
The best way to view this output is to cut and paste it
in PLT IDE which is excelent for highlighting this
kind of s-expressions.
http://img368.imageshack.us/img368/1294/plt2om7.png
With psudo s-expr form of trace output and PLT IDE,
I can produce hundreds of thousands of lines of output
and locate error relatively easily.
--
Blog: http://kazimirmajorinc.blogspot.com
WWW: http://www.instprog.com
>>>>> "Francogrex" == Francogrex <······@grex.org> writes:
Francogrex> I never cared for the function trace. I just find it confusing and
Francogrex> almost never tells me clearly how the function i'm tracing is really
Francogrex> working inside. See for example this:
I never thought of trace as a way of figuring out how a function
worked. When I trace something, I'm much more interested in the
arguments and the outputs to see what is happening between the caller
and callee. I guess that includes understanding how a recursive
function works, but you'd still need to kind of understand the insides
of the function to help you understand the recursion.
But I find it invaluable for debugging things.
And some trace facilities are very powerful. Look at the CMU User's
manual for some of the possibilities. I use the :wherein,
:wherein-only, :print and :break options all the time for debugging
code.
Ray
Most implementations do tail call elimination, and this will in general
confuse the simple tracing model. In nearly every language there is a
conflict between expressiveness, efficiency, and debuggability.
You might rewrite your example this way, which will enhance
debuggability, or at least traceability:
(defun fibonacci (n)
(declare (notinline fibonacci +))
(if (<= n 1) n
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
Unfortunately, this requires temporarily changing your source code. It
would be nicer if one could globally turn off various optimizations for
debugging. Unfortunately, some reasonable code that assumes tail call
elimination, and which therefore codes iteration as recursion, might not
work.
IIRC, Scheme mandates where tail-call elimination must be performed. CL
doesn't.
On 15 abr, 19:15, "Steven M. Haflich" <····@alum.mit.edu> wrote:
> Most implementations do tail call elimination, and this will in general
> confuse the simple tracing model. In nearly every language there is a
> conflict between expressiveness, efficiency, and debuggability.
>
> You might rewrite your example this way, which will enhance
> debuggability, or at least traceability:
>
> (defun fibonacci (n)
> (declare (notinline fibonacci +))
> (if (<= n 1) n
> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
>
> Unfortunately, this requires temporarily changing your source code. It
> would be nicer if one could globally turn off various optimizations for
> debugging. Unfortunately, some reasonable code that assumes tail call
> elimination, and which therefore codes iteration as recursion, might not
> work.
>
> IIRC, Scheme mandates where tail-call elimination must be performed. CL
> doesn't.
Instead, just
(declaim (optimize (speed 0) (debug 3)))
I believe this would eliminate tail call optimization.
But note that fibonacci is not tail recursive, though the tail call
can't be optimized into a loop (otherwise, SBCL would do this, which
is not the case).
>>>>> "Steven" == Steven M Haflich <···@alum.mit.edu> writes:
Steven> Most implementations do tail call elimination, and this will in
Steven> general confuse the simple tracing model. In nearly every language
Steven> there is a conflict between expressiveness, efficiency, and
Steven> debuggability.
Steven> You might rewrite your example this way, which will enhance
Steven> debuggability, or at least traceability:
Steven> (defun fibonacci (n)
Steven> (declare (notinline fibonacci +))
Steven> (if (<= n 1) n
Steven> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
I think this depends on the Lisp implementation. When compiled, I
know cmucl will trace the recursive calls as you would want, even
without the notinline declaration. (But the + function may not be
traced. It is in this case because it isn't open-coded.)
CL-USER> (compile 'fibonacci)
; Compiling LAMBDA (N):
; Compiling Top-Level Form:
FIBONACCI
NIL
NIL
CL-USER> (trace fibonacci)
(FIBONACCI)
CL-USER> (fibonacci 4)
0: (FIBONACCI 4)
1: (FIBONACCI 3)
2: (FIBONACCI 2)
3: (FIBONACCI 1)
3: FIBONACCI returned 1
3: (FIBONACCI 0)
3: FIBONACCI returned 0
2: FIBONACCI returned 1
2: (FIBONACCI 1)
2: FIBONACCI returned 1
1: FIBONACCI returned 2
1: (FIBONACCI 2)
2: (FIBONACCI 1)
2: FIBONACCI returned 1
2: (FIBONACCI 0)
2: FIBONACCI returned 0
1: FIBONACCI returned 1
0: FIBONACCI returned 3
3
CL-USER>
Ray
Raymond Toy wrote:
> Steven> You might rewrite your example this way, which will enhance
> Steven> debuggability, or at least traceability:
>
> Steven> (defun fibonacci (n)
> Steven> (declare (notinline fibonacci +))
> Steven> (if (<= n 1) n
> Steven> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
>
> I think this depends on the Lisp implementation. When compiled, I
> know cmucl will trace the recursive calls as you would want, even
> without the notinline declaration. (But the + function may not be
> traced. It is in this case because it isn't open-coded.)
That's interesting. On many platforms a self tail call can sometimes be
performed a little more efficiently without going through the regular
function call mechanics, since the function calling itself can know what
its stack frame wants to look like, and may already have it essentially
already set up. Does cmucl do something to modify the function, rather
than just encapsulating it in the trace machinery?
Anyway, all these things do indeed depend on the implementation, and the
effect of optimization declarations is not portable.
I don't entirely agree with the previous suggestion that turning off
optimization is the right thing. While it may disable tail jumping in
many implementations, it might also turn off other optimizations in the
function body. When a bug does indeed dpend on some particular
optimization -- perhaps a type declaration that is being violated -- the
declaration may have no effect on the unoptimized function and only
cause unpredictable results under optimization. So turning off
optimization changes what you intend to debug.