Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

Реализация параметрического полиморфизма

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

        Языки программирования, лишённые полиморфизма, лишены и обобщённого программирования. В них для нового типа данных надо заново писать алгоритмы той же сортировки или поиска. Поэтому, задавая себе вопрос: «Какой язык программирования мне хочется выучить», узнавайте, есть ли в нём полиморфизм и обобщённое программирование.

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

Немного о параметрическом полиморфизме

        Некоторые читатели статьи о двухстековой модели памяти и обеспечению ею возврата объектов переменной длины отмечали, что подобная возможность приятная, но мелочь. Какие объекты у нас имеют переменную длину? Как правило, строки. Значит в программах или подпрограммах, которые занимаются обработкой строк, это пригодится. А в остальных случаях это не стоит того, чтобы ломать устои. «Раз это до сих пор никто не использует, значит это никому не нужно».

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

Полиморфизм через создание специализированных версий функций

        Допустим, нам нужна функция обмена значений между каким-то объектами. Пишем шаблонную функцию:
template <typename T>
void swap (T* arg1, T* arg2) {
	 T  tmp = *arg1;
	*arg1 = *arg2;
	*arg2 = tmp;
}
int main() {
	int  a=0;
	int  b=1;
	swap(&a,&b);
	cout << a;
	return 0;
}
        Затем в программе мы делает вызов этой функции с объектами типа char, int, long, float, double. Тогда при компиляции будет создана функция «swap» в нескольких версиях. Это можно увидеть при получении ассемблерного текста. Имя функции «swap» модифицируется таким образом, чтобы иметь в себе информацию об используемых типах. Например: «swap_char», «swap_int», «swap_long», «swap_float», «swap_double» (на самом деле в существующих компиляторах это не так, но для простоты опустим подробности). Допустим, типы char, int, long, float, double имеют соответственно размер 1, 4, 8, 4, 8 байтов. Вот как будет выглядеть стековый кадр таких функций:
Реализация параметрического полиморфизма
У каждой версии функции — свой размер стекового кадра.


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

        То есть единой функции «swap» не существует, а существуют её специализированные версии. Если в программе «swap» будет вызвана с 20 типами, то компилятор сгенерирует 20 вариантов этой функции.

Википедия: «Мономорфизация при компиляции шаблонов C++ является неизбежной, так как в системе типов языка отсутствует поддержка полиморфизма — полиморфный язык здесь является статической надстройкой над мономорфным ядром языка. Это приводит к кратному увеличению объёма получаемого машинного кода, что получило известность как «раздувание кода».

        Таким образом, просто создаётся иллюзия полиморфизма. А почему бы нет? Функция работает с разными типами? Работает. А детали реализации — они и есть детали, разработчик в них может не вдаваться. И не важно, что в крабовых палочках нет ничего от краба, главное, что их готовы покупать как крабовые.

        Подобный полиморфизм есть и в Rust, и в D, и в других языках. Вот пример из D:
auto add(T)(T lhs, T rhs) {
    return lhs + rhs;
}
        В обобщённой функции add два набора параметров: первый (в первых скобках) — для периода компиляции, когда создаются экземпляры функций. Второй — для времени исполнения. «T» в первых скобках — это переменная типа или типовая переменная, она ссылается на тип. В языках со статической типизацией она существует только в период компиляции. После мономорфизации (создания заточенных под конкретный тип версий функций) надобность в ней пропадает, во время исполнения её нет. В языках с динамической типизацией она существует и во время исполнения.

        Правда, есть одна проблема, которая перестаёт многим видеться проблемой — такой полиморфизм является одной из причин разбухания кода. Но когда даже телефоны имеют гигабайты памяти, то неудивительно, что на это махнули рукой. Такие программы не влезут в кэш процессора L1, ну да ладно — гигагерцы и гигабайты спасают.

        К такому полиморфизму есть один заковыристый вопрос. Спрашивается, как мне получить указатель на функцию «swap»? Ведь версий функций может быть и десять, и двадцать. А мне нужен один-единственный адрес, чтобы получить его, как параметр или возвратить, как результат. Т.е. чтобы указатель на функцию был объектом первого класса и позволял бы манипуляции в функциональном стиле. Но в «голом» виде этой функции не существует, поэтому не существует её адрес. Но является ли это проблемой? Дело в том, что этот вид полиморфизма — статический. Типы, которыми параметиризируются функции, известны во время компиляции. А раз так, то потребность в адресе функции удовлетворяется не адресом абстрактной «swap», а конкретной «swap_char», «swap_int» и т.д.

        Если же полиморфизм динамический, а не статический, то специализированные версии функции не создаются. В таком случае и выделение памяти под объекты происходит динамически. Поскольку длина этих объектов будет ясна в период исполнения, то где создаются эти объекты? Правильно, в «куче». Но у нас есть двухстековая модель памяти!

