Сегодня у меня в гостях Чарльз Уэзерелл, автор книги «Этюды для программистов», изданной в 1978 году. До сих пор эта книга остается отличным источником интересных реальных задач из разных областей информатики для студентов, изучающих программирование. Сейчас Чарльз работает в компании Оракл, и любезно согласился рассказать немного о себе и о книге.

Предупреждение: Данная статья является переводом с английского. Я не профессиональный переводчик, поэтому в тексте могут встречаться мелкие неточности. Желающие всегда могут прочитать оригинал на английском.

---

Программы должны быть в форме понятных комментариев, объясняющих назначение кода, который следует за этими комментариями. Форматирование должно быть таковым, чтобы читателю было легко и просто понять ваш код. А компилятору без разницы. В частности, следуйте соглашениям, принятым в математике и вашем естественном языке, а не вычитанным в каком-то непонятном руководстве по языку программирования. Сначала пишите комментарии, а затем код, и не наоборот. Если вы не знаете точно, что хотите получить и почему, любой код, который вы напишете, будет по определению, неверным.

---

«Этюды» не похожи на другие учебники по программированию. В них есть задачи из наиболее важных областей, и преподнесены они весьма нетрадиционным образом. Как родилась идея собрать реалистичные задачи и обыграть их в виде законченных игровых ситуаций? Можете рассказать вкратце как родились «Этюды»?

С 1974 по 1979 я преподавал в университете UC Davis. Там была новая группа выпускников по специальности «Информатика», призванных составить учебную программу по этому предмету, но в реальности это была просто группа людей из разных факультетов. Департамент прикладных наук нанял меня как первого профессора по этой специальности для создания учебной программы. Вместе с небольшой группой других профессоров и преподавателей мы создали новый учебный план с учетом требований по специальности и начали преподавать новые и переработанные курсы.

Работая над учебной программой, мы сошлись во мнении, что студентам стоит иметь опыт работы над реальными задачами в дополнение к теоретическим знаниям. Но под «реальными» задачами я не имею в виду коммерческие или прикладные задачи, так как я убежден, что такие знания очень быстро устаревают. Вместо этого я хотел дать студентам задачи, в которых надо было понять требования и поработать над спецификациями. Кроме этого, необходимо было научить студентов работать в группе. Например, задача по созданию компилятора давалась группе студентов из 2-3 человек, и оценка ставилась всей группе. Также надо было описать, как они поделили работу, и был ли выбор удачным.

Через некоторое время мы решили начать курс программирования проектов, чтобы закрепить знания студентов по созданию законченных приложений. Я сформулировал несколько проектов, которые мы придумали. Но, когда потребовались еще идеи, вокруг были только книги с примитивными задачами, например, распечатать таблицу истинности булевых функций и пару задач, используемых в университете Карнеги-Меллон. Так, сам того не замечая, я уже писал «Этюды». Так вышло, что я ушел из университета UC Davis практически сразу после публикации книги и точно не знаю, продолжили ли они использовать книгу в курсе по проектам.

Сколько длилась работа над книгой?

Я работал над «Этюдами» полтора-два года. Вначале уже было несколько готовых глав от курсовых. Договор с издательством подписали очень быстро, как я помню, где-то за месяц. Затем около года я писал остальные главы. Конечно, приходилось это делать вместе с основной работой. Рецензирование и корректура заняли еще месяцев шесть. И через пару месяцев после окончания работы я получил первую копию.

Почему вы не писали книг после «Этюдов», и почему «Этюды» не переиздавались?

Из университета UC Davis я ушел работать в Bell Labs. Там я вел проект по созданию первых компиляторов языка Ада. Мы публиковали техническое отчеты, но писать книгу реально не было времени. После Bell Labs я переехал в Силиконовую Долину работать в стартапе, и опять для книги не было времени. Далее появилась семья, а дети, как большинство родителей знает, требуют времени. Ну, а дальше вы и сами знаете.

