Продолжение первой части перевода интервью, взятого у создателя Стандартной библиотеки шаблонов Алекса Степанова в 1995 году. В этой части Алекс рассуждает о том, почему шаблоны устроены именно так и почему они хороши. Также описана весьма захватывающая история о том, как удалось внести STL в Стандарт.
Алекс, где и когда вы решили предложить STL как часть определения ANSI/ISO Стандарта C++?
В течение лета 1993 г., Эндрю Кёниг посещал Стэнфорд для преподавания курса C++. Я показал ему кое-что из наших материалов, и, я думаю, он был искренне захвачен увиденным. Он организовал приглашение для меня в качестве докладчика на ноябрьской встрече Комитета по Стандарту C++ в Сан-Хосе. Я прочитал доклад, обозначенный как «Наука программирования на C++». Моя речь была скорее теоретическая. Основная позиция заключалась в том, что существуют фундаментальные законы, которые связывают очень примитивные операции, такие как конструкторы, присваивание и равенство. C++ как язык не навязывает никаких ограничений. Вы можете определить собственный оператор равенства для того, чтобы выполнить умножение. Но равенство должно быть равенством, и оно должно быть рефлексивной операцией. A должно быть равно A. Оно должно быть симметричным. Если A равно B, то B равно A. A должно быть транзитивным. Обычные математические аксиомы. Равенство присуще другим операциям. Имеются аксиомы, связывающие конструктор и равенство. Если вы конструируете объект с копирующим конструктором из другого объекта, то два объекта должны быть равны. C++ не обязывает к этому, но это один из основных законов, которому мы должны подчиниться. Присваивание должно создавать одинаковые объекты. Т.о., я представил группу аксиом, которые связаны с этими основными операциями. Я немного говорил об аксиомах итераторов и показал некоторые обобщенные алгоритмы, обрабатывающие итераторы. Это была двухчасовая лекция и, я думаю, весьма сухая. Однако она была очень хорошо принята. В то время я не думал об использовании этой штуки в качестве части стандарта, т.к. обычно воспринималось, что это была некая продвинутая техника программирования, которая не стала бы широко использоваться в «реальном мире». Я думал, что у практичных людей не было никакого интереса к любой из этих работ.
Эта речь была в ноябре, и я не думал об ANSI до января. 6-го января я получил письмо от Энди Кёнига, который является редактором документа Стандарта, в котором говорилось, что, если я хочу сделать мою библиотеку частью Стандарта, то должен представить предложение до 25 января. Мой ответ был «Энди, ты чокнутый?», на что он ответил, «Да, я чокнутый, но почему бы не попробовать?».
В тот момент было много кода и совсем не было документации — гораздо меньше, чем формальное предложение. Менг и я провели несколько 80-часовых рабочих недель, чтобы успеть с предложением вовремя, до возможного момента его отправки. В то время единственный человек, знавший о готовящемся предложении, был Энди. Он был единственной поддержкой и много помогал в этот период. Мы отправили предложение и стали ждать. В процессе подготовки мы определили множество вещей. Когда вы записываете что-либо, особенно когда вы оформляете это как Стандарт, вы обнаруживаете все возможные изъяны вашего проекта. Мы были вынуждены заново реализовать каждый отдельный фрагмент кода в библиотеке, несколько сотен компонент, в промежутке между отправкой письма в январе и следующей встречей в Сан-Диего в марте. Затем мы должны были пересмотреть предложение, т.к. выявили массу проблем в процессе написания кода.
Вы можете охарактеризовать дискуссии и обсуждения по предложению в Комитете? Была ли немедленная поддержка? Сопротивление?
Мы не верили, что из этого что-то получится. Я выступил с докладом, который был очень хорошо воспринят. Было много возражений, большинство из которых приняли такую форму: это огромное предложение, слишком поздно для него, на предыдущем заседании была утверждена резолюция не принимать каких-либо серьезных предложений — и вот эта огромная штука, крупнейшее предложение из когда-либо рассмотренных, с множеством совершенно новых вещей. Было проведено голосование, и, что интересно, подавляющее большинство проголосовало за рассмотрение этого предложения на следующем заседании, и направило его на голосование на следующем заседании в Ватерлоо, Онтарио.
Бьярн Страуструп стал ярым сторонником STL. Многие люди помогали с предложениями, модификациями и инспекциями. Бьярн приехал сюда на неделю, чтобы работать с нами. Энди постоянно помогал. C ++ — сложный язык, так что не всегда ясно, что означает заданная конструкция. Почти каждый день я звонил Энди или Бьярну, чтобы спросить, возможно ли в C++ то-то и то-то. Я должен оказать Энди особое уважение. Он задумал STL в качестве части стандартной библиотеки. Бьярн стал главным лоббистом STL в комитете. Были и другие люди, привнёсшие пользу: Майк Вилот, глава Группы Библиотеки, Натан Майерс из Rogue Wave, Ларри Подмолик из Andersen Consulting. Были и многие другие.
STL в том виде, каком мы предложили его в Сан-Диего, была написана на текущей версии C++. Нас попросили переписать его с помощью новых ANSI / ISO возможностей языка, некоторые из которых ещё не были реализованы. Была большая зависимость от времени Бьярна и Энди, которые пытались проверить, что мы использовали эти нереализованные возможности правильно.
Будущие пользователи хотели, чтобы контейнеры были независимыми от модели памяти, которая была несколько чрезмерной, поскольку язык не включает в себя модели памяти. Они хотели, чтобы библиотека предоставляла какой-либо механизм для абстрагирования модели памяти. Более ранние версии STL предполагали, что размер контейнера выражается в виде целого числа типа
Следующая важная вещь заключалась в том, чтобы расширить наш оригинальный набор структур данных ассоциативными структурами. Это было легче, но достичь состояния Стандарта всегда трудно, потому что нам нужно было что-то, что люди будут использовать для своих контейнеров годами. С точки зрения контейнеров, STL очень чётко делится пополам. А именно, он предоставляет два основных вида контейнерных классов: последовательности и ассоциативные контейнеры. Проводя аналогии — они как обычная память и ассоциативная память. Такое определение обладает понятной семантикой, объясняющей, что эти контейнеры делают.
Когда я прибыл в Ватерлоо, Бьярн провел много времени, объясняя мне, что я не должен беспокоиться за результат, что скорее всего попытка не удастся, но мы сделали всё возможное, мы старались, и мы должны были набраться храбрости. Уровень ожиданий был низким. Мы готовились к оппозиционному большинству. В итоге некоторое сопротивление было, но незначительное. Результаты голосования в Ватерлоо были неожиданными, т.к. было около 80% «за» и 20% «против». Все ожидали битвы, все ожидали споры. Был бой, но голосование было абсолютным большинством.
Какое влияние оказывает STL на библиотеки классов, опубликованные в рабочем документе ANSI / ISO от февраля 1994?
STL была включена в рабочий документ в Ватерлоо. Документ STL разделен на части, и размещён в разных местах рабочего документа, относящихся к Библиотеке. Майл Вилот ответственен за это. Я не буду принимать активное участие в редакционной деятельности. Я не член Комитета, но каждый раз когда предлагается изменение, касающееся STL, оно находится в моём ведении. Комитет очень деликатен.
Комитетом был принят ряд изменений в шаблонах. Какие из них оказывают влияние на STL?
До принятия STL было два изменения, которые были использованы в пересмотренной STL. Одно из них — это возможность иметь шаблонные функции-члены. STL широко использует их, чтобы можно было построить любой контейнер из любого другого контейнера. Доступен единственный конструктор, который позволяет строить векторы из списков или из других контейнеров. Также есть шаблонный конструктор, параметризованный итератором, поэтому, если вы передаёте пару итераторов в конструктор контейнера, то контейнер создаётся из элементов, определённых этим диапазоном. Диапазон есть множество элементов, определяемых парой итераторов, обобщенных указателей или адресов. Второй существенной возможностью, используемой в STL, были аргументы шаблонов, которые сами являются шаблонами, именно с помощью них были реализованы распределители, которые предлагались изначально.
А требования STL имели какое-либо влияние на предлагаемые изменения в шаблонах?
В Valley Forge Бьярн предложил существенное дополнение к шаблонам — «частичную специализацию», которая позволила бы многим алгоритмам и классам быть гораздо более эффективными и решала бы проблему размера кода. Я работал с Бьярном над предложением, и оно было мотивировано необходимостью обеспечить ещё большую эффективность STL. Позвольте мне объяснить, что есть частичная специализация. Сейчас вы можете иметь шаблонную функцию, параметризованную классом T, скажем
Алекс, где и когда вы решили предложить STL как часть определения ANSI/ISO Стандарта C++?
В течение лета 1993 г., Эндрю Кёниг посещал Стэнфорд для преподавания курса C++. Я показал ему кое-что из наших материалов, и, я думаю, он был искренне захвачен увиденным. Он организовал приглашение для меня в качестве докладчика на ноябрьской встрече Комитета по Стандарту C++ в Сан-Хосе. Я прочитал доклад, обозначенный как «Наука программирования на C++». Моя речь была скорее теоретическая. Основная позиция заключалась в том, что существуют фундаментальные законы, которые связывают очень примитивные операции, такие как конструкторы, присваивание и равенство. C++ как язык не навязывает никаких ограничений. Вы можете определить собственный оператор равенства для того, чтобы выполнить умножение. Но равенство должно быть равенством, и оно должно быть рефлексивной операцией. A должно быть равно A. Оно должно быть симметричным. Если A равно B, то B равно A. A должно быть транзитивным. Обычные математические аксиомы. Равенство присуще другим операциям. Имеются аксиомы, связывающие конструктор и равенство. Если вы конструируете объект с копирующим конструктором из другого объекта, то два объекта должны быть равны. C++ не обязывает к этому, но это один из основных законов, которому мы должны подчиниться. Присваивание должно создавать одинаковые объекты. Т.о., я представил группу аксиом, которые связаны с этими основными операциями. Я немного говорил об аксиомах итераторов и показал некоторые обобщенные алгоритмы, обрабатывающие итераторы. Это была двухчасовая лекция и, я думаю, весьма сухая. Однако она была очень хорошо принята. В то время я не думал об использовании этой штуки в качестве части стандарта, т.к. обычно воспринималось, что это была некая продвинутая техника программирования, которая не стала бы широко использоваться в «реальном мире». Я думал, что у практичных людей не было никакого интереса к любой из этих работ.
Эта речь была в ноябре, и я не думал об ANSI до января. 6-го января я получил письмо от Энди Кёнига, который является редактором документа Стандарта, в котором говорилось, что, если я хочу сделать мою библиотеку частью Стандарта, то должен представить предложение до 25 января. Мой ответ был «Энди, ты чокнутый?», на что он ответил, «Да, я чокнутый, но почему бы не попробовать?».
В тот момент было много кода и совсем не было документации — гораздо меньше, чем формальное предложение. Менг и я провели несколько 80-часовых рабочих недель, чтобы успеть с предложением вовремя, до возможного момента его отправки. В то время единственный человек, знавший о готовящемся предложении, был Энди. Он был единственной поддержкой и много помогал в этот период. Мы отправили предложение и стали ждать. В процессе подготовки мы определили множество вещей. Когда вы записываете что-либо, особенно когда вы оформляете это как Стандарт, вы обнаруживаете все возможные изъяны вашего проекта. Мы были вынуждены заново реализовать каждый отдельный фрагмент кода в библиотеке, несколько сотен компонент, в промежутке между отправкой письма в январе и следующей встречей в Сан-Диего в марте. Затем мы должны были пересмотреть предложение, т.к. выявили массу проблем в процессе написания кода.
Вы можете охарактеризовать дискуссии и обсуждения по предложению в Комитете? Была ли немедленная поддержка? Сопротивление?
Мы не верили, что из этого что-то получится. Я выступил с докладом, который был очень хорошо воспринят. Было много возражений, большинство из которых приняли такую форму: это огромное предложение, слишком поздно для него, на предыдущем заседании была утверждена резолюция не принимать каких-либо серьезных предложений — и вот эта огромная штука, крупнейшее предложение из когда-либо рассмотренных, с множеством совершенно новых вещей. Было проведено голосование, и, что интересно, подавляющее большинство проголосовало за рассмотрение этого предложения на следующем заседании, и направило его на голосование на следующем заседании в Ватерлоо, Онтарио.
Бьярн Страуструп стал ярым сторонником STL. Многие люди помогали с предложениями, модификациями и инспекциями. Бьярн приехал сюда на неделю, чтобы работать с нами. Энди постоянно помогал. C ++ — сложный язык, так что не всегда ясно, что означает заданная конструкция. Почти каждый день я звонил Энди или Бьярну, чтобы спросить, возможно ли в C++ то-то и то-то. Я должен оказать Энди особое уважение. Он задумал STL в качестве части стандартной библиотеки. Бьярн стал главным лоббистом STL в комитете. Были и другие люди, привнёсшие пользу: Майк Вилот, глава Группы Библиотеки, Натан Майерс из Rogue Wave, Ларри Подмолик из Andersen Consulting. Были и многие другие.
STL в том виде, каком мы предложили его в Сан-Диего, была написана на текущей версии C++. Нас попросили переписать его с помощью новых ANSI / ISO возможностей языка, некоторые из которых ещё не были реализованы. Была большая зависимость от времени Бьярна и Энди, которые пытались проверить, что мы использовали эти нереализованные возможности правильно.
Будущие пользователи хотели, чтобы контейнеры были независимыми от модели памяти, которая была несколько чрезмерной, поскольку язык не включает в себя модели памяти. Они хотели, чтобы библиотека предоставляла какой-либо механизм для абстрагирования модели памяти. Более ранние версии STL предполагали, что размер контейнера выражается в виде целого числа типа
size_t и что расстояние между двумя итераторами имеет тип ptrdiff_t. И теперь нам сказали — почему бы вам не абстрагироваться от этого? Это трудная задача, потому что язык не абстрагируется от этого; C и C++ массивы не параметризованы этими типами. Мы изобрели механизм под названием «распределитель» (аллокатор), который инкапсулирует информацию о модели памяти. Это вызвало серьезные последствия для каждого компонента в библиотеке. Вы можете задаться вопросом, что модели памяти должны делать с алгоритмами или интерфейсами контейнера. Если вы не можете использовать такие вещи, как size_t, то вы также не можете использовать такие вещи, как T * из-за различных типов указателей (T *, T huge *, и т.д.). Тогда вы не можете использовать ссылки, поскольку с различными моделями памяти у вас есть различные типы ссылок. Были огромные последствия для библиотеки.Следующая важная вещь заключалась в том, чтобы расширить наш оригинальный набор структур данных ассоциативными структурами. Это было легче, но достичь состояния Стандарта всегда трудно, потому что нам нужно было что-то, что люди будут использовать для своих контейнеров годами. С точки зрения контейнеров, STL очень чётко делится пополам. А именно, он предоставляет два основных вида контейнерных классов: последовательности и ассоциативные контейнеры. Проводя аналогии — они как обычная память и ассоциативная память. Такое определение обладает понятной семантикой, объясняющей, что эти контейнеры делают.
Когда я прибыл в Ватерлоо, Бьярн провел много времени, объясняя мне, что я не должен беспокоиться за результат, что скорее всего попытка не удастся, но мы сделали всё возможное, мы старались, и мы должны были набраться храбрости. Уровень ожиданий был низким. Мы готовились к оппозиционному большинству. В итоге некоторое сопротивление было, но незначительное. Результаты голосования в Ватерлоо были неожиданными, т.к. было около 80% «за» и 20% «против». Все ожидали битвы, все ожидали споры. Был бой, но голосование было абсолютным большинством.
Какое влияние оказывает STL на библиотеки классов, опубликованные в рабочем документе ANSI / ISO от февраля 1994?
STL была включена в рабочий документ в Ватерлоо. Документ STL разделен на части, и размещён в разных местах рабочего документа, относящихся к Библиотеке. Майл Вилот ответственен за это. Я не буду принимать активное участие в редакционной деятельности. Я не член Комитета, но каждый раз когда предлагается изменение, касающееся STL, оно находится в моём ведении. Комитет очень деликатен.
Комитетом был принят ряд изменений в шаблонах. Какие из них оказывают влияние на STL?
До принятия STL было два изменения, которые были использованы в пересмотренной STL. Одно из них — это возможность иметь шаблонные функции-члены. STL широко использует их, чтобы можно было построить любой контейнер из любого другого контейнера. Доступен единственный конструктор, который позволяет строить векторы из списков или из других контейнеров. Также есть шаблонный конструктор, параметризованный итератором, поэтому, если вы передаёте пару итераторов в конструктор контейнера, то контейнер создаётся из элементов, определённых этим диапазоном. Диапазон есть множество элементов, определяемых парой итераторов, обобщенных указателей или адресов. Второй существенной возможностью, используемой в STL, были аргументы шаблонов, которые сами являются шаблонами, именно с помощью них были реализованы распределители, которые предлагались изначально.
А требования STL имели какое-либо влияние на предлагаемые изменения в шаблонах?
В Valley Forge Бьярн предложил существенное дополнение к шаблонам — «частичную специализацию», которая позволила бы многим алгоритмам и классам быть гораздо более эффективными и решала бы проблему размера кода. Я работал с Бьярном над предложением, и оно было мотивировано необходимостью обеспечить ещё большую эффективность STL. Позвольте мне объяснить, что есть частичная специализация. Сейчас вы можете иметь шаблонную функцию, параметризованную классом T, скажем
swap (Т & , Т &) и обменивающую их значения. Это наиболее обобщённый из возможных видов функции. Если вы хотите специализировать функцию, и сделать что-то другое для определенного типа, вы можете иметь функцию swap (Int &, Int &), которая делает обмен целочисленных значений каким-то иным путём. Однако было невозможно иметь промежуточную частичную специализацию, чтобы иметь шаблон функции следующего вида:template void swap(vector&, vector&);
Эта специализация предусматривает особый способ обменять векторы. Это важная задача с точки зрения эффективности. Если вы обмениваете векторы с помощью самой обобщённой swap, который использует три присваивания, то векторы копируются три раза, что требует линейного времени. Однако, если у нас есть эта частичная специализация swap для векторов, то вы можете иметь быструю операцию с константным временем, которая перемещает пару указателей в заголовках. Это позволит, например, отсортировать вектор векторов гораздо быстрее. С текущей версией STL, без частичной специализации, единственный способ заставить ее работать быстрее с каким-либо конкретным видом вектора, таким как вектором , состоит в том, чтобы определить свой собственный swap, и это можно сделать, но это обременительно для программиста. В очень многих случаях частичная специализация позволила бы алгоритмам быть более эффективными на некоторых обобщённых классах. Вы можете иметь самый обобщённый swap, менее обобщённый, и ещё менее обобщённый, ну и совсем конкретный swap. Вы можете сделать частичную специализацию, и компилятор найдёт ближайшее соответствие. Другим примером является copy. В текущей реализации алгоритм copy просто обходит последовательность элементов, определенных итераторами, и копирует их по одному. Однако, с частичной специализацией можно определить шаблон функции:
template T ** copy(T**,T**,T**);
Она будет эффективно копировать диапазон указателей с помощью memcpy, потому что, когда мы копируем указатели, мы не должны беспокоиться о конструировании и разрушении (объектов), и мы можем просто перемещать биты с memcpy. Это можно определить единожды для всей Библиотеки, и пользователю не нужно беспокоиться об этом. Можно иметь частичные специализации алгоритмов для некоторых типов. Это было очень важное изменение, и, насколько я знаю, оно было положительно воспринято в Valley Forge и станет частью стандарта.
Какие типы приложений, выходящих за пределы библиотек стандартных классов, лучше всего обслуживаются STL?
У меня есть надежды на то, что STL введёт стиль программирования, который называется обобщенным программированием. Я считаю, что этот стиль применим к любому типу приложения, то есть, в нём стараются писать алгоритмы и структуры данных в наиболее общем виде. Указание семейств или категорий структур, удовлетворяющих общим семантическим требованиям, является универсальной парадигмой, применимой к чему угодно. Пройдёт много времени, прежде чем технология разовьётся и будет понята. STL является отправной точкой для этого способа программирования.
В итоге у нас будут стандартные каталоги обобщённых компонентов с чётко определенными интерфейсами и чётко определенными сложностными характеристиками. Программисты больше не будут программировать на микро-уровне. Вам никогда не придётся писать бинарный поиск снова. Даже сейчас STL предоставляет несколько алгоритмов бинарного поиска, написанных в наиболее общем виде. Все, что может быть найдёно алгоритмом двоичного поиска, может быть найдено этими алгоритмами. Минимальные требования, налагаемые алгоритмом, являются только требованиями, которые использует код. Я надеюсь, что это же случится и для всех программных компонентов. У нас будут стандартные каталоги и люди перестанут писать эти вещи.
Это было мечтой Дуга Макилроя, когда он опубликовал знаменитую статью о фабриках компонентов в 1969 году. STL является примером технологии программирования, которые позволяют реализовать такие фабрики. Конечно, необходимы существенные усилия, не только исследовательские, но и промышленные, чтобы обеспечить программистов такими каталогами, иметь инструменты, которые позволят людям находить компоненты, в которых они нуждаются, и состыковать компоненты, и убедиться, что их сложностные предположения выполняются.
Продолжение следует...
