Filtered functions

I am very excited that I can finally annouce a public release of filtered functions, an extension of generic functions that Charlotte Herzeel, Jorge Vallejos, and myself have developed some time ago and that we are very excited about because it seems to be quite powerful in a number of very different scenarios. It took a while to release filtered functions, because it is a quite non-trivial extension of generic functions and requires a CLOS MOP implementation that is compliant with the AMOP specification to quite a deep level. Therefore, this required some serious preparation in the form of a much improved Closer to MOP library, that I released today as well.

You can find filtered functions and Closer to MOP at the Closer project website. Below you will find a general overview of the concept.

Filtered functions are an extension of generic functions, extended with a filtering step where the arguments received by a generic function are mapped to other values based on user-defined mapping functions. Those filtered values are then used to perform the actual selection and execution of applicable methods. Nevertheless, the methods that are eventually executed see the original objects as received by the generic function, and not the filtered ones.

Here are some examples to illustrate the expressive power of filtered functions.

Factorial

In order to be able to use filtered functions, we need to have filter functions that map received arguments to values that we actually want to base our dispatch on. For the factorial function, we want to distinguish between negative and positive numbers, and the number zero. For that we can just use the Common Lisp function SIGNUM that returns +1 for positive numbers, -1 for negative numbers, and just 0 for the number 0. The filtered function FAC can thus be defined as follows.

(define-filtered-function fac (n)
  (:filters (:sign #'signum)))

DEFINE-FILTERED-FUNCTION is exactly like DEFGENERIC, except that it can also define one or more filters. Here, it defines a filter with the name :SIGN wich specifices that the function SIGNUM is to be used for filtering.

We can now define methods for FAC:

(defmethod fac :filter :sign ((n (eql +1)))
  (* n (fac (- n 1))))

(defmethod fac :filter :sign ((n (eql 0)))
  1)

(defmethod fac :filter :sign ((n (eql -1)))
  (error "Fac not defined for negative numbers."))

Here, we use the qualifiers :FILTER :SIGN in the method definitions to indicate that we indeed want to use the :SIGN filter for method selection. We then use EQL specializers to ensure that the method definitions are applicable for the three different cases that SIGNUM yields. Remember that the method bodies always see the original arguments, not the filtered ones, and this is why the FAC methods can do the correct computations.

State pattern

Filtered functions can be used to dispatch methods based on the state of an argument passed to a filtered function, which enables expressing State-like idioms. Assume the following simple CLOS class is defined for implementing a stack.

(defconstant +stack-size+ 10)

(defclass stack ()
  ((contents :initform (make-array +stack-size+)
             :reader stack-contents))
   (index :initform 0
          :accessor stack-index)))

Instances of this class have three different states: Such a stack can either be empty, or full, or anywhere in between (in 'normal' state). We can express this as a function that recognizes the state of a stack.

(defun stack-state (stack)
  (cond ((<= (stack-index stack) 0) 'empty)
        ((>= (stack-index stack) +stack-size+) 'full)
        (t 'normal)))

It is now straightforward to use stack-state in a filter named :state for the typical stack operations.

(define-filtered-function stack-push (stack value)
  (:filters (:state #'stack-state)))

(define-filtered-function stack-pop (stack)
  (:filters (:state #'stack-state)))

(define-filtered-function stack-emptyp (stack)
  (:filters (:state #'stack-state)))

We can now group the behavior of a stack according to its different states. Note that for 'normal' state, we do not need to mention the use of any filter here, because the methods are not specialized on anything specific anyway. (Filtered functions always allow for 'regular' methods alongside the filtered methods.)

;;; Normal state

(defmethod stack-push (stack value)
  (setf (aref (stack-contents stack)
              (stack-index stack))
        value)
  (incf (stack-index stack)))

(defmethod stack-pop (stack)
   (decf (stack-index stack))
   (aref (stack-contents stack)
         (stack-index stack)))

(defmethod stack-emptyp (stack)
  nil)

;;; Empty state

(defmethod stack-pop :filter :state ((stack (eql 'empty)))
  (error "Stack is empty."))

(defmethod stack-emptyp :filter :state ((stack (eql 'empty)))
  t)

;;; Full state

(defmethod stack-push :filter :state ((stack (eql 'full)) value)
  (error "Stack is full."))

Note that we used a derived state function here, that determines the state of the stack based on some of its other properties. Since filter functions can be any functions, we could also use the reader of a slot as a filter function, and thus have the behavior of a filtered function depend on the explicit state of an object.

Filtered functions can do a lot more: As already mentioned, they can use more than one filter; filter functions can see all the arguments a generic function receives; and filters can be guarded, which means that methods that use a particular filter may be completely ignored if the arguments don't fulfil a certain predicate. You can read the paper Filtered Dispatch that I co-authored with Charlotte Herzeel, Jorge Vallejos and Theo D'Hondt for a more thorough introduction, background information and semantics, and which also includes an extensible metacircular Lisp interpreter as an example, based on implementing EVAL as a filtered function.