Динамическая отправка

Эта статья о выборе реализации полиморфной операции. Информацию о динамической привязке см. в разделе Позднее связывание .

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

Объектно-ориентированные системы моделируют проблему как набор взаимодействующих объектов, которые выполняют операции, называемые по имени. Полиморфизм — это явление, при котором каждый из взаимозаменяемых объектов выполняет операцию с одним и тем же именем, но, возможно, отличается по поведению. В качестве примера, Файловый объект и базы данных имеют Оба объекта StoreRecord метод, который можно использовать для записи кадровой записи в хранилище. Их реализации различаются. Программа содержит ссылку на объект, который может быть либо Файловый объект или Объект базы данных . Что это такое, возможно, было определено настройками времени выполнения, и на этом этапе программа может не знать или не знать, что это такое. Когда программа вызывает StoreRecord объекта, что-то должно выбрать, какое поведение будет применено. Если рассматривать ООП как отправку сообщений объектам, то в этом примере программа отправляет сообщение StoreRecord сообщение объекту неизвестного типа, оставляя системе поддержки времени выполнения отправку сообщения нужному объекту. Объект реализует любое поведение, которое он реализует.

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

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

Однократная и многократная отправка

Основная статья: Множественная отправка

Выбор версии метода для вызова может основываться либо на одном объекте, либо на комбинации объектов. Первый вариант называется одиночной диспетчеризацией и напрямую поддерживается распространенными объектно-ориентированными языками, такими как Smalltalk , C++ , Java , C# , Objective-C , Swift , JavaScript и Python . В этих и подобных языках можно вызвать метод деления с синтаксисом, напоминающим

dividend.divide(divisor)  # dividend / divisor

где параметры являются необязательными. Это рассматривается как отправка сообщения с именем делить с параметром делитель ​ дивиденды . Реализация будет выбрана только на основе , тип дивиденда (возможно рациональный , с плавающей запятой , матрица ), независимо от типа или значения делитель .

Напротив, некоторые языки отправляют методы или функции на основе комбинации операндов; в случае деления типы дивиденды и делитель вместе определяют, какой деления будет выполнена операция . Это известно как множественная отправка . Примерами языков, поддерживающих множественную диспетчеризацию, являются Common Lisp , Dylan и Julia .

Механизмы динамической диспетчеризации

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

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

Некоторые языки предлагают гибридный подход.

Динамическая диспетчеризация всегда требует дополнительных затрат, поэтому некоторые языки предлагают статическую диспетчеризацию для определенных методов.

реализация на С++

C++ использует раннее связывание и предлагает как динамическую, так и статическую отправку. Форма отправки по умолчанию — статическая. Чтобы получить динамическую отправку, программист должен объявить метод как виртуальный .

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

Перегрузка типов не приводит к динамической отправке в C++, поскольку язык учитывает типы параметров сообщения как часть формального имени сообщения. Это означает, что имя сообщения, которое видит программист, не является формальным именем, используемым для привязки.

Реализация Go, Rust и Nim

В Go , Rust и Nim используется более универсальный вариант раннего связывания. Указатели Vtable передаются вместе со ссылками на объекты как «толстые указатели» («интерфейсы» в Go или «объекты свойств» в Rust). ).

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

Термин «толстый указатель» просто относится к указателю с дополнительной связанной информацией. Дополнительной информацией может быть указатель виртуальной таблицы для динамической отправки, описанной выше, но чаще всего это размер связанного объекта для описания, например, среза .

См. также: Умный указатель

Реализация Smalltalk

Smalltalk использует диспетчер сообщений на основе типов. Каждый экземпляр имеет единственный тип, определение которого содержит методы. Когда экземпляр получает сообщение, диспетчер ищет соответствующий метод в сопоставлении сообщений и методов для этого типа, а затем вызывает этот метод.

Поскольку тип может иметь цепочку базовых типов, этот поиск может оказаться дорогостоящим. Казалось бы, наивная реализация механизма Smalltalk имеет значительно более высокие накладные расходы, чем реализация C++, и эти накладные расходы будут возникать для каждого сообщения, получаемого объектом.