В семидесятых Юрис Хартманис, один из моих любимых учителей, сказал мне, что если написать учебник по информатике, то должно хватить денег на новую машину. В те времена было много библиотек, которые все были готовы купить хотя бы по одной копии, обеспечивая минимальный уровень дохода хотя бы на Фольксваген (Фольксваген Жук тогда еще выпускался!). Если повезет, то могло хватить и на Мерседес. Естественно, если написать что-то вроде «Экономикс» Самуэльсона, то можно ежегодно покупать Ламборгини.

Но успех учебникам приходит, только когда они используются в учебных курсах. Увы, только несколько колледжей в Штатах начали использовать «Этюды», поэтому денег это приносило немного. Издательство не горело желанием работать над переизданием. Книга хорошо продавалась индивидуальным покупателям, но для учебников это - несущественный бизнес.

Но кое-что необычное произошло. Сразу после публикации «Этюдов» советское министерство образования посмотрело книгу и решило купить права на переиздание на территории Советского Союза. Если честно, это был настоящий дипломатический прорыв. Обычно Советский Союз просто игнорировал авторские права. Данный платеж был приятным сюрпризом.

Увы, в абсолютном эквиваленте сделка была не очень прибыльной. Они заплатили за права 1200 долларов США, что даже в семидесятых было не очень много. Я получил половину, $600. Конечно, было здорово, что «Этюды» были переведены на русский, после чего весьма широко использованы в советской учебной программе. Например, я работал с двумя русскими, использовавшими книгу, будучи студентами. Александр, вы третий! В целом, было напечатано около 60-ти тысяч экземпляров на русском языке.

И какую же машину с этого мне было купить? В итоге, я купил новое пианино, которое до сих пор стоит у меня в гостиной.

Как вы находили темы для этюдов?

По-разному. Пара задач были просто взяты из жизни. Например, задачи для этюдов про расчет расхода бензина и дохода от инвестирования я использовал сам. Часть задач родилась из моего увлечения компьютерными играми и искусственным интеллектом, например, про игры Калах и Менеджмент. Задачи про языки программирования в конце книги были вариантами из нашего курса по компиляторам. Какие-то этюды были классическими теоретическими задачами, просто немного завуалированными: машины Тьюринга, раскрашивание карты, сканер форматов.

В четвертой главе задача про автоматическое форматирование текста придумана моим коллегой из Ливерморской лаборатории. Он создал один из самых первых форматировщиков текста, который я использовал, работая над диссертацией и над черновиками «Этюдов». Не стоит забывать, что это было до того, как UNIX стал популярным, и даже программа nroff был чем-то «продвинутым». Поэтому задача, поставленная в этой главе, выглядела актуальной.

Приведенные в книге решения выбраны среди тех, что «умещались» в физический размер книги. Я также хотел показать студентам реальный код. Помните, в последней задаче даже говорилось, что решение является неполным.

Для каждого этюда вы рекомендовали время исполнения. С 1978 года языки программирования «немного» изменились, став «чуть более» развитыми. Но даже сейчас ваши рекомендации выглядят весьма жестко. Вы пробовали «проиграть» этюды, работая над книгой? Есть ли у вас любимый этюд?

Сейчас понятно, что это было ошибкой. Даже по нынешним меркам, даже на таком языке как Руби (кстати, моем любимом на сегодняшний день), который так много делает за вас, рекомендованные длительности исполнения остаются весьма суровыми. Не стоит забывать, что когда «Этюды» создавались, UNIX только набирал популярность, Бейсик, Фортран и Паскаль были основными языками обучения, а C только появился. Фактически не было интерактивных терминалов для программирования, и студенты готовили программы на перфокартах (хотя у моих студентов был доступ к терминалам, благодаря связям в Ливерморской лаборатории).

