Книга американского специалиста по системному программированию — уникальный сборник задач по программированию из разных областей: моделирования, точности вычислений, обработки текстов, искусственного интеллекта, конструирования компиляторов. Большинство задач базируется на реальных и игровых ситуациях.
Для всех, кто преподает и изучает программирование.
Завтрак с Чарльзом Уэзереллом, автором культовой книги «Этюды для программистов», затянулся на четыре часа. В конце-концов официантка попросила нас из ресторана в Пало-Альто, сказав что в ресторан большая очередь, а мы тут с восьми утра заседаем. За это время мы обсудили массу интересных вещий: работу Чарльза в Ливерморской лаборатории и Оракле, объектно-ориентированное и функциональное программирование, компиляторы и языки описания аппаратуры, закладки в процессоры, неэффективность нейронных сетей и незаслуженно забытый Пролог, посещение Чарльзом России, обработку текста конечным автоматом в аппаратном сопроцессоре и создание школьниками видеоигр на ПЛИС.
Содержания четырех часов с Чарльзом Уэзереллом хватит для пятидесяти статей на Хабре, поэтому перечислю в основном темы, после чего приведу некоторые детали про три из них:
- Объектно-ориентированное и функциональное программирование. Single assignment, function values, get rid of mutations, get rid of timing.
- Структуры данных и алгоритмы компиляторов. Muchnik SSA и книга по оптимизациям. Bob Morgan (Compass) building optimizing compilers. Векторизирующие компиляторы и Randy Allen (мой коллега по Wave и коллега Чарльза про другим компаниям).
- Эволюция парсера Yacc, внутренних представлений языка Ada (DIANA) и фронтенда VHDL в Synopsys.
- Атрибутивные грамматики и неудачное, на мой взгляд, использование их в методичке МФТИ по Теории Реализации Языков Программирования (ТРЯП).
- Язык программирования JOVIAL и стандартизация Ады. Язык IDL.
- Программирование в ливерморской лаборатории вычислений для физиков и химиков на CDC 7600 и Cray-1. Ливерморский Фортран — расширение Fortran-77 со структурами и днамическим выделением памяти. Использование микрофишей в том числе для автоматического поиска и изготовления анимаций. Harry Nelson. И как в лабораторию попал кубик Рубика до того, как он стал известен.
- Советский клон Cray-1 Электроника СС БИС. Компилятор Фортрана в ИПМ и компилятор Си, над которым мы работали в МФТИ.
- Реверс-инжиниринг генератора случайных чисел в Synopsys VCS. Congruential generator with register shift. LSFR.
- Неэффективность нейросетей и незаслуженно забытый язык Prolog.
- Применение методов из Пролога для статического анализа текста программ.
- В том числе анализ кода процессора, написанного на Verilog или VHDL с целью отыскания в нем закладок. Закладка, разбросанная по разным частям описания процессора на уровне регистровых передач. Нахождение «лишнего» кода, который делает что-то вне спецификации. Например конечный автомат, который ждет ключевой фразы, текст в видимых программисту регистрах, после чего переводит процессор в привилегированный режим.
- Гибридные методы анализа кода — динамическое выполнение с последующим статическим исследованием пространства состояний из некоей точки выполнения.
- Список Hakmem из MIT.
- Большинство программистов в жизни используют только пять алгоритмов — quick sort, binary search, hashing, list insertion, и еще чего-то (AVL binary tree insertion?).
- История Unix troff в Bell Labs.
- Работа Чарльза Уэзерелла в Оракле над SQL.
- Хороший пример использования аппаратного сопроцессора для MIPS CorExtend / UDI — User Defined Instructions. Добавление в процессор команд для быстрого лексического анализа, с конечным автоматом внутри сопроцессора и сохранением состояния между индивидуальными командами. История вопроса со времен IBM/360 translate test и CDC STAR.
- Использование аппаратного сопроцессора для предварительной очистки потока данных перед применением к нему алгоритмов машинного обучения.
- Игра Rogue, Scientific American в штатах и СССР.
- Летняя Школа Юных Программистов в Новосибирске и комары в ней (по моим воспоминаниям и рассказов коллег Чарльза Уэзерелла)
- Как Чарльз провел 36 часов в Москве и две недели в Питере. Эрмитаж. В питерских вузах он лекции не читал.
- Предложил Чарльзу съездить на летнюю школу в МИЭТ / Зеленоград в июле или еще куда-нибудь осенью (МГУ? МФТИ? ИТМО?).
- Обучение школьников и младших студентов. Необходимость выйти из шаблона (например последовательного программирования) и изучение Verilog на ПЛИС как один из способов выхода из такого шаблона.
- Использование микросхем малой степени интеграции перед упражнениями на ПЛИС, чтобы школьник или студент интуитивно понял, что код на Verilog — это описание электронной схемы, а не программы (цепочки инструкций).
- Пример для RTL на FPGA для летней школе в МИЭТ / Зеленоград в июле — самообучающийся конечный автомат, которые вычисляет тенденции оппонента в игре «камень ножницы бумага».
- Другой пример — соревнование конечных автоматов (зверьков), которые перемещают игрока к цели по карте (глобусу). Объекты на карте имеют «запах» — положительный (еда) или отрицательный (электричество которое может ударить). Конструирование карты в ПЛИС, вывод и спрайта игрока на VGA с помощью модуля генерации развертки.
Вот мы разбирали недавние споры на Хабре про ООП. Чарльз агитирует и за ООП, и за функциональное программирование, где оно применимо. Я показал Чарльзу увиденный мною в двух проектах пример неудачного дизайна классов для представления узлов дерева синтаксического разбора и оптимизаций на этом дереве, после чего Чарльз сказал, что конечно же алгоритмы транформации дерева разбрасывать по мелким классам таком образом не стоит, а вместо этого дерево разбора нужно быстро перекинуть в control flow graph, на котором использовать table driven transformations на основе static single assignment, с небольшим количеством исключений. Чарльз просветил меня про работы Мучника, Боба Моргана и Рэнди Аллена по векторизации:
Потом я рассказал Чарльзу, что послезавтра мы в компании будем проводить семинар в Лас-Вегасе на конференции автоматизации проектирования электроники, и мне нужен его совет по хорошему примеру сопроцессора на основе протокола CorExtend / UDI — User Defined Instructions. Это протокол используется в ядрах MIPS. CorExtend/UDI позволяет встроить в процессор блок, который декодирует и выполняет дополнительные к основной системе команд инструкции, которые может определить разработчик системы на кристалле. Блок может быть синтезирован и стать частью микросхемы или быть сконфигурирован в ПЛИС/FPGA.
Дополнительные инструкции двигаются по конвейеру процессора вместе с основными. Они получают данные из видимых программистом регистров общего назначения и могут вернуть результат в регистр. Эти инструкции также могут сохранять в сопроцессоре некое состояние. Их можно убить исключениями, если исключение произойдет например в следующей за данной инструкцией в конвейере:
Послезавтра в презентации на семинаре я собираюсь использовать пример с инструкцией простой конволюции для нейросети. Но достигаемое при этом ускорение не впечатляет — всего в два раза. Нельзя ли сделать пример получше?
Чарльз тут же придумал гораздо более удачный пример: аппаратный лексический анализ. В сопроцессор можно поместить конечный автомат, который будет определять числа, идентификаторы и комментарии в потоке текста. Он будет сохранять сохранением состояния между индивидуальными командами, которые передают текст из регистров в автомат. Результат текущего анализа (размеченный текст) будет возвращаться тоже в регистр.
Чарльз также рассказал мне историю вопроса инструкций для парсирования текста со времен 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 лет, но любой из этюдов может быть до сих пор использован по назначению. Я сам с удовольствием давал этюды из этой книги студентам.
Тематика задач совершенно разная: ретроспективная задача по программе, которая печатает свой текст, игра Джона Конвея “Жизнь”, игровое и имитационное моделирование, интерпретаторы форматов и форматирование текста, статистический анализ карточных игр, символьные алгебраические вычисления, плавающая арифметика и работа с числами большой разрядности, математические методы взлома шифров, искусственный интеллект, машина Тьюринга, рекурсивные алгоритмы поиска, компрессия данных, эмуляция виртуальной компьютерной архитектуры, связывающий загрузчик, компилятор, интерпретатор символьного а-ля функционального языка и т.д. И все эти задачи времен, когда программировали на фортране с помощью перфокарт!
Удивительно, как человек смог написать столь долгоживущую книгу, легкого и неперегруженного чрезмерной научностью содержания. Я пытался найти какие-то еще книги Уэзерелла, но безуспешно. Может это его единственная книга.
И я бережно храню переведенный на русский экземпляр до сих пор. Не исключено, что эта книга пришлась мне в нужное время, и поэтому она стала моей главной книгой.
С различным успехом, но с огромным азартом, я возился в разные времена со всеми этюдами.
Был интересный эпизод с одним из этюдов. В главе 24, под названием “Секрет фирмы, или Математический подход к раскрытию шифров” описывается задача по взлому шифра Виженера (точнее, одной из его модификаций). В книге давался зашифрованный текст, описывался метод взлома и предлагалось расшифровать секретное послание.
И так меня эта задача торкнула, что я даже списался с одним из технических переводчиков этой книги. Тогда еще мне пришлось делать это по обычной бумажной почте России. У меня была масса вопросов, так как расшифровать предлагаемый в книге пример не получалось (математический анализ я тогда еще не изучал). Мне ответили, и среди всего прочего рассказали, как они сами (те, кто переводил книгу) расшифровывали. Ведь им, чтобы опубликовать это на русском языке, надо было иметь исходное сообщение, но в книге не приводился ответ, так что пришлось засучить рукава и заняться английской шифровкой:
Решить задачу предложенным автором способом не получилось, и наши решили все по-своему (советская математическая школа показала себя), выявив, что метод автора не совсем правильный. В русском варианте в главе 24 есть “партия переводчика”, где описывается “советский” способ решения. Попутно наши переводчики выяснили, что в английском оригинале, “Etudes for programmers”, есть опечатка! Одна из строк шифровки просто пропущена. Уже после перевода они связывались с господином Уэзереллом, и тот подтвердил факт наличия досадной опечатки.
Кстати, в интернете ходит много решений “этюдов” Уэзерелла. Например, программа, играющая в Калах, или интерпретатор символьного интерактивного языка TRAC.
Но теперь к самому главному.
Пару дней назад королевская почта доставила мне то, что я так давно мечтал полистать лично — это английский оригинал этой книги.
Книга была издана аж в 1978 (я тогда даже не ходил пешком под стол, а просто лежал) и более не переиздавалась. Я купил списанный библиотечный экземпляр. Немного потертый, переклеенный скотчем по корешку, с библиотечным кармашком для карточки на обратной стороне обложки. Экстаз, один словом.
Если в мире программирования могут существовать иконы, то “Этюды для программистов” Чальза Уэзеррела одна из них.