Бессмертная и постоянно развивающаяся "The Art of Computer Programming" была официально издана как eBook. В связи с этим издание InformIT провело замечательную Q&A сессию с ее автором Дональдом Кнутом. Честь задать свой вопрос Кнуту выпала не последним людям в мире Computer Science – ученым, авторам книг, ведущим разработчикам компаний-лидеров. Мы отобрали и перевели для вас несколько вопросов и ответов, с нашей точки зрения наиболее полно раскрывающих Дональда Кнута как личность и ученого.
Джон Бентли, исследователь: Какими из всех написанных вами программ вы гордитесь больше всего и почему?
Дон Кнут: Это все равно, что попросить родителей назвать имя своего самого любимого ребенка.
Безусловно, я горжусь TEX и METAFONT, потому что они помогли изменить мир и подарили мне много друзей. Более того, они сделали возможным появление этих электронных книг (прим. перводчика TAOCP), поэтому я невероятно счастлив, что работа, которую я проделал 30 лет назад, каким-то чудесным образом пережила многочисленные технологические изменения и что 3000 страниц TAOCP сегодня так замечательно смотрятся на маленьком планшете.
Во время подготовки Тома 4 TAOCP (прим.пер. "The Art of Computer Programming") в 90-х я написал несколько десятков коротких подпрограмм с использованием того, что сегодня известно как «грамотное программирование» (прим. переводчика "literate programming"). Эти небольшие эссе были включены в "The Stanford GraphBase" (1994), и я до сих пор с удовольствием использую и модифицирую их. Больше всего мне нравится реализация красивого алгоритма Тарьяна для сильно связных компонент со страниц 512-519.
Должен признаться, что также испытываю некоторую гордость за реализацию арифметики с плавающей запятой по стандарту IEEE, которую можно найти в моей книге MMIXware (1999). А также метасимулятором для MMIX, при помощи которого я объясняю множество принципов продвинутых конвейерных компьютеров с самых азов.
Грамотное программирование по-прежнему остается одной из самых главных радостей моей жизни. На самом деле я пишу примерно по две программы в неделю, как маленьких, так и больших, по мере того, как готовлю новый материал для следующих томов TAOCP.
Деннис Шаша, Университет Нью-Йорка: Как можно сравнить красивый алгоритм с красивой теоремой? Другими словами, каковы ваши критерии красоты для каждого из них?
Дон Кнут: Красота обладает множеством аспектов в глазах наблюдателя. Некоторые теоремы и алгоритмы красивы для меня, потому что предполагают множество различных вариантов применения; другие – потому что способны на многое в условиях крайне ограниченных ресурсов; третьи – потому что включают паттерны, прекрасные с эстетической точки зрения; а четвертые – потому что основаны на концепции, чистой, как поэзия.
Например, я уже отметил алгоритм Тарьяна для сильно связных компонент. Структуры данных, которые он разработал для этой проблемы, стыкуются друг с другом каким-то удивительным, прекрасным образом, так что величины, к которым нужно прибегать во время исследования ориентированных графов, магическим образом всегда оказываются у вас под рукой. А еще его алгоритм в качестве побочного продукта выполняет топологическую сортировку.
Иногда даже возможно доказать красивую теорему, выявив красивый алгоритм. За примером обращайтесь к Теореме 5.1.4D и/или Следствию 7H в TAOCP.
Марк Тауб, Pearson: Влияет ли каким-либо образом появление «аппов» (небольших, монофункциональных, сетевых программ) как доминантной парадигмы программирования в сегодняшние дни на ваши планы на будущие материалы для TAOCP?
Дон Кнут: Те, кто разрабатывает «аппы», используют все те же идеи и парадигмы, уже опубликованные в первых томах. А также «аппы» используют постоянно развивающиеся библиотеки, теснейшим образом связанные с TAOCP. Пользователям этих библиотек следует знать кое-что о том, что имеет место быть внутри.
Будущие тома, скорее всего, будут еще более «апп-пригодными», поскольку я собрал тонны потрясающих игр и пазлов, особенно наглядно и увлекательно иллюстрирующих техники программирования.
Радиа Перлман, Intel: Если бы вы родились 200 лет назад, какую карьеру вы бы избрали для себя?
Дон Кнут: Привет! Потрясающий вопрос, не помню, чтобы его мне когда-нибудь ранее задавали.
Если бы я родился в 1814 году, то скорее всего был бы не слишком образованным и вряд ли бы имел доступ к образованию. Все мои предки мужского пола в эту эпоху были работниками ферм, которые им не принадлежали, в регионе нынешней Северной Германии.
Но думаю, вы имели в виду несколько иное. Что, если бы я был одним из тех немногих, у которых была возможность получить продвинутое образование и определенная свобода в выборе профессии?
Всю свою жизнь я хотел быть учителем. На самом деле, когда я учился в первом классе, я мечтал преподавать для первых классов, во втором – для вторых... И, наконец, я стал преподавателем в колледже. Поэтому, думаю, я стал бы учителем, если бы это было возможно.
Если продолжить размышлять в этом ключе, нужно объяснить, что значит быть гиком. Фред Груенбергер давным давно сказал мне, что по его опыту только 2% студентов действительно резонировали с компьютерами так же, как он или я. Это число отпечаталось у меня в уме, и в течение всех этих лет я не раз убеждался в правдивости этого эмпирического наблюдения. Например, в 1977 году я узнал, что среди 11 000 выпускников Университета Иллионойса было только 220 студентов, избравших Computer Science в качестве основной дисциплины!
Таким образом, я пришел к убеждению, что только малый процент населения земного шара обладает особым складом ума, который присущ и мне, и что эти люди узнали о существовании друг друга после того, как computer science получила свое имя.
Проще говоря, люди, подобные мне, и есть «гики». И они составляют около 2% от мирового населения. Я не вижу другого объяснения резкому возникновению множества факультетов компьютерных наук – практически от нуля до единицы в каждом колледже и университете в период между 1965 и 1975 – кроме того, что они предоставили долгожданное прибежище, где гики смогли работать вместе. И таким же образом, я не вижу другого разумного объяснения провалу множества проектов по разработке программного обеспечения, которые мне доводилось наблюдать в течение последних лет, кроме того, что они оказались в руках не гиков.
Так кем же были гики в начале 19 века? Если бы я начал свою карьеру до 1814 года, возможно, я бы начал вместе с Абелем (1802), но на него претендуют в первую очередь математики. Якоби (1804), Гамильтон (1805), Киркман (1806), Де Морган (1806), Лювилль (1809), Каммер (1810) и китайец Ли Шанлан (1811) – следующие в списке. Я перечисляю математиков, чьи работы непосредственно обращаются к моему «внутреннему гику». А если взять именно указанный вами период, то это Каталан (1814) и Сильвестер (1814), Буль (1815), Вейерштрасс (1815) и Борхардт (1817). Я бы наслаждался обществом всех этих людей и, если бы мне повезло, занимался бы подобными вещами.
Между прочим, первым «100% гиком» я бы назвал Алана Тьюринга. Многие из его предшественников демонстрировали яркие симптомы этой «болезни», но именно он был полностью ею «заражен».
Тони Гэддиз, писатель: Помните ли вы конкретное мгновение, когда открыли для себя радость программирования и решили, что посвятите ему всю жизнь?
Дон Кнут: Летом 1957, между первым и вторым курсом в технологическом в Кливленде, мне довелось провести всю ночь наедине с IBM 650, и я был абсолютно покорен.
Но тогда я не рассматривал это как дело всей моей жизни, поскольку не знал никого с такой профессией. В действительности, как я говорил раньше, делом всей моей жизни было преподавание. Я написал мануал к компилятору в 1958 году, который по стечению обстоятельств был использован в качестве учебника для одного из моих курсов в 1959(!). Но даже тогда программирование было для меня в первую очередь хобби, а уже потом, в магистратуре, оно дало возможность содержать себя.
Я не видел связи между программированием и планируемой карьерой профессора математики, пока не познакомился в конце 1962 года с Бобом Флойдом. До того, как я встретил Джорджа Форсайта в 1964, я не мог и подумать, что компьютерные науки когда-либо станут академической дисциплиной.
Роберт Седжвик, Принстон: Дон, помню, несколько лет назад вы придерживались позиции, что не стоит пытаться достучаться до каждого при помощи ваших книг, так как они будут полезны лишь людям с определенными интересами и отношением, тем, кому нравится программировать и исследовать взаимосвязь программирования и математики. Но вот мне стало интересно, что вы думаете по этому поводу сейчас. Общество проделало долгий путь к осознанию преимуществ всеобщей грамотности. А сейчас перед нами стоит вопрос, стоит ли всех обучать программированию. Каково ваше мнение?
Дон Кнут: Полагаю, все профессора колледжей считают, что их предмет нужно преподавать всем и каждому. В этом отношении я не могу удержаться, чтобы не процитировать прекрасную работу Джона Хаммерсли от 1968 года:
Только ради того, чтобы позабавиться реакцией, я спросил видного исследователя английской литературы, какая образовательная польза содержится в изучении голиардической поэзии, гаэльских ругательств западной Шотландии и рунической эротики. «Практическая подготовка в области голиардической поэзии более чем полезна каждому, кто надеется обрести хотя бы скромное умение использовать свой родной язык», – заявил он. И оседлал своего любимого конька, пустившись в рассуждения по этому вопросу, а также сетуя на всеобщее невежество. Мне с трудом удалось вернуть его к гаэльским ругательствам, которые, как оказалось, вдохновляли его гораздо меньше. «На самом деле, – признался он, – это совсем не моя тема. Конечно, я аплодирую стоя большому словарному запасу, никогда не знаешь, какой из казалось бы бесполезных кусочков знания может внезапно приобрести важнейшее практическое значение. Я вполне могу представить себе ситуацию, где это может очень даже пригодиться.» «А что насчет рунической эротики?» «Не дошла до наших дней.» (Мне почудилась нотка легкого сожаления в его голосе.) Конечно, горные выси образованности могут доставлять изысканное наслаждение, но разве «человек с улицы» имеет достаточно времени, настойчивости и интеллектуальной способности переварить все это?
Безусловно, программирование – это не рядовой предмет. Он по своей сути дает возможность сделать многое из различных областей знания. Мне также известно, что вы весьма преуспели в преподавании продвинутых концепций программирования студентам всех направлений в Принстоне и при помощи интернета.
Но ваш вопрос про каждого. Я по-прежнему считаю, что пройдет еще много лет прежде, чем я порекомендую своим весьма умным жене, сыну и дочери изучить программирование, а уж тем более кому-то еще из моих знакомых.
Несколько лет назад Ник Трефетен рассказал мне о том, как навещал своего сына-старшеклассника в Оксфорде – одном из самых лучших мест для учебы в мире – и узнал, что ни один из школьников не умел программировать! Британия сейчас пытается изменить эту ситуацию, надо сказать, более активно, чем Штаты. Тем не менее, подобная революция произойдет через как минимум одно поколение. Откуда взяться учителям сейчас?
Я работаю в основном только с теми студентами, которые интересуются программированием настолько, чтобы сделать его неотъемлемой частью своей жизни. TAOCP предназначена для специалистов. Я изначально писал ее для гиков, а не широкой аудитории. Нужно же кому-то писать книги не только для чайников. (Под чайником я имею в виду умного не-гика. Это гораздо больший рынок и очень важный, но это не моя целевая аудитория, а «всеобуч» – не моя сильная сторона.)
С другой стороны, хотите – верьте, хотите – нет, но я подхожу к объяснениям в моих книгах, представляя себе читателя-неспециалиста. Я стараюсь избегать профессионального жаргона везде, где это возможно. Особенно я избегаю терминов из высшей математики, которые способны испугать «программиста с улицы». Везде, где это возможно, я стараюсь переводить результаты из теоретической литературы на язык, понятный старшекласснику.
Я знаю, что мои книги все равно не такие уж легкие для полного понимания, даже для гиков. Но я мог бы сделать их гораздо более трудными.
Уди Манбер, Google: Ранние тома TAOCP позволили программированию стать computer science, придали необходимую строгость. Это произошло в те времена, когда компьютеры использовались в основном для вычислений. Сегодня большинство приложений пригодны для использования обычными людьми – социальное взаимодействие, поиск, развлечения и т.д. Скорость – не всегда важнейший фактор, а вопросом «правильности» редко даже просто задаются. Можете ли вы дать совет, как разработать новую computer science, которая привнесла бы определенную строгость в новые приложения?
Дон Кнут: Вычисления, бывшие в центре всего в период зарождения computer science, никуда не делись. Они продолжают расти из года в год. Конечно, теперь они составляют существенно меньший кусок пирога, но я не так уж верю в необходимость уделять существенное внимание большим кускам.
Моя работа над METAFONT познакомила меня с приложениями, где невозможно определить «правильность». Откуда мне знать, например, что моя программа для буквы А воспроизводит правильное изображение? Да ниоткуда. И я научился жить в этой неопределенности. С другой стороны, во время реализации шаблонов, которые интерпретировали спецификации METAFONT и отрисовывали соответствующие растровые отображения, для строгости было предостаточно места. Алгоритмы, использующиеся для рендеринга шрифтов, – одни из самых интересных, которые мне доводилось видеть.
Как пользователь продуктов Google, Adobe и других компаний, я знаю, какой строгости требуют манипуляции с данными карт, передачей данных, данными элементов изображения, лингвистическими данными, метаданными и т.д. Более того, большинство вычислений совершается при помощи распределенных и децентрализованных алгоритмов, которые требует такой строгости, какую в 60-х невозможно было и представить.
Поэтому я не могу сказать, что строгость покинула сцену computer science. Однако мне бы очень хотелось, чтобы программисты Google, Adobe и Apple научились быть достаточно строгими по отношению к своим продуктам, чтобы те перестали «валить» мой домашний компьютер в случаях, когда я не использую Linux.
В целом, я с вами соглашусь, нужда в строгости не стала меньшей, скорее увеличилось количество типов строгости, которые имеют значение. Тот факт, что правильность не может быть определена с самого начала, не должен убаюкивать и заставлять забывать о том, что в каждой нетривиальной системе существуют промежуточные уровни, где правильность имеет решающее значение. Устойчивость системы и ее качество не должны пасть жертвой компромисса.
С другой стороны, я не думаю, что все нужно математизировать. И не все, что использует компьютеры, является поддисциплиной computer science. Многие части значимых программных систем не требуют особых гик-талантов, и наоборот. В идеале должно быть взаимодействие между несколькими дисциплинами, потому что разнообразные наборы ортогональных навыков и делают жизнь такой замечательной штукой. Vive la différence.
На самом деле я сам лишь частично следую пути строгости. Я редко даю формальное доказательство того, что мои программы правильны, как только я создал убедительное для себя неформальное доказательство. Мне не интересно, например, точно определить правильность для TEX или формально верифицировать, что моя реализация 550-страничной программы не имеет багов. Я знаю, что возможны аномальные результаты, когда пользователь может задать страницу в милю шириной или константы с триллионами нулей и т.п. Я позаботился о том, чтобы избежать катастрофических падений, но я не проверяю каждую дополнительную операцию на возможный выход за границы.
Существует фундаментальный пробел даже в основах моей основной математической специальности – анализе алгоритмов. Рассмотрим для примера компьютерную программу, которая сортирует список чисел по порядку. Благодаря работам Флойда, Хоара и других, у нас есть формальное определение семантики, и инструменты, которые мы используем для верификации этой сортировки, действительно всегда достижимы. Моя работа заключается в том, чтобы выйти за пределы правильности в направлении анализа таких вещей, как время прогона программы: я пишу рекурсию, которая, например, должна представить среднее число сравнений, выполняемых программой в отношении случайного набора входных данных. Я на 100% уверен, что моя рекурсия корректно описывает работу программы, и все мои коллеги согласны, что рекурсия «очевидно» валидна. Тем не менее, у меня нет формальных инструментов, чтобы доказать правильность моей рекурсии. На самом деле я вообще не понимаю свой собственный ход мысли! Мой студент Лил Рамшав приступил к созданию подходящих обоснований для этого тезиса (1979), но задача кажется по своей сути сложной. Тем не менее, это не лишает меня сна.
Роберт Тарьян, Принстон: Какие направления работы над проектированием и анализом алгоритмов выглядят для вас наиболее многообещающими? Какие из нерешенных задач вам наиболее интересны, кажутся наиболее важными?
Дон Кнут: Мой текущий черновик на тему выполнимости уже содержит 25 исследовательских задач, большинство из которых еще не достаточно хорошо известны сообществу теоретиков. Поэтому многие из них могут быть решены до выхода Тома 4B. Нерешенные задачи возникают постоянно. Но ваш вопрос, конечно, более общего характера.
В целом я концентрируюсь на алгоритмах, работающих быстро для задач, размер которых — число n — является практически возможным. Большинство современной литературы посвящено алгоритмам, которые имеют замечательную асимптотику, но они полезны только тогда, когда n превышает размер вселенной.
С одной стороны подобная литература облегчает мне жизнь, потому что мне не нужно обсуждать эти методы в TAOCP. Я сочувствую чистой науке и не возражаю против нее, она значительно улучшает нашу способность решать практические задачи и интересна сама по себе. Поэтому иногда я играю в асимптотические игры. Но я точно не против использования множества других алгоритмов.
Например, я читал про алгоритмы, которые решают, принадлежит ли данный граф G к определенному классу. Является ли G, например, хордальным? Ранее вы и другие ученые открыли прекрасные алгоритмы для хордальности и задач минимального заполнения, а впоследствии было разработано огромное число невероятно остроумных процедур для характеристки графов других классов. Но я с удивлением обнаружил, что очень немногие из этих новейших алгоритмов были реализованы. Они существуют только на бумаге, зачастую детали только обозначены.
Два года назад мне понадобился алгоритм, чтобы определить, является ли G так называемым графом сравнимости, и то, что было уже опубликовано, меня крайне разочаровало. Полагаю, что все «наиболее эффективные» алгоритмы для этой задачи слишком сложны, чтобы заслуживать доверия, даже если бы у вас был год на их реализацию.
Таким образом, я считаю, что текущее состояние исследований в области проектирования алгоритмов неверно интерпретирует подлинную природу эффективности. И существующая литература демонстрирует опасную тенденцию, присущую современному представлению о том, что стоит публиковать.
Если спуститься на землю, возникает и другой вопрос – эффективность алгоритмов на реальных компьютерах. В качестве части стэнфордского проекта GraphBase я реализовал четыре алгоритма для вычисления минимальных каркасов графов, один из которых во многом походил на метод, который вы разработали с Черитон и Карпом. Хотя я ожидал, что ваш метод окажется «победителем», поскольку обращается к данным в два раза реже, чем другие. А он оказался даже в два или три раза хуже, чем старый добрый метод Крускала. Отчасти из-за плохого взаимодействия с кэшем, но в основном – из-за большой константы, скрытой за O-нотацией.
Все вопросы и ответы можно увидеть тут.
Фото: fbbva.es. Bill Bradford. wikipedia.org
Релоцировались? Теперь вы можете комментировать без верификации аккаунта.