В последние годы, когда спрос на C++ снова растёт, интересно заглянуть в недалёкое прошлое и вспомнить, как создавалась эта классическая платформа разработки. В данном вопросе безусловно содержательными являются книги Страуструпа, вроде «Дизайна и эволюции C++». Однако, не менее интересно услышать о языке от самых первых его последователей, а иногда и полноценных соавторов. Пожалуй, наиболее известным из них является наш соотечественник Алекс Степанов, автор Стандартной библиотеки шаблонов. Интервью, приводимое далее, было взято у Алекса в 1995-м году колумнистом журнала Dr.Dobbs Элом Стивенсом.
Расскажите нам что-нибудь о вашем cтоль длительном интересе к обобщённому программированию.
Я начал размышлять об обобщенном программировании в конце 70-х, когда заметил, что некоторые алгоритмы зависят не от конкретной реализации структуры данных, а лишь от небольшого числа существенных семантических свойств этой структуры. Так что я начал изучать самые разные алгоритмы, и обнаружил, что большинство из них могут быть абстрагированы от конкретной реализации так, что эффективность при этом не теряется. Эффективность является для меня одной из основных забот. Глупо абстрагировать алгоритм таким образом, что, когда вы его задействуете такую его реализацию, он становится неэффективным.
В то время я думал, что правильным путём для проведения подобного рода исследования является разработка языка программирования, что я и начал делать вместе с двумя моими друзьями, Дипаком Капуром (в настоящий момент — профессор Университета штата Нью-Йорк, Албани) и Девидом Мюссером, профессором Политехнического Института Ренсселаера. Тогда мы втроём работали в Исследовательском Центре компании General Electric в Скенектади, штат Нью-Йорк. Мы начали работать над языком под названием Tecton, который позволил бы людям описывать алгоритмы, связанные с тем, что мы назвали обобщёнными структурами. Они представляют собой просто коллекции формальных типов и их свойств. Что-то вроде математического инструментария. Мы осознали, что можно определить алгебру операций над этими структурами: вы можете пополнять их, обогащать их и делать с ними самые разные вещи.
Имели место некоторые интересные идеи, но исследование не привело нас к практическим результатам, поскольку Tecton был функциональным языком. Мы поверили в идею Бекуса Наура о том, что следует освободить программирование от стиля Фон-Неймана, и мы не хотели иметь в языке побочных эффектов в качестве результата работы процедуры или функции. В итоге это не позволило затронуть много алгоритмов, которые по сути своей требовали понятий состояния и побочного эффекта.
Интересный факт о Tecton, который я осознал где-то в конце 70-х, состоял в том, что в этом языке имелось основное ограничение, накладываемое на принятое представление абстрактного типа данных (АТД). Обычно АТД представляют как нечто, говорящее вам лишь о поведении объекта, в то время как реализация полностью скрыта. Считалось общепринятым, что сложность операции является частью реализации, а абстракция игнорирует сложность. Один из фактов, который я сейчас рассматриваю в качестве центрального в обобщённом программировании, заключается в том, что сложность, или по меньшей мере некоторое общее представление о сложности, должна быть ассоциирована с операцией.
Рассмотрим пример. Представим АТД «Стек». Недостаточно иметь методы «Занести в стек» и «Вытолкнуть из стека»: постулат — в стек что-то заносится, и после того, как вершина стека вытолкнута, получается тот же стек. Утверждение первостепенной важности состоит в том, что занесение элемента в стек является операцией с постоянным временем независимо от размера стека. Если я реализую стек так, что каждый раз при занесении в него элемента эта операция становится всё медленнее и медленнее, то никто не захочет использовать этот стек.
Нам нужно отделить реализацию от интерфейса, но не ценой полного игнорирования сложности. Сложность должна быть и является частью неписаного соглашения между модулем и его пользователем. Причина для введения понятия АТД состояла в том, чтобы допустить создание взаимозаменяемых программных модулей. Невозможно иметь взаимозаменяемые модули до тех пор, пока эти модули не разделяют схожее сложностное поведение. Если я заменю один модуль другим с таким же функциональным поведением, но с отличными компромиссами по сложности, то пользователь данного кода будет неприятно удивлен. Я мог бы сказать ему все, что мне нравится, об абстракции данных, но он все равно не хотел бы использовать код. Утверждения о сложности должны быть частью интерфейса.
Приблизительно в 1983 г. я перешел из GE Research на факультет Политехнического Университета, ранее известного как Бруклинский Политехнический, в Нью-Йорке. Я начал работать над графовыми алгоритмами. Моим основным соавтором был Аарон Кершенбаум, сейчас работающий в IBM Йорктаун Хайтс. Он был экспертом в графовых и сетевых алгоритмах, и я убедил его в том, что некоторые идеи высокоуровневого и обобщённого программирования были применимы к графовым алгоритмам. Он имел доступ к нескольким исследовательским грантам и обеспечил меня поддержкой для того, чтобы я начал работать с ним над применением этих идей к реальным сетевым алгоритмам. Он был заинтересован в создании набора инструментов в виде высокоуровневых обобщенных компонентов, так что некоторые из этих алгоритмов могли бы быть реализованы. Дело в том, что некоторые сетевые алгоритмы настолько сложны, что они никогда не были реализованы на тот момент, хотя и были хорошо проанализированы теоретически. Я решил использовать диалект Лиспа под названием Scheme для построения такого набора инструментов. Мы с Аароном разработали на Scheme большую библиотеку компонентов, демонстрирующую все виды техник программирования. Сетевые алгоритмы были основной целью. Позже Дейв Мюссер, всё еще работающий в GE Research, присоединился к нам, и мы разработали ещё больше компонент, достаточно большую библиотеку. Она использовалась в университете студентами, оканчивающими учебу, но никогда не была задействована в коммерческих целях. Занимаясь этой работой, я осознал, что побочные эффекты функций важны, т.к. на самом деле невозможно осуществлять операции на графах без побочных эффектов. Нельзя копировать граф каждый раз, когда необходимо модифицировать вершину. Так что озарение в то время заключалось в том, что при построении обобщённых алгоритмов можно совмещать техники высокого порядка с умеренным использованием побочных эффектов. Побочные эффекты не являются непременно плохими; они плохи, лишь будучи неверно используемыми.
Летом 1985 г. я был приглашён обратно в GE Research для преподавания курса высокоуровневого программирования. Там я показывал, как можно конструировать сложные алгоритмы, используя эту технику. Одним из посещавших курс был Арт Чен, впоследствии — управляющий Лабораторией Информационных Систем. Он был достаточно впечатлён, чтобы задать мне вопрос: мог ли я создать с помощью этой техники готовую для промышленного применения библиотеку на языке Ada, при обеспечении им моей поддержки. Будучи бедным доцентом, я ответил согласием, хотя я не знал тогда никакой Ada. Вместе с Дейвом Мюссером мы начали работу над созданием Ada-библиотеки. Это было существенным обстоятельством, т.к. переключение с динамически типизированного языка, такого как Scheme, к строго типизированному языку, такому как Ada, позволило мне осознать важность строгой типизации. Все понимают, что строгая типизация помогает в поиске ошибок. Я обнаружил, что строгая типизация в контексте дженериков языка Ada (обобщённых процедур — т.е. применимых к любому типу), также являлась инструментом выявления моделей. Она являлась не только инструментом для вылавливания ошибок. Она также была инструментом для размышления. Эта работа привела меня к идее ортогональной декомпозиции пространства компонентов. Я осознал, что программные компоненты принадлежат разным категориям. Приверженцы ООП думают, что всё является объектом. Когда я работал над обобщённой библиотекой для Ada, я осознал, что это не так. Есть вещи, являющиеся объектами. Вещи, которые имеют состояние и изменяют свое состояние, являются объектами. И в то же время существуют вещи, не являющиеся объектами. Бинарный поиск — это не объект. Это алгоритм. Более того, я осознал, что, декомпозируя пространство компонентов на несколько ортогональных измерений, мы можем уменьшить число компонентов, и, что более важно, мы можем предоставить концептуальную основу того, как проектировать что-либо.
Затем мне была предложена работа в Лаборатории Белла в группе языка C++ над библиотеками C++. Они спросили меня, мог бы я сделать то же на C++. Конечно, я не знал C++, и конечно же я ответил согласием. Но я не мог сделать этого на C++, т.к. в 1987 г. C++ не имел шаблонов, которые необходимы для этого стиля программирования. Наследование было единственным механизмом для получения обобщённости, и он не был достаточным.
Даже сейчас наследование в C++ не представляет особой ценности для обобщённого программирования. Давайте обсудим, почему. Многие пытались использовать наследование для реализации структур данных и контейнерных классов. Как нам известно теперь, было очень мало успешных попыток, если таковые вообще были. Наследование C++ и стиль программирования, связанный с ним, являются существенно ограниченными. Так, в нём невозможно реализовать дизайн, который включает такую простую вещь, как использование оператора сравнения на равенство. Если вы начинаете с базового класса X в качестве корня вашей иерархии и определяете для этого класса виртуальный оператор сравнения на равенство, получающий аргумент типа X, то далее унаследуйте класс Y от X. Каков интерфейс оператора сравнения на равенство? Он имеет равенство, которое сравнивает Y с X. Используя в качестве примера животных (объектно-ориентированные люди любят животных), определите «млекопитающее» и унаследуйте «жирафа» от млекопитающего. Затем определите функцию-член «спариваться», в которой одно животное спаривается с другим и возвращает животное. Затем вы выводите «жирафа» из животного и, конечно, он имеет функцию «спариваться», в которой жираф спаривается с животным и возвращает животное. Это определенно не то, что вам бы хотелось. В то время как спаривание может быть не очень важным для C++-программистов, оператор равенства является таковым. Я не знаю ни одного алгоритма, в котором не использовалась бы некоторая разновидность сравнения на равенство.
Вам нужны шаблоны, чтобы иметь дело с подобными проблемами. Вы можете иметь шаблонный класс «Животное», имеющий функцию-член «спариваться», которая принимает животное и возвращает животное. Когда вы инстанцируете «Жирафа», «спариваться» сделает верные действия. В связи с этим шаблон является более мощным механизмом.
Однако, я оказался способен создать весьма большую библиотеку алгоритмов, которая позже стала частью Библиотеки Стандартных Компонентов Лаборатории Систем Юникс. Я многому научился в Лабораториях Белла, беседуя о программировании с людьми вроде Энди Кенига и Бьярна Страуструпа. Я осознал, что C/C++ является важным языком программирования с некоторыми базовыми парадигмами, которые уже не могут быть проигнорированы. В частности, я узнал, что указатели очень хороши. Я не имею ввиду «висячие» указатели. Я не имею ввиду указатели на стек. Но я имею ввиду, что общая нотация указателя — это мощный инструмент. Понятие адреса используется повсеместно. Неверно полагается, что указатели делают наше последовательным. Это не так. Без некоего рода адреса мы не сможем описать никакой параллельный алгоритм. Если вы попытаетесь описать параллельное суммирование n чисел, то не сможете этого сделать до тех пор, пока не сможете говорить о первом числе, которое складывается со вторым, пока третье число складывается с четвертым. Вам требуется некоторая разновидность индексации. Вам нужна какая-либо адресация для описания алгоритма любого рода, последовательного или параллельного. Нотация адреса или позиции является основной в нашем осмыслении и концептуализации вычислительных процессов — алгоритмах.
Теперь давайте подумаем, почему C — замечательный язык. Принято считать, что C — это такой большой «хак», который преуспел, т.к. Юникс был написан на нём. Я не согласен. В течение долгого периода времени компьютерные архитектуры эволюционировали, не в силу того, что какие-то умные люди выяснили, как развивать архитектуры, но по причине нужды самых разных программистов решать реальные проблемы. На самом деле, «умные» люди в то время продвигали тэгированные (ЛИСП-ориентированные) архитектуры, что, конечно, было не очень-то релевантно основным нуждам разработчиков. Компьютеры, которые были способны иметь дело только с числами, эволюционировали в компьютеры с побайтово адресуемой памятью, плоскими пространствами адресов и указателями. Это было естественной эволюцией, отражающей растущее множество проблем, которые решали люди. C, отразивший гений Дениса Риччи, предоставил минимальную модель компьютера, которая как результат развития была получена в течение прошедших 30 лет. C не был быстрым хаком. По мере того как компьютеры эволюционировали до возможности обработки всех видов проблем, C, являясь минимальной моделью такого компьютера, стал очень популярным языком для решения всех видов проблем в различных областях с высокой степенью эффективности. В этом и состоит секрет переносимости C: он является лучшем представлением абстрактного компьютера, которое мы имеем. Конечно, абстракция осуществлена над множеством реальных компьютеров, а не каких-то воображаемых вычислительных устройств. Более того, люди понимали машинную модель, лежащую в основе C. Для среднего инженера гораздо проще понять машинную модель, положенную в основу C, чем машинную модель Ada или даже Scheme. C преуспел, т.к. он делал правильные вещи, а не потому что AT&T разрекламировала его или потому что Unix писался на нём.
C++ успешен, т.к., вместо попытки предложить машинную модель, изобретенную разве что в процессе созерцания своего пупа, Бьярн начал с C и попытался развивать C далее, предоставляя больше техник обобщённого программирования, но в контексте рамок этой машинной модели. Машинная модель C очень проста. У вас есть память, где находятся сущности. У вас есть указатели на последовательные элементы памяти. Это очень просто для понимания. C++ сохраняет данную модель, но делает сущности, располагающиеся в памяти, более исчерпывающими, чем в машине C, т.к. C имеет ограниченный набор типов данных. А именно, C имеет структуры, предоставляющие разновидность расширяемой системы типов, но он не позволяет вам определять операции над структурами. Это ограничивает расширяемость системы типов. C++ существенно продвинул машинную модель C к действительно расширяемой системе типов.
В 1988 г. я перешел в HP Labs, где я был нанят для работы над обобщёнными библиотеками. В течение нескольких лет, я работал вместо этого над жесткими дисками, и это было захватывающе, но совершенно ортогонально к этой области исследований. Я вернулся к разработке обобщенной библиотеки в 1992, когда Билл Ворли, бывший заведующим моей лаборатории, запустил проект по алгоритмам со мной в качестве руководителя. C++ к тому моменту имел шаблоны. Я обнаружил, что Бьярн проделал превосходную работу по проектированию шаблонов. Очень давно я принял участие в нескольких дискуссиях в Лабораториях Белла о проектировании шаблонов, и спорил с Бьярном достаточно жёстко о том, что он должен сделать шаблоны C++ настолько близкими к дженерикам Ada, насколько это возможно. Я думаю, что спорил так жёстко, что он принял противоположное решение. Я осознал важность наличия шаблонных функций в C++, а не только шаблонных классов, как многие считают. Я думал, однако, что шаблонные функции должны работать как дженерики Ada, т.е. что они должны были быть явно инстанцируемы. Бьярн не послушал меня и спроектировал механизм шаблонных функций, в котором шаблоны инстанцируются явно, используя механизм перегрузки. Эта специфическая техника стала решающей для моей работы, т.к. я обнаружил, что она позволила мне делать многое из того, что было невозможно в Ada. Я вижу этот особый дизайн, разработанный Бьярном, как превосходный результат, и я счастлив, что он не последовал тогда моему совету.
Когда вы начали работу над STL и каково было его первоначальное назначение?
В 1992 г., когда проект был сформирован, в нём было 8 человек. Постепенно группа уменьшалась, и в итоге включала двоих — меня и Менг Ли. Пока Менг была новичком в той области — она разрабатывала компиляторы большую часть ее профессиональной жизни, она приняла от начала до конца видение исследований по обобщённому программированию, и поверила, что они могут привести к изменению процесса разработки ПО в тот момент, когда очень малое число людей разделяло это убеждение. Я не думаю, что смог бы сконструировать STL без её помощи (в конце концов, STL означает Степанов и Ли). Мы написали гигантскую библиотеку, много кода с большим количеством структур данных и алгоритмов, функциональных объектов (функторов), адапторов и т.д. Было много кода, но никакой документации. Наша работа рассматривалась в качестве исследовательского проекта с целью демонстрации того, что можно иметь алгоритмы, определенные настолько общо, насколько это возможно, но по-прежнему максимально эффективные. Мы потратили много времени, делая замеры, и обнаружили, что можем сделать эти алгоритмы настолько обобщенными, насколько они могут быть таковыми, но по прежнему настолько же эффективными, как и вручную написанный код. В этом стиле программирования отсутствуют какие-либо накладные расходы по скорости! Библиотека разрасталась, но было неясно, где она управлялась как проект. Потребовалось несколько удачных событий, чтобы подвести его к STL.
Продолжение следует...
Автор: excoder