Реальные реализации Smalltalk часто используют метод, известный как встроенное кэширование. это делает отправку метода очень быстрой. Встроенное кэширование в основном хранит предыдущий адрес метода назначения и класс объекта места вызова (или несколько пар для многостороннего кэширования). Кэшированный метод инициализируется наиболее распространенным целевым методом (или просто обработчиком промахов в кэше) на основе селектора метода. Когда во время выполнения достигается место вызова метода, он просто вызывает адрес в кеше. (В генераторе динамического кода этот вызов является прямым вызовом, поскольку прямой адрес обратно исправляется логикой промаха в кэше.) Код пролога в вызываемом методе затем сравнивает кэшированный класс с фактическим классом объекта, и если они не совпадают , выполнение переходит к обработчику промахов в кэше, чтобы найти правильный метод в классе. Быстрая реализация может иметь несколько записей в кэше, и часто требуется всего пара инструкций, чтобы обеспечить выполнение правильного метода при первоначальном промахе в кэше. Обычным случаем будет совпадение кэшированного класса, и выполнение просто продолжится в методе.

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

Поскольку Smalltalk является рефлексивным языком, многие реализации позволяют превращать отдельные объекты в объекты с помощью динамически генерируемых таблиц поиска методов. Это позволяет изменять поведение объекта отдельно для каждого объекта. целая категория языков, известных как языки, основанные на прототипах Из этого выросла , наиболее известными из которых являются Self и JavaScript . Тщательная разработка кэширования диспетчеризации методов позволяет даже языкам, основанным на прототипах, обеспечивать высокопроизводительную диспетчеризацию методов.

Многие другие динамически типизированные языки, включая Python , Ruby , Objective-C и Groovy, используют аналогичные подходы.

Пример на Python

class Cat:
    def speak(self):
        print("Meow")

class Dog:
    def speak(self):
        print("Woof")


def speak(pet):
    # Dynamically dispatches the speak method
    # pet can either be an instance of Cat or Dog
    pet.speak()

cat = Cat()
speak(cat)
dog = Dog()
speak(dog)

Пример на С++

#include <iostream>

// make Pet an abstract virtual base class
class Pet {
public:
    virtual void speak() = 0;
};

class Dog : public Pet {
public:
    void speak() override
    {
        std::cout << "Woof!\n";
    }
};

class Cat : public Pet {
public:
    void speak() override
    {
        std::cout << "Meow!\n";
    }
};

// speak() will be able to accept anything deriving from Pet
void speak(Pet& pet)
{
    pet.speak();
}

int main()
{
    Dog fido;
    Cat simba;
    speak(fido);
    speak(simba);
    return 0;
}

См. также

• Функция многоверсионности
• Перегрузка функций
• Передача сообщений
• Переопределение метода
• Двойная отправка
• Привязка имени

Дальнейшее чтение