Реализация параметрического полиморфизма с помощью двух стеков

Полиморфизм с параметрами
        Параметрический полиморфизм позволяет полиморфной функции иметь единственное тело. Как отмечалось, в стеке такой функции хранятся лишь адреса полиморфных объектов, а сами объекты хранятся в отнюдь не шустрой «куче».

        Но двухстековая модель данных позволяет нам размещать в стеке объекты, размер которых известен лишь в момент исполнения. Вот поэтому она отлично совмещается с параметрическим полиморфизмом. Какие бы параметры ни поступили на вход функции, какого бы размера они ни были, какие локальные данные, соответствующие входным параметрам, ни поместили в стек, — со всем с этим легко справиться с помощью двух стеков. Потому что, несмотря на разницу в размерах входных типов, соблюдается дисциплина LIFO при получении и освобождении памяти.

        Но как это реализовать? Надо помнить, что самая лучшие функции — это те, которые устроены как чёрный ящик: связь с внешним миром они поддерживают через параметры. Как функция должна узнать, какие кокретно типы она в данный момент обслуживает? От этого зависит, какой набор подпрограмм будет применяться к параметрам и локальным переменным. Функции-конструкторы в зависимости от типа выделят память в стеке, другие функции произведут операции над данными. Выходит, что для решения этих проблем в функцию-чёрный-ящик должна быть передана переменная типа, а может и не одна. Тогда, узнав типы из переменных, полиморфная типа функция может и память выделить, и операции над данными произвести. Раз это будет делаться во время исполнения, то в это же время должна существовать и переменная типа. Вывод: у нас получилпсь динамическая типизация, а не статическая, к которой мы стремимся.

        А как же статическая типизация? Тут мой первоначальный оптимизм наткнулся на ограничения реальности. Терять преимущества статической типизации не входит в наши планы. Ведь если тип, переданный в функцию-чёрный-ящик, становится известным во время исполнения, то и некоторые ошибки будут выявлены именно в это время. К примеру, в функции сортировки контейнеров присутствует операция «меньше или равно» и мы решили их отсортировать. В одном случае — контейнер со строками, в другом — с комплексными числами. Будь у нас статическая типизация, мы бы получили ошибку при компиляции для второго варианта — для комплексных чисел операция «меньше или равно» не определена. Из-за динамической типизации про отсутствие оперции «меньше или равно» мы узнает, только запустив программу.

        Можно ли это как-то преодолеть? Да, но способ не очень практичный. Для этого перед вызовом функции должны быть взяты адреса всех функций и операций, которые будут применяться к данным типа-параметра и переданы полиморфной функции. Например, перед вызовом функции сортировки целых чисел надо взять указатель на операцию «меньше или равно» для целых чисел. Затем передать функции сортировки этот указатель в качестве одного из параметров. А вот при попытке взять указатель на операцию «меньше или равно» для комплексных чисел при компиляции будет выдано сообщение об ошибке: данная операция для данного типа отсутствует. Непрактичность этого способа в том, что таких указателей может потребоваться много. Нагромождения дополнительных параметров можно избежать, передавая их в функцию неявно. Но фактического сокращения их не произойдёт.

        Обойтись без дополнительных параметров при статической типизации можно созданием специализированных версий функций сиречь мономорфизацией. Т.е. мы возвращаемся к тому, с чего начали. Или с помощью inline-подстановок, если полиморфная функция невелика. Что лучше — дополнительные параметры или мономорфизация? Наверное, это зависит от способа оптимизации. Если компилятору дано задание изготовить быстрый исполняемый модуль, то приоритет — за моноформизацией. Если цель — компактный код, то решение с единственным телом полиморфной функции и дополнительными параметрами может оказаться лучшим.

Заключение

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

Опубликовано: 2019.02.22, последняя правка: 2019.03.21    16:34

Оцените

Отзывы

     2019/03/13 01:46, Comdiv          # 

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

Подобный полиморфизм есть и в Java

Это тоже не совсем так

     2019/03/13 17:33, Автор сайта          # 