Сложно сказать, какой этюд у меня любимый. Мне нравится интерпретатор языка TRAC, так как приходится возвращаться к основам языков программирования, а эти вопросы часто упускаются в учебной программе. Языки TRAC и макрогенератор Strachey были придуманы в одно и то же время, независимо друг от друга. Оба автора опубликовали свои работы с интервалом в несколько месяцев. Языки очень похожи и демонстрируют, как работа с текстовыми данными может решать сложные задачи. Очень полезно изучать их вместе, чтобы увидеть, в чем эти языки отличаются, а в чем, напротив, похожи. Еще мне нравится этюд про перемещающий загрузчик, так как он решает все еще актуальные задачи в трансляции языков программирования. Мне до сих пор непонятно, почему подобные приемы все еще не используются сплошь и рядом.

Если честно, у меня не было достаточно времени прорешать все задачи в процессе работы над книгой. Однако, работая в Bell Labs, я был вынужден изучать UNIX и ее утилиты. Так, например, я решил реализовать этюд про расход бензина на awk’е. Забавно, я нашел ошибку в самом awk’е и отписал об этом Брайну Кернигану. Он сказал, что знал об этой проблеме, но никому не удавалось ее локализовать. Ошибка была классической – использование памяти после ее освобождения.

Не могу не спросить про этюд о шифре Виженера. Там была парочка «подстав», например «незначительная» опечатка в виде пропущенной строки в середине зашифрованного текста и также «немного неверный» метод взлома, предлагаемый как вариант решения. Конечно, ничто из этого не остановило читателей от успешного взлома, и даже сделало этюд еще более интересным. Все же, что там произошло с этой главой?

Да, неудобно вышло. При подготовке текста книги в издательстве все черновики перенабирались заново, но вот картинки печатались с оригинала как есть. Увы, моя картинка с зашифрованным текстом содержала ошибку. Интересно, что до перевода на русский никто не жаловался (или по крайней мере мне не сообщали). А неточности в самой задаче были скорее всего из-за моего изложения. Хотелось бы надеяться, что это единственное подобное место в книге.

Мне кажется, что подготовка и возможно прорешивание задач для книги в целом было задачей не из простых. Есть ли еще подобные сюрпризы в книге?

Задуманных сюрпризов нет. Когда я решал задачу про расход бензина, я осознал, что постановка недостаточно четкая. Возможно, было еще несколько мест, где могли требоваться уточнения.

Думаю, в целом получилось не так уж и плохо. Конечно, подготовка решабельных задач заняла гораздо больше времени, чем требовалось студентам на их решение. Мне не хотелось глупо выглядеть перед читателями.

К счастью, мне помогали, чтобы было очень кстати. Текст и картинки были изначально подготовлены с использованием новых средств форматирования и рисования, разработанных Хэнком Моллом и Джоном Битти. Это очень упрощало работу. Я писал сам текст на «формулярах», специальных листах для перфокарт. Эти листы затем отправлялись людям в группу «набивки», которые заодно еще и отчитывали текст. Если им казалось, что я допустил ошибку (или явную несуразицу), они набивали оба варианта, исходный и исправленный, чтобы я мог выбрать правильный.

Издатель попросил нескольких сторонних людей прочитать книгу и высказать свое мнение. Один из них оставил комментарии фактически на каждой строке текста. Именно он помог сделать книгу значительно лучше. Тогда я не знал, кто именно это был. Позже обнаружилось, что это был Стив Мачник (известный своей книгой про оптимизацию в компиляторах). Я был ему очень благодарен.

Если бы вы писали Этюды сегодня, что бы вы добавили?

Для начала, я определенно хотел бы исправить ошибки в задаче про шифр.

Электронная подпись и криптография с открытым ключом могли бы стать новой задачей. Также я бы подправил главу про арифметику высокой точности. Однозначно я бы изменил главу по языкам программирования и компиляторам с учетом современных подходов. Еще идея (изначально от Джона Флетчера) – сделать пару этюдов по написанию интерпретатора Лиспа на Руби (например) и упрощенный Руби на Лиспе. Или что-то в этом роде.

