Утерянная диссертация Денниса Ритчи
Многие из вас, дорогие читатели, слышали о Деннисе Ритчи. В конце 1960-х он оставил аспирантские исследования в области прикладной математике в Гарварде ради должности в Bell Telephone Laboratories, где и проработал всю жизнь. Вскоре после поступления на работу в Labs Ритчи объединил свои усилия с Кеном Томпсоном для создания фундаментальной пары, породившей весь последующий цифровой мир: операционной системы Unix и языка программирования C. Томпсон вёл разработку ОС, а Ритчи занимался созданием C, на котором Томпсон переписал Unix. В то время Unix стал основой для большинства операционных систем, из которых строился наш цифровой мир, а язык C стал (и по-прежнему остаётся) одним из самых популярных языков для создания ПО, приводящего этот мир в движение.
Создатели Unix Кен Томпсон и Деннис Ритчи. Источник фотографии неизвестен.
На личных веб-страницах Ритчи сайта Labs (которые до сих пор поддерживает текущий владелец Nokia), он описывает в характерном ему сухом и уничижительном стиле своё путешествие в академический мир компьютерных наук:
«Я… получил степень бакалавра и учёную степень в Университете Гарварда, где студентом занимался физикой, а аспирантом — прикладной математикой… Темой моей докторской диссертации 1968 года были подрекурсивные иерархии функций. Опыт моей студенческой учёбы убедил меня, что я недостаточно умён для физика, и что компьютеры — это довольно любопытно. Мой аспирантский опыт убедил меня, что я недостаточно умён, чтобы стать специалистом в теории алгоритмов, и что мне больше нравятся процедурные, а не функциональные языки»1.
Какой бы ни была цена этого самоанализа, путь Денниса определённо привёл его в область и среду, в которых он внёс выдающийся вклад.
«Всё, кроме сброшюрированного экземпляра»
Возможно, может показаться неожиданным, что до недавнего момента, несмотря на заслуженную славу Ритчи в компьютерной области, его диссертация — интеллектуальная и биографическая развилка, отделяющая его академическую карьеру в компьютерных науках от работы в Bell Labs, приведшей к появлению C и Unix — была утеряна. Утеряна? Да, совершенно верно — её не издавали и она отсутствовала в общедоступных коллекциях; о ней даже не было записей ни в библиотечном каталоге Гарварда, ни в базах данных диссертаций.
После смерти Денниса Ритчи в 2011 году его сестра Линн провела очень тщательный поиск официальной копии и любых записей в Гарварде. Ничего этого не было, зато она обнаружила копию у вдовы бывшего научного руководителя Ритчи. До недавнего времени, в течение четверти века прочитать диссертацию Ритчи могли всего с десяток человек. Почему же так получилось?
Из описания академического пути Ритчи можно заметить, что он не говорит явным образом, что получил PhD за свою диссертацию 1968 года. Потому что он не получил это звание. Почему? Похоже, причиной стала невозможность выполнения нужных требований для официального помещения его завершённой диссертации в библиотеки Гарварда. Профессор Альберт Мейер из Массачусетского технологического института, учившийся в одном потоке с Ритчи на магистратуре, вспоминает эту историю в недавнем интервью:
«Эту историю я услышал от Пата Фишера [научного руководителя Ритчи и Мейера в Гарварде] и она действительно правдива: в те времена по правилам Гарварда нужно было передать университету сброшюрированную копию своей диссертации — для получения PhD требовалось свидетельство из библиотеки. По словам Пата, Деннис представил свою диссертацию. Она была одобрена диссертационным советом; у него был напечатанный на машинке оригинал диссертации, готовый к передаче, но потом он узнал, что библиотеке нужно передать сброшюрированную копию. А цена брошюрирования в то время была значительной… не неподъёмной, но нетривиальной суммой. Пат сказал, что Деннис отнёсся к этому так: „Если библиотеке Гарварда нужна сброшюрированная копия для хранения, то пусть она и платит за книгу, потому что я не собираюсь!“ И, очевидно, он так на это и не пошёл, в результате не получив PhD. То есть он доучился не до ступени „всё, кроме диссертации“. Он дошёл до ступени „всё, кроме сброшюрированной копии“»2.
Хоть расследование Линн Ритчи и подтвердило, что Деннис Ритчи так и не передал сброшюрированную копию своей диссертации и не выпустился из Гарварда с PhD, его брат Джон считает, что за действиями Денниса стояло нечто иное, кроме как раздражение из-за высокой цены: у него уже была престижная должность исследователя в Bell Labs и «ему никогда не нравилось заниматься мелочами жизни». Мы никогда не узнаем истинных причин; возможно, они не были полностью понятны и самому Ритчи. Но мы знаем со всей определённостью, что до недавнего времени диссертация Денниса Ритчи была утерянной в течение четверти века.
Деннис Ритчи (справа) примерно во время начала работы в Bell Laboratories с двумя сотрудниками Labs: его отцом Алистером Ритчи (слева) и основоположником электронной телефонной коммутации Уильямом Кейстером (в центре). Фотография из коллекции семейства Ритчи.
В коллекции
В коллекции Денниса Ритчи, недавно пожертвованной братом и сестрой Ритчи Музею компьютерной истории, на данный момент обнаружено несколько исторических сокровищ. Первое — это коллекция самого первого исходного кода Unix, датируемая 1970-71 годами. Ещё одна — потемневшая и покрытая пятнами фотокопия докторской диссертации Ритчи Program Structure and Computational Complexity. Музей с радостью воспользовался возможностью создания цифровой копии собственного оригинала диссертации Ритчи (а также гораздо более разборчивого цифрового скана копии оригинала, которым владеет Альберт Мейер) и впервые опубликовал их.
Расшифровка диссертации Ритчи
Впервые опубликованная страница из ранее утерянной рукописи диссертации Денниса Ритчи.
Одно дело — восстановить копию потерянной диссертации Ритчи и опубликовать её, другое — понять её. Чтобы получить представление о том, чему посвящена диссертация Ритчи, нам нужно вернуться в начало 20-го века, в период творческого брожения умов, в который математики, философы и логики ломали головы над самыми фундаментальными основами математики. На протяжении многих веков, предшествовавших этому брожению умов, качественные характеристики математического знания — его точность и определённость — придавали ему особый, подчас божественный статус. Хотя философские рассуждения об источнике или основах этих качеств простираются как минимум до Пифагора и Платона, в начале 20-го века влиятельные математики и философы начали считать фундаментом математики формальную логику, в которой правила и процедуры рассуждений выражались в системах символов.
На протяжении 1920-х годов чрезвычайно влиятельным исследователем, стремившимся объявить основой математики формальную логику, был немецкий математик Давид Гильберт. В частности, Гильберт полагал, что можно установить определённые качества математики, например, что математика свободна от противоречий и что истинность или ложность любого математического предположения можно продемонстрировать определёнными доказательствами формальной логики. В доказательствах такого вида, отстаиваемых Гильбертом и называемых «финитными», используются простые, явные, почти механические правила манипулирования символами формальной логики. Такие доказательства должны быть основаны на строгом построении строк символов, строка за строкой, выводимых одна из другой.
В 1930-х в поисках таких правил логических манипуляций над символами математики и философы нашли связь между вычислениями и пошаговыми жёстко заданными процессами, которыми живые вычислители («компьютеры») и механические калькуляторы выполняли математические операции. Курт Гёдель вывел доказательство, относящееся к этой теме, но, к сожалению для Гильберта и его союзников, оно продемонстрировало обратное. Вместо того, чтобы доказать, что логика является гарантией доказуемости всего, что является истинным в математике, логика Гёделя продемонстрировала нечто противоположное — что математика неполна. Для получения этого поразительного результата Гёдель основывал свои рассуждения на особых типах математических объектов, называемых примитивными рекурсивными функциями. Для Гёделя в рекурсивных функциях было важно то, что они вычисляемы, что в них используются «конечные процедуры», подобные тем простым, почти механическим правилам, к которым обращался Гильберт.
Слева: студент Курт Гёдель в 1925 году. Википедия/общественное достояние. Справа: Давид Гильберт, 1912 год. Википедия
Вскоре после Гёделя американский математик и логик Алонзо Чёрч использовал похожие рассуждения о вычислимости для формулирования логического доказательства, показавшего, что математика не всегда разрешима, то есть что в математике существуют такие формулировки, истинность или ложность которых доказать невозможно. Доказательство Чёрча основывалось на понятии «эффективно вычислимых функций», основу которого заложили рекурсивные функции Гёделя. Почти в то же время, независимо от Чёрча, британец Алан Тьюринг вывел доказательство того же самого результата, но на основании «исчислимости», определённой работой абстрактной «вычислительной машины». Эта абстрактная машина Тьюринга, способная выполнять любые вычисления или расчёты, позже стала важнейшим фундаментом теоретических компьютерных наук.
В последовавшие десятилетия, предшествовавшие возникновению компьютерных наук как признанной дисциплины, математики, философы и прочие начали исследовать природу самих вычислений, всё сильнее отдаляясь от связей с основами математики. В своём интервью Альберт Мейер объясняет это так:
«В 1930-х и 1940-х активно прорабатывалось понимание того, что вычислимо, а что нет. Благодаря Гёделю и Тьюрингу появились логические ограничения того, что можно и что нельзя вычислить. А новая идея, появившаяся в начале 1960-х, заключалась в следующем: „Давайте попробуем понять, что можно делать при помощи вычислений“. Так появилось понятие вычислительной сложности, означавшее, что вычислениями можно получать всевозможные вещи, но не все они даются легко… Насколько хорошо можно их вычислить?»
Позже, с развитием электронных цифровых вычислений, для многих таких исследователей вопрос стал заключаться не столько в том, что логические рассуждения о вычислимости могут сказать нам о природе математики, сколько в том, что такие логические рассуждения могут сообщить о пределах самой вычислимости. Когда все эти пределы были хорошо исследованы, интерес исследователей сместился к изучению природы вычислимости в рамках этих пределов. Что мы можем доказать в области возможных вычислений?
Профессор Альберт Мейер делится своими воспоминаниями о Ритчи в интервью 2018 года.
Одним из немногих мест, где проводились подобные исследования в середине 1960-х, когда Деннис Ритчи и Альберт Мейер поступили в аспирантуру Гарварда, были отдельные части кафедр прикладной математики. Часто такие кафедры также были местами, в которых впервые в учебных заведениях начинали применяться электронные цифровые вычисления. Мейер вспоминает:
«Прикладная математика была огромной областью, в которой теория вычислений занимала крошечную новую часть».
Тяга к кафедре прикладной математике Гарварда возникла и у Ритчи, и у Мейера благодаря их студенческим занятиям математикой в университете, хоть Мейер и не помнит, чтобы знал Ритчи студентом. В своей аспирантской работе они оба сильно заинтересовались теорией вычислений, поэтому выбрали в качестве научного руководителя Пата Фишера. В то время Фишер только что получил степень PhD и работал в Гарварде только в самые важные первые годы исследований Ритчи и Мейера, а затем, в 1965 году, перешёл в Колумбийский университет. (Позже, в 1982 году, Фишер стал одной из целей Унабомбера.) Мейер вспоминает:
«Патрика очень интересовало понимание природы вычислений: что их упрощало, что усложняло, почему их нужно выполнять различными способами… Что способны выполнять разные виды программ?»
Задача на лето и её решение
После их первого года аспирантских исследований Фишер по отдельности нанял Ритчи и Мейера в качестве своих лаборантов на лето (по крайней мере, Мейер не знал о найме Ритчи). Чем же должен был заняться Мейер? Работой над одной «нерешённой задачей» теории вычислений, выбранной Фишером. В конце года он должен был предоставить отчёт. Фишер при этом отсутствовал. Мейер провёл печальное лето, в одиночку работая над задачей; в конце он сообщил Фишеру, что добился только незначительных результатов. Вскоре после этого, попав на семинар для аспирантов Фишера, Мейер был поражён, поняв решение летней задачи. Он радостно поделился своим открытием с Фишером, но «был удивлён и немного разочарован сообщением Пата он том, что Деннис тоже решил задачу». Фишер поставил перед Ритчи и Мейером одну задачу на лето, и даже не сказал им об этом!
Деннис Ритчи во время учёбы аспирантом. Его отец Алистер Ритчи (тоже работавший в Bell Labs) находится на заднем сиденье мотоцикла Денниса BSA 650. Снимок принадлежит семейству Ритчи.
Летняя задача Фишера была попыткой ответа на более общий вопрос вычислительной сложности — об относительной простоте, или о том, насколько быстро вычисляется одно по сравнению с другим. Вспомним, что Гёдель использовал примитивные рекурсивные функции, чтобы продемонстрировать пример вычислимости конечными процедурами — важнейшим элементом его знаменитой работы. В 1950-х польский математик Анджей Гжегорчик создал иерархию тех же рекурсивных функций на основании быстроты или медленности роста функций. Фишер поручил Мейеру и Ритчи на лето исследовать, как эта иерархия функций связана с вычислительной сложностью.
К чести Мейера, его разочарование в итогах летней работы обеспечило большее внимание к решению Ритчи: циклическим программам. Мейер вспоминает: "… эта концепция циклических программ (loop programs), изобретённая Деннисом… была столь изящна и важна, а также стала таким потрясающим исследовательским и интеллектуальным механизмом анализа темы, что меня больше не волновало, что задачу решил он, а не я".
Решение летней задачи Фишера в виде циклических программ стало фундаментом диссертации Ритчи 1968 года. По сути, это очень маленькие, ограниченные компьютерные программы, которые показались бы знакомыми любому, кто когда-либо использовал команду FOR для создания программных циклов на BASIC. В циклических программах можно было присваивать переменной нулевое значение, прибавлять к переменной единицу или перемещать значение из одной переменной в другую. И это всё, на что они были способны. Единственным средством контроля над циклическими программами был… простой цикл, в котором последовательность инструкций повторяется заданное количество раз. Также важно то, что циклы могли быть «вложенными», то есть цикл можно было помещать внутрь цикла.
В своей диссертации Ритчи показал, что именно такие и только такие циклические функции нужны для создания примитивных рекурсивных функций Гёделя; именно такие функции составляли иерархию Гжегорчика. Гёдель позиционировал свои рекурсивные функции как фактически вычислимые, а Ритчи показал, что для этой работы подходят именно циклические программы. Диссертация Ритчи показала, что степень «вложенности» циклических программ — глубина циклов внутри циклов — является мерой их вычислительной сложности, а также критерием времени, необходимого для их вычислений. Более того, он показал, что оценка циклических программ по их глубине вложенности циклов полностью эквивалентна иерархии Гжегорчика. Скорость роста примитивных рекурсивных функций и в самом деле связана с их вычислительной сложностью; фактически, они идентичны.
Мейер вспоминает:
«Циклические программы превратились в очень простую модель, которую мгновенно мог понять любой исследователь теории вычислений… Традиционная формулировка с точки зрения примитивных рекурсивных иерархий имела очень подробную логическую запись со сложным синтаксисом. И внезапно вместо этого мы получили описание циклических программ в трёх-четырёх строках».
Хотя, как мы уже поняли, разработка Ритчи таких циклических программ так и не попала в мир компьютерных наук через его диссертацию, ей удалось проникнуть в литературу благодаря совместной публикации 1967 года, написанной вместе с Альбертом Мейером.
Мейер рассказывает:
«Деннис был очень приятным, добродушным, скромным парнем. Очевидно, очень умным, но в то же время немногословным… Поэтому мы мало общались, и говорили о статье, которую по большей части писал я. Мне кажется, он её вообще не писал, но он прочитал её и внёс свои комментарии… и объяснил мне понятие циклических программ».
Статья «The Complexity of Loop Programs» была опубликована ACM в 1967 году; она стала важным шагом в начале продуктивной и успешной карьеры Мейера в теоретических компьютерных науках3. Но она также стала точкой расставания для него и Ритчи. Мейер вспоминает:
«Для меня это было разочарованием. Я бы с удовольствием продолжил совместную работу, потому что он казался умным и приятным человеком, с которым интересно работать, но, знаете, он уже занимался другими вещами. Он мог не спать всю ночь и играть в Spacewar!»
В начале своей статьи я сказал, что в биографической заметке на своём веб-сайте Ритчи пошутил: «Мой аспирантский опыт убедил меня, что я недостаточно умён, чтобы стать специалистом в теории алгоритмов, и что мне больше нравятся процедурные, а не функциональные языки». Да, его пристрастие к процедурным языкам несомненно, но наше исследование его утерянной диссертации говорит, что он всё-таки был достаточно умён для теоретических компьютерных наук. Больше похоже на то, что благодаря опыту учёбы аспирантом Ритчи был очарован теоретической работой, что, в свою очередь, привело к увлечению практической реализацией, построением новых систем и новых языков как способом исследования границ, природы и возможностей вычислений.
Прочитать утерянную диссертацию Денниса Ритчи:
Примечания
- Dennis M. Ritchie bio, Bell Labs
- Oral History of Albert Meyer, interviewed by David C. Brock, September 5, 2018, CHM
- Albert R. Meyer and Dennis M. Ritchie, “The Complexity of Loop Programs,” in Proceedings of the 1967 22nd National Conference On - (the 1967 22nd national conference, Washington, D.C., United States: ACM Press, 1967), 465–69, doi.org/10.1145/800196.806014.
Об авторе
Дэвид Брок (David C. Brock) — историк технологий и директор Центра истории программного обеспечения Музея компьютерной истории. Он интересуется историей вычислений, электроники и оборудования, а также устной историей.
См. также: