We continue our overview of Lisp features possibly missed by the beginner arriving from C++ with define-setf-expander.  In C, you had the concept of lvalues, assignable expressions such as a variable name or a pointer or array dereference.  In C++, you got to things like operator=, to make assignable operations to objects, or functions that returned a modifiable reference, which is usable as an lvalue.

In Lisp, a similar concept is the setf expander.  The setf macro is the common means by which an existing place has its value modified.  In that way, it fills the niche used by the assignment operator in C/C++.  Lisp also has things that you would think of as lvalues, setf cannot be used to assign a value to arbitrary expressions.

When the programmer wants to generalize setf to situations that are more complex than a simple setf-able place, define-setf-expander is one way to do it.  However, before you spend too much effort on this feature, check out defsetf, which I will cover in an upcoming post.  The defsetf macro, when the situation is simple enough to allow its use, is less complicated.

Here’s an example of define-setf-expander at work.  I define a function, max-value, that, when given an array of numbers, returns the largest number in the array, and a second return value holding the list of indices where those values can be found.  Imagine I also have a context where I want to replace all instances of the largest value in the array with a new value, using setf.  This is where a setf-expander is helpful.
 

(defun max-value (arr)
  "Returns 2 values.  The first is the maximum scalar value in the array of numbers.  The second is a list of lists of array indices."
  (labels
      ((convert-to-indices (row-major-index dimensions)
         (let (rv)
           (dolist (dim (reverse dimensions))
             (multiple-value-bind (div rem)
                 (floor row-major-index dim)
               (push rem rv)
               (setf row-major-index div)))
           rv)))

    (let* ((adim (array-dimensions arr))
           (num-elements (array-total-size arr))
           max-val indices)
      (dotimes (i num-elements)
        (let ((val (row-major-aref arr i)))
          (cond
            ((or (not max-val)
                 (> val max-val))
             (setf max-val val
                   indices (list (convert-to-indices i adim))))
            ((= val max-val)
             (push (convert-to-indices i adim) indices)))))
      (values max-val indices))))

