В последние годы, когда спрос на C++ снова растет , интересно заглянуть в недавнее прошлое и вспомнить, как создавалась эта классическая платформа разработки.
Книги Страуструпа, такие как « Проектирование и эволюция C++ Однако не менее интересно услышать о языке от самых первых его последователей, а иногда и от полноправных соавторов.
Пожалуй, самый известный из них — наш (в общем:) соотечественник Алексей Степанов , автор Стандартная библиотека шаблонов .
Приведенное ниже интервью было взято с Алексом в 1995 году обозревателем журнала.
Материал будет интересен как новичкам в изучении C++, так и опытным пользователям языка.
Алекс, расскажи нам что-нибудь о своем давнем интересе к обобщенному программированию.
Я начал задумываться об обобщенном программировании в конце 1970-х годов, когда заметил, что некоторые алгоритмы зависят не от конкретной реализации структуры данных, а только от небольшого числа существенных семантических свойств этой структуры.
Поэтому я начал рассматривать различные алгоритмы и обнаружил, что большинство из них можно абстрагировать от конкретной реализации без потери эффективности.
Эффективность — одна из моих главных задач.
Глупый абстрагируйте алгоритм таким образом, что при использовании полученной реализации он станет неэффективным.
В то время я подумал, что правильным способом проведения такого рода исследований является разработка языка программирования, чем я начал заниматься вместе с двумя моими друзьями Дипаком Капуром (в настоящее время профессором Государственного университета Нью-Йорка, Олбани).
) и Дэвид Массер, профессор Политехнического института Ренсселера.
В то время мы втроем работали в исследовательском центре General Electric в Скенектади, штат Нью-Йорк.
Мы начали работать над языком под названием Tecton, который позволил бы людям описывать алгоритмы, связанные с тем, что мы называли универсальными структурами.
Это просто коллекции формальных типов и их свойств.
Что-то вроде математического инструментария.
Мы поняли, что над этими структурами можно определить алгебру операций: дополнять их, обогащать и делать с ними всевозможные действия.
Было несколько интересных идей, но исследования не привели к практическим результатам, поскольку Tecton был функциональным языком.
Мы верили в идею Бекуса Наура о том, что программирование должно быть освобождено от стиля фон Неймана , и мы не хотели, чтобы это было в языке побочные эффекты как результат процедуры или функции.
В результате это не позволило нам коснуться многих алгоритмов, которые по своей сути требовали концепций состояния и побочного эффекта.
Интересный факт о Tecton, который я осознал где-то в конце 70-х, заключался в том, что язык имел серьезное ограничение на представление принятого абстрактного типа данных (ADT).
Обычно ADT рассматривается как нечто, сообщающее только поведение объекта, в то время как реализация полностью скрыта.
Было общепринято, что сложность операции является частью реализации и что абстракция игнорирует сложность.
Один из фактов, который я сейчас считаю центральным в обобщенном программировании, заключается в том, что сложность или, по крайней мере, некое общее представление о сложности должно быть связано с операцией.
Давайте посмотрим на пример.
Представим себе АТД «Стек».
Недостаточно иметь методы «Затолкнуть в стек» и «Вытолкнуть из стека»: постулат заключается в том, что что-то заталкивается в стек, и после того, как вершина стека выталкивается, получается тот же самый стек.
Важнейшее утверждение состоит в том, что помещение элемента в стек является операцией, выполняемой за постоянное время, независимо от размера стека.
Если я реализую стек таким образом, что каждый раз, когда в него помещают элемент, операция становится всё медленнее и медленнее, то никто не захочет использовать этот стек.
Нам нужно отделить реализацию от интерфейса, но не ценой полного игнорирования сложности.
Сложность должна быть и является частью неписаного соглашения между модулем и его пользователем.
Причиной внедрения концепции ADT было создание взаимозаменяемых программных модулей.
Невозможно иметь взаимозаменяемые модули, если только эти модули не имеют одинакового сложного поведения.
Если я заменю один модуль другим с таким же функциональным поведением, но с другим компромиссом по сложности, пользователь этого кода будет неприятно удивлен.
Я мог бы рассказать ему все, что мне нравится об абстракции данных, но он все равно не захочет использовать этот код. Заявления о сложности должны быть частью интерфейса.
Примерно в 1983 году я перешел из GE Research на факультет Политехнического университета, ранее известного как Бруклинский политехнический институт, в Нью-Йорке.
Я начал работать над графовыми алгоритмами.
Моим главным соавтором был Аарон Кершенбаум, сейчас работающий в IBM Yorktown Heights. Он был экспертом в графовых и сетевых алгоритмах, и я убедил его, что некоторые идеи общего и высокого уровня программирования применимы и к графовым алгоритмам.
У него был доступ к нескольким исследовательским грантам, и он оказал мне поддержку, чтобы я мог начать работать с ним над применением этих идей к реальным сетевым алгоритмам.
Он был заинтересован в создании набора инструментов в виде универсальных компонентов высокого уровня, чтобы можно было реализовать некоторые из этих алгоритмов.
Дело в том, что некоторые сетевые алгоритмы настолько сложны, что в то время так и не были реализованы, хотя теоретически они были хорошо проанализированы.
Для создания такого набора инструментов я решил использовать диалект Лиспа под названием Scheme. Мы с Аароном разработали большую библиотеку компонентов на Scheme, которая демонстрирует все виды методов программирования.
Сетевые алгоритмы были основной целью.
Позже к нам присоединился Дэйв Массер, все еще работавший в GE Research, и мы разработали еще больше компонентов, довольно большую библиотеку.
Его использовали в университете заканчивающие учебу студенты, но никогда не использовали в коммерческих целях.
Выполняя эту работу, я понял, что побочные эффекты функций важны, потому что.
фактически невозможно выполнять операции над графиками без побочных эффектов.
Вы не можете копировать граф каждый раз, когда вам нужно изменить вершину.
Тогда идея заключалась в том, что при построении обобщенных алгоритмов можно сочетать методы высокого порядка с умеренным использованием побочных эффектов.
Побочные эффекты не обязательно плохи; они плохи только в том случае, если ими злоупотребляют. Летом 1985 года меня снова пригласили в GE Research преподавать курс по программированию высокого уровня.
Там я показал, как с помощью этой техники можно строить сложные алгоритмы.
Одним из слушателей курса был Арт Чен, который позже стал руководителем лаборатории информационных систем.
Он был настолько впечатлен, что спросил меня, могу ли я при моей поддержке создать готовую к использованию библиотеку на языке Ada, используя эту технику.
Будучи бедным доцентом, я согласился, хотя никакой Ады в то время я не знал.
Вместе с Дэйвом Массером мы начали работу над созданием библиотеки Ada. Это было важным обстоятельством, поскольку переход от динамически типизированного языка, такого как Scheme, к строго типизированному языку, такому как Ada, заставил меня осознать важность строгой типизации.
Все понимают, что строгая типизация помогает находить ошибки.
Я обнаружил, что строгая типизация в контексте Обобщенные языковые шаблоны Ada (обобщенные процедуры – т.е.
применимые к любому типу), был также инструментом выявления закономерностей.
Это был не только инструмент для отлова ошибок.
Это также был инструмент для размышлений.
Эта работа привела меня к идее ортогональной декомпозиции пространства компонентов.
Я понял, что программные компоненты относятся к разным категориям.
Приверженцы ООП считают, что все является объектом.
Когда я работал над универсальной библиотекой для Ады, я понял, что это не так.
Есть вещи, которые являются объектами.
Вещи, которые имеют состояние и меняют свое состояние, являются объектами.
И в то же время есть вещи, которые не являются объектами.
Бинарный поиск не является объектом.
Это алгоритм.
Более того, я понял, что, разбивая пространство компонентов на несколько ортогональных измерений, мы можем уменьшить количество компонентов и, что более важно, обеспечить концептуальную основу для того, как что-то проектировать.
Затем мне предложили работу в Bell Labs в группе языка C++, занимающейся библиотеками C++.
Они спросили меня, могу ли я сделать то же самое на C++.
Конечно, я не знал C++ и, конечно же, согласился.
Но я не мог сделать это на C++, потому что.
в 1987 году в C++ не было шаблонов, необходимых для такого стиля программирования.
Наследование было единственным механизмом достижения общности, но этого было недостаточно.
Даже сейчас наследование в C++ не представляет особой ценности для общего программирования.
Давайте обсудим, почему.
Многие люди пытались использовать наследование для реализации структур данных и классов-контейнеров.
Как мы теперь знаем, успешных попыток было очень мало, если вообще были.
Наследование C++ и связанный с ним стиль программирования существенно ограничены.
Таким образом, невозможно реализовать проект, включающий что-то столь же простое, как использование оператора сравнения на равенство.
Если вы начнете с базового класса X как корня вашей иерархии и определите для этого класса виртуальный оператор сравнения на равенство, который принимает аргумент типа X, то унаследуете класс Y от X. Каков интерфейс оператора сравнения на равенство? Он имеет равенство, которое сравнивает Y с X. На примере животных (объектно-ориентированные люди любят животных) определите «млекопитающее» и унаследуйте «жирафа» от млекопитающего.
Затем определите функцию-член «mate», в которой одно животное спаривается с другим и возвращает животное.
Затем вы выводите «жирафа» из животного, и, конечно, у него есть особенность «спаривания», когда жираф спаривается с животным и возвращает животное.
Это определенно не то, чего вам хотелось бы.
Хотя спаривание может быть не очень важно для программистов C++, оператор равенства имеет большое значение.
Я не знаю ни одного алгоритма, который не использовал бы ту или иную форму сравнения на равенство.
Для решения подобных проблем вам нужны шаблоны.
У вас может быть шаблонный класс «Животное», который имеет функцию-член «mate», которая принимает животное и возвращает животное.
Когда вы создаете экземпляр «Giraffe», «mate» поступит правильно.
В этом плане шаблон является более мощным механизмом.
Однако мне удалось создать очень большую библиотеку алгоритмов, которая позже стала частью библиотеки стандартных компонентов Unix Systems Laboratory. В Bell Labs я многому научился, общаясь о программировании с такими людьми, как Нди Кениг и Бьерн Страуструп.
Я понял, что C/C++ — это важный язык программирования с некоторыми базовыми парадигмами, которые больше нельзя игнорировать.
В частности, я узнал, что указатели очень хороши.
я не имею в виду подвесные вывески .
Я не имею в виду указатели на стек.
Но я имею в виду, что общая запись указателей — это мощный инструмент. Понятие адреса используется повсюду.
Ошибочно считается, что указатели делают наше мышление последовательным.
Это не верно.
Без какого-либо адреса мы не сможем описать ни один параллельный алгоритм.
Если вы попытаетесь описать параллельное суммирование n чисел, вы не сможете этого сделать, пока не сможете говорить о том, что первое число прибавляется ко второму, а третье число прибавляется к четвертому.
Вам нужна какая-то форма индексации.
Для описания алгоритма любого типа, последовательного или параллельного, необходима какая-то адресация.
Обозначение адреса или позиции имеет основополагающее значение для нашего понимания и концептуализации вычислительных процессов — алгоритмов.
Теперь давайте подумаем, почему C — отличный язык.
Принято считать, что C — это большой «хак», который успешен, потому что… на нем была написана Unix. Я не согласен.
В течение длительного периода времени компьютерные архитектуры развивались не потому, что какие-то умные люди придумали, как развивать эту архитектуру, а потому, что всем видам программистов требовалось решать реальные проблемы.
На самом деле "умные" люди в то время продвигали теги( LISP-ориентированный ) архитектура, что, конечно, не очень соответствовало основным потребностям разработчиков.
Компьютеры, способные работать только с числами, превратились в компьютеры с памятью с байтовой адресацией, плоскими адресными пространствами и указателями.
Это была естественная эволюция, отражающая растущее разнообразие проблем, которые решали люди.
Язык 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, где меня наняли для работы над универсальными библиотеками.
Вместо этого в течение нескольких лет я работал над жесткими дисками, что было увлекательно, но совершенно противоположно этой области исследований.
Я вернулся к разработке обобщенных библиотек в 1992 году, когда Билл Уорли, который был директором моей лаборатории, начал проект по алгоритмам под моим руководством.
В C++ к тому времени уже были шаблоны.
Я обнаружил, что Бьерн отлично справился с разработкой шаблонов.
Давным-давно я принимал участие в нескольких дискуссиях по поводу дизайна шаблонов в Bell Labs и весьма решительно спорил с Бьярном, что ему следует делать шаблоны C++ как можно ближе к дженерикам Ada. Думаю, я так сильно спорил, что он принял противоположное решение.
Я осознал важность наличия в C++ шаблонных функций, а не только шаблонных классов, как полагают многие.
Однако я считал, что функции шаблонов должны работать как дженерики Ada, т. е.
что их экземпляры должны быть явно созданы.
Бьерн не послушал меня и разработал механизм функции шаблона, в котором экземпляры шаблонов создаются явно с использованием механизма перегрузки.
Эта конкретная техника стала решающей в моей работе, потому что.
я обнаружил, что она позволяет мне делать многие вещи, которые были невозможны в Аде.
Я считаю этот конкретный дизайн Бьярна отличным результатом и рад, что он тогда не последовал моему совету.
Когда вы начали работать над STL и какова была его первоначальная цель? В 1992 году, когда проект был сформирован, в нем работало 8 человек.
Постепенно группа становилась меньше, и в итоге в нее вошли двое — я и Мэн Ли.
Хотя Мэн была новичком в этой области (большую часть своей профессиональной жизни она занималась разработкой компиляторов), она разделяла идею исследования общего программирования и считала, что это может привести к изменению процесса разработки программного обеспечения в то время, когда очень мало кто разделял это убеждение.
Я не думаю, что смог бы разработать STL без ее помощи (в конце концов, STL означает Степанов и Ли).
Мы написали гигантскую библиотеку, много кода со множеством структур данных и алгоритмов, функциональных объектов (функторов), адаптеров и т. д. Кода было много, но документации не было.
Наша работа рассматривалась как исследовательский проект, целью которого было продемонстрировать, что можно иметь алгоритмы, которые определены как можно более широко и при этом остаются максимально эффективными.
Мы потратили много времени на измерения и обнаружили, что можем сделать эти алгоритмы настолько общими, насколько это возможно, и при этом оставаться такими же эффективными, как написанный вручную код. В этом стиле программирования нет никаких затрат на скорость! Библиотека росла, но было неясно, где она управляется как проект. Потребовалось несколько счастливых событий, чтобы привести его в STL. ( Продолжение ) ( Оригинальная статья ) Теги: #C++ #Степанов #обобщенное программирование #STL #C++
-
Реестр Easy Critical Обзор
19 Oct, 24 -
Что Может «Чувствовать» Робот?
19 Oct, 24 -
Огс Маджонг 0.6
19 Oct, 24
