Мультиметод

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Мультиме́тод (англ. multimethod) или мно́жественная диспетчериза́ция (англ. multiple dispatch) — механизм, позволяющий выбрать одну из нескольких функций в зависимости от динамических типов или значений аргументов. Представляет собой расширение одиночной диспетчеризации (виртуальных функций), где выбор метода осуществляется динамически на основе фактического типа объекта, для которого этот метод был вызван. Множественная диспетчеризация обобщает динамическую диспетчеризацию для случаев с двумя или более объектами.

В явном виде мультиметоды поддерживаются «объектной системой Common Lisp’а» (CLOS).

Основы диспетчеризации[править | править вики-текст]

Разработчики программ, как правило, группируют исходный код в именованные блоки, называемые вызовами, процедурами, подпрограммами, функциями или методами. Код функции выполняется путём её вызова, который заключается в выполнении фрагмента кода, обозначенного её именем. При этом управление временно передаётся вызываемой функции; когда выполнение этой функции завершается, управление обычно передаётся обратно команде, следующей после вызова ввызывающей функции.

Имена функций обычно выбираются так, чтобы описывать их назначение. Иногда нужно назвать несколько функций одним и тем же именем - как правило из-за того, что они выполняют концептуально схожие задачи, но работают с разными типами входных данных. В таких случаях одного имени функции в месте её вызова недостаточно для определения вызываемого блока кода. В дополнение к имени в этом случае для выбора конкретной реализации функции также используются количество и тип аргументов вызываемой функции.

В более традиционных объектно-ориентированных языках программирования с одиночной диспетчеризацией при вызове метода (отправке сообщения в Smalltalk, вызове функции-члена в C++), один из его аргументов рассматривается особым образом и используется для определения того, какой из (потенциально многих) методов с этим именем должен быть вызван. Во многих языках,этот особый аргумент обозначается синтаксически: например, в ряде языков программирования специальный аргумент помещается перед точкой при вызове метода:

special.method (other, arguments, here) 

так что lion.sound() будет давать рев, а sparrow.sound() будет давать чириканье.

В отличии от них в языках с множественной диспетчеризацией выбираемый метод - это просто тот метод, аргументы которого совпадают с числом и типом аргументов в вызове функции. Здесь нет особого аргумента, который "владеет" функцией/методом, на которую ссылается конкретный вызов.

Common Lisp Object System (CLOS) является одной из первых и хорошо известных реализаций множественной диспетчеризации.

Типы данных[править | править вики-текст]

При работе с языками, в которых типы данных различаются во время компиляции, выбор среди доступных вариантов функций может происходить во время компиляции. Создание таких вариантов альтернативных функций для выбора во время компиляции обычно называют перегрузкой функций.

В языках программирования, которые определяют типы данных во время выполнения программы (позднее связывание), выбор среди вариантов функций должен происходить во время выполнения на основе динамически определяемых типов аргументов функций. Функции, альтернативные реализации которых выбираются таким образом, обычно называются мультиметодами.

Существуют некоторые затраты во время выполнения программы, связанные с динамической диспетчеризацией вызовов функций. В некоторых языках различие между перегрузкой функций и мультиметодами могут быть размыты, при этом компилятор определяет, может ли выбор вызываемой функции быть произведён во время компиляции, или потребуется более медленная диспетчеризация во время выполнения программы.

Практическое использование[править | править вики-текст]

Для того чтобы оценить, насколько часто множественная диспетчеризация используется на практике, Мушевичи (Muschevici) с соавторами[1] исследовал приложения, использующие динамическую диспетчеризацию. Они проанализировали девять приложений, в основном компиляторов, написанных на шести различных языках программирования: Common Lisp Object System, Dylan, Cecil, MultiJava, Diesel и Nice. Результаты показывают, что от 13% до 32% обобщенных функций используют динамическую типизацию одного аргумента, в то время как от 2,7% до 6,5% функций используют динамическую типизацию нескольких аргументов. Остальные 65%-93% обобщенных функций имеют один конкретный метод (перегружены), и, таким образом, не рассматривались как использующие динамическую типизацию своих аргументов. Кроме того, в исследовании сообщается, что от 2% до 20% обобщенных функций имели две, а 3%-6% имели три свои конкретные реализации. Доля функций с большим числом конкретных реализаций быстро уменьшалась.

