Уэзерелл этюды для программистов

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

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

Завтрак с Чарльзом Уэзереллом, автором культовой книги «Этюды для программистов», затянулся на четыре часа. В конце-концов официантка попросила нас из ресторана в Пало-Альто, сказав что в ресторан большая очередь, а мы тут с восьми утра заседаем. За это время мы обсудили массу интересных вещий: работу Чарльза в Ливерморской лаборатории и Оракле, объектно-ориентированное и функциональное программирование, компиляторы и языки описания аппаратуры, закладки в процессоры, неэффективность нейронных сетей и незаслуженно забытый Пролог, посещение Чарльзом России, обработку текста конечным автоматом в аппаратном сопроцессоре и создание школьниками видеоигр на ПЛИС.

Содержания четырех часов с Чарльзом Уэзереллом хватит для пятидесяти статей на Хабре, поэтому перечислю в основном темы, после чего приведу некоторые детали про три из них:

  1. Объектно-ориентированное и функциональное программирование. Single assignment, function values, get rid of mutations, get rid of timing.
  2. Структуры данных и алгоритмы компиляторов. Muchnik SSA и книга по оптимизациям. Bob Morgan (Compass) building optimizing compilers. Векторизирующие компиляторы и Randy Allen (мой коллега по Wave и коллега Чарльза про другим компаниям).
  3. Эволюция парсера Yacc, внутренних представлений языка Ada (DIANA) и фронтенда VHDL в Synopsys.
  4. Атрибутивные грамматики и неудачное, на мой взгляд, использование их в методичке МФТИ по Теории Реализации Языков Программирования (ТРЯП).
  5. Язык программирования JOVIAL и стандартизация Ады. Язык IDL.
  6. Программирование в ливерморской лаборатории вычислений для физиков и химиков на CDC 7600 и Cray-1. Ливерморский Фортран — расширение Fortran-77 со структурами и днамическим выделением памяти. Использование микрофишей в том числе для автоматического поиска и изготовления анимаций. Harry Nelson. И как в лабораторию попал кубик Рубика до того, как он стал известен.
  7. Советский клон Cray-1 Электроника СС БИС. Компилятор Фортрана в ИПМ и компилятор Си, над которым мы работали в МФТИ.
  8. Реверс-инжиниринг генератора случайных чисел в Synopsys VCS. Congruential generator with register shift. LSFR.
  9. Неэффективность нейросетей и незаслуженно забытый язык Prolog.
  10. Применение методов из Пролога для статического анализа текста программ.
  11. В том числе анализ кода процессора, написанного на Verilog или VHDL с целью отыскания в нем закладок. Закладка, разбросанная по разным частям описания процессора на уровне регистровых передач. Нахождение «лишнего» кода, который делает что-то вне спецификации. Например конечный автомат, который ждет ключевой фразы, текст в видимых программисту регистрах, после чего переводит процессор в привилегированный режим.
  12. Гибридные методы анализа кода — динамическое выполнение с последующим статическим исследованием пространства состояний из некоей точки выполнения.
  13. Список Hakmem из MIT.
  14. Большинство программистов в жизни используют только пять алгоритмов — quick sort, binary search, hashing, list insertion, и еще чего-то (AVL binary tree insertion?).
  15. История Unix troff в Bell Labs.
  16. Работа Чарльза Уэзерелла в Оракле над SQL.
  17. Хороший пример использования аппаратного сопроцессора для MIPS CorExtend / UDI — User Defined Instructions. Добавление в процессор команд для быстрого лексического анализа, с конечным автоматом внутри сопроцессора и сохранением состояния между индивидуальными командами. История вопроса со времен IBM/360 translate test и CDC STAR.
  18. Использование аппаратного сопроцессора для предварительной очистки потока данных перед применением к нему алгоритмов машинного обучения.
  19. Игра Rogue, Scientific American в штатах и СССР.
  20. Летняя Школа Юных Программистов в Новосибирске и комары в ней (по моим воспоминаниям и рассказов коллег Чарльза Уэзерелла)
  21. Как Чарльз провел 36 часов в Москве и две недели в Питере. Эрмитаж. В питерских вузах он лекции не читал.
  22. Предложил Чарльзу съездить на летнюю школу в МИЭТ / Зеленоград в июле или еще куда-нибудь осенью (МГУ? МФТИ? ИТМО?).
  23. Обучение школьников и младших студентов. Необходимость выйти из шаблона (например последовательного программирования) и изучение Verilog на ПЛИС как один из способов выхода из такого шаблона.
  24. Использование микросхем малой степени интеграции перед упражнениями на ПЛИС, чтобы школьник или студент интуитивно понял, что код на Verilog — это описание электронной схемы, а не программы (цепочки инструкций).
  25. Пример для RTL на FPGA для летней школе в МИЭТ / Зеленоград в июле — самообучающийся конечный автомат, которые вычисляет тенденции оппонента в игре «камень ножницы бумага».
  26. Другой пример — соревнование конечных автоматов (зверьков), которые перемещают игрока к цели по карте (глобусу). Объекты на карте имеют «запах» — положительный (еда) или отрицательный (электричество которое может ударить). Конструирование карты в ПЛИС, вывод и спрайта игрока на VGA с помощью модуля генерации развертки.
