Введение

Многократная отправка или мультиметоды — это особенность некоторых языков программирования, при которой функция или метод могут быть динамически выбраны для исполнения на основе типа во время выполнения (динамического) или, в более общем случае, какого-либо другого атрибута нескольких из их аргументов. Это обобщение однократной отправки (однодиспетчерского полиморфизма), где вызов функции или метода динамически выбирается на основе типа объекта, к которому метод был применен. Многократная отправка направляет динамический выбор к конкретной реализации функции или метода, используя совокупность характеристик одного или нескольких аргументов.

Понимание отправки

Разработчики компьютерного программного обеспечения обычно организуют исходный код в именованные блоки, называемые подпрограммами, процедурами, функциями или методами. Код в функции выполняется путем её вызова – выполнения фрагмента кода, ссылающегося на её имя. Это временно передает управление вызванной функции; когда выполнение функции завершено, управление обычно возвращается к инструкции в вызывающем коде, следующей за вызовом. Имена функций обычно выбираются так, чтобы отражать назначение функции. Иногда желательно присваивать нескольким функциям одно и то же имя, часто потому, что они выполняют концептуально схожие задачи, но оперируют с разными типами входных данных. В таких случаях, ссылки на имя при вызове функции недостаточно для идентификации блока кода, который должен быть выполнен. Вместо этого, число и тип аргументов вызова функции также используются для выбора одной из нескольких реализаций функции. В более традиционных, то есть языках объектно-ориентированного программирования с одинарной отправкой, при вызове метода (отправке сообщения в Smalltalk, вызове метода-члена в C++) один из его аргументов обрабатывается особым образом и используется для определения, какой из (потенциально многих) классов методов с таким именем должен быть применен. Во многих языках специальный аргумент указывается синтаксически; например, в ряде языков программирования специальный аргумент помещается перед точкой при вызове метода: special.method(other, arguments, here), так что lion.sound произведет рык, а sparrow.sound – чириканье. В отличие от этого, в языках с множественной отправкой выбранный метод – это просто тот, аргументы которого соответствуют числу и типу аргументов вызова функции. Нет специального аргумента, которому «принадлежит» функция/метод, выполняемый при конкретном вызове. Common Lisp Object System (CLOS) является ранним и хорошо известным примером множественной отправки. Еще одним заметным примером использования множественной отправки является язык программирования Julia. Множественную отправку следует отличать от перегрузки функций, в которой статическая информация о типах, такая как объявленный или выведенный тип терма (или базовый тип в языке с подтипированием), используется для определения, какая из нескольких возможностей будет использована в данном месте вызова, и это определение производится во время компиляции или компоновки (или в другое время до начала выполнения программы) и впоследствии остается неизменным для данного развертывания или запуска программы. Многие языки, такие как C++, предлагают надежную перегрузку функций, но не поддерживают динамическую множественную отправку (C++ допускает только динамическую одинарную отправку через использование виртуальных функций).

Типы данных

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

Проблемы

Есть несколько известных проблем с динамической диспетчеризацией, как одинарной, так и множественной. Хотя многие из этих проблем решены для одинарной диспетчеризации, которая является стандартной функцией в объектно-ориентированных языках программирования на протяжении десятилетий, они становятся более сложными в случае множественной диспетчеризации.

Выразительность и модульность

В большинстве популярных языков программирования исходный код поставляется и развертывается в виде функциональных блоков, которые мы здесь будем называть пакетами; фактическая терминология для этой концепции варьируется в зависимости от языка. Каждый пакет может содержать несколько определений типов, значений и функций, пакеты часто компилируются отдельно в языках с этапом компиляции, и может существовать нециклическая зависимость. Полная программа представляет собой набор пакетов, с главным пакетом, который может зависеть от нескольких других пакетов, а вся программа состоит из транзитивного замыкания зависимостей. Так называемая проблема выразительности связана со способностью кода в зависимом пакете расширять поведение (функции или типы данных), определенных в базовом пакете, из включающего пакета, не изменяя исходный код базового пакета. Традиционные объектно-ориентированные языки с одинарной отправкой упрощают добавление новых типов данных, но не новых функций; традиционные функциональные языки, как правило, имеют обратный эффект, а множественная отправка, при правильной реализации, позволяет и то, и другое. Желательно, чтобы реализация множественной отправки обладала следующими свойствами:

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

Эффективность

Хорошо известны эффективные способы реализации единой диспетчеризации, в том числе в языках программирования, которые компилируются в объектный код и связываются с низкоуровневым (не учитывающим язык) компоновщиком, в том числе динамически во время загрузки/запуска программы или даже под управлением кода приложения. Метод "vtable", разработанный в C++ и других ранних объектно-ориентированных языках (где каждый класс имеет массив указателей на функции, соответствующих виртуальным функциям этого класса), почти так же быстр, как и статический вызов метода, требующий O(1) накладных расходов и только одного дополнительного обращения к памяти даже в неоптимизированном случае. Однако метод vtable использует имя функции, а не тип аргумента в качестве ключа поиска и не масштабируется для случая множественной диспетчеризации. (Он также опирается на объектно-ориентированную парадигму, в которой методы являются характеристиками классов, а не самостоятельными сущностями, независимыми от какого-либо конкретного типа данных). Эффективная реализация множественной диспетчеризации остаётся актуальной исследовательской задачей.

Использование на практике

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

Примеры

Различие между множественной и одинарной отправкой может стать понятнее на примере. Представьте игру, в которой среди (видимых пользователю) объектов есть космические корабли и астероиды. Когда два объекта сталкиваются, программе может потребоваться выполнять разные действия в зависимости от того, что с чем столкнулось.