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 thisused, 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 thisparameter in the sense of a single object calling this method, because otherwise there would have to be this2, this3etc. 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 :

${\ displaystyle M: = \ lbrace x | P (x) \ rbrace}$

All elements for which is true belong to . The amount can be infinite. Is represented by an anonymous lambda expression . ${\ displaystyle x}$ ${\ displaystyle P (x)}$ ${\ displaystyle M}$ ${\ displaystyle P}$

Representation by extension

In this representation, all elements of the set are listed:

{\ displaystyle M: ​​= \ lbrace 2,39, {\ text {HUT}}, {\ text {STOCK}}, {\ text {UMBRELLA}} \ rbrace}

Representation as an interval

A connected interval from the set forms the set :

{\ displaystyle \ mathbb {Z}}

{\ displaystyle M}

{\ displaystyle M: ​​= \ lbrace 10, \ dotsc, 20 \ rbrace}

Program code

Class definitions

The classes set-by-intension, set-by-extensionand are integer-range-setdefined for these three representations . The latter two are derived from the abstract class enumeratable-set, which in turn is derived as set-by-intensionfrom 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 predicateas a function with a range of values , which decides whether the argument passed to it belongs to: ${\ displaystyle \ lbrace w, f \ rbrace}$ ${\ displaystyle M}$

(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-extensionand integer-range-setas 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 :initargspecified after the keyword , which is used during instantiation to assign an initial value to the slot. In the example program the slot name, the :accessorand that are :initargalways 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 fromand 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-setis constructed as a constant instance of the class set-by-extensionwith no elements. The instantiation takes place in Common Lisp by the function make-instancespecifying 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-setand the generic function intersection2for 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. enumerationsupplies an enumeration of the elements of an indirect instance of enumerateable-set, i.e. direct instances of set-by-extensionand 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 intersection2are 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 class`integer-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-setagain, 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 eqlSpecializer

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 eqlspecializer (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 loopis 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. ${\ displaystyle n> 1}$

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-primesas an instance of set-by-intension:

(set 'set-of-primes (make-instance 'set-by-intension
                                   :predicate #'prime))

The second set is the set first-100of 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 intersection2calculated 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 thisor 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 .

Web links

Common Lisp HyperSpec

[1] Common Lisp - The Language. 2nd edition.

Multi-method

Multi-methods in Common Lisp

Practical example in Common Lisp

Set representations

Program code

Class definitions

Class any-set(abstract)

class set-by-intension

Class enumerateable-set(abstract)

class set-by-extension

class integer-range-set