• Липпман, Стэнли Б. (1996). Внутри объектной модели C++ . Аддисон-Уэсли . ISBN  0-201-83454-5 .
• Гребер, Маркус; Ди Джеронимо-младший, Эдвард «Эд»; Пол, Матиас Р. (2 марта 2002 г.) [24 февраля 2002 г.]. «Информация GEOS/NDO для RBIL62?» . Группа новостей : comp.os.geos.programmer . Архивировано из оригинала 20 апреля 2019 г. Проверено 20 апреля 2019 г. […] Причина, по которой Geos требует 16 прерываний, заключается в том, что схема используется для преобразования межсегментных («далеких») вызовов функций в прерывания без изменения размера кода. Причина, по которой это делается, заключается в том, что «что-то» (ядро) может подключиться к каждому межсегментному вызову, выполняемому приложением Geos, и убедиться, что правильные сегменты кода загружаются из виртуальной памяти и блокируются. В терминах DOS это можно сравнить с оверлейным загрузчиком, но его можно добавить, не требуя явной поддержки со стороны компилятора или приложения. Происходит примерно следующее: […] 1. Компилятор реального режима генерирует такую ​​инструкцию: CALL <segment>:<offset> -> 9A <offlow><offhigh><seglow><seghigh> с <seglow>< seghigh> обычно определяется как адрес, который должен быть исправлен во время загрузки в зависимости от адреса, по которому был размещен код. […] 2. Компоновщик Geos превращает это во что-то другое: INT 8xh -> CD 8x […] DB <seghigh>,<offlow>,<offhigh> […] Обратите внимание, что это снова пять байт, поэтому это может быть установил "на место". Теперь проблема в том, что для прерывания требуется два байта, а для инструкции CALL FAR нужен только один. В результате 32-битный вектор (<seg><ofs>) необходимо сжать до 24 бит. […] Это достигается двумя вещами: во-первых, адрес <seg> кодируется как «дескриптор» сегмента, чей наименьший полубайт всегда равен нулю. Это экономит четыре бита. Кроме того, […] оставшиеся четыре бита попадают в младший полубайт вектора прерывания, создавая таким образом что-то от INT 80h до 8Fh. […] Обработчик прерываний для всех этих векторов один и тот же. Он «распакует» адрес из нотации в три с половиной байта, найдет абсолютный адрес сегмента и перенаправит вызов после выполнения загрузки виртуальной памяти... Возврат из вызова также будет введите соответствующий код разблокировки. […] Младший полубайт вектора прерывания (80h–8Fh) содержит биты с 4 по 7 дескриптора сегмента. Биты от 0 до 3 дескриптора сегмента (по определению дескриптора Geos) всегда равны 0. […] все API Geos работают по схеме «оверлей» […]: когда приложение Geos загружается в память, загрузчик автоматически заменить вызовы функций в системных библиотеках соответствующими вызовами на основе INT. В любом случае, они не постоянны, а зависят от дескриптора, назначенного сегменту кода библиотеки. […] Первоначально Геос планировалось преобразовать в защищенный режим очень рано […], а реальный режим является только «устаревшим вариантом» […] почти каждая строка ассемблерного кода готова для него […]
• Пол, Матиас Р. (11 апреля 2002 г.). «Re: [fd-dev] АНОНС: CuteMouse 2.0 альфа 1» . freedos-dev . Архивировано из оригинала 21 февраля 2020 г. Проверено 21 февраля 2020 г. […] в случае таких искаженных указателей […] много лет назад мы с Акселем думали о том, как использовать *одну* точку входа в драйвер для нескольких векторов прерываний (поскольку это сэкономило бы нам много места для несколько точек входа и более или менее идентичный код кадрирования запуска/выхода во всех них), а затем внутренне переключиться на разные обработчики прерываний. Например: 1234h:0000h […] 1233h:0010h […] 1232h:0020h […] 1231h:0030h […] 1230h:0040h […] все указывают на одну и ту же точку входа. Если вы подключите INT 21h к 1234h:0000h и INT 2Fh к 1233h:0010h и т. д., все они пройдут через одну и ту же «лазейку», но вы все равно сможете различать их и внутренне разветвляться на разные обработчики. Представьте себе «сжатую» точку входа в заглушку A20 для загрузки HMA . Это работает до тех пор, пока ни одна программа не начнет выполнять магию сегмента: смещения. […] Сравните это с противоположным подходом, заключающимся в наличии нескольких точек входа (возможно, даже поддерживающих IBM Interrupt Sharing Protocol ), который потребляет гораздо больше памяти, если вы перехватываете много прерываний. […] Мы пришли к выводу, что на практике это, скорее всего, не сохранится, потому что никогда не знаешь, нормализуют или денормализуют указатели другие драйверы и по каким причинам. […] (Примечание. Что-то похожее на « толстые указатели » специально для : Intel сегмента реального режима адресация со смещением на процессорах x86 , содержащая как намеренно денормализованный указатель на общую точку входа кода, так и некоторую информацию, позволяющую различать разные вызывающие программы. Хотя в открытой системе нельзя полностью исключить сторонние экземпляры, нормализующие указатели (в других драйверах или приложениях) , эту схему можно безопасно использовать на внутренних интерфейсах, чтобы избежать избыточных последовательностей входных кодов. .)
• Брайт, Уолтер (22 декабря 2009 г.). «Самая большая ошибка Си» . Цифровой Марс . Архивировано из оригинала 8 июня 2022 г. Проверено 11 июля 2022 г. [1]
• Холден, Дэниел (2015). «Библиотека толстых указателей» . Виолончель: Высокий уровень C. Архивировано из оригинала 11 июля 2022 г. Проверено 11 июля 2022 г.