iterative copy-tree in lisp

Question

The common lisp function copy-tree is often implemented in a recursive way, and thus is prone to stack overflow.

Here is my attempt at writing an iterative version, one-pass, no stack, no unnecessary consing, version of copy-tree in common-lisp, working with nested, perhaps dotted, lists.

 (defun my-copy-tree (tree)
 (do* ((result (list tree))
 (node result)
 (next))
 ((null node) result)
 (cond ((and (consp (cdar node))(atom (caar node)))
 (setf (cdr node) (cons (cdar node) (cdr node))
 (car node) (caar node) 
 node (cdr node)))
 ((consp (cdar node))
 (setf (cdr node) (cons (cdar node) (cdr node))
 (car node) (cons (caar node) (cdr node))
 node (car node)))
 ((consp (caar node))
 (setf (car node) (cons (car node) (cdr node))
 (cdr node) (cdaar node)
 node (car node)
 (car node) (caar node)))
 (t (setf next (cdr node)
 (cdr node) (cdar node)
 (car node) (caar node)
 node next)))))

The performance is ok. In fact, on sbcl it is faster than the native implementation, and almost as fast as copy-list for proper lists. It also has no problem making copies of "reversed" lists like the one given by

(reduce 'cons (make-list 1000000 :initial-element 0))

(by the way, are there any lisp implementation with a native copy-tree that does not stack-overflow on these kind of deep lists ?)

Unfortunately, my code is unreadable, and I must say I can't really understand it now without drawing a whole page of cons cells. Also it is not very flexible, e. g. there is no obvious way to turn it into a reduce-tree, in contrast to the recursive version.

How to rewrite the code above in a more readable and flexible way, and so to speak in a more lispy way, without losing performance ?

Writing an efficient implementation of copy-tree in lisp should be a standard exercice but google didn't bring anything relevant.

Answer 1

RE: how to rewrite to make it more readable

1. Stop using c[a,d]*r. While I have a soft spot for them your code may be more readable via first, second etc.
2. Name the predicates of the cond statement. What are they testing for? Use flet or labels.
3. Perhaps name the setf blocks to make it more clear what they are doing.
4. Perhaps split the setf blocks into separate setf lines. I had to check the hyperspec to verify that in fact each one was evaluated sequentially. It would be clearer if they were explicitly sequential.

To summarize:

• improve naming
• make things explicit

Re: performance

Without having performance benchmarks I cannot tell how the above changes would change the performance of the code. I also noticed that you didn't specify a optimize declaration. That could be used to change performance.

• Svante: I disagree on the setf splitting (I see the distinction of setf/psetf as quite clear).