3

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?

5
  • emacs.stackexchange.com/tags/elisp/info
    – Drew
    Commented Feb 25, 2022 at 16:18
  • With Emacs Lisp you're often better off with iteration. If you get a stack overflow, that's the direction to pursue.
    – Drew
    Commented Feb 25, 2022 at 16:22
  • @Drew ah well I though I was in that category [about the elisp tag] as in most other Lisps dialects, recursion would have been the way to go (since TCO is implemented in many Lisp dialects). About iteration, it's really funny to see a functional language that makes it more "natural" to write iterative over recursive.
    – jthulhu
    Commented Feb 25, 2022 at 16:24
  • Emacs Lisp is almost, but not quite, a general-purpose language: it is meant as an Emacs extension language, so many things are not provided (in particular, TCO - it probably did not even have a compiler to begin with; only relatively recently did it get lexical scoping and native compilation is still in beta AFAIK). If you want to extend Emacs, you want to (have to?) use Emacs Lisp. For other purposes, use a general-purpose Lisp like CL.
    – NickD
    Commented Feb 25, 2022 at 17:58
  • 1
    Elisp is not a functional language in the usual sense. Neither is any other Lisp (except a pure, academic functional subset of Lisp), for that matter. Beyond the usual side-effect constructs, even just quote destroys referential transparency (which it can be argued is essential for a purely functional language).
    – Drew
    Commented Feb 25, 2022 at 18:28

2 Answers 2

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.

7
  • 1
    How could the first solution utilize TCO? I was taught that TCO is only possible when the very last call is the recursive call, which is not the case since the very last call is an addition, isn't it?
    – jthulhu
    Commented Feb 25, 2022 at 11:20
  • @BlackBeans you are right, I'll edit my answer
    – jue
    Commented Feb 25, 2022 at 11:23
  • 1
    Also, my first recursive solution does not fail with (error [...]) (as I would have expected), but simply freezes... do you have any idea on why?
    – jthulhu
    Commented Feb 25, 2022 at 11:25
  • @BlackBeans I generated a list with 2000 random values an processed it with your first recursive function, it dropped into the debugger, with above quoted error
    – jue
    Commented Feb 25, 2022 at 11:30
  • @BlackBeans, now I'm just guessing: could you set variable debug-on-error to t?
    – jue
    Commented Feb 25, 2022 at 11:32
4

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.