r/Common_Lisp • u/[deleted] • Mar 10 '23
R for Recursion
Have you heard about NASA’s 10 rules for developing safety-critical code?
The first rule forbids recursion and there are many reasonable arguments for that. Even if you don't write safety-critical systems, the use of recursion makes your software less reliable, because:
it is difficult to reason about when and what your function returns
function becomes vulnerable to stack overflow
But if you CL, recursion becomes a very natural and concise way to express your ideas. Let us learn from the masters! There is a famous macro called flatten described in a marvelous book "On Lisp" written by Paul Graham. Here is the code:
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))It parses an arbitrarily deep tree of objects and returns you a flat list. Clear and concise. It is even referenced by another famous book "Let over Lambda" (D. Hoyte). From that I conclude the this macro is an example of idiomatic Lisp code. Now test it with a not-so-small tree of objects:
(let ((x (loop for i from 0 to 1000000 collect (cons i i))))
(flatten x))SBCL crashes with the message:
Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.This is only the half of the story. If you look carefully at the macro, it is not just recursive, but it uses a recursive core, which is not visible to a caller. This seems to be also a good Lisp style, which unfortunately forces you to mistrust the code written by others.
Yes, functional programming in unthinkable without recursion. Moreover, if you manage to make a call tail-recursive, than a decent compiler must be able to transform it in a loop without run-time overhead. And so we can enjoy brevity of the code and its performance at the same time.
What really scares me, is how actively recursive functions are used in Lisp. They are scattered nearly everywhere. Is this performance/expressiveness lottery really worth it? If yes, I have a proposal.
We have a convention, that a name of a function which modifies its argument should start with "n" prefix (nreverse, nconc, etc). This sends a clear message to its caller. Recursion is equally dangerous, so why not to use an "r" prefix for the functions where recursion is used? This would discourage a reckless programmer to use rflatten in a safety-critical code. Let's vote!