Is this Common Lisp code similar / equal to what they're teaching in LISP 3rd Edition by Winston / Horn?

user_14235490 0
Viewed 78

They're saying that

(defun user-reverse (l)
  (if (endp l)
      nil
      (append (user-reverse (rest l))
              (list (first l)))))

Is bad because of n(n + 1)/2 of computation.

Then they say go this way :

(defun user-reverse (l &optional result)
  (if (endp l)
      result
      (user-reverse (rest l)
                    (cons (first l) result))))

So I was thinking, why couldn't you do something like this instead :

(defun user-reverse (l)
  (do ((new-list nil))
      ((endp l) new-list)
    (push (pop l) new-list)))

Is any of this a bad habit or anything? Or does it copy the list or something? They teach 'DO' a couple chapters back and was wondering if any of the LISPers out can say if this is on par or worse or what not to their example? Basically, was wondering in terms of their bad 'n' example how it stands up?

reverse common-lisp lisp time-complexity list
1 Answers

There are two issues:

  • complexity&efficiency of the algorithm&datastructure
  • recursion vs. loop

Let's look first at the complexity/efficiency problem.

A list in Lisp is a singly linked list of cons cells or the empty list. Thus naive appending to the end of a list is a costly operation. In Lisp lists it is cheap to add an element to the front of a list and costly to add to the end of a list. Thus a routine should be written such that it does not use these costly operations.

If we have a recursive routine like the first one using the costly append operation, one wants to find a different routine, which does not add to the end of the list. That's why the second routine is better than the first one.

recursion vs. loop

The second version you posted is end recursive. The recursive call can be replaced by a jump and an update of two variables. This uses tail call optimization (TCO). In Lisp this is an optimization, which often a compiler can do. But they are not required to do so and interpreter-based implementations often do not. In Scheme it is required by the language definitions that implementations support TCO.

With TCO the second version is both using efficient operations and runs in constant space (it allocates a reversed list, though).

Without TCO the second version is using efficient operations, but may cause a stack overflow for large lists.

loop

The third version is using a loop - here DO. It is both using efficient operators and is limited only by memory size. It is not limited by stack size, since it does not do any recursive calls.

Often in real-world software (-> not written for teaching purpose) in Lisp one will find the code using loops, because TCO is not generally available in all implementations. For example the ABCL implementation of Common Lisp runs on the Java Virtual Machine (JVM). Since the JVM does not provide direct features to implement TCO, programming language implementations for the JVM usually don't provide TCO. ABCL is no exception.

dolist

The loop version can be written with dolist:

(defun user-reverse (l &aux r)
  (dolist (e l r)
    (push e r)))
Rainer_Joswig_695450
Related