Tail recursive function in 'labels' not acting tail recursive

Hello,

I’m wondering about the tail recursion reduction properties of LW. I have the following function:

(labels ((helper (l n)

(values (if (cdr l)

(let ((item-2 (car l)))

(if (>= (ajenda-item-time item)

(ajenda-item-time item-2))

(helper (cdr l) (incf n))

(setf (cdr l) (cons item (cdr l)))))

(setf (cdr l) (list item)))

n)))

but when I run it I get a popup about a stack overflow on large lists. I know how to eliminate the stack overflow popup by increasing the stack size, but this looks tail recursive to me. I have tried to declaim (speed 3) with no results. Am I missing something to get proper tail recursion optimization out of the LW compiler?

—

Burton Samograd

Re: Tail recursive function in 'labels' not acting tail recursive

See section 9.7.4 in the "LispWorks User Guide and Reference Manual" (http://www.lispworks.com/documentation/lw70/LW/html/lw-63.htm#pgfId-887598).

So, at a minimum, you need to specify (debug <something-less-than-3>), and be using either 64-bit LispWorks or be on an x86 platform.

Disclaimer: I could well be misinterpreting this.

On Fri, Jan 27, 2017 at 4:39 AM, BusFactor1 Inc. <busfactor1@gmail.com> wrote:

Hello,

I’m wondering about the tail recursion reduction properties of LW. I have the following function:

(labels ((helper (l n)

(values (if (cdr l)

(let ((item-2 (car l)))

(if (>= (ajenda-item-time item)

(ajenda-item-time item-2))

(helper (cdr l) (incf n))

(setf (cdr l) (cons item (cdr l)))))

(setf (cdr l) (list item)))

n)))

but when I run it I get a popup about a stack overflow on large lists. I know how to eliminate the stack overflow popup by increasing the stack size, but this looks tail recursive to me. I have tried to declaim (speed 3) with no results. Am I missing something to get proper tail recursion optimization out of the LW compiler?

—

Burton Samograd

Re: Tail recursive function in 'labels' not acting tail recursive

Hi,

how about VALUES? You call the function, but then it needs to return to HELPER to the values statement.

For TCO requirements see:

http://www.lispworks.com/documentation/lw70/LW/html/lw-63.htm#pgfId-887598

9.7.4 Tail call optimization

In 64-bit LispWorks and on x86 platforms the compiler optimizes tail calls unless

• The compiler optimize quality debug is 3, or

• There is something with dynamic scope on the stack, such as a special binding, a catch or cl:dynamic-extent allocation (so it is not really a tail call)

On all other platforms the compiler optimizes tail calls unless 1.) or 2.) above apply, or

• The call has more than 4 arguments and this is more than the number of fixed (not &optional/&rest/&key) parameters in the calling function.

• The call has more than 4 arguments and the calling function has &rest/&key parameters.

Regards,

Rainer

Am 27.01.2017 um 04:39 schrieb BusFactor1 Inc. <busfactor1@gmail.com>:

Hello,

I’m wondering about the tail recursion reduction properties of LW. I have the following function:

(labels ((helper (l n)
(values (if (cdr l)
(let ((item-2 (car l)))
(if (>= (ajenda-item-time item)
(ajenda-item-time item-2))
(helper (cdr l) (incf n))
(setf (cdr l) (cons item (cdr l)))))
(setf (cdr l) (list item)))
n)))

but when I run it I get a popup about a stack overflow on large lists. I know how to eliminate the stack overflow popup by increasing the stack size, but this looks tail recursive to me. I have tried to declaim (speed 3) with no results. Am I missing something to get proper tail recursion optimization out of the LW compiler?

—
Burton Samograd