Prev: [ANN] New release of Closer to MOP (v0.6)
Next: Filtered functions
From: Pascal Costanza on 4 Dec 2009 17:08
Hi,

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 at the Closer project website at
http://common-lisp.net/project/closer/ - 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" at http://p-cos.net/documents/filtered-dispatch.pdf
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.


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
 | 
Pages: 1
Prev: [ANN] New release of Closer to MOP (v0.6)
Next: Filtered functions