2017-08-21 14:11 GMT+02:00, Eric Brunel eric.brunel@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; } }
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.