Отчет с завтрака с Чарльзом Уэзереллом, автором культовой книги «Этюды для программистов»

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



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

    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 с помощью модуля генерации развертки.


    Вот мы разбирали недавние споры на Хабре про ООП. Чарльз агитирует и за ООП, и за функциональное программирование, где оно применимо. Я показал Чарльзу увиденный мною в двух проектах пример неудачного дизайна классов для представления узлов дерева синтаксического разбора и оптимизаций на этом дереве, после чего Чарльз сказал, что конечно же алгоритмы транформации дерева разбрасывать по мелким классам таком образом не стоит, а вместо этого дерево разбора нужно быстро перекинуть в 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, из внутренней библиотеки которой я одолжил исходную книгу на английском:



    Only registered users can participate in poll. Log in, please.

    Если Чарльза Уэзерелла пригласить в Россию, то где ему прежде всего стоит выступить?

    • 8.6%В МГУ10
    • 23.3%В МФТИ27
    • 4.3%В Сколково5
    • 13.8%В Зеленограде16
    • 12.1%В ИТМО14
    • 28.4%В Сибири33
    • 9.5%В другом месте (укажите в комментариях)11

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 14

      +3
      Два гения собрались!
      Как можно за 4 часа обсудить столько тем.
      • UFO just landed and posted this here
          +1
          Оказывается, вот для чего Юра у меня книжку одолжил.
          Классный автограф, спасибо!
            0
            И всё же вы форменный маньяк.
            P.S. Побольше бы таких.
              0
              Спасибо. Ваше мнение по возможности продвижения обучения TLA+ в университетских\околопрограммных средах?
                0
                Я не работал с TLA+, но я работал и работаю с SVA (SystemVerilog assertions) там тоже темпоральный язык («если в некоем цикле то-то и то-то произойдет, то в течение 3-5 циклов нужно ждать такое-то событие») и софтвер для формального доказательства свойств кода на уровне регистровых передач. Это можно внедрить в курс hardware register transfer level verification как часть курса digital design. Нужда индустрии, в том числе российской, в этом есть.
                0
                По поводу игр на FPGA вот, такие темы могут быть:
                1) Игра River Raid: habr.com/ru/post/313092
                2) Игра Жизнь: habr.com/ru/post/282722
                3) Игра теннис: marsohod.org/projects/plata1/7-videogametennis
                4) Игра питон: marsohod.org/projects/plata1/151-snake
                из чего-то совсем простого Волк-Коза-Капуста:
                marsohod.org/projects/plata1/70-koza

                  0
                  Оффтоп
                  Игры Питон, Тетрис, Жизнь можно реализовать на LED-матрице



                  +1
                  «Этюды для программистов» — великая книга по содержанию и уникальная по форме (я воспользовался этой формой). Было бы очень интересно, если бы Чарльз Уэзерелл написал на Хабр статью и ответил на вопросы Хабровчан — благо теперь на Хабре можно писать и на английском. Из перечисленных тем, мне особо интересной показалась:
                  Неэффективность нейросетей и незаслуженно забытый язык Prolog.


                  Спасибо за интересный Отчет и респект Чарльзу!
                    0
                    Это будет проходить в самом МИЭТ? Или где-то в Зеленограде? Интересуется студент, если что!)
                      0
                      В смысле летняя школа в МИЭТ (Чарльз Уэзерелл на нее пока не планирует)? В посте есть ссылка bit.ly/miet-summer-school-2019
                      0
                      Спасибо за интересный отчет!
                      Были бы рады видеть Чарльза Уэзерелла в МИЭМ НИУ ВШЭ.)
                        0
                        Надо же. В моём сознании Уэзеррел стоит в одном ряду с Кнутом, Дейкстрой, Виртом, Керниганом… Потому что в далёких 80-х, когда мы ещё учились в школе, а компьютеры и программирование были совсем другими, его книжка уже была классикой.
                        А на фотке он не выглядит таким уж древним.
                          0
                          Ты знаешь, Гуля, я тоже был удивлен. У него очень живое, подвижное мышление, как у 30-летнего. И хранящая многие подробности память.

                        Only users with full accounts can post comments. Log in, please.