Да, Вы правы. Перепутал, не Java имел в виду, а Rust. Функция Rust, параметризированная типом:
fn identity<T>(x: T) -> T { x}
ошибается именно в той части, которая ставится во главу угла в этой заметке
А как на Обероне пишут полиморфные функции? Как, допустим, описать функцию «меньше или равно», которая сравнивала бы пары и целых чисел, и плавающих, и строк? И чтоб при попытке сравнить несравнимое выдавалась синтаксическая ошибка? Типа того:
fn less_or_equal<T>(x, y: T) -> bool {...}

     2019/03/13 19:48, CD          # 

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

     2019/03/14 11:03, kt          # 

А я в свое время «разочаровался» в полиморфизме. Хотя в языке PL/1 полиморфизм через специализированные версии функций (т.н. «дженерики») был предложен 50 (!) лет назад. Т.е. в языке было допустимо описание функции типа:
DCL X GENERIC(A ENTRY(FIXED), B ENTRY(FLOAT));
Затем почему-то синтаксис изменили на такой:
DCL X GENERIC(A WHEN(FIXED), B WHEN(FLOAT));
Но в любом случае нетрудно доработать таблицу компилятора, чтобы он генерировал подстановку процедуры в зависимости от параметров. Но когда я уже собрался дорабатывать компилятор, выяснилось, что в реальных задачах мне полиморфизм негде применять. Точнее, там, где полиморфизм на самом деле нужен — в численных расчетах — он уже реализован самим языком. А остальные случаи — редкая экзотика, ради которой не стоит и огород городить. Правда, оговорюсь — это в стоящих передо мной задачах не нашлось применения, а не вообще во всех случаях.

     2019/03/14 12:57, Comdiv          # 

Почитал о generic в PL/I https://www.ibm.com/support/knowledgecenter/SSY2V3_4.5.0/com.ibm.ent.pl1.zos.doc/lr/lsh-generic.html
По первому впечатлению, это разновидность перегрузки функций по статическому типу входных аргументов, но в явном виде. Если это так, тогда это вообще не то.

     2019/03/14 13:06, Автор сайта          # 

Пишется схожим образом, что и в любом ООП.

Э-э-э-э-э... Вы не путайте функции, которые параметризуются параметром и ООП с его наследованием. Параметром таких функций может быть любые типы, не зависимо от того, наследуются они один от другого или нет. Лишь бы эти типы допускали операции, производимые на экземплярами типов внутри функции. Так что ООП и функции, параметризируемые типами, — это ортогональные, не пересекающиеся концепции. Ладно, ещё подождём, может Comdiv нам что-то напишет, ведь я, честно говоря, в Обероне так себе.

Синтаксической ошибки для несовместимых вещей не будет, только runtime

Жаль, конечно, что ошибки Boeing 737 MAX 8 выявляются только fly time.

редкая экзотика, ради которой не стоит и огород городить... Правда, оговорюсь – это в стоящих передо мной задачах не нашлось применения, а не вообще во всех случаях.

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

     2019/03/14 15:30, kt          # 

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

А для чего перегружать функции по типам аргументов как не для задач полиморфизма? Ну, ладно, пусть только задач "ad-hoc-полиморфизма".

     2019/03/15 01:59, Comdiv          # 

А для чего ...?

Для того, чтобы можно было применять один и тот же код для экземпляров разных типов одного подкласса. ad-hoc полиморфизм же сам по себе не нужен(+/-), в этом я с Вами согласен.

может Comdiv нам что-то напишет

Вы сами все написали в примечании, но не поняли, что ли. Иначе мне это трудно объяснить.

     2019/03/15 17:42, Автор сайта          # 

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

А функции, параметризированные типом, делают это для любого типа. Допустим внутри функции, параметризированном типом T, к объектам типа T применяются операции/функции «<» и «==».
fn less_or_equal<T>(x, y: T) -> bool {
if (x < y) return true;
if (x == y) return true;
return false;
}
Не важно, какого типа x и y, главное, что для типа T существуют операции/функции «<» и «==». Такой вид полиморфизма выводит на более высокий уровень абстракций. Не во всех языках он есть.

     2019/03/15 17:56, Comdiv          # 

Если для типа T существуют операции «<» и «==»", то этот тип принадлежит к подклассу сравниваемых типов и это прямо противоречит утверждению "не важно, какого типа x и y"

     2019/03/18 01:10, Автор сайта          # 

Вы принуждаете к отточенности формулировок :) Вам надо бы премию за улучшение контента :) Формулирую второй раз: «Для любого типа T, для которого существуют операции «<» и «==», будет определена функция
fn less_or_equal<T>(x, y: T) -> bool
При этом типы конкретные типы T1, T2, ... Tn могут не иметь ничего общего между собой, им не нужно иметь общего предка».

