Multiple dispatch
As a multi-method is referred to methods of an object-oriented programming language, the choice is made not only by the type of an object, but by the dynamic types of multiple objects. This type of method selection is also referred to as multiple dispatch, multiple distribution '.
A distinction is the multiple distribution of the potential in many procedural programming languages overload in the methods are polymorphic with respect to the static types of its parameters.
While in classical OO languages such as Java exclusively the dynamic type of the implicit first parameter this is used, can be specialized in languages with multiple dispatch methods on the dynamic types of all its parameters. The overload offered by many (especially C-like ) compiled languages corresponds to a multiple dispatch at compile time. Interestingly, however, provide most scripting languages multi-methods in the form of overloading in favor of dynamic typing not to. (However, dynamic typing does not preclude multi-methods. )
The most well-known OO environment that has this ability is Common Lisp Object System ( CLOS ), but also languages like Dylan, Slate, Cecil, Guile, or Java descendant Nice offer the kind. In C it is possible to implement multi-methods as functors and templates in various ways.
- Set integer -range 2.2.4.1 method of the generic function intersection2 for calls with two parameters of the class
- 2.2.4.2 Additional methods for the generic function intersection2 for dealing with the empty set
Multi-methods in Common Lisp
Object-oriented programming ( OOP) with multi-methods differs in some respects fundamentally different from " one-dimensional object-oriented programming ." In Common Lisp multi-methods are based on three basic concepts that must be understood differently than, say, in Java:
- Classes: You are always defined without their own methods. The class definition belongs only the list of superclasses and the list of their slots ( = " member variables "). Later the Klassendefininition can no methods are added.
- 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 corresponding methods
- Methods: You know no implicit this parameter in the sense of an individual, this method calling object, otherwise it will also this2, this3 etc. would give. Instead, all raised objects like normal parameters in the parameter list of the method appear.
Practical example in Common Lisp
The following example uses multi-methods to implement the formation of the intersection of interoperable with three different amounts of internally represented.
Set representations
There are the following three implementations are supported for volumes:
Program code
Class definitions
For these three representations of the classes set -by- intension, set -by -extension and integer -range -set can be defined. The latter two are derived from the abstract class enumeratable -set, which in turn is as set -by- intension derived from the main class any- set.
The relationship of the classes is therefore as follows:
The implementation of the class hierarchy in Common Lisp is carried out in five different definitions.
Class any- set ( abstract )
Common Lisp: ( defclass ... )
Classes are declared in Common Lisp with ( defclass
( defclass any- set () ()) Class set -by- intension
This contains only the place predicate predicate as a function with values that can decide whether the argument passed 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 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 " ) as the first name (eg ext) and in most cases the desired name of the access function ( getter / setter ), called in Lisp " accessor ". In most cases even the name of the Intiialisierungsargumentes is after the keyword: initarg specified, which is used in the Instantierung to assign an initial value of the slot. In the sample program are the slot name: accessor and: initarg always identical.
It contains only the ext slot that contains a list of items:
( defclass set -by -extension ( enumerateable - set) ( (ext: accessor ext: initarg: ext ))) Class integer -range -set
This form stores of the closed Ahlen Full range from the smallest value and the largest value to.
( defclass integer -range set ( enumerateable - set) ( ( from: accessor from: initarg: from ) ( to: accessor to: initarg: to ))) The empty set
The empty set empty set is constructed as a constant instance of the class set -by -extension without any elements. The instantiation is done in Common Lisp using the function make -instance, specifying the class and Initialisierungsargumentes that in the above class definition: ie ext. For this argument here, the empty list nil is passed.
( defvar empty -set (make- instance ' set -by -extension: ext nil) ) Generic Functions
Now the definition of the generic function is enumeration for the class enumerateable -set as well as the generic function intersection2 for two arguments of type any- set. Generic functions put only the signature that they only define the type of the parameter, not the parameter names and they have no function body. The definitions announce the existence of ( concrete ) methods for the above or of them derived classes.
( defgeneric enumeration ( enumerateable - set)) ( defgeneric intersection2 (any set any- set)) Enumeration methods of the generic function
These two methods are no multi-methods. In Java, they would simply Enumeration enumeration (); be declared as a class SetByExtension methods. enumeration provides a list of the elements of an indirect instance of enumerateable -set, ie 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)) Specific methods of the generic function intersection2
Common Lisp: functions and macros
( remove- if-not ... )
Takes a function and a list. The function is applied sequentially to each element of the list. It returns a new list of all elements for which the function has "true" delivered.
( intersection ... )
Makes a list of the intersection of the elements of all the passed list. ( intersection ' (1 2 3 ) ' ( 2 3 4) ) provides, for example, ' (3: 2 ).
(lambda ... )
Takes a parameter list and an expression in which the specified list parameters may occur. It returns an anonymous function that can be called with an appropriate argument list and calculates the given expression with this.
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 this case is from the two predicates of a and ; ; b a new predicate composed by ANDing and ; ; the result instance of the class SET -BY- INTENSION so ; ; initialized: (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 ) ) ( b intersection2 a) ); Return to the commutative case ( defmethod intersection2 ((a enumerateable - set) ( b enumerateable - set)) (make- instance ' set -by -extension : ext ( intersection ( enumeration a) ( enumeration b )))) Set integer -range method of the generic function intersection2 for calls with two parameters of the class
Although this case is already covered by the third method above, it makes sense here to provide a more specific method to regain a result of class integer -range set, since their representation is compact.
( defmethod intersection2 ((a integer -range set) ( b integer -range set)) ; ; The maximum of the lower N and M of the mininum ; ; Ceilings formed. Now, if n> m applies, the intersection ; ; empty, otherwise an instance of class INTEGER RANGE SET with the ; ; Limits of N and 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 dealing with the empty set
Common Lisp: The eql - specializer
Common Lisp can methods of a generic function specialize not only in classes, but also to a single instance.
For this is not indicated as the type of the parameter a class but the expression ( eql
The following two methods is by using a eql - Specializers (see box) ensures that the intersection of the empty set and an arbitrary amount without further investigation is the empty set itself:
( 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. To facilitate the dialogue with Common Lisp, you have to make the definition of suitable methods for predefined by the system generic function print -object which attracts the Lisp system to represent the quantities in the output.
( 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 ))) example of use
Common Lisp: (loop ... )
The macro loop is a powerful iteration. loop loops can usually be read naively, to capture their content. The example on the left can be translated as:
- " N is a prime number, if applicable, for each natural number of 2 to the square root of N, the remainder of n / i is not null"
Previously, the condition is still set as the number 1 is not a prime number in the mathematical sense.
The overall functionality is seen from the following application example.
The set of all prime numbers can be represented by the predicate prime.
( defun prime (s) ( when ( > n 1) (loop for i from 2 to ( n isqrt ) never ( eql 0 (mod n i)) ))) With this definition as a predicate, it is now possible to construct the set of all primes set -of- primes as an instance of set -by- intension:
(set 'set -of- primes (make- instance' set -by- intension : predicate # ' prime ) ) A second amount of first functions, the amount 100 of the integers from 1 to 100:
(set 'first -100 (make -instance ' integer -range -set: from 1 to 100) ) The intersection of both sets, so the prime numbers from 1 to 100, can now be calculated intersection2 by calling the generic function:
( intersection2 set -of- primes first- 100) There is the correct output
(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
- In the method call is not a single invoker syntactically recognizable because all the parameters are treated equally. There is no implicit this, or something similar.
- Methods are never directly invoked in Common Lisp but only indirectly via the generic function of the same name.
- The generic function performs the dispatch by the " hooked " methods. For this purpose, it first determines a sorted list on the specificity of the applicable methods and calls the method with the highest specificity. Applicable are all methods whose formal parameter either the classes of the current parameters match or are directly or indirectly the parent class.
- If the declaration of the generic function omitted, Common Lisp does that even once the first method definition is performed.
- The inheritance mechanisms within the class hierarchy with respect to the slots ( the "Member Variables") operate as in one-dimensional OOP.
- In this example, the Common Lisp Object System ( CLOS ) is presented only as far as is necessary for the understanding of multi-methods. The functionality of CLOS goes considerably further.
- Multi -dimensional methods can represent completely OOP, but not vice versa.