Читайте также:  Телефон lenovo phab 2 pro

Вот мы разбирали недавние споры на Хабре про ООП. Чарльз агитирует и за ООП, и за функциональное программирование, где оно применимо. Я показал Чарльзу увиденный мною в двух проектах пример неудачного дизайна классов для представления узлов дерева синтаксического разбора и оптимизаций на этом дереве, после чего Чарльз сказал, что конечно же алгоритмы транформации дерева разбрасывать по мелким классам таком образом не стоит, а вместо этого дерево разбора нужно быстро перекинуть в control flow graph, на котором использовать table driven transformations на основе static single assignment, с небольшим количеством исключений. Чарльз просветил меня про работы Мучника, Боба Моргана и Рэнди Аллена по векторизации:

Потом я рассказал Чарльзу, что послезавтра мы в компании будем проводить семинар в Лас-Вегасе на конференции автоматизации проектирования электроники, и мне нужен его совет по хорошему примеру сопроцессора на основе протокола CorExtend / UDI — User Defined Instructions. Это протокол используется в ядрах MIPS. CorExtend/UDI позволяет встроить в процессор блок, который декодирует и выполняет дополнительные к основной системе команд инструкции, которые может определить разработчик системы на кристалле. Блок может быть синтезирован и стать частью микросхемы или быть сконфигурирован в ПЛИС/FPGA.

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

Послезавтра в презентации на семинаре я собираюсь использовать пример с инструкцией простой конволюции для нейросети. Но достигаемое при этом ускорение не впечатляет — всего в два раза. Нельзя ли сделать пример получше?

Читайте также:  Sudo dpkg i deb

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

Чарльз также рассказал мне историю вопроса инструкций для парсирования текста со времен IBM/360 translate test и CDC STAR. Еще он сказал мне, что такой сопроцессор можно использовать для машинного обучения, для предварительной очистки потока данных перед применением к нему алгоритмов машинного обучения.

Потом я рассказал Чарльзу сагу, как группа инженеров и преподавателей перевела и внедрила в различных российских вузах учебник Дэвида Харриса и Сары Харрис «Цифровая схемотехника и архитектура компьютера» (см. посты на Хабре 1, 2, 3). Сейчас объединенными усилиями МИЭТ, РОСНАНО, преподавателей МИФИ и других вузов мы планируем летнюю школу в МИЭТ на которой продвинутые школьники проектируют на ПЛИС видеоигры с выводом на графический экран (секция Между физикой и программированием). Для того используются идеи из книжки Designing Video Game Hardware in Verilog by Steven Hugg, December 15, 2018:

Игры можно разрабатывать как в виде чисто аппаратных конечных автоматов, так и в комбинации аппаратной графики на ПЛИС с программами на простом процессорном ядре schoolMIPS, которое описано в см. постах Станислава Жельнио на Хабре и wiki по schoolMIPS на GitHub. На ПЛИС можно довольно просто сделать генерацию развертки для VGA, выводить на экран карту из памяти и движущиеся спрайты c фигурками:

Чарльз предложил помимо игр с танчиками и гонками сделать соревнование конечных автоматов (зверьков), которые перемещают игрока к цели по карте (глобусу). Объекты на карте имеют «запах» — положительный (еда) или отрицательный (электричество которое может ударить). Школьники могут писать на верилоге конечные автоматы, которые видят окружение, встраивать их в код, который делает вывод графики и поддерживает карту, после чего соревноваться, у кого такой код лучше:

Для генерации элементов псевдослучайного поведения можно использовать аппаратные блоки LFSR:

Под конец Чарльз оставил два автографа — для русских читателей (русскую книгу я одолжил у Сергея Вакуленко) и читателей в нашей компании Wave Computing, из внутренней библиотеки которой я одолжил исходную книгу на английском:

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

Лет пятнадцать назад мне в руки попала книга Чарльза Уэзерелла “Этюды для программистов”.

Книга содержит 27 “этюдов”. Каждый этюд – это законченная задача для обучающихся программированию. Удивительно, книге более 30 лет, но любой из этюдов может быть до сих пор использован по назначению. Я сам с удовольствием давал этюды из этой книги студентам.

Тематика задач совершенно разная: ретроспективная задача по программе, которая печатает свой текст, игра Джона Конвея “Жизнь”, игровое и имитационное моделирование, интерпретаторы форматов и форматирование текста, статистический анализ карточных игр, символьные алгебраические вычисления, плавающая арифметика и работа с числами большой разрядности, математические методы взлома шифров, искусственный интеллект, машина Тьюринга, рекурсивные алгоритмы поиска, компрессия данных, эмуляция виртуальной компьютерной архитектуры, связывающий загрузчик, компилятор, интерпретатор символьного а-ля функционального языка и т.д. И все эти задачи времен, когда программировали на фортране с помощью перфокарт!

Читайте также:  Marvel s spider man digital deluxe edition

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

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

С различным успехом, но с огромным азартом, я возился в разные времена со всеми этюдами.

Был интересный эпизод с одним из этюдов. В главе 24, под названием “Секрет фирмы, или Математический подход к раскрытию шифров” описывается задача по взлому шифра Виженера (точнее, одной из его модификаций). В книге давался зашифрованный текст, описывался метод взлома и предлагалось расшифровать секретное послание.

И так меня эта задача торкнула, что я даже списался с одним из технических переводчиков этой книги. Тогда еще мне пришлось делать это по обычной бумажной почте России. У меня была масса вопросов, так как расшифровать предлагаемый в книге пример не получалось (математический анализ я тогда еще не изучал). Мне ответили, и среди всего прочего рассказали, как они сами (те, кто переводил книгу) расшифровывали. Ведь им, чтобы опубликовать это на русском языке, надо было иметь исходное сообщение, но в книге не приводился ответ, так что пришлось засучить рукава и заняться английской шифровкой:

Решить задачу предложенным автором способом не получилось, и наши решили все по-своему (советская математическая школа показала себя), выявив, что метод автора не совсем правильный. В русском варианте в главе 24 есть “партия переводчика”, где описывается “советский” способ решения. Попутно наши переводчики выяснили, что в английском оригинале, “Etudes for programmers”, есть опечатка! Одна из строк шифровки просто пропущена. Уже после перевода они связывались с господином Уэзереллом, и тот подтвердил факт наличия досадной опечатки.

Кстати, в интернете ходит много решений “этюдов” Уэзерелла. Например, программа, играющая в Калах, или интерпретатор символьного интерактивного языка TRAC.

Но теперь к самому главному.

Пару дней назад королевская почта доставила мне то, что я так давно мечтал полистать лично — это английский оригинал этой книги.

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

Если в мире программирования могут существовать иконы, то “Этюды для программистов” Чальза Уэзеррела одна из них.