Четвёртая часть интервью 2001 года Ф. Франы с Э. Дейкстрой.
В этой части Дейкстра снова говорит о разочаровании IBM System/360 и объясняет свою известную фразу о победе Запада над СССР в холодной войне.
Здесь герой интервью упоминает много своих работ, важных для развития программирования: речь идёт о 60-х годах XX века.
В 1960-х годах разработчики программ столкнулись с проблемами. Раньше, по выражению Дейкстры, были слабые компьютеры, поэтому проблемы были не так сложны, а в эти годы появились сложные компьютеры, поэтому и проблемы ПО «раздулись» соответственно.
Помимо этого, можно сказать, что все проекты сильно выходили за рамки своих бюджетов или оставались недоделанными. То, что всё‑таки выпускалось «в прод», работало не так, как ожидалось или было неэффективным. Тремя словами такое положение дел в сфере разработки окрестили «кризисом программного обеспечения».
Добавим ещё один момент: в то время практически везде ПО не было чем‑то самостоятельным, оно шло в комплекте с «с железом» и продавалось целиком. Софт был неотъемлемой частью оборудования и работал только на нём. Программисты стали выделяться как отдельные профессионалы, а программы — как продукты позже.
в скобках квадратных [ ] указаны примечания самого интервьюера Ф. Франы;
в скобках фигурных { } указаны мои уточнения.
В этом блоке привожу пояснения.
Ссылки на источники есть в конце.
Интервью с Эдсгером В. Дейкстрой, аннотация интервьюера
Интервьюер: Филип Л. Франа, Университет Джеймса Мэдисона
Дата: 2 августа 2001 года
Место: Остин, Техас
Архив: Институт Чарльза Беббиджа, Центр истории обработки информации, Университет Миннесоты
Аннотация: В этом устном интервью Эдсгер Дейкстра рассказывает о своем раннем образовании и подготовке в качестве теоретического физика и «программиста». Дейкстра описывает свою работу по разработке программного обеспечения для Математического центра в Амстердаме, завершение своей докторской диссертации и свою деятельность на нескольких ранних конференциях по обработке информации. Дейкстра также рассуждает о разработке ALGOL 60 и о зарождении информатики в Европе и Америке.
Эдсгер Дейкстра
герой интервью
Филип Франа
интервьюер
Дейкстра: Дальше в сентябре я поехал на первый конгресс IFIP в Мюнхене и выступил с приглашённой речью о развитии программирования. Именно там меня с овациями встретили, видимо, я говорил что‑то необычное. Об этом я ещё расскажу позже. Затем я стал профессором математики в Эйндховене и два года преподавал численный анализ.
В первой части интервью Дейкстра упоминал, что изначально был физиком, но конечном итоге его работа привела его в мир математики. Eindhoven University of Technology, где он стал профессором, был одним из ведущих технических университетов Нидерландов.
Дейкстра преподавал численный анализ (Numerical analysis), что является одной из ключевых дисциплин математики, связанной с разработкой и анализом алгоритмов для решения математических задач на компьютере. Эта область была важной в 1960-е годы, когда компьютеры только начинали использоваться для решения сложных математических задач.
Основные направления численного анализа в 1960-х годах:
Решение линейных и нелинейных уравнений. Разработка методов для нахождения корней уравнений, включая методы Ньютона, бисекции и секущих.
Численное интегрирование и дифференцирование. Создание алгоритмов для вычисления интегралов и производных, таких как методы трапеций и Симпсона.
Численные методы решения дифференциальных уравнений. Разработка методов для решения обыкновенных и частных дифференциальных уравнений, включая методы Эйлера и Рунге‑Кутты.
Численные методы линейной алгебры. Исследование алгоритмов для решения систем линейных уравнений, таких как метод Гаусса и метод Гаусса‑Жордана.
Численные методы оптимизации. Разработка алгоритмов для нахождения экстремумов функций, включая методы градиентного спуска и методы наискорейшего спуска.
Какие численные методы развивались после 60-х годов: адаптивные методы, методы на основе машинного обучения, численные методы для уравнений в частных производных (УЧП).
Подход Дейкстры к численным методам можно оценить в более поздней видео‑лекции на Youtube An Interplay Between Programming and Mathematics (Взаимодействие между программированием и математикой) 1992 года.
? Что в лекции кратко?
В лекции не рассматриваются конкретные численные методы, но сделан акцент на методологических аспектах программирования, роли абстракций и математического обоснования алгоритмов, а именно:
-
Доказательство корректности: подтверждение, что алгоритм выполняет задуманную задачу при любых входных данных.
Формальная верификация. Строгое математические доказательства, подтверждающее, что алгоритм работает для всех допустимых исходных данных, всегда завершает свою работу (терминальность), производит правильный результат.
Применение математической индукции в доказательстве корректности алгоритма. Например, верно для n=0 или n=1, и для некого произвольного числа n=k+1.
Разделение разработки и доказательства. Дейкстра полагал, что доказательство корректности уже готового алгоритма может выявлять ошибки, которых можно избежать, если доказывать параллельно с разработкой алгоритма.
-
Оценка сложности: определение времени и памяти, необходимых для выполнения алгоритма, что помогает понять его эффективность. Например:
O(log n).Важной для автора является роль абстракций в программировании. Затрагиваются вопросы структурного программирования, модульности и избегания «спагетти‑кода».
Взгляд Дейкстры на абстракцию в программировании можно оценить в статье The fruits of misunderstanding («Плоды непонимания»). Здесь он критикует «антропоморфизм» в программировании: люди пытаются в программах найти человеческие качества со способностью «думать, намереваться».
Сегодня утром я отказался писать популярную статью о вопросе «Могут ли машины мыслить?» Я сказал редактору, что считаю этот вопрос таким же некорректным и неинтересным, как и вопрос «Могут ли плавать подводные лодки?» Но редактор, будучи социологом, остался невозмутим: он посчитал последний вопрос очень интересным.
Здесь автор считает постановку вопроса некорректной (на 1983 год). Если «мыслить» — это процесс обработки информации и принятия решений, то компьютеры «мыслили» в принципе, с момента появления. Если «мыслить» — это то, что присуще человеку с его сознанием, рефлексией, эмоциями, творчеством, то «машины», впрочем, не могут мыслить до сих пор (2025). Ложные аналогии, по мнению Дейкстры, мешали понимать и создавать качественные программы. А с точки зрения редактора такая постановка вопроса привлекательна для читателей.
Дейкстра: К 1963–64 году я совместно с Карелом С. Шольтеном {Carel S. Scholen} разработал спецификацию аппаратных каналов и прерываний Electrologica X8 — последнего компьютера, созданного моими друзьями.
Революционные на тот момент подходы:
Аппаратные каналы (hardware channels):
Это отдельные процессы или устройства, отвечающие за управление операциями ввода‑вывода. В X8 использовался специальный периферийный процессор (CHARON), который разгружал центральный процессор, выполняя операции с устройствами ввода‑вывода.
Прерывания (interrupts):
Механизм, позволяющий устройствам сигнализировать центральному процессору о необходимости выполнить операцию. Это позволяло системе быть более эффективной, так как процессор не тратил время на опрос устройств, а продолжал выполнение основной программы до поступления прерывания.Почему нидерландские разработки исчезли с рынка? Компания была приобретена компанией Philips, да и конкуренция с IBM не оставляла шансов.
Про Electrologica можно почитать в статье The Electrologica X1 and X8 computers.
Дейкстра: После этого я приступил к разработке многозадачной системы THE, которую завершил несколько лет спустя.
Операционная система THE (нид. Technische Hogeschool Eindhoven) разрабатывалась под руководством Дейкстры. Это была одной из первых ОС, поддерживающих многозадачность.
Она предполагала несколько слоёв:
Уровень 0: Управление мультипрограммированием, включая распределение процессорного времени между процессами и обработку прерываний.
Уровень 1: Управление памятью, включая распределение и освобождение памяти для процессов.
Уровень 2: Обработка взаимодействия между операционной системой и системной консолью.
Уровень 3: Управление вводом‑выводом, включая буферизацию данных от различных устройств.
Уровень 4: Выполнение пользовательских программ, включая их сборку, выполнение и вывод результатов.
Уровень 5: Интерфейс пользователя (не был реализован разработчиками).
Интересно, что THE OS была разработана для компьютера Electrologica X8, который мы упоминали выше, и который не поддерживал аппаратное управление памятью. Такие компоненты как MMU (Memory Management Unit), встроенные в оборудование компьютера, позволяют распределять для процессов оперативную память, работая с физическими адресами реальной памяти. У Electrologica X8 такого не было.
Поэтому Дейкстра реализовал один из первых вариантов программно‑ реализованной виртуальной памяти, что позволило эффективно управлять памятью без специальной аппаратной поддержки.
Подробно об ОС THE можно почитать непосредственно в статье Дейкстры The Structure of the 'THE'‑Multiprogramming System.
Кстати, IBM, которая много раз упоминается ниже, в то время использовала аппаратные средства управления памятью.
Дейкстра: Конечно же, в 1964 году IBM объявила о модели 360. Я был чрезвычайно раздосадован по поводу Джерри Блаау, с которым я сотрудничал, и который должен был обладать знаниями получше, потому что в организации ввода‑вывода этой машины имелись серьёзные недочёты.
Франа: О которых вы говорили с ним ранее?
Дейкстра: Нет, я не говорил, но он должен был знать о моей диссертации на соискание научной степени и о том, как важно проектирование таких вещей, но это явно не было частью культуры IBM. В моей лекции Тьюринга я описал неделю, которую посвятил изучению спецификаций модели 360, как (смех) самую тёмную неделю в моей профессиональной жизни.
Иными словами, изучение технической документации IBM System/360 вызвало у него сильнейшее разочарование и, возможно, фрустрацию. В этом интервью выбрал формулировку мягче (всё‑таки, уже 2001 год, дела давно минувших дней). Но в 60-х он высказывался резче, признавал символом неэффективности и с большими изъянами в архитектуре. Это подтвердилось после начала массового использования и, по мнению Дейкстры, повлияло на всю индустрию того времени.
Кстати говоря, на конференции в Германии 1968 года участники говорят, что разработка OS/360 обошлась IBM более чем в 50 миллионов долларов в год и потребовала в сумме свыше 5000 человеко‑лет. Для сравнения, американцы на запуск целого ракеты‑носителя Atlas в те годы потратили 25 миллионов долларов.
Сумма 50 млн долларов эквивалентна примерно 478 млн долларов на 2025 год с учётом инфляции 856%.
Вспомним, что в последующие десятилетия американский и европейский подходы к разработке ПО взяли друг у друга лучшее, но «победил», можно сказать, американский коммерческий подход
Дейкстра: На конференции НАТО по инженерии программного обеспечения в 1969 году в Риме я характеризовал решение советских властей создать копию IBM 360 с битовой совместимостью как самую значительную американскую победу в холодной войне.
Франа: Это отразилось в документах конференции?
Дейкстра: Нет. Это не отразилось в документах, но всё равно распространилось. Мне было известно, что в советском вычислительном центре было размещено объявление. На нём был изображён казак, танцующий с флагом, на котором написано «Мы хотим IBM», а под этим была цитата о победе в холодной войне.
Пруфов не нашла. Звучит как какой‑то анекдот, в СССР, конечно, «умели в плакаты», но танцующих казаков с флагом IBM представить сложно.
Дейкстра: И мне выпала возможность рассказать об этом русской аудитории в Петербурге. Кто‑то спросил моё мнение о модели IBM 360, и я подумал, что это самое компактное изложение и дал его.
Уточним, тут он говорит о своём выражении, что IBM 360 был величайшей победой Запада в холодной войне над СССР.
Как известно, СССР в разработке компьютеров в 50-х был на мировом уровне в «компьютерной гонке», делал уникальные вещи, а к концу 60-х было принято решение копировать западный образец, что привело к известным последствиям.
Дейкстра: И треть аудитории засмеялась — так можно было узнать, кто из них понимал английский. Мой способ их проверки.
Ладно, теперь про 1964–65 годы. Я обобщил алгоритм Деккера {Dekker} для N процессов, и последнее предложение этой одностраничной статьи звучало: «И это, как автор полагает, завершает доказательство». По мнению Дага Росса {Doug Ross}, который написал рецензию на статью, это был один из первых опубликованных алгоритмов с доказательством его корректности. Правда это или нет, я не знаю.
Автор имеет в виду алгоритм Деккера для взаимного исключения (например, для избежания гонки между процессами в многозадачных системах). Алгоритм был предложен Тёном Деккером в 1965 году для решения задачи синхронизации двух процессов, позже был обобщён Дейкстрой на произвольное количество процессов.
Когда Дейкстра говорит «И это, как автор полагает, завершает доказательство» (And this, the author believes, completes the proof), делая акцент на документе в одну страницу, это тоже некая ирония: хотя он считает доказательство завершённым, на самом деле процесс всегда можно продолжать или переосмысливать.
Он осознаёт, что доказательство может быть не идеально, а работа — не завершена. И иронизирует над научными формулировками, где каждая фраза исключительно серьёзна. Само доказательство можно прочитать здесь: Solution of a Problem in Concurrent Programming Control.
Дейкстра: Да, я написал «Совместные последовательные процессы» и придумал проблему обедающих пятерых, которая позже стала известной как проблема обедающих философов.
Cooperating Sequential Processes (1965) — одна из важнейших работ Эдсгера Дейкстры, в которой он представил концепцию взаимодействующих последовательных процессов. Проблема обедающих философов иллюстрирует, как должны быть синхронизированы процессы, чтобы они не «зависали» из‑за недоступных ресурсов. Задача состоит в том, что философы сидят за столом и должны по очереди есть и думать, но для того чтобы поесть, им нужно использовать ресурсы — обе вилки, которые лежат между ними.
При этом у них есть три проблемы:
Взаимная блокировка (deadlock): ситуация, когда каждый философ взял левую вилку и ждёт правую. В результате все философы оказываются в состоянии ожидания, и никто не может есть.
Голодание (starvation): один из философов может постоянно оставаться голодным, если ему не удаётся получить обе вилки из‑за постоянной занятости соседей.
Зацикливание (livelock): философы могут бесконечно брать и класть вилки, не успевая поесть, если их действия постоянно блокируют друг друга.
Это оказало огромное влияние на разработку операционных систем в области управления многозадачностью.
Конец перевода и разбора четвёртой части интервью.
Использованные источники и ссылки, упоминаемые в статье:
Видео-лекция An Interplay Between Programming and Mathematics
Статья The fruits of misunderstanding
Статья The Electrologica X1 and X8 computers
Статья The Structure of the 'THE'-Multiprogramming System
Брошюра конференции в Германии Software Engineering
Статья Solution of a Problem in Concurrent Programming Control