Это перевод статьи A celebration of code – 6 pieces of code that had an impact.
- Как продуманный дизайн софта спас приземление на луну
- Быстрый обратный квадратный корень
- Game of Life Джона Конвея в APL
- Странная красота Фибоначчи в Хаскелле
- ≈ 20 строчный орфограф Питера Норвига
- «Марко! Поло!»
Код у программистов вызывает особую реакцию. Он может завораживать, восхищать или вдохновлять. А может разочаровывать, запутывать или даже вызывать страх. Недавно я спрашивал коллег, какие фрагменты кода произвели на них наибольшее впечатление. Из множества ответов я выбрал шесть, чтобы продемонстрировать разнообразие экосистемы, из которой складывается программирование. Каждый из примеров чем-то отличается, но все они одинаково впечатляют.
Строчки кода, которые для непосвященных могут выглядеть бредовыми, рассказывают истории об их авторах и пользователях: истории умных людей, людей практичных, творческих, сознательных или бесстрашных. В некоторых случаях от этих строчек кода зависели жизни людей.
Но почему мы так заботимся о том, чтобы код, который мы пишем, был элегантным и чистым? Компьютеру, безусловно, всё равно. Он добросовестно выполняет любые данные ему инструкции — без исключения, не задумываясь об их элегантности, эффективности, необходимости или разумности.
Но если ТОЛЬКО люди будут смотреть на исходный код, разве нет смысла писать его для людей? Без вопросов. Это именно тот подход, который предложили Х. Абельсон, Г. Суссман и Дж. Суссман в книге «Структура и интерпретация компьютерных программ». По мнению авторов, «программы должны писаться в первую очередь для чтения людьми и только попутно для исполнения машинами». Следующие шесть фрагментов кода — отличный пример этого принципа.
Как продуманный дизайн софта спас приземление на луну
Первый пример в этой статье — история невероятных обстоятельств и необходимость в максимальной надёжности.
Успешно завершив несколько суборбитальных и орбитальных пилотируемых космических полётов программы "Меркурий", НАСА нацелилась выше (игра слов) с экспедициями «Аполлона». Конечная цель — достигнуть лунной орбиты, и в завершении выполнить полноценную посадку — невероятно повысила уровень сложности. Когда полёт происходит относительно близко к Земле, можно выполнять все необходимые навигационные вычисления тут же, но те же вычисления — вообще не вариант для лунных миссий. Понадобился компьютер, который находился бы на космическом корабле и контролировал его. Так был создан компьютер управления Аполлоном (AGC — Apollo Guidance Computer).
Несмотря на свою скромность по современным стандартам, AGC был гением инженерии. Умещённый в форм-фактор размером с чемодан, со скромным энергопотреблением 55 ватт, он мог выполнять около 85 000 инструкций CPU в секунду — эквивалентно полноразмерному мейнфрейму IBM System/360, размером с холодильник. Настолько же впечатляет, как он был запрограммирован: на собственном языке ассемблера, который хранился в блоках верёвочной памяти (тип постоянной памяти, подобной RAM на магнитных (ферритовых) сердечниках, где отдельный сердечник не хранит информацию, а только выполняет роль трансформатора — прим. переводчика), напоминающих плетёные вручную нити для ткачества. Программное оборудование, созданное MIT Instrumentation Laboratory, под руководством Маргарет Гамильтон, позднее назовут «базой сверхнадёжного дизайна софта».
Как программисты, большинство из нас стремится создавать надёжные программы, и, конечно же, никто не строит некачественный софт намеренно. Однако в контексте миссий для полётов на Луну, требования к надежности программного и аппаратного оборудования далеко за пределами того, с чем подавляющее большинство из нас когда-нибудь столкнётся. Мало того, что программы хранились в read-only памяти, а следовательно, не могли быть изменены во время экспедиции, самые мельчайшие логические ошибки могли привести к тому, что астронавты остались бы брошенными на Луне или оказались в открытом космосе без возможности вернуться на Землю. Было ясно, что для ошибок и погрешностей нет никаких оправданий, но было невозможно протестировать все вероятности, когда могли произойти нарушения в течение такой долгой миссии. Эти два ограничения означали, что если что-то произойдёт, на исправлении ошибок и восстановлении будет сосредоточено значительное количество сил. И всё, конечно же, пошло не так.
На четвёртый день миссии Нил Армстронг и Базз Олдрин отделили лунный модуль Аполлона от командного модуля и начали спуск к поверхности Луны. Когда оставалось всего 6000 футов (1,83 км) до поверхности, компьютер управления лунным модулем начал выдавать коды ошибок. Компьютерная система реального времени внезапно начала получать тысячи прерывающих сигналов от радара сближения, который отслеживал командный модуль. Эти помехи были ответственно обработаны бортовым управляющим компьютером, который внезапно оказался перегруженным работой. Хоть краткая перегрузка вряд ли была бы проблемой для тех, кто ковыряется с Excel таблицей, она, несомненно, означала катастрофу для астронавта, который справляется с посадкой космического корабля, приземляющегося на Луну.
К счастью, софт лунного модуля был тщательно спроектирован и, столкнувшись с перегрузкой задачами, легковесная операционная система реального времени прервала обрабатываемые задачи, которым был задан более низкий приоритет. В такой жёстко контролируемой системе кооперативная многозадачность была целесообразным выбором, который позволил системе возобновить критические задачи — вроде управления ориентацией, отбросив другие операции до тех пор, пока циклы не возобновятся. Если бы не продуманная работа команды Гамильтон, экспедиция, скорее всего, была бы далека от успеха. Именно их работа буквально сформировала ход истории, а спустя годы эти две строки кода (EXECUTIVE.agc # L147 и EXECUTIVE.agc # 208) свидетельствуют об этом выдающемся достижении.
Быстрый обратный квадратный корень
Сделай код рабочим, сделай его качественным, а потом сделай его быстрым — это старая поговорка, напоминающая о рисках преждевременной оптимизации. Однако бывают моменты, когда растяжение границ производительности рождает инновации.
Любому человеку, имевшему хотя бы малейший интерес к компьютерам и интернету, в 1999 году снесло крышу. Фильм «Матрица», с Киану Ривз в роли главного героя, предложил мрачный взгляд на антиутопическое будущее, где компьютеры поработили человечество и погрузили его в симуляцию настолько реалистичную, что люди не могли этого распознать. В реальной жизни, однако, состояние компьютерной графики было далеко от фотореализма. И тут причина не в слабости мастерства, поскольку разработчики графических программ в то время пытались выйти за стандартные рамки ранних графических процессоров OpenGL.
В то время id Software была одной из самых легендарных студий, она была известна творением одного хита за другим — каждый из них делал революционные шаги в графике компьютерных игр. В 1999 году id Software выпустили Quake III Arena, сигнализируя о переходе на новейшую версию своего встроенного игрового движка id Tech 3. Это привнесло несколько характерных новых возможностей, включая ограниченную поддержку шейдеров, за несколько лет до того, как эти функции появились в графических процессорах. В основе процесса рендеринга Quake III Arena лежит незаметный, но жизненно важный фрагмент кода — алгоритм быстрого обратного квадратного корня.
И только после релиза исходного кода Quake III Arena в 2005 году знания об алгоритме распространились более широко. До того момента он передавался как тайный рецепт зелья от одного разработчика другому, и буквально единицы знали о его существовании. До сих пор автор алгоритма остается неизвестным, но лучшие из возможных вариантов его происхождения предполагают Грега Уолша, Клива Молера и Уильяма Кахана в конце 1980-х годов. Несмотря на то, что его важность была чётко продемонстрирована, алгоритм оставался в значительной степени неизвестным до начала нового тысячелетия. Единственным доказательством знания об алгоритме вне оригинального круга авторов оказалась пара архивных сообщений на китайском форуме разработчиков.
Алгоритм (исключая директивы препроцессора и комментарии) выглядит так:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}
Источник
Разбитый на составляющие, алгоритм использует умный ход, чтобы быстро найти грубо приближенный обратный квадратный корень, а затем постепенно уточнять его, используя метод Ньютона. Тайной осталось то, как была найдена магическая константа 0x5f3759df. Похоже, что это число было известно уже несколько десятилетий и передавалось только избранным. С тех пор как алгоритм стал известен широкой аудитории, была найдена улучшенная константа, которая совершенствует приблизительную величину.
Важность роста скорости, которую даёт алгоритм, напрямую связана с областью, в которой он используется. Чтобы визуализировать полноэкранные шейдеры реального времени, вычислять углы падения теней и отражения для имитации освещения, векторные вычисления должны выполняться миллионы раз в секунду. До появления аппаратно-ускоренных преобразований и освещения, эти вычисления выполнялись в процессоре, и именно их значительно ускорил быстрый алгоритм обратного квадратного корня. Используя этот алгоритм, Quake III Arena была способна поддерживать ряд дополнительных функций программной реалистичной визуализации, которые стали доступны только в аппаратно-ускоренной форме спустя годы.
Game of Life Джона Конвея в APL
В жизни почти любого программиста есть смысл, если он решится на одну задачу, несомненно приносящую радость — создать свою собственную версию Game of Life Джона Хортона из 1970-х. Это интересное испытание, оно не занимает слишком много времени, а результаты и отдача — приятны. Большинство начинающих программистов предпочитает императивный стиль программирования, который также даёт множество возможностей для обучения. Но Йони, один из наших синьор разработчиков, был сильно впечатлён (а любопытство к функциональному программированию подогревало его интерес), увидев Game of Life, реализованную в APL.
Правила Game of Life очень просты. Игровая площадка — это простая двумерная матрица ячеек. Поскольку симуляция двигается на один шаг за раз, рождение, жизнь или смерть клеток определяют простые правила, в зависимости от состояния в котором находятся соседи каждой клетки. Из этих простых основ, которые составляют идею Game of Life, строится удивительно комплексное поведение. Комбинации клеток могут действовать сообща в предсказуемом стиле, и эти комбинированные структуры, как видно, являются полными по Тьюрингу.
Начав с простых глайдеров и автоматов, любители вышли за границы и продолжили реализацию логическими воротами, вплоть до метапикселей (имитацию пикселей на экране компьютера), и в итоге создали Game Of Life внутри Game Of Life. В течение нескольких лет группа пользователей CodeGolf StackExchange реализовала рабочий, программируемый CPU (с ROM, RAM и ALU юнитами) в Game of Life, на котором можно запускать Tetris.
Если «Матрица» — это правда, и мы все живём в гигантском симуляторе, теперь есть определённая вероятность, что всё это построено на почтенной Game of Life.
Странная красота Фибоначчи в Хаскелле
Ключевая часть программирования — выбор правильного уровня абстракции для определённой задачи. Разные языки программирования предлагают разные уровни формулировки в исходном коде, и особенно в последние годы функциональные языки программирования восстали из мглы веков и набирают всё большую популярность. Причина, по которой эти языки часто получают признание своих пользователей в том, что как только вы переключитесь на восприятие новой информации новым способом, особенно если ваш предыдущий опыт больше связан с императивными языками — вы получите награду в виде совершенно нового уровня абстракции для формулировки задач и их решений.
Для нашего разработчика Юхи, автора библиотеки функционального реактивного программирования bacon.js, это откровение пришло в форме реализации последовательности Фибоначчи в Haskell. Большинство решений последовательности Фибоначчи склоняется к простому циклу for и является ещё одним основным элементом головоломок программирования. Haskell, как чистый функциональный язык с ленивой семантикой, позволяет строить решение намного более лаконичным способом. Учитывая, что математическое определение последовательности Фибоначчи просто Fn = Fn-1+Fn-2, Haskell позволяет выразить эту последовательность в почти такой же краткой форме:
fib = 0 : 1 : zipWith (+) fib (tail fib)
Это, конечно, даёт бесконечный список чисел, который во многих других контекстах приведёт к бесконечному циклу и программной ошибке. Однако в Haskell, ленивом языке, список может быть выражен и выполнен отдельно, что позволяет программисту взять столько значений, сколько необходимо для конкретного случая. По словам Юхи, возможность формулировать бесконечные вычисления привела к тому, что структура и интерпретация компьютерных программ могут быть разделены. Слова Юхи: «мне сорвало крышу, когда я увидел это в первый раз. Чувак, ты просто застёгиваешь список его же концом!
≈ 20 строчный орфограф Питера Норвига
Мы, люди, далеки от совершенства. Наши пальцы работают с клавиатурой и сенсорными экранами, и время от времени оказываются не совсем там, куда мы намеревались нажать. Часто эти ошибки довольно мелкие и забавные, но бывают случаи, когда они имеют катастрофические последствия. В 1962 году зонд Mariner 1 был потерян из-за опечатки, орфографической ошибки, которая стоила НАСА около 18,5 миллионов долларов. Хоть проверка орфографии, вероятней всего, не спасла бы Mariner 1, не сюрприз, что подобные решения — основной продукт обработки естественного языка.
Хоть в последние годы и произошёл сдвиг в области глубоких нейронных сетей, они всё так же считаются тяжеловесными инструментами, которым требуется большой объем обучающих ресурсов и приличная доза времени CPU для обучения. Результаты довольно впечатляющие, но столь же впечатляет реализация, созданная вручную Питером Норвейгом, написанная ещё в 2007 году во время трансатлантического перелёта. Для такого быстрого и короткого (около 36 строк) решения, этот кусок кода добился приличной точности, равной приблизительно 70%.
Очевидно, коррекция орфографии — авторитетная область науки, а результаты Норвейга проигрывали несколькими факторами. Этот пример одинаково можно применить к любому менее изученному софту для машинного обучения. Перед тем, как резко переходить к обучению полноценной, сложной модели, есть смысл поэкспериментировать и наметить простую базовую линию, с которой можно будет сравнивать любые потенциальные улучшения. Иногда «удовлетворительное» решение задачи буквально «самая простая штука, которая может сработать».
«Марко! Поло!»
Конечно, сорванная крыша — это очень субъективный опыт. То, что удивительно и ново одним — ежедневная рутина для других. Тем не менее, многие программисты всё ещё помнят точный момент, когда их зацепило. С одним из наших разработчиков Марко это случилось, когда он ввёл вот эти две строки в интерпретатор Commodore 64 Basic:
10 PRINT "MARKO"
20 GOTO 10
Остальное уже история. Для маленького ребёнка сама идея управлять компьютером и давать ему команды — захватывающа и нова. В одно мгновение ты превращаешься из потребителя игр и развлечений в создателя новых и свежих идей. Естественно, что первый код при написании собственных программ часто был громоздким, но вскоре интерес и опыт росли, и всё более и более сложные проекты обретали жизнь. Не потребовалось бы много времени, для выхода за пределы возможностей системы C64 Basic, но оперативность компьютера принесла новые возможности.
В отсутствии абстракции, Commodore 64 позволял записывать в ячейку оперативной памяти (POKE) и считывать из памяти напрямую (PEEK), инициируя различные эффекты (как желательные, так и нежелательные, но в основном милые).
Естественно, можно было использовать эти возможности, чтобы разыгрывать друзей и ничего не подозревающих владельцев магазинов. Кто-то подошёл к этому с фантазией и стал программировать на ассемблере. Независимо от того, какой уровнь знаний вы обрели, точка отправления была одинаковой, и система содержала все необходимые инструменты, чтобы писать в оперативную память напрямую и не бояться её сломать. Даже самое грубое обращение с адресами памяти всегда можно было поправить одним щелчком переключателя.
В определённом смысле недавно мы двинулись в другом направлении: в нашем полном распоряжении есть больше вычислительной мощности, чем когда-либо, но возможностей проникать в её глубь, чтобы понять, как там всё устроено, становится всё меньше и меньше. Тим Кук, если вы читаете это, я хочу вернуть свою возможность прямой записи в оперативку!
(Примечание автора: сообщество программирующих на C64 все ещё существует и чувствует себя хорошо)
Эта статья — всего лишь небольшая группа случаев, которые наша команда считает удивительными фрагментами кода. Естественно, в такой обширной области, как компьютеризация, примеров, которые могут вызвать похожее драматичное разрастание серого вещества, безграничное множество — у вас, возможно, есть свои.
