walk.lisp

(defun dotted-list-p (lst)
  (when (consp lst)
    (loop :for rest = (cdr lst) then (cdr rest)
	  :while (consp rest)
	  :finally (return (not (null rest))))))

(defun walk-inner (sexp pre mid post)
  (cond
    ((atom sexp)
     (funcall mid sexp))
    ((dotted-list-p sexp)
     (loop
      :for rest = sexp then (cdr rest)
      :collect (walk (if (consp rest) (car rest) rest) pre mid post)
      :while (consp rest)))
    ((listp sexp)
     (mapcar
      #'(lambda (sexp) (walk sexp pre mid post))
      sexp))))

(defun walk (sexp pre mid post)
  (if (and (listp sexp) (not (dotted-list-p sexp)))
      (funcall
       post
       (walk-inner
	(funcall pre sexp)
	pre mid post))
      (walk-inner sexp pre mid post)))