Shape of a program

(defun bad-reverse (lst)
  (let* ((len (length lst))
	 (ilimit (truncate (/ len 2))))
    (do ((i 0 (1+ i))
	 (j (1- len) (1- j)))
	((>= i ilimit))
      (rotatef (nth i lst) (nth j lst)))))

It used to be thought that you could judge someone’s character by looking at the shape of his head. Whether or not this is true of people, it is generally true of Lisp programs. Functional programs have a different shape from imperative ones. The structure in a functional program comes entirely from the composition of arguments within expressions, and since arguments are indented, functional code will show more variation in indentation. Functional code looks fluid on the page; imperative code looks solid and blockish, like Basic.

Even from a distance, the shapes of bad- and good-reverse suggest which is the better program. And despite being shorter, good-reverse is also more efficient: O(n) instead of O(n^2).

(defun good-reverse (lst)
  (labels ((rev (lst acc)
		(if (null lst)
		  (rev (cdr lst) (cons (car lst) acc)))))
    (rev lst nil)))

— p.30

— On Lisp

— Paul Graham



2018.03.02 Friday ACHK