Теория[править | править вики-текст]

Теория языков с мультивызовами впервые была разработана Кастаньей (Castagna) с соавторами, путём определения модели для перегруженных функций с поздним связыванием[2][3]. Это дало первую формализацию проблемы ковариации и контрвариации объектно ориентированных языков программирования[4] и решение проблемы бинарных методов[5].

Пример[править | править вики-текст]

Для лучшего понимания разницы между мультиметодами и одиночной диспетчеризацией можно продемонстрировать следующий пример. Представим себе игру, в которой, наряду с разнообразными другими объектами, присутствуют астероиды и космические корабли. Когда два каких-либо объекта сталкиваются, программа должна выбрать какой-либо определенный алгоритм действий, в зависимости от того, что столкнулось с чем.

Common Lisp[править | править вики-текст]

В языке с поддержкой мультиметодов, таком, как Common Lisp, код выглядел бы вот так:

(defgeneric collide (x y))

(defmethod collide ((x asteroid) (y asteroid))
  ;;астероид сталкивается с астероидом
  )

(defmethod collide ((x asteroid) (y spaceship))
  ;;астероид сталкивается с космическим кораблем
  )

(defmethod collide ((x spaceship) (y asteroid))
  ;;космический корабль сталкивается с астероидом
  )

(defmethod collide ((x spaceship) (y spaceship))
  ;;космический корабль сталкивается с космическим кораблем
  )

и аналогично для других методов. Явная проверка и "динамическое приведение типов" здесь не используются. 

При наличии множественной диспетчеризации традиционный подход к определению методов в классах и хранению их в объектах становится менее привлекательным, поскольку каждый метод collide-with относится к двум различным классам, а не к одному. Таким образом, специальный синтаксис для вызова метода, в общем случае, исчезает, так что вызов метода выглядит точно также, как вызов обычной функции, и методы группируются не по классам, а в обобщенных функциях.

Perl 6[править | править вики-текст]

В Perl 6, как и в предыдущих его версиях, используются проверенные идеи из других языков и системы типов, предлагающие убедительные преимущества в анализе кода со стороны компилятора и мощной семантике путём множественной диспетчеризации.

В нём есть как мультиметоды, так и мультиподпрограммы. Так как большинство операторов на самом деле является подпрограммами, есть также операторы с множественной диспетчеризацией.

Наряду с обычными ограничениями типов в нём есть также ограничения типа "где", что позволяет создавать очень специализированные подпрограммы.

subset Mass of Real where 0 ^..^ Inf; 
role Stellar-Object {
  has Mass $.mass is required;
  method name () returns Str {...};
}
class Asteroid does Stellar-Object {
  method name () { 'an asteroid' }
}
class Spaceship does Stellar-Object {
  has Str $.name = 'some unnamed spaceship';
}
my Str @destroyed = < obliterated destroyed mangled >;
my Str @damaged = « damaged 'collided with' 'was damaged by' »;

# We add multi candidates to the numeric comparison operators because we are comparing them numerically,
# but doesn't make sense to have the objects coerce to a Numeric type.
# ( If they did coerce we wouldn't necessarily need to add these operators. )
# We could have also defined entirely new operators this same way.
multi sub infix:« <=> » ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass <=> $b.mass }
multi sub infix:« <   » ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass <   $b.mass }
multi sub infix:«   > » ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass   > $b.mass }
multi sub infix:«  == » ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass  == $b.mass }

# Define a new multi dispatcher, and add some type constraints to the parameters.
# If we didn't define it we would have gotten a generic one that didn't have constraints.
proto sub collide ( Stellar-Object:D $, Stellar-Object:D $ ) {*}

# No need to repeat the types here since they are the same as the prototype.
# The 'where' constraint technically only applies to $b not the whole signature.
# Note that the 'where' constraint uses the `<` operator candidate we added earlier.
multi sub collide ( $a, $b where $a < $b ) {
  say "$a.name() was @destroyed.pick() by $b.name()";
}
multi sub collide ( $a, $b where $a > $b ) {
  # redispatch to the previous candidate with the arguments swapped
  samewith $b, $a;
}

# This has to be after the first two because the other ones
# have 'where' constraints, which get checked in the
# order the subs were written. ( This one would always match. )
multi sub collide ( $a, $b ){
  # randomize the order
  my ($n1,$n2) = ( $a.name, $b.name ).pick(*);
  say "$n1 @damaged.pick() $n2";
}