Я бы, возможно, убрал один или два простых этюда. Есть много задач из области искусственного интеллекта (в частности, генетического программирования), которые пришлись бы в тему. Можно было взять что-нибудь из нового в области структур данных (например, насколько красно-черные деревья производительнее простых двоичных деревьев). Если честно, сложно однозначно сказать, какая б задача точно подошла, до тех пор, пока не поработаешь над ней.

Большинство этюдов сфокусированы на реализации, нежели на том, как в целом подступиться к задаче, так как почти всегда вы даете подробное описание метода решения. Как вы думаете, нужно ли также давать студентам задачи без какой-либо подсказки о возможном решении? Что это могли бы быть за задачи? И как следовало бы их оценивать по-вашему?

В жизни всегда встречаются проблемы, в которых сначала надо понять, в чем именно проблема. Было бы неплохо обучить студентов подобному анализу, так как в реальности подобный навык – редкость. Но это не было изначальной идеей «Этюдов», так как это тема достойна целого отдельного курса. В «Этюдах» предполагалось давать студентам осмысленную задачу для практики полного цикла разработки. Здесь все еще очень много того, что студент должен самостоятельно решить. Например, решения оценивались по качеству кода, по умению автора объяснить результаты и по производительности программы.

Тут возможно сделать целый курс из задач того типа, что вы предлагаете, но тогда на лекциях надо разбирать методы подобного анализа, и книга также должна включать в себя соответствующие материалы. Это получится совсем другая книга.

Чарльз, в плане ваших интересов и работы вне «Этюдов». Я знаю, вы эксперт в области компиляторов. Вы работали, например, над созданием компилятора языка XPL. Над чем вы сейчас работаете в Оракле? Все еще программируете?

Да, программирую. Что мне нравится в программировании, так это то, что можно реально сделать то, о чем думаешь.

Моя основная область знаний – это теория, разработка и реализация языков программирования. Когда я был студентом, информатика как таковая еще не существовала, и моей специальностью была прикладная математика. Но мой диплом был связан с добавлением новых возможностей в язык TRAC (не напоминает один из этюдов?). Я работал над XPL, над полной компилирующей средой для Ада, над LR-генератором парсеров грамматик (вместе в Элом Шэнноном), над предложениями по добавлению массивов в Фортран, над новым языком описания потоков данных (вместе с Джимом МакГроу), и (довольно недавно) над новым генератором кода и оптимизатором для ораклового языка PL/SQL. Последнее время я работаю над некоторыми специальными проектами Оракле в области языков программирования. Если все получится, вы сможете прочитать об этом.

Глядя на тематику задачи в вашей книге, трудно угадать вашу личную область интересов. Даже в разделе по компиляторам вы даете задачу про интерактивный функциональный язык TRAC наряду с классическим процедурным языком. Так какие же области информатики вас интересуют больше всего?

Больше всего меня интересуют:

1. Языки программирования, в частности, определение их семантики.

2. Структуры данных и их производительность.

3. Игры и искусственный интеллект.

В основном, конечно, моя работа связана с первой темой. Я много занимался производительностью компиляторов, что, несомненно, связано и со второй темой. Еще в средней школе, я интересовался компьютерами и любил игры. Отсюда появился и третий интерес. Для меня компьютеры всегда были и остаются интересным развлечением. Хотя мне уже не понять всего того, что мой младший сын принимает как должное, имея айпад.

Мой интерес в компьютерных играх можно увидеть в паре статей, которые я написал (с друзьями) про разновидность шахмат, называемую Кригшпиль (Kriegspiel). Они были опубликованы в журнале «Computer Journal». В одной из них была приведена полная программа для проверки правильности ходов в Кригшпиле. На тот момент было несколько обучающих программ для студентов, но в которых, увы, проверялись далеко не все тонкости шахматных правил. Были, конечно, шахматные программы, но до времен открытого программного обеспечения было еще далеко, а авторы шахматных программ не хотели раскрывать своих секретов, так как продавали их. Поэтому, насколько я знаю, моя программа была первой открытой реализацией для проверки шахматных ходов. Может быть, и последней. Здесь, в Силиконовой Долине, об этом проекте есть мое аудио интервью в компьютерном музее.

