Кодеры за работой. Размышления о ремесле программиста

Сегодня Норвиг - глава исследовательского отделения Google, ранее руководил отделением качества поиска. До прихода в Google возглавлял подразделение вычислительной техники исследовательского центра НАСА, а до того, в конце 1990-х, был одним из первых сотрудников интернет-стартапа Junglee. Норвиг - лауреат Премии НАСА за выдающиеся достижения (2001), член Американской ассоциации искусственного интеллекта и Ассоциации вычислительной техники.

Благодаря опыту работы в Google, НАСА и Junglee Норвиг знаком как с “ха-керским”, так и с “инженерным” подходом к созданию ПО. В нашей беседе он коснулся преимуществ и недостатков каждого из них. Как у бывшего профессора информатики, а ныне сотрудника одной из крупнейших корпораций по производству ПО, у него есть интересный взгляд на отношения между академической компьютерной наукой и промышленной практикой.

Мы говорили о том, как изменилось программирование за последние годы, почему никакие методы проектирования не помогут тому, кто не понимает, что делает, и в чем НАСА может выиграть, применяя менее надежное, но дешевое ПО.

Сейбел: Когда вы начали программировать?

Норвиг: В старших классах школы. У нас был PDP-8, кажется так, и уроки информатики - мы осваивали Бейсик. Там-то все и началось.

Сейбел: Какой это был год?

Норвиг: Я закончил школу в 1974 - значит, 1972 или 1973. Кое-что осталось в памяти. Помню, как учительница пыталась что-то объяснять, тасуя колоду карт. Алгоритм был примерно такой: используем генератор случайных чисел для выбора двух карт, поменяем их местами, отметив это в битовом векторе, и будем продолжать, пока не поменяются местами все карты. Помнится, я подумал: “Что за идиотизм, глупее не придумаешь. Так можно продолжать до бесконечности, потому что на какую-то пару карт можно никогда не попасть”. Я еще не мог сказать тогда, что это n в квадрате, хотя такой алгоритм может быть порядка n. Я просто знал, что алгоритм неправильный. Потом я предлагал алгоритм перестановки, кажется, Кнута - от 0 до 52, затем от 0 до 51 и так далее - алгоритм порядка n. Но помню, что учительница отстаивала свой способ. Тогда я понял, что у меня, видимо, есть способности к программированию, а еще - что учителя тоже не все знают.

Сейбел: Вы сразу поняли, что ее алгоритм неправильный? Или сначала покрутили в голове, а потом уже осознали, что тут много лишней работы?

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

Еще я полистывал найденные на антресолях старые номера “Scientific American” - этот журнал выписывал отец. Там была статья Кристофера Стрейчи о проектировании ПО: автор утверждал, что ожидается переход на высокоуровневые языки. Он придумал язык, компилятор для которого так и не появился, - чисто бумажный язык - и хотел писать на нем программу для игры в шашки. Это была первая нетривиальная программа, о которой я узнал, - в школе мы не шли дальше тасования карт. Недавно я перечитывал ее и первое, что заметил, - ошибку. Просто здорово - ведь Стрейчи знал толк в программах, в “Scientific American” были редакторы, но ошибку никто не увидел. В пояснении он описывал функцию “сделать ход”, которая получала позицию на доске и возвращала ход, но в коде у этой функции кроме позиции на доске был еще один параметр. Они явно начали с описания, а код писали позже. И выяснили, что бесконечный поиск невозможен, поэтому ввели дополнительный параметр - “глубину поиска”: вызывать функцию рекурсивно можно было только до установленного предела. Это добавили позже, а документацию не исправили.

Сейбел: Это была первая интересная программа, с которой вы познакомились. А какой была первая интересная программа, которую вы сами написали?

Норвиг: Наверное, Game of Life. Это было домашнее задание, которое я быстро сделал. Конечно, никаких 30-дюймовых мониторов не было - только телетайп с желтой бумагой. Я подумал, что расточительство - печатать на отдельном листе одно маленькое поле (кажется, 10x10), на следующем - еще одно и так далее. Поэтому я решил распечатать пять поколений подряд. В Бейсике не было трехмерных массивов, а я почему-то не мог просто взять несколько двухмерных массивов - памяти не хватало или еще что-то. Мне нужно было пять или шесть двумерных массивов, и тогда я придумал битовые поля.

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