December 04, 2009

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.


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)))

(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))
(incf (stack-index stack)))

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

(defmethod stack-emptyp (stack)

;;; Empty state

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

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

;;; 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.


Richard said...

Have you looked at Clojure's multimethods? They use a similar approach to dispatch, where a value is computed from the arguments by using a dispatch function, and the method is selected using isa? (a hierarchy-respecting equality functions).

I've used them to implement a state machine, which seems to ring true with your experience.

Jules said...

It's nice to see CL picking up some good ideas from Clojure.

Pascal Costanza said...

Just for completeness: We presented the paper "Filtered Dispatch" that describes filtered functions at the Dynamic Languages Symposium in Cyprus in July 2008 (where Rich Hickey also gave a keynote about Clojure). Back then, the multi-method facility in Clojure didn't incorporate a notion of per-function hierarchies. This came only later - the release of Clojure from December 2008 didn't have these hierarchies yet, but the first 'official' release with that feature is from March 2009. It is these kinds of hierarchies that CLOS already has, and that Clojure added only later, that make dynamic dispatch reliable and expressive. Before that, Clojure basically provided a form of predicate dispatch, with the disadvantages and drawbacks described in our paper, and only a very ad-hoc mechanism to solve them. It's nice to see that Clojure picked up some good ideas from Common Lisp here by now.

A remaining difference is that in Clojure multi-methods, you can only use one dispatch function, whereas in our approach, a filtered function can have several filters associated, without introducing any ambiguities. It's also not obvious to me how you can perform supercalls in Clojure (as with call-next-method), but maybe that's just not described in the place on the Clojure website where I would expect it.

We avoid ambiguity in the presence of multiple filters by taking the order into account in which they are mentioned in the definition of the filtered function. This is based on a similar idea previously described by Jim Newton and Christophe Rhodes, and you can find the relevant literature references in our paper.

Yes, the way multi-methods are done in Clojure by now are probably nice to work with.

Geoff Wozniak said...

Very nice extension. It's nice to be able to express more in function definitions.

Makes me wish I could have stuck around for the DLS when I was at ECOOP.