COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Strange behavior with trace command

• Follow

```The problem is very simple: we want a function returning true if and
only if all the numbers in the input list are odd. For example a
solution may be:

(defun all-oddp (l)
(if (null l)
t
(and
(oddp (car l))
(all-oddp (rest l)))))

When I try to trace its execution with the standard trace command, I
find that the function is always called once regardless of the input.
Does it happen because the compiler eliminates the recursion? But if
this is true, how can I debug it?

```
 0
Reply zcarioni (1) 12/17/2011 4:01:39 PM

```On 12=E6=9C=8818=E6=97=A5, =E5=8D=88=E5=89=8D1:01, zermelo <zcari...@gmail.=
com> wrote:
> The problem is very simple: we want a function returning true if and
> only if all the numbers in the input list are odd. For example a
> solution may be:
>
> (defun all-oddp (l)
> =C2=A0 =C2=A0 (if (null l)
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 t
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 (and
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (oddp (car l))
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (all-oddp (rest l)))))
>
> When I try to trace its execution with the standard trace command, I
> find that the function is always called once regardless of the input.
> Does it happen because the compiler eliminates the recursion? But if
> this is true, how can I debug it?

I tried on SBCL 10.50.
----

CL-USER(1): (defun all-oddp (l)
(if (null l)
t
(and (oddp (car l))
(all-oddp (rest l)))))

ALL-ODDP
CL-USER(2): (all-oddp '(1 3 5))
T

CL-USER(3): (trace all-oddp)

(ALL-ODDP)

CL-USER(4): (all-oddp '(1 3 5))
0: (ALL-ODDP (1 3 5))
1: (ALL-ODDP (3 5))
2: (ALL-ODDP (5))
3: (ALL-ODDP NIL)
3: ALL-ODDP returned T
2: ALL-ODDP returned T
1: ALL-ODDP returned T
0: ALL-ODDP returned T
T
-------------
I find all-oddp called recursively.

What is your environment?

```
 0
Reply poketo7878 (2) 12/17/2011 4:26:11 PM

```zermelo <zcarioni@gmail.com> writes:

> Does it happen because the compiler eliminates the recursion?

That could be true, or the compiler makes the recursive call in such a
way that the TRACE facility is circumvented.

> But if this is true, how can I debug it?

Try not compiling the function, running it in interpreted mode. Or,
possibly adding (declare (notinline all-oddp)) will work too.

--
Frode V. Fjeld
```
 0
Reply frodevf (92) 12/17/2011 5:21:05 PM

```On 17 Dic, 17:26, pocket <poketo7...@yahoo.co.jp> wrote:
> On 12=E6=9C=8818=E6=97=A5, =E5=8D=88=E5=89=8D1:01, zermelo <zcari...@gmai=
l.com> wrote:
>
> > The problem is very simple: we want a function returning true if and
> > only if all the numbers in the input list are odd. For example a
> > solution may be:
>
> > (defun all-oddp (l)
> > =C2=A0 =C2=A0 (if (null l)
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 t
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 (and
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (oddp (car l))
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (all-oddp (rest l)))))
>
> > When I try to trace its execution with the standard trace command, I
> > find that the function is always called once regardless of the input.
> > Does it happen because the compiler eliminates the recursion? But if
> > this is true, how can I debug it?
>
> I tried on SBCL 10.50.
> ----
>
> CL-USER(1): (defun all-oddp (l)
> (if (null l)
> t
> (and (oddp (car l))
> (all-oddp (rest l)))))
>
> ALL-ODDP
> CL-USER(2): (all-oddp '(1 3 5))
> T
>
> CL-USER(3): (trace all-oddp)
>
> (ALL-ODDP)
>
> CL-USER(4): (all-oddp '(1 3 5))
> =C2=A0 0: (ALL-ODDP (1 3 5))
> =C2=A0 =C2=A0 1: (ALL-ODDP (3 5))
> =C2=A0 =C2=A0 =C2=A0 2: (ALL-ODDP (5))
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 3: (ALL-ODDP NIL)
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 3: ALL-ODDP returned T
> =C2=A0 =C2=A0 =C2=A0 2: ALL-ODDP returned T
> =C2=A0 =C2=A0 1: ALL-ODDP returned T
> =C2=A0 0: ALL-ODDP returned T
> T
> -------------
> I find all-oddp called recursively.
>
> What is your environment?

I have tried with several compilers. For example, trace works as
expected with Allegro, but it just shows one call with Lispbox.
```
 0
Reply zermelo (5) 12/17/2011 7:59:22 PM

```On 2011-12-17, zermelo <zcarioni@gmail.com> wrote:
> The problem is very simple: we want a function returning true if and
> only if all the numbers in the input list are odd.

Lisp has this nearly built-in:

(every #'oddp list-of-numbers)

> For example a
> solution may be:
>
> (defun all-oddp (l)
>     (if (null l)
>         t
>         (and

The expression  (if (null <expr>) t <else>)  is clumsy!

The (null <expr>) already returns the value t if it is true. Instead try:

(or (null x) <else>)

Lisp's OR operator will return the first true value (and not evaluate
the rest). So combining that with the rest of your code:

(or (null x)
(and (oddp (first l))
(all-oddp (rest l))))

>             (oddp (car l))
>             (all-oddp (rest l)))))

Do not mix CAR/REST. It's not incorrect, but it's stylistically silly.
FIRST pairs with REST, CAR with CDR!  No brainer, right?

> When I try to trace its execution with the standard trace command, I
> find that the function is always called once regardless of the input.

What do you mean? The function appears to be called /just/ once, no matter
how long the list, without any evidence of recursive calls?

That does look like tail call elimination at work.

Your code is reduced to a loop, and so trace it like a loop:

(defun all-oddp (l)
(format t "(all-oddp ~s)~%" l)
(or (null x)
(and (oddp (first l))
(all-oddp (rest l)))))

Find out how to disable your Lisp's tail optimization.
```
 0
Reply kaz15 (1129) 12/17/2011 8:09:37 PM

4 Replies
25 Views

(page loaded in 0.092 seconds)