Обычно, мой подход следующий: сначала я пытаюсь подобрать подходящую теоретическую модель для задачи, а затем разобраться, как применить ее на практике.

За все эти годы вы видели язык программирования, который могли бы назвать лучшим?

На текущий момент мне очень нравится Руби. Я написал много кода на С, но мне не нравится низкий уровень безопасности в нем. Раньше мне нравился XPL, который похож на С (конечно, он был создан независимо), но гораздо более безопасен.

Будучи студентом, я написал одну длинную программу на Сноболе. Я моделировал на нем исследовательскую задачу по оптимизации кода. Получилось записать формальное доказательство теорем прямо в виде процедур на Сноболе. Это было откровением. Так я заинтересовался языками, в которых есть интересные динамические свойства.

Я хотел бы уделить время на изучение Haskell или схожего языка для какого-нибудь хорошего проекта. Уверен, там есть чему поучиться. Надо понимать, что написание простого примера вовсе не означает знание и понимание языка. Используя Руби около года в одном проекте, я каждый день узнаю что-то новое.

Создавая языки типа С, люди хотели быть ближе к компьютерному железу, понимание работы которого было обязательным для любого профессионального программиста в те дни. И, как следствие этого, влияло на учебную программу. Как стоит учить программированию сейчас? Его чисто прикладной стороне?

Я никогда особо не интересовался железом, хотя и писал на ассемблере, в котором даже не было мнемонического обозначения машинных команд в трансляторе.

Мне кажется, что вопрос поставлен неверно. Проблема не в программировании как таковом, а в анализе и процессе разработки. Можно написать все что угодно на любом языке. Вопрос в том, правильно ли выбран язык для конкретной задачи или нет.

Поэтому, я бы учил принципам программирования и затем просил студентов применять их в разных языках. Например, вы знаете, что компилятор Фортрана всегда включает в себя интерпретатор? (для форматов). Более того, в Фортране 77 надо реализовать в интерпретаторе возможность вызова по имени. Или, например, вы захотите добавить механизм исключений в интерпретатор. Видите, базовые вещи могут всплывать в самых неожиданных местах.

(Кстати, это объясняет, почему я добавил этюд про интерпретатор форматов. В свое время мне пришлось написать два разных интерпретатора форматов для Фортрана).

Мы начали интервью с вашей книги. А у вас есть своя «версия» Этюдов? Какие-то книги или люди, которые оказали на вас большое влияние?

Когда я учился в школе, друг моих родителей устроил меня на летом на подработку. В итоге я работал в школьном компьютерном центре. Тогда это означало ленты, перфокарты и подобные вещи. Но следующим летом школьный центр купил IBM 1401. И так как никто вокруг не знал это лучше меня, мне разрешили стать одним из программистов. Через несколько недель я уже работал над программой расчета зарплат для одного крупного государственного проекта.

Этот опыт помог мне получить работу в колледже, где тоже использовали 1401. С тех пор моя жизнь была плотно связана с компьютерами, и я решил получить высшее образование по информатике вместо того, чтобы идти работать после колледжа. Не столько благодаря знаниям, сколько везению, я попал в Корнелльский университет. На факультете мне также повезло с очень отзывчивыми людьми. Возможно, самую большую поддержку в учебе мне оказали Юрис Хартманис и Джон Хопкрофт. Я думаю, что даже сейчас книги Хопкрофта по теории языков являются классикой (в первом или втором издании). Но, как я уже сказал, все на факультете всячески помогали студентам. Если посмотреть на выпускников Корнелла с 60-х по 70-е, то можно увидеть много известных людей.

Если говорить о книгах, моим любимым автором является Кнут. Настоятельно рекомендую его «Искусство программирования». Сначала вы скорее всего мало что поймете. По моей теории эту книгу надо читать снова и снова, по несколько страниц. И с каждым разом будет открываться что-то новое.

