Years-old rumination about some On Lisp code

onlisp-critique.lisp

;; In the book "On Lisp", Paul Graham has a chapter on Returning
;; Functions.  He admits that his examples are obscured by the
;; separation of function and variable namespaces.  He presents Scheme
;; solutions to Scheme problems, disguised as Common Lisp code.

;; One of the examples is an attempt at "orthogonality", reducing the
;; number of operators by having a ! function that returns the
;; destructive counterpart of an operator.  The attempt fails because
;; it does not reduce the number of operators, just the number of
;; operator names (qua symbols).  His Lisp1 remove-if/delete-if
;; example indicates that he thinks that use of ! is trading syntactic
;; complexity for conceptual simplicity, but that is wrong.  Here's
;; what you need to know in each case:
;;
;;        ((! remove-if) oddp lst) | (delete-if oddp lst)
;;        The ! mechanism          |
;;        What remove-if does      | What delete-if does
;;
;; Notably, in the second case you don't need to know about remove-if.
;; Is it worth introducing more operator names to avoid the !
;; mechanism?  I think so.
;;
;; He claims that the first variant is clearer, odd taste.
;;
;; He claims that the ! operator gives destructive operations a
;; distinct, recognizable form.  Here's a function to destructively
;; remove even numbers in a list:
;;
;; (define (odds! lst)
;;   ((! remove-if) evenp lst))
;;
;; See, we called it odds! to show that it's destructive, so why is it
;; any worse than (! odds)?  If we want to use the ! mechanism, we
;; need more code:
;;
;; (def! odds odds!)
;;
;; But now there's the expectation of a nondestructive odds:
;;
;; (define (odds lst)
;;   (remove-if evenp lst))
;;
;; I see repetition here, and proliferation of operators, hence less
;; orthogonality.
;;
;; I note that ! returns the original function if there is no
;; destructive variant.  This makes it possible to leave the
;; destructive implementations for future definition.  It also makes
;; it possible to disable them.  There should be another function to
;; determine whether there is a destructive variant, !p.

;; Another example concerns CDR-recursion on lists.  He shows LREC,
;; which takes a stepper function and a base value/function.  The
;; stepper function takes a list element and a continuation function.
;; This in Common Lisp is not easy on the eyes, with hash-quotes and
;; funcalls and lambdas.  Here's a Common Lisp refinement (for
;; pedagogy, I did not care for hygiene; furthermore, the macros are
;; anaphoric):

(defpackage #:snippets/onlisp-critique
  (:use #:cl))

(in-package #:snippets/onlisp-critique)

(defun lrec-fn (fn base)
  (labels ((self (lst)
             (if (null lst)
                 (if (functionp base)
                     (funcall base)
                     base)
                 (funcall fn (car lst)
                          (lambda ()
                            (self (cdr lst)))))))
    #'self))

;; The stepper forms can use X and (NEXT).

(defmacro lrec (stepper &optional base)
  `(lrec-fn (lambda (x next-v)
              (declare (ignorable x))
              (flet ((next () (funcall next-v)))
                ,stepper))
            ,base))

;; Another Schemism is to do things like (define foo
;; (compute-function)), which we tend not to do in Common Lisp, but
;; here's a helper:

(defmacro setfun (name form)
  `(progn
     (setf (fdefinition ',name) ,form)
     ',name))

;; Here's a helper to make things a bit more concise:

(defmacro deflrec (name stepper &optional base)
  `(setfun ,name (lrec ,stepper ,base)))

;; And the first few examples:

(deflrec our-length (1+ (next)) 0)
(deflrec our-copy-list (cons x (next)))
(deflrec our-remove-duplicates (adjoin x (next)))

;; For the find-if/some functions, which take a predicate, we can
;; define an operator to again make things easier on the eye:

;; The filter stepper forms can also use FN.

(defmacro deffilter (name stepper &optional base)
  `(setfun ,name
           (lambda (fn-v lst)
             (flet ((fn (&rest args)
                      (apply fn-v args)))
               (funcall (lrec ,stepper ,base) lst)))))

;; And get concise definitions:

(deffilter our-find-if (if (fn x) x (next)))
(deffilter our-some (or (fn x) (next)))