Le 2017-08-21 14:55, PR a écrit :
2017-08-21 14:11 GMT+02:00, Eric Brunel <eric.bru...@pragmadev.com>:
Hello all,
I'm trying to get ECL to optimize tail self-calls in the C code
generated from the Lisp files and it looks like I'm missing something,
because I can't find a way to do that.
Here is an example that works (not written by me, it's from cliki.net):
(defun fib (n)
"Tail-recursive computation of the nth element."
(check-type n (integer 0 *))
(labels ((fib-aux (n f1 f2)
(if (zerop n)
f1
(fib-aux (1- n) f2 (+ f1 f2)))))
(fib-aux n 0 1)))
The generated C code uses goto, as you can see:
static cl_object LC1fib_aux(cl_object v1n, cl_object v2f1, cl_object
v3f2)
{
cl_object env0;
const cl_env_ptr cl_env_copy = ecl_process_env();
cl_object value0;
ecl_cs_check(cl_env_copy,value0);
{
TTL:
if (!(ecl_zerop(v1n))) { goto L1; }
value0 = v2f1;
cl_env_copy->nvalues = 1;
return value0;
L1:;
v1n = ecl_one_minus(v1n);
{
cl_object v4;
v4 = v3f2;
v3f2 = ecl_plus(v2f1,v3f2);
v2f1 = v4;
}
goto TTL;
}
}
It does indeed, and I think I got it: the optional parameters to my
function seem to prevent the optimization from happening. If I rewrite
my function as:
(defun enumerate-aux (l index result)
(cond
((null l) (reverse result))
(t (enumerate-aux (cdr l) (+ index 1) (cons (list index (car l))
result)))
)
)
(defun enumerate (l) (enumerate-aux l 0 nil))
the generated code for the enumerate-aux function is as expected:
static cl_object L1enumerate_aux(cl_object v1l, cl_object v2index,
cl_object v3result)
{
cl_object T0, T1;
cl_object env0;
const cl_env_ptr cl_env_copy = ecl_process_env();
cl_object value0;
ecl_cs_check(cl_env_copy,value0);
{
TTL:
if (!(v1l==ECL_NIL)) { goto L1; }
value0 = cl_reverse(v3result);
return value0;
L1:;
{
cl_object v4;
v4 = ecl_cdr(v1l);
{
cl_object v5;
v5 = ecl_plus(v2index,ecl_make_fixnum(1));
T0 = ecl_car(v1l);
T1 = cl_list(2, v2index, T0);
v3result = CONS(T1,v3result);
v2index = v5;
v1l = v4;
}
}
goto TTL;
}
}
Not sure I understand why, but I have a solution.
Thank you very much!
- Eric -
Paul
Here is the behavior I'm getting for this simple Lisp function:
(defun enumerate (l &optional (index 0) (result nil))
(cond
((null l) (reverse result))
(t (enumerate (cdr l) (+ index 1) (cons (list index (car l))
result)))
)
)
As far as I can see, this function is properly tail-recursive, so I
expected the generated C code to take the into account and generate a
goto instead of a recursive call. But what I'm getting is this:
static cl_object L1enumerate(cl_narg narg, cl_object v1l, ...)
{
cl_object T0, T1, T2, T3, T4;
cl_object env0;
const cl_env_ptr cl_env_copy = ecl_process_env();
cl_object value0;
ecl_cs_check(cl_env_copy,value0);
if (ecl_unlikely(narg<1)) FEwrong_num_arguments_anonym();
if (ecl_unlikely(narg>3)) FEwrong_num_arguments_anonym();
{
cl_object v2index;
cl_object v3result;
va_list args; va_start(args,v1l);
{
int i = 1;
if (i >= narg) {
v2index = ecl_make_fixnum(0);
} else {
i++;
v2index = va_arg(args,cl_object);
}
if (i >= narg) {
v3result = ECL_NIL;
} else {
i++;
v3result = va_arg(args,cl_object);
}
}
va_end(args);
if (!(v1l==ECL_NIL)) { goto L3; }
value0 = cl_reverse(v3result);
return value0;
L3:;
T0 = ecl_cdr(v1l);
T1 = ecl_plus(v2index,ecl_make_fixnum(1));
T2 = ecl_car(v1l);
T3 = cl_list(2, v2index, T2);
T4 = CONS(T3,v3result);
value0 = L1enumerate(3, T0, T1, T4);
return value0;
}
}
The recursive call is generated as a recursive call in C too...
I'm almost sure I've seen C code generated from ECL that generated
self
tail calls as goto's, and I know it works when using the bytecode,
where
you just have to compile the function. But my search for a way to
trigger this behavior for the generated C code has been unsuccessful
so
far.
I'm using ECL 16.1.3. I used "ecl -c ... --compile ..." to get the C
code, but my main build uses asdf:make-build with an ASD file.