Будучи классе десятом, я впервые увидел книгу Ньюмана «Мир математики». Она помогла мне разобраться в истории математики и информатики. Уверен, даже сейчас, для молодежи (не говоря уже о людях постарше), эта книги актуальна.

Все попадают в мир компьютеров по-разному. Возможно, сейчас это значительно проще, так как они везде. Как так получилось, что вы занялись компьютерами во времена мейнфреймов и перфокарт?

Частично я уже ответил в предыдущем вопросе. У моего отца было небольшой механический калькулятор, чем-то похожий на описанный в книге Феликса Клейна. Отцовский появился у нас от компании Ориент (я полагаю, отец получил его во время Второй Мировой), без каких-либо инструкций, и на японском языке. К счастью, цифры были арабские. Я часами пытался в нем разобраться.

В средней школе я уже интересовался компьютерами и математикой. Однажды мне достался игрушечный «компьютер», сделанный из мазонита, скрепок, винтов, цветных лампочек, батареек и проводов. Сейчас это можно было б назвать логическим симулятором, но на нем можно было собирать простые схемы, используя выключатели как входы и лампы накаливания как выходы. Я был в восторге. Я нашел несколько книг про компьютеры того времени, и это было несказанно интересно.

В первый год в старшей школе я поехал в летний лагерь, где мы изучали алгебру, теорию множеств, немного о конечных разностях (для меня все это было загадкой), и даже программировали компьютер. Там я научился играть в бридж, чтобы иметь деньги на девушек (в школе девушки являются сильным мотиватором!).

К моменту окончания школы, благодаря всему вышеописанному и нескольким курсам из колледжа (преимущественно с Томом Читемом), я был уже достаточно увлечен.

Под занавес, есть выражение про три вещи, которые каждый мужчина обязан сделать. Есть ли такие три вещи для программистов?

Не уверен, что могу назвать то, что каждый программист должен сделать. Но я знаю, что каждый программист должен знать или уметь делать.

1. Иметь познания в формальной математике. Уровня для понимания книг Хопкрофта и Ульмана, дополненного немного теорией графов, будет достаточно. Дискретная математика крайне необходима; математический анализ может понадобится в некоторых областях.

2. Умение понятно писать на родном языке. Дейкстра говорил, что человек, не умеющий писать на собственном языке, не может писать хорошие программы (надеюсь, Дейкстра это действительно говорил!). Написание программ, по сути, - как написание прозы. Если вы не можете связно излагать на родном языке, сделать это, например, на С, будет еще сложнее.

3. Стоит помнить, что программа предназначена для общения людей, а не компьютеров. Что вы напишете, то компьютер и сделает. Ему все равно, что именно. Ваша задача убедить других людей, что то, что вы попросили компьютер исполнить, правильно. Помните, компьютеру на правильность наплевать.

4. (Бонус, четыре по цене трех). Ответ на последний вопрос значит, что программы должны быть в форме понятных комментариев, объясняющих назначение кода, который следует за этими комментариями. Форматирование должно быть таковым, чтобы читателю было легко и просто понять ваш код. А компилятору без разницы. В частности, следуйте соглашениям, принятым в математике и вашем естественном языке, а не вычитанным в каком-то непонятном руководстве по языку программирования. Сначала пишите комментарии, а затем код, и не наоборот. Если вы не знаете точно, что хотите получить и почему, любой код, который вы напишете, будет, по определению, неверным.

Я надеюсь, что если посмотреть на главы «Этюдов», будет видно, что даже в те времена я старался применять эти принципы.

Спасибо, Чарльз, за ответы. Мы, поклонники «Этюдов», все еще надеемся увидеть ваши новые книги. А пока, если вы, дорогие читатели, все еще не знакомы с книгой «Этюды для программистов» Чарльза Уэзерелла, не поленитесь, прочтите. Эта книга того стоит.

■

// Чарльз Уэзерелл, Александр Дёмин

// Август 2012

P.S. Если вы хотите задать какие-то вопросы Чарльзу, можно это сделать в комментариях на странице с оригиналом интервью на английском. Чарльз постарается лично на них ответить.