Ещё вопрос к Вам. Я правильно понял, что в Обероне есть полиморфизм подтипов, но параметрического полиморфизма в нём нет?

     2019/03/19 12:38, Comdiv          # 

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

"Я правильно понял, что в Обероне есть полиморфизм подтипов, но параметрического полиморфизма в нём нет"
Для того, чтобы понять ответ на этот вопрос, нужно понимать разницу между термином и понятием. С точки зрения терминологии, нет там ни того, ни другого. С точки зрения понятий там есть и то и другое. Если Вы понимаете, как используются полиморфные функции в C, то, на первый взгляд, должны бы понимать, как это может быть использовано в Oberon или в любых ООП-языках. В Oberon то, что называют полиморфными функциями, используется разработчиками на практике. Естественно, не так и не в той же степени, что в C++ или в любой другом языке.

     2019/03/20 14:37, rst256          # 

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

И если ввести особый тип указатель типа void* с размером, работу по передаче размера можно будет передать компилятору, вот пример кода:
//опред. ф-и в коде
template <sized T>
void swap (T* arg1, T* arg2) {
T tmp = *arg1;
*arg1 = *arg2;
*arg2 = tmp;
}

//опред. ф-и созданное компилятором
void swap (void *arg1, void *arg2, size_t n) {
char tmp[n];
memcpy(tmp, arg1, n);
memcpy(arg1, arg2, n);
memcpy(arg2, tmp, n);
}

//вызов ф-и в коде
swap (arg1, arg2);

//вызов ф-и созданный компилятором
swap (arg1, arg2, sizeof(*arg1));

Добавить свой отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Устарел ли текст как форма представления программы

Русский язык и программирование

Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

Некоторые «вкусности» Алгол-68

«Двухмерный» синтаксис Python

Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

Должна ли программа быть удобочитаемой?

Стиль языка программирования

Тексто-графическое представление программы

●  Разделители

●  Строки программы

●  Слева направо или справа налево?

Комментарии

●  Длинные комментарии

●  Короткие комментарии

●  Комментарии автоматической генерации документации

●  Нерабочий код

●  Помеченные комментарии

Нужны ли беззнаковые целые?

Шестнадцатиричные и двоичные константы

Условные операторы

Переключатель

Циклы

●  Продолжение цикла и выход из него

Некошерный «goto»

Изменение приоритетов операций

Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

Так ли нужны операции «&&», «||» и «^^»?

Постфиксные инкремент и декремент

Почему в PHP для конкатенации строк используется «.»?

Указатели и ссылки в C++

●  Обработка ошибок

Использование памяти

Почему динамическое распределение памяти — это плохо

Как обеспечить возврат функциями объектов переменной длины?

●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●  Массивы переменной длины в C/C++

●  Размещение объектов в стеке, традиционный подход

●  Размещение объектов переменной длины с использованием множества стеков

●  Размещение объектов переменной длины с использованием двух стеков

●  Реализация двухстековой модели размещения данных

●  Двухстековая модель: тесты на скорость

●  Изменение длины объекта в стеке во время исполнения

●  Размещение объектов переменной длины с использованием одного стека

Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

Безопасность и размещение объектов переменной длины в стеке

Массивы, структуры, типы, классы переменной длины

О хранении данных в стеке, вместо заключения

Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее

Последние комментарии

2019/03/24 14:55 ••• Автор сайта
Реализация двухстековой модели размещения данных

2019/03/23 19:01 ••• Автор сайта
Размещение объектов переменной длины с использованием множества стеков

2019/03/21 16:51 ••• Автор сайта
Выбор кодировки для компилятора

2019/03/20 16:13 ••• rst256
Обработка ошибок

2019/03/20 14:37 ••• rst256
Реализация параметрического полиморфизма

2019/02/24 23:14 ••• MihalNik
Каким должен быть язык программирования?

2019/02/20 14:09 ••• Автор сайта
Ошибка при отсутствии выполняемых действий

2019/02/16 14:52 ••• kt
Заметки о выходе из функции без значения и зеркальности get и put

2019/02/14 20:42 ••• Автор сайта
Новости и прочее

2019/02/12 22:46 ••• Антон
В защиту PL/1

2019/02/09 13:07 ••• Автор сайта
Почему динамическое распределение памяти — это плохо

2019/01/01 18:08 ••• Comdiv
Двухстековая модель: тесты на скорость