Simple recursive function freezes Emacs — how to correct the definition?

Question

I was trying to familiarize myself with several languages by doing the advent of code exercises in these languages, and one that got me stuck is Emacs Lisp, in the very first exercise.

The goal is to count, given a certain list of numbers, the number of consecutive increasing numbers in the list. Assume for the rest of this post input is the list we want to process, which contains 2000 numbers (so it's a relatively small list).

My first solution was maybe not so idiomatic, because it was inspired by a previous solution in a other language (basically a translation).

It's

(require 'dash)

(defun translated-solution (vals)
  (-sum 
    (-zip-with
      (lambda (x y) (if (< y x) 1 0))
      vals (cdr vals))))

Basically it duplicates the list, skips the first element of the copy, then compares the two versions element-wise, summing each time the second element is greater than the first one. It works fine.

My second solution is

(require 'cl)
(defun recursive-solution (vals)
  (let ((x (car vals))
    (y (cadr vals))
    (tail (cddr vals)))
    (if (and x y)
    (+ 
      (if (< x y) 0 1)
      (recursive-solution (cons y tail)))
      0)))

This works on small lists, but makes Emacs hard-freeze when testing on input, forcing me to kill -9...

I understand this could be caused by a stack overflow, due to recursing too much, but I don't understand why would that cause Emacs to freeze. If it were the case, I would expect Emacs either to crash, or to take back control over the interpreter resulting in an error.

Anyways, I tried a tail-recursive version:

(defun tail-recursive-solution (vals)
  (flet ((aux (vals s)
          (let ((x (car vals))
            (y (cadr vals))
            (tail (cddr vals)))
        (if (and x y)
            (aux (cons y tail) (if (> y x) (1+ s) s))
          s))))
    (aux vals 0)))

but get aux: Variable binding depth exceeds max-specpdl-size. This looks like a preemptive error to a stack overflow, due to the fact that Emacs lisp probably allows a binding-depth that is smaller than the stack size. But this seems like the tail recursion optimization has not been made, and I don't understand why.

So, my question is: why do these simple functions on such a small input make Emacs go crazy? What is the idiomatic way to solve this exercise?

Answer 1

Now, Emacs Lisp does implement Optimized Tail-Recursion,
since Emacs 28.1 (Released Apr 4, 2022).

12.3 Local Variables:

Recursive calls to name that occur in tail positions in body are guaranteed to be optimized as tail calls, which means that they will not consume any additional stack space no matter how deeply the recursion runs. Such recursive calls will effectively jump to the top of the loop with new values for the variables.

A function call is in the tail position if it’s the very last thing done so that the value returned by the call is the value of body itself, as is the case in the recursive call to sum above.

---

If you want to invoke some recursive calls, please:

1. setq both max-lisp-eval-depth and max-specpdl-size to an available large fixnum;

2. use the named-let form, which is specified in the GNU Emacs Lisp Reference Manual that it is guaranteed to be optimized as tail calls.

3. make sure that your recursive call:

   is in the tail position if it’s the very last thing done so that the value returned by the call is the value of body itself

---

So, try it

Answer 2

Elisp does not implement Tail-Call Optimization (TCO).

Your first recursive solution fails with

(error "Lisp nesting exceeds ‘max-lisp-eval-depth’")

at least here.

tco.el is a package, which provides TCO.

Otherwise one could use a iterative approach.