Multi-method
As a multi-method is called method of object-oriented programming , the selection is not only based on the type of hit the object, but on the basis of dynamic types of multiple objects. This type of method selection is also known as multiple dispatch ('multiple distribution').
A distinction must be made between the multiple distribution and the overloading possible in many procedural programming languages , in which methods are polymorphic with regard to the static types of their parameters.
While in classic object-oriented languages such as Java only the dynamic type of the implicit first parameter is this
used, languages with multiple dispatch methods can also specialize in the dynamic types of all their parameters . The overload offered by many (especially C -like) compiled languages corresponds to a multiple dispatch at translation time. Interestingly, most scripting languages do not offer multi-methods in the form of overloading in favor of dynamic typing . However, dynamic typing does not rule out multimethods.
The first and best-known object-oriented environment that has this capability is the Common Lisp Object System (CLOS), but languages such as Dylan , Slate , Cecil , Guile , Seed7 , Julia or the Java descendant Nice also offer this. In C ++ it is possible to implement multi-methods as functors and templates in different ways.
Multi-methods in Common Lisp
Object-oriented programming with multi-methods differs fundamentally from one-dimensional object-oriented programming in some points . In Common Lisp, multi-methods are based on three elementary concepts that are to be understood differently than e.g. B. in Java:
- Classes: They are always defined without their own methods. The class definition only includes the list of superclasses and the list of their slots (= "member variables"). Even later, no methods can be added to the class definition.
- Generic functions: Instead of a class, the methods are grouped under a generic function with the same name. The generic function itself is just a container for the associated methods.
- Methods: You do not know an implicit
this
parameter in the sense of a single object calling this method, because otherwise there would have to bethis2
,this3
etc. Instead, all addressed objects appear like normal parameters in the method's parameter list.
Practical example in Common Lisp
The following example uses multi-methods to implement the formation of the intersection with three internally differently represented sets in an interoperable manner.
Set representations
The following three implementations are to be supported for quantities:
- Representation through intension
- The element affiliation is given by a predicate :
- All elements for which is true belong to . The amount can be infinite. Is represented by an anonymous lambda expression .
- Representation by extension
- In this representation, all elements of the set are listed:
- Representation as an interval
- A connected interval from the set forms the set :
Program code
Class definitions
The classes set-by-intension
, set-by-extension
and are integer-range-set
defined for these three representations . The latter two are derived from the abstract class enumeratable-set
, which in turn is derived as set-by-intension
from the main class any-set
.
The relationship between the classes is therefore as follows:
any-set |
|||||||||||||||||||||
set-by-intension |
enumerateable-set |
||||||||||||||||||||
set-by-extension |
integer-range-set |
||||||||||||||||||||
The implementation of the class hierarchy in Common Lisp takes place in five individual definitions.
Class any-set
(abstract)
Common Lisp: (defclass …)
Classes are also declared in Common Lisp (defclass <superclasses> <slot-definitions>)
. <superclasses> is the list of superclasses and <slot-definitions> is a list of slot definitions.
(defclass any-set ()
())
class set-by-intension
This only contains the one-digit predicate predicate
as a function with a range of values , which decides whether the argument passed to it belongs to:
(defclass set-by-intension (any-set)
((predicate :accessor predicate :initarg :predicate)))
Class enumerateable-set
(abstract)
Their purpose is to have a common parent class for the classes set-by-extension
and integer-range-set
as a reference point for method definitions .
(defclass enumerateable-set (any-set)
())
class set-by-extension
Common Lisp: Slot Definitions
The definition of slots (in Java "member variables") first contains the name (for example ext
) and usually also the desired name of the access function (getter / setter), which is called "Accessor" in Lisp. In most cases, the name of the initialization argument is also :initarg
specified after the keyword , which is used during instantiation to assign an initial value to the slot. In the example program the slot name, the :accessor
and that are :initarg
always identical.
It only contains the slot ext
, which contains a list of elements:
(defclass set-by-extension (enumerateable-set)
((ext :accessor ext :initarg :ext)))
class integer-range-set
This form stores the smallest value from
and the largest value of the closed range of integers to
.
(defclass integer-range-set (enumerateable-set)
((from :accessor from :initarg :from)
(to :accessor to :initarg :to)))
The empty crowd
The empty set empty-set
is constructed as a constant instance of the class set-by-extension
with no elements. The instantiation takes place in Common Lisp by the function make-instance
specifying the class and the initialization argument that is called in the above class definition :ext
. The empty list is passed here for this argument nil
.
(defvar empty-set (make-instance 'set-by-extension :ext nil))
Generic functions
The generic function enumeration
for the class enumerateable-set
and the generic function intersection2
for two arguments of the type are now defined any-set
. Generic functions only define the signature , they only define the type of parameters, not the parameter names, and they have no function body. The definitions announce the existence of (concrete) methods for the named classes or classes derived from them.
(defgeneric enumeration (enumerateable-set))
(defgeneric intersection2 (any-set any-set))
Methods of the generic function enumeration
These two methods are not yet multi-methods. In Java they would simply be declared Enumeration enumeration();
as methods of a class SetByExtension
. enumeration
supplies an enumeration of the elements of an indirect instance of enumerateable-set
, i.e. direct instances of set-by-extension
and integer-range-set
.
(defmethod enumeration ((s set-by-extension))
(ext s))
(defmethod enumeration ((s integer-range-set))
(loop for i from (from s) to (to s) collect i))
Concrete methods of the generic function intersection2
Common Lisp: Functions and Macros
(remove-if-not …)
Takes over a function and a list. The function is applied to each element of the list in turn. A new list of all elements for which the function returned “true” is returned.
(intersection ...)
Forms a list with the intersection of the elements of all transferred lists. (intersection '(1 2 3) '(2 3 4))
delivers z. B. '(2 3)
.
(lambda …)
Adopts a parameter list and an expression in which the parameters named in the list may appear. It returns an anonymous function that can be called with a suitable list of arguments and uses this to calculate the transferred expression.
The five methods of the generic function intersection2
are all multi- methods .
(defmethod intersection2 ((a set-by-intension) (b enumerateable-set))
(make-instance 'set-by-extension
:ext (remove-if-not (predicate a)
(enumeration b))))
(defmethod intersection2 ((a set-by-intension) (b set-by-intension))
;; In diesem Fall wird aus den beiden Prädikaten von a und
;; b ein neues Prädikat durch UND-Verknüpfung zusammengesetzt und
;; die Ergebnis-Instanz der Klasse SET-BY-INTENSION damit
;; initialisiert:
(make-instance 'set-by-intension
:predicate (lambda (x)
(and (funcall (predicate a) x)
(funcall (predicate b) x)))))
(defmethod intersection2 ((a enumerateable-set) (b set-by-intension))
(intersection2 b a)) ; Rückführung auf den kommutativen Fall
(defmethod intersection2 ((a enumerateable-set) (b enumerateable-set))
(make-instance 'set-by-extension
:ext (intersection (enumeration a) (enumeration b))))
Method of the generic function intersection2
for calls with two parameters of the classinteger-range-set
Although this case is already covered by the fourth method above, it makes sense here to provide a more specific method in order to get a result of the class integer-range-set
again, since its representation is more compact.
(defmethod intersection2 ((a integer-range-set) (b integer-range-set))
;; Es wird das Maximum N der unteren und das Minimum M der
;; Obergrenzen gebildet. Falls nun N>M gilt, ist die Schnittmenge
;; leer, sonst eine Instanz der Klasse INTEGER-RANGE-SET mit den
;; Grenzen N und M
(let ((n (max (from a) (from b)))
(m (min (to a) (to b))))
(if (> n m)
empty-set
(make-instance 'integer-range-set :from n :to m))))
Additional methods for the generic function intersection2
for handling the empty set
Common Lisp: The eql
Specializer
Common Lisp can specialize methods of a generic function not only on classes, but also on a single instance. For this purpose, a class is not specified as the type of the parameter, but the expression (eql <instanz>)
. If the associated generic function is now called with exactly this instance, then this method is more specific than one that was defined in the same position with a suitable class and is called instead of this.
The following two methods use a eql
specializer (see box) to ensure that the intersection of the empty set and any set is the empty set itself without further investigation:
(defmethod intersection2 ((a (eql empty-set)) (b any-set))
empty-set)
(defmethod intersection2 ((a any-set) (b (eql empty-set)))
empty-set)
print-object
–Methods
With the above definitions, the functionality is fully implemented. In order to simplify the dialog with Common Lisp, the definition of suitable methods for the generic function predefined by the system print-object
, which the Lisp system uses to display the quantities for output , is now carried out .
(defmethod print-object ((s set-by-extension) stream)
(prin1 (ext s) stream))
(defmethod print-object ((s set-by-intension) stream)
(format stream "~A" (function-lambda-expression (predicate s))))
(defmethod print-object ((s integer-range-set) stream)
(format stream "(~A .. ~A)" (from s) (to s)))
Application example
Common Lisp: (loop … )
The macro loop
is a powerful iteration tool. loop
- Loops can mostly be read naively in order to grasp their content. The example on the left can be translated as follows:
- "N is a prime number if for every natural number from 2 to the root of n it is true that the remainder of n / i is never zero"
Before that, the condition is set because the number 1 is not a prime number in the mathematical sense.
The overall functionality can be seen in the following application example.
The set of all prime numbers can be represented by the predicate prime
.
(defun prime (n)
(when (> n 1)
(loop for i from 2 to (isqrt n)
never (eql 0 (mod n i)))))
With this definition as a predicate it is now possible to construct the set of all prime numbers set-of-primes
as an instance of set-by-intension
:
(set 'set-of-primes (make-instance 'set-by-intension
:predicate #'prime))
The second set is the set first-100
of whole numbers from 1 to 100:
(set 'first-100 (make-instance 'integer-range-set :from 1 :to 100))
The intersection of both sets, i.e. the prime numbers from 1 to 100, can now be intersection2
calculated by calling the generic function :
(intersection2 set-of-primes first-100)
The correct output takes place
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
Explanation
- No single calling instance is syntactically recognizable from the method call, since all parameters are treated in the same way. There is no such thing as implicit
this
or anything like that. - In Common Lisp, methods are never called directly, but only indirectly via the generic function of the same name.
- The generic function carries out the dispatch on "attached" methods. To do this, it first determines a list of the applicable methods sorted by specificity and calls the method with the highest specificity. All methods whose formal parameters either correspond to the classes of the current parameters or are directly or indirectly their parent class can be used.
- If the declaration of the generic function is omitted, Common Lisp does this itself as soon as the first method definition takes place.
- The inheritance mechanisms within the class hierarchy with regard to the slots ("member variables") work like one-dimensional object-oriented programming.
- In this example, the Common Lisp Object System (CLOS) is presented only as far as is necessary to understand multi-methods. The functionality of CLOS goes much further.
- Multi-methods can fully represent one-dimensional object-oriented programming, but not the other way around.
Individual evidence
- ^ Common Lisp - The Language. 2nd edition.
literature
- Common Lisp Standard - ANSI INCITS 226-1994 (R2004) ( Memento from September 27, 2009 in the Internet Archive )
- Patrick M. Krusenotto Functional Programming and Metaprogramming - Interactive in Common Lisp Springer 2016, ISBN 978-3-658-13743-4 .