(define-setf-expander max-value (arr &environment env)
  (multiple-value-bind (tmpspace old-values new-values
                                 setting-form getting-form)
      (get-setf-expansion arr env)
    (declare (ignore new-values setting-form))
    (let ((nval (gensym)))
      (values tmpspace
              old-values
              `(,nval)
              `(multiple-value-bind (val indices)
                   (max-value ,getting-form)
                 (declare (ignore val))
                 (dolist (one-ind indices)
                   (let ((linear-ind (apply 'array-row-major-index 
                                            ,getting-form one-ind)))
                     (setf (row-major-aref ,getting-form linear-ind)
                           ,nval)))
                 ,nval)
              `(max-value ,getting-form)))))

(defun demonstrate ()
  (let ((test-array (make-array '(4 3) 
                                :initial-contents '((0 1 2) 
                                                    (3 4 11) 
                                                    (11 7 8)
                                                    (9 10 11)))))
    (format t "Input array is: ~A~%" test-array)
    (multiple-value-bind (max-val indices)
        (max-value test-array)
      (format t "The maximum value is: ~A~%" max-val)
      (format t "Appearing at indices: ~A~%" indices))
    (format t "We setf the max-value to 50.~%")
    (setf (max-value test-array) 50)
    (format t "The array is now: ~A~%" test-array)))

CL-USER> (demonstrate)
Input array is: #2A((0 1 2) (3 4 11) (11 7 8) (9 10 11))
The maximum value is: 11
Appearing at indices: ((3 2) (2 0) (1 2))
We setf the max-value to 50.
The array is now: #2A((0 1 2) (3 4 50) (50 7 8) (9 10 50))
NIL

I will point out that the define-setf-expander macro is not something that I have frequently seen used, it’s a helpful tool for certain unusual cases, but is not commonly needed.  In most contexts, the programmer will write a special-purpose function to perform the effects of the setf, but when the setf is buried in an existing macro, this can be a useful way to re-use the macro without having to write special-case code all through it.

Continuing with the features of Lisp that a newcomer arriving from C++ might not have encountered, we look at define-modify-macro.  The rationale behind this is that certain operations that you might naively think of as modifying a data structure might actually create a new data structure.  This is generally not true of functions that act on objects, but may be true of functions that act on lists.

The C++ programmer is used to having explicit syntax to decide whether a variable is passed by value or by reference.  In Lisp, that is determined by the data type, rather than in the declaration of the function.  Numbers and symbols are passed by value.  If a parameter to a function evaluates as a number or a symbol, and the function modifies the parameter in its body, the effect of such modification is not propagated back to the caller.  On the other hand, if the parameter is a structure, object, or array, it is passed by reference, and modifications made to the contents of such entities will persist after the function returns.  Lists, though, are a bit complicated.  The thing that is passed is a pointer to a node in a singly-linked list.  If the list is modified, for instance by reversing its contents, the caller will still have a pointer to the same node, but now the forward links from that node won’t necessarily traverse the whole list.  You go from having a reference to the beginning of the list to having a reference to somewhere in the middle of the list, and the forward linkage means you can’t back up to see what has been moved ahead of your entry point.  Consequently, functions that modify lists will usually return a new list, rather than modifying the linkages of the passed list.

It’s a common mistake for a beginner to expect the sort function, when acting on a list as opposed to an array, to modify the list and make it sorted.  In fact, it returns a new list, and destroys the original list (the programmer cannot make any assumptions about what the input list looks like after sort is called).  The programmer is responsible for retaining the returned value and using it when the sorted list is desired.

The define-modify-macro macro allows you to construct the fairly common construct of calling a function on a list and assigning the result back to the place (think of this like a variable or pointer) that held the original list.  Here’s an example of how this might work with reverse.
 

(define-modify-macro reversef (&rest args)
  reverse)

(defun demonstrate ()
  (let* ((input-list '(9 1 3 2 4 8 7 6))
         (input-list-copy input-list))
    (format t "Input list: ~A~%" input-list)
    (reverse input-list)
    (format t "Input list after calling reverse: ~A~%" 
            input-list)
    (reversef input-list)
    (format t "Input list after calling reversef: ~A~%"
            input-list)
    (format t "Input list copy after calling reversef: ~A~%"
            input-list-copy)))

CL-USER> (demonstrate)
Input list: (9 1 3 2 4 8 7 6)
Input list after calling reverse: (9 1 3 2 4 8 7 6)
Input list after calling reversef: (6 7 8 4 2 3 1 9)
Input list copy after calling reversef: (9 1 3 2 4 8 7 6)
NIL

Notice that only the place passed to reversef sees the change.  The input-list-copy variable, while originally pointing at the same list as input-list, is a different place, and is not updated.  Where, originally, the two places pointed to the same list, they now point to different lists.

As we continue on this tour of less commonly used functions, we reach define-method-combination.  This is really very rarely used.  There’s almost always another way to achieve the ends that this macro provides.  Peter Seibel, in his book Practical Common Lisp, remarks that this macro is necessary in maybe 1% of 1% of cases.

What this macro allows the programmer to do is to define new method combination rules.  There are the standard rules, which I described earlier in call-next-method.  There are several combination rules that run all applicable primary methods and apply an operation to them, from the set +,and, or, list, append, nconc, min, max, and progn.  When none of these is suitable, define-method-combination is available.

So, let’s set up an example.  In this scenario, we’ve got a tax policy simulator running.  There are three categories of tax rule sets, for students, adults, and retired people.  Not all rule sets contain methods for all tax regulations.  So, we declare that, when computing a tax regulation for a student, we use the student rule, unless there is no student rule for that regulation, in which case we use the adult rule.  If there is no adult rule, we use the retired rule.  Similarly, computing on an adult first tries adult rules, then student rules, then finally retired rules.  Given this model, we created a class system of multiple inheritance as follows:
 

(defparameter *student-tax-rate* 0.05)
(defparameter *adult-tax-rate* 0.20)
(defparameter *retired-tax-rate* 0.10)

(defparameter *student-pension-rate* 0.00)
(defparameter *adult-pension-rate* 0.10)
(defparameter *retired-pension-rate* 0.00)

(defclass student-tax-rules ()
  ())

(defclass adult-tax-rules ()
  ())

(defclass retired-tax-rules ()
  ())

(defclass student-taxpayer (student-tax-rules adult-tax-rules retired-tax-rules)
  ((special-income-rules        :initform nil)
   (special-pension-rules       :initform nil)))

(defclass adult-taxpayer (adult-tax-rules student-tax-rules retired-tax-rules)
  ((special-income-rules        :initform nil)
   (special-pension-rules       :initform nil)))

(defclass retired-taxpayer (retired-tax-rules adult-tax-rules student-tax-rules)
  ((special-income-rules        :initform nil)
   (special-pension-rules       :initform nil)))

(defgeneric compute-income-tax (ruleset income)
  (:documentation "Compute tax on income."))

(defgeneric compute-pension-payments (ruleset income)
  (:documentation "Compute pension contributions."))

(defmethod compute-income-tax ((rules student-tax-rules) income)
  (/ (floor (* income *student-tax-rate* 100.0d0)) 100))

(defmethod compute-income-tax ((rules adult-tax-rules) income)
  (/ (floor (* income *adult-tax-rate* 100.0d0)) 100))

(defmethod compute-income-tax ((rules retired-tax-rules) income)
  (/ (floor (* income *retired-tax-rate* 100.0d0)) 100))

(defmethod compute-pension-payments ((rules student-tax-rules) income)
  (/ (floor (* income *student-pension-rate* 100.0d0)) 100))

(defmethod compute-pension-payments ((rules adult-tax-rules) income)
  (/ (floor (* income *adult-pension-rate* 100.0d0)) 100))

(defmethod compute-pension-payments ((rules retired-tax-rules) income)
  (/ (floor (* income *retired-pension-rate* 100.0d0)) 100))

(defun demonstrate ()
  (let ((obj-student (make-instance 'student-taxpayer))
        (obj-adult (make-instance 'adult-taxpayer))
        (obj-retired (make-instance 'retired-taxpayer)))

    (let ((student-income 15000.0d0))
      (format t "Student earns $~,2F at a summer job~%" student-income)
      (format t "~8TPays $~,2F in income tax~%"
              (compute-income-tax obj-student student-income))
      (format t "~8TPays $~,2F in pension contributions~%"
              (compute-pension-payments obj-student student-income)))

    (let ((adult-income 35000.0d0))
      (format t "Adult earns $~,2F at job~%" adult-income)
      (format t "~8TPays $~,2F in income tax~%"
              (compute-income-tax obj-adult adult-income))
      (format t "~8TPays $~,2F in pension contributions~%"
              (compute-pension-payments obj-adult adult-income)))

    (let ((retired-income 5000.0d0))
      (format t "Retiree earns $~,2F babysitting~%" retired-income)
      (format t "~8TPays $~,2F in income tax~%"
              (compute-income-tax obj-retired retired-income))
      (format t "~8TPays $~,2F in pension contributions~%"
              (compute-pension-payments obj-retired retired-income)))))

This produces an output like this:
 

CL-USER> (demonstrate)
Student earns $15000.00 at a summer job
        Pays $750.00 in income tax
        Pays $1275.00 in pension contributions
Adult earns $35000.00 at job
        Pays $7000.00 in income tax
        Pays $2975.00 in pension contributions
Retiree earns $5000.00 babysitting
        Pays $500.00 in income tax
        Pays $425.00 in pension contributions
NIL

I’ve made very simple tax rules, in a real simulator, things would be more complicated, and would likely be a function of work history, marital status, and so on, so changing two sets of rules to look similar would not be a simple matter of changing a single scalar parameter.

So, your simulator is running, you’re getting requests from politicians to simulate certain changes to the rules, and a new one comes in that doesn’t fit your data model.  The proposed change is to reduce the pension contributions in adults and shift them to students and retired people.  It is to be done by saying that the pension contribution for any person is 85% of the maximum pension contribution under any of the three sets of rules.  Where before a given taxpayer invoked only one method when asked to compute pension contributions, now we must compute all available rules, find the largest, and return 85% of that number.  We do this by defining a new method combination rule and declaring that pension contribution methods must use it.  I’m modifying the template in the CLHS page on define-method-combination, one that implements the standard method combination rules:
 

(define-method-combination pension-contrib-combination ()
  ((around (:around))
   (before (:before))
   (primary () :required t)
   (after (:after)))
  (flet ((call-methods (methods)
           (mapcar #'(lambda (method)
                       `(call-method ,method))
                   methods)))
    (let ((form (if (or before after (rest primary))
                    `(multiple-value-prog1
                         (progn ,@(call-methods before)
                                (* 0.85 
                                   (funcall 'max 
                                            ,@(call-methods primary))))
                       ,@(call-methods (reverse after)))
                    `(call-method ,(first primary)))))
      (if around
          `(call-method ,(first around)
                        (,@(rest around)
                           (make-method ,form)))
          form))))

(defgeneric compute-pension-payments (ruleset income)
  (:method-combination pension-contrib-combination)
  (:documentation "Compute pension contributions."))

Now, when we run the test function, we get this output:
 

CL-USER> (demonstrate)
Student earns $15000.00 at a summer job
        Pays $750.00 in income tax
        Pays $1275.00 in pension contributions
Adult earns $35000.00 at job
        Pays $7000.00 in income tax
        Pays $2975.00 in pension contributions
Retiree earns $5000.00 babysitting
        Pays $500.00 in income tax
        Pays $425.00 in pension contributions
NIL

Now, you can run your simulation, present the results, and then return to the usual mode of running.  One warning: at least under SBCL v1.14, simply removing the :method-combination option from the defgeneric will not return the method combination rules to their standard behaviour in a running Lisp instance.  To reset the behaviour without reloading the Lisp image, you should load a new defgeneric with the :method-combination option set to standard.

Exception handling in Lisp is an interesting topic, with some interesting differences from the C++ model.  It’s best that conditions, restarts, and handlers all be discussed together, so here I will simply point you back at an earlier series of articles that provides a basic introduction to Lisp exceptions for the C++ programmer.

Next up is define-compiler-macro.  This provides the programmer with an optimization option that has no parallel in C++.  To begin, I’m going to point to the entry in the CLHS, which has a good example of when this might be useful.

What this macro does is to provide a way for a programmer to rewrite forms in the program based on information available at compile-time.  The substituted forms should be alternative ways at arriving at the same result, but presumably in a way that is more efficient given the context.  Note that this is not a way to specialize on information available at run-time, such as the types of variables, or their values, but is a way for the compiler to look at the way some forms are built up after macro substitution, and possibly improve the efficiency by conditionally rewriting those forms before the compiler acts on them.

One common use of this macro is in the context of expensive functions with no side-effects, being passed literal constants.  The programmer can use define-compiler-macro to move the calculations to compile-time, and so avoid the cost of performing that calculation every time the running program encounters it, while leaving the code intact in the case that the arguments are unknown at compile time.

As pointed out in the CLHS, the programmer may not use this to write optimizations of the Lisp language functions themselves, and is encouraged to restrict the implementation of define-compiler-macro forms to code that the programmer is responsible for maintaining.