# The following two candidates can be anywhere after the proto,
# because they have more specialized types than the preceding three.

# If the ships have unequal mass one of the first two candidates gets called instead.
multi sub collide ( Spaceship $a, Spaceship $b where $a == $b ){
  my ($n1,$n2) = ( $a.name, $b.name ).pick(*);
  say "$n1 collided with $n2, and both ships were ",
  ( @destroyed.pick, 'left damaged' ).pick;
}

# You can unpack the attributes into variables within the signature.
# You could even have a constraint on them `(:mass($a) where 10)`.
multi sub collide ( Asteroid $ (:mass($a)), Asteroid $ (:mass($b)) ){
  say "two asteroids collided and combined into one larger asteroid of mass { $a + $b }";
}

my Spaceship $Enterprise .= new(:mass(1),:name('The Enterprise'));
collide Asteroid.new(:mass(.1)), $Enterprise;
collide $Enterprise, Spaceship.new(:mass(.1));
collide $Enterprise, Asteroid.new(:mass(1));
collide $Enterprise, Spaceship.new(:mass(1));
collide Asteroid.new(:mass(10)), Asteroid.new(:mass(5));

Python[править | править вики-текст]

В языках, которые не поддерживают множественную диспетчеризацию на уровне синтаксиса, таких как Python, как-правило воможно использовать множественную диспетчеризацию с помощью библиотек расширений. Например, модуль multimethods.py[6] реализует мультиметоды в духе CLOS в Python без изменения синтаксиса или ключевых слов языка.

from multimethods import Dispatch
from game_objects import Asteroid, Spaceship
from game_behaviors import ASFunc, SSFunc, SAFunc
collide = Dispatch()
collide.add_rule((Asteroid,  Spaceship), ASFunc)
collide.add_rule((Spaceship, Spaceship), SSFunc)
collide.add_rule((Spaceship,  Asteroid), SAFunc)
def AAFunc(a, b):
    """Behavior when asteroid hits asteroid"""
    # ...define new behavior...
collide.add_rule((Asteroid, Asteroid), AAFunc)
# ...later...
collide(thing1, thing2)

Функционально это очень похоже на пример с CLOS, но синтаксис соответствует стандартному синтаксису Python.

Путём использования декораторов Python 2.4, Гвидо ван Россум написал пример реализации мультиметодов[7] с упрощенным синтаксисом:

@multimethod(Asteroid, Asteroid)
def collide(a, b):
    """Behavior when asteroid hits asteroid"""
    # ...define new behavior...
@multimethod(Asteroid, Spaceship)
def collide(a, b):
    """Behavior when asteroid hits spaceship"""
    # ...define new behavior...
# ... define other multimethod rules ...

и далее определяется мультиметод декоратора.

Пакет PEAK-Rules реализует множественную диспетчеризацию с синтаксисом, подобным приведенному выше примеру.[8]

Эмуляция множественной диспетчеризации[править | править вики-текст]

Java[править | править вики-текст]

В языках, имеющих только одиночную диспетчеризацию, таких как Java, этот код будет выглядеть следующим образом (однако шаблон посетителя может помочь решить эту задачу):

 /* Example using run time type comparison via Java's "instanceof" operator */

 interface Collideable {
     /* Making this a class would not change the demonstration. */
     void collideWith(Collideable other);
 }

 class Asteroid implements Collideable {
     public void collideWith(Collideable other) {
         if (other instanceof Asteroid) {
             // Handle Asteroid-Asteroid collision.
         }
         else if (other instanceof Spaceship) {
             // Handle Asteroid-Spaceship collision.
         }
     }
 }

 class Spaceship implements Collideable {
     public void collideWith(Collideable other) {
         if (other instanceof Asteroid) {
             // Handle Spaceship-Asteroid collision.
         }
         else if (other instanceof Spaceship) {
             // Handle Spaceship-Spaceship collision.
         }
     }
 }

C[править | править вики-текст]

C не имеет динамической диспетчеризации, поэтому она должна быть реализована вручную в той или иной форме. Часто используется перечисление для идентификации подтипа объекта. Динамическая диспетчеризация может быть реализована путем поиска этого значения в таблице ветвлений указателей на функции. Вот простой пример, в C:

typedef void (*CollisionCase)();

void collision_AA() { /* обработка столкновения Астероид-Астероид */   };
void collision_AS() { /* обработка столкновения Астероид-Корабль */  };
void collision_SA() { /* обработка столкновения Корабль-Астероид */  };
void collision_SS() { /* обработка столкновения Корабль-Корабль */ };

typedef enum {
    asteroid = 0,
    spaceship,
    num_thing_types /* не является типом объекта, используется для нахождения количества объектов */
} Thing;

CollisionCase collisionCases[num_thing_types][num_thing_types] = {
    {&collision_AA, &collision_AS},
    {&collision_SA, &collision_SS}
};

void collide(Thing a, Thing b) {
    (*collisionCases[a][b])();
}

int main() {
    collide(spaceship, asteroid);
}

C++[править | править вики-текст]

На 2015 год, C++ поддерживает только одиночную диспетчеризацию, хотя поддержка множественной диспетчеризации рассматривается.[9] Методы обхода этого ограничения аналогичны: либо использование шаблона посетителя, либо динамического приведения типов:

 // Example using run time type comparison via dynamic_cast

 struct Thing {
     virtual void collideWith(Thing& other) = 0;
 };

 struct Asteroid : Thing {
     void collideWith(Thing& other) {
         // dynamic_cast to a pointer type returns NULL if the cast fails
         // (dynamic_cast to a reference type would throw an exception on failure)
         if (Asteroid* asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Asteroid-Asteroid collision
         } else if (Spaceship* spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Asteroid-Spaceship collision
         } else {
             // default collision handling here
         }
     }
 };

 struct Spaceship : Thing {
     void collideWith(Thing& other) {
         if (Asteroid* asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Spaceship-Asteroid collision
         } else if (Spaceship* spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Spaceship-Spaceship collision
         } else {
             // default collision handling here
         }
     }
 };

либо таблицы поиска указателей на методы:

#include <typeinfo>
#include <unordered_map>

typedef unsigned uint4;
typedef unsigned long long uint8;

class Thing {
  protected:
    Thing(const uint4 cid) : tid(cid) {}
    const uint4 tid; // type id

    typedef void (Thing::*CollisionHandler)(Thing& other);
    typedef std::unordered_map<uint8, CollisionHandler> CollisionHandlerMap;

    static void addHandler(const uint4 id1, const uint4 id2, const CollisionHandler handler) {
        collisionCases.insert(CollisionHandlerMap::value_type(key(id1, id2), handler));
    }
    static uint8 key(const uint4 id1, const uint4 id2) {
        return uint8(id1) << 32 | id2;
    }

    static CollisionHandlerMap collisionCases;

  public:
    void collideWith(Thing& other) {
        CollisionHandlerMap::const_iterator handler = collisionCases.find(key(tid, other.tid));
        if (handler != collisionCases.end()) {
            (this->*handler->second)(other); // pointer-to-method call
        } else {
            // default collision handling
        }
    }
};

class Asteroid: public Thing {
    void asteroid_collision(Thing& other)   { /*handle Asteroid-Asteroid collision*/ }
    void spaceship_collision(Thing& other)  { /*handle Asteroid-Spaceship collision*/}

  public:
    Asteroid(): Thing(cid) {}
    static void initCases();
    static const uint4 cid;
};

class Spaceship: public Thing {
    void asteroid_collision(Thing& other)   { /*handle Spaceship-Asteroid collision*/}
    void spaceship_collision(Thing& other)  { /*handle Spaceship-Spaceship collision*/}

  public:
    Spaceship(): Thing(cid) {}
    static void initCases();
    static const uint4 cid; // class id
};

Thing::CollisionHandlerMap Thing::collisionCases;
const uint4 Asteroid::cid  = typeid(Asteroid).hash_code();
const uint4 Spaceship::cid = typeid(Spaceship).hash_code();

void Asteroid::initCases() {
    addHandler(cid, cid, (CollisionHandler) &Asteroid::asteroid_collision);
    addHandler(cid, Spaceship::cid, (CollisionHandler) &Asteroid::spaceship_collision);
}

void Spaceship::initCases() {
    addHandler(cid, Asteroid::cid, (CollisionHandler) &Spaceship::asteroid_collision);
    addHandler(cid, cid, (CollisionHandler) &Spaceship::spaceship_collision);
}

int main() {
    Asteroid::initCases();
    Spaceship::initCases();

    Asteroid  a1, a2;
    Spaceship s1, s2;

    a1.collideWith(a2);
    a1.collideWith(s1);

    s1.collideWith(s2);
    s1.collideWith(a1);
}

Библиотека yomm11[10] позволяет автоматизировать этот подход.

В своей книге "Дизайн и эволюция C++" (англ. The Design and Evolution of C++) Страуструп упоминает, что ему нравится концепция мультиметодов и что он рассматривал возможность их реализации в C++, но утверждает, что ему не удалось найти пример эффективной (в сравнении с виртуальными функциями) их реализации и решить некоторые возможные проблемы неоднозначности типов. Он далее утверждает, что, хотя было бы хорошо реализовать поддержку этой концепции, она может быть приближенно реализована двойной диспетчеризацией или таблицей поиска на основе типов, как описано в примере на C/C++ выше, поэтому эта задача имеет низкий приоритет при разработке будущих версий языка.[11]

Реализация в языках программирования[править | править вики-текст]

Поддержка мультиметодов в других языках путём расширений:

Мультипараметрические классы типов в Haskell и Scala также могут быть использованы для эмуляции мультиметодов.

Примечания[править | править вики-текст]

  1. Muschevici, Radu; Potanin, Alex; Tempero, Ewan; Noble, James (2008). "Multiple dispatch in practice"Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications. OOPSLA '08 (Nashville, TN, USA: ACM): 563–582
  2. Giuseppe Castagna; Giorgio Ghelli & Giuseppe Longo (1995). "A calculus for overloaded functions with subtyping."Information and Computation (Academic press) 117 (1): 115–135
  3. Castagna, Giuseppe (1996). Object-Oriented Programming: A Unified Foundation. Birkhäuser. p. 384.
  4. Giuseppe Castagna (1995). "Covariance and contravariance: conflict without a cause"Transactions on Programming Languages and Systems (TOPLAS) (ACM) 17 (3). doi:10.1145/203095.203096
  5. Kim Bruce; Luca Cardelli; Giuseppe Castagna; Gary T. Leavens; Benjamin Pierce (1995). "On binary methods"Theory and Practice of Object Systems 1 (3)
  6. multimethods.py, Multiple dispatch in Python with configurable dispatch resolution by David Mertz, et al.
  7. Five-minute Multimethods in Python
  8. "PEAK-Rules 0.5a1.dev"Python Package Index. Retrieved 21 March 2014.
  9. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2216.pdf
  10. yomm11, Open Multi-Methods for C++11 by Jean-Louis Leroy.
  11. Stroustrup, Bjarne (1994). "Section 13.8". The Design and Evolution of C++. Indianapolis, IN, U.S.A: Addison Wesley. ISBN 0-201-54330-3.
  12. Steele, Guy L. (1990). "chapter 28". Common LISP: The Language. Bedford, MA, U.S.A: Digital Press.ISBN 1-55558-041-6.
  13. "Type classes: exploring the design space". 1997-05-02.
  14. "Elixir Lang | Getting Started | Modules". Retrieved2016-02-21.
  15. "Background and Goals". Retrieved 2008-04-13.
  16. "Visitor Pattern Versus Multimethods". Retrieved2008-04-13.
  17. "Cecil Language". Retrieved 2008-04-13.
  18. "How S4 Methods Work" (PDF). Retrieved 2008-04-13.
  19. "Methods"The Julia Manual. Julialang. Retrieved11 May 2014.
  20. "Multimethods in Groovy". Retrieved 2008-04-13.
  21. "Methods - LassoGuide 9.2". Retrieved 2014-11-11.
  22. "Perl 6 FAQ". Retrieved 2008-04-13.
  23. "Multiple Dispatch in Seed7". Retrieved 2011-04-23
  24. "Multimethods in Clojure". Retrieved 2008-09-04.
  25. "Multimethods in C# 4.0 With 'Dynamic'". Retrieved2009-08-20.
  26. "The Fortress Language Specification, Version 1.0"(PDF). Retrieved 2010-04-23.
  27. "TADS 3 System Manual". Retrieved 2012-03-19
  28. "Multiple dispatch".
  29. "Nim Manual". Retrieved 2015-05-08.