Pull to refresh
57
0
Пётр Советов @true-grue

User

Send message

Для первых двух примеров я бы предложил написать учебный интерпретатор на уровне питоновского AST. Учитывайте при реализации отсутствие в Питоне явных объявлений переменных.

По третьему примеру могу сказать только, что код перед публикацией надо бы проверять на корректность :)

Это неплохая вводная книга, но выбор для издания именно Racket-версиии -- сомнительное решение. Код в версии учебника для Python вместе с match/case выглядит, местами, даже изящнее Scheme. Да и читательский охват был бы шире.

Я, кстати говоря, вовсе не против разработки компиляторов на Racket, это замечательный диалект Scheme, но в рассматриваемом учебнике нет какой-то особенной специфики теории компиляции функциональных языков или LOP (Language-Oriented Programming).

Если вы знакомы с английским, то Python-версию книги можно совершенно свободно скачать здесь: https://github.com/IUCompilerCourse/Essentials-of-Compilation

P.S. А если вас интересуют прикладные аспекты разработки DSL-компиляторов на Python, то могу порекомендовать посмотреть мой недавний доклад: https://www.youtube.com/watch?v=h-TzDPL2nDE

Любопытный проект! Очень хорошо, что нацелились на простоту, минимализм и не используете LLVM.

От постоянных isinstance в коде можно было бы отказаться с помощью match/case (эту конструкцию для компиляторщиков и придумали, я почти не шучу). В этом докладе я агитирую за нее: https://github.com/true-grue/python-dsls

Отечественная версия «Змейки» (хотел сказать, как на телефоне Nokia, но тогда на телефонах еще не было игр)

Ага, а еще -- одна из самых оригинальных российских игр за всю историю.

В Rosetta 2, насколько я знаю, гибрид SBT/DBT, это учитывалось при сравнении?

Время трансляции не сравнивалось, это любопытный момент. Есть известные унивесальные приемы в духе супероптимизации, позволяющие получить хороший результат SBT-трансляции ценой весьма длительного времени работы транслятора.

Извините, что встреваю, но в подобных случаях полезно посоветовать классику :) https://norvig.com/21-days.html

Поддерживаю! На мой взгляд, одно из самых серьезных произведений в жанре, с точки зрения проработки технологий будущего. Очень достоверно показано, как люди будут жить при AR. Любопытно, что большинство моих знакомых "ценителей жанра" прошло мимо Dennou Coil, а жаль.

Согласен, на самом деле это весьма важные сегодня вопросы статического параллелизма. Если отвлечься от спецпроцессоров, то в современных процессорах общего назначения статически распараллеливаются операции команд SIMD-расширений и скоро, судя по всему, придется статически учитывать задержки при межядерных коммуникациях, как на картинке ниже:

Со времен работ Карцева технологии компиляции и, в частности, статического анализа, интенсивно развивались. Но Карцев отметил в своем учебнике, что наиболее радикальным решением было бы "создание принципиально новых языков программирования". Вообще, еще раз замечу, что в книге очень много интересных положений.

Спасибо за комментарий!

По поводу 2-6 процессоров. В книге, говоря современным языком, речь идет о функциональных узлах в составе одного VLIW-ядра. Интересно, что Карцев весьма консервативен в своей оценке. В этом смысле любопытно вспомнить, что в VLIW-проектах Фишера фигурировало до 30 параллельных RISC-операций!

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

В целом, речь идет об ограничениях для двух разных типов параллелизма. Если воспользоваться терминологией Карцева, то это параллелизм смежных операций (внутри ядра) и параллелизм независимых ветвей (на уровне системы ядер).

По поводу "не реализуемо в принципе". Цитата из учебника верна не только для VLIW, так работают in-order процессоры. Я с Вами согласен, что для специализированных процессоров такие решения наиболее применимы.

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

Индуктивный синтез программ, в сущности, представляет собой поиск в пространстве возможных программ по заданной спецификации (состоящей из примеров входов и выходов, различного рода ограничений). В супероптимизаторах предпочтение отдается самому короткому решению, поэтому синтез начинают с программы длиной 1, затем 2 и так далее.

Вот, к примеру, уже классическая работа по синтезу линейных RISC-подобных программ: Synthesis of Loop-free Programs.

Любопытная заметка! Спасибо Вам за ссылку на статью, послужившую вдохновением. Странно только, что Вы поместили свой текст в "компиляторы", но ни словом не обмолвились, что техника, которую Вы применяете, относится к известному и весьма сегодня популярному направлению -- синтезу программ. Опять же, если обращаться к компиляторным технологиям, хотел бы поинтересоваться, почему в своих решениях Вы не пошли по пути традиционной супероптимизации?

Жаль разочаровывать, если Вы ожидали увидеть там скрытый намек на "Эльбрус" или Itanium.

Авторы RISC-V не верят в перспективы VLIW в области GPP, об этом они неоднократно заявляли. Как и большинство специалистов сегодня, Хеннесси с Паттерсоном разделяют мнение, что VLIW-архитектуры замечательно себя показывают в области предметно-ориентированных ускорителей и в этом отношении RISC/CISC им, в целом, не конкуренты.

Перед авторами RISC-V стояла непростая задача обеспечения точек роста новой архитектуры. Поэтому в RISC-V стандартизированы возможности расширения команд, добавления специализированных ускорителей. Естественно, речь не идет о "каких угодно расширениях" (это самое "что угодно" добавляется в отдельные ускорители) и, в частности, вы не найдете в документе ничего о TTA, Dataflow или каких-нибудь CGRA.

По какой причине возник небольшой, укладывающийся в одну страницу, раздел VLIW-расширения? Думаю, авторы предполагали возможность реализации простых компактных вариантов в духе 2-issue in-order.

С удовольствием! Информация есть в документе The RISC-V Instruction Set Manual (https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf). См. раздел Supporting VLIW encodings. Он начинается со следующего абзаца:

"Although RISC-V was not designed as a base for a pure VLIW machine, VLIW encodings can be added as extensions using several alternative approaches. In all cases, the base 32-bit encoding has to be supported to allow use of any standard software tools".

Мне известно о существовании нескольких академических RISC-V VLIW-процессоров, но, в целом, разумеется, типичный современный VLIW-ускоритель удобнее добавлять к RISC-V-ядру отдельно.

Имело бы смысл упомянуть о современных применениях VLIW, чтобы не было вопросов к уровню компетентности автора. Вы же в тексте просто "поставили крест" на архитектуре. Это относится и к весьма наивному разделению на CISC (x86) и RISC (ARM). Я, конечно, могу предполагать, что Вы в таком ключе пишете, рассчитывая на аудиторию, не вникающую в подобные тонкости, но, все же.

А вот реакция на мои слова о "ценнейшем опыте", как мне показалось, получилось чрезмерной. Уже достаточно давно процессоры не принято разрабатывать "на коленке за вечер под пиво". Мне кажется, Вы здесь поторопились с ответом и, на самом деле, вполне в курсе понятий design space exploration, compiler-in-the-loop, hardware/software codesign. Процессор со статическим параллелизмом -- как раз очень интересный объект научного исследования на компиляторную тематику. По мотивам "эльбрусов" мне вспоминается несколько вполне приличных научных статьей, диссертаций и даже стартапов международного уровня.

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

  1. Архитектура VLIW "плоха": менее производительна чем RISC/CISC и не энергоэффективна.

  2. Оригинальные процессорные архитектуры разрабатывать вовсе не следует.

Выше уже справедливо заметили, что в области специализированных процессоров первое положение полностью безосновательно. Но специализация может быть достаточно широкой. Возьмем, к примеру, VLIW-процессор 2018 года от Kalray для задач Embedded HPC, Networking, Storage. Что он собой представляет: 16 nm, 85 64-bit VLIW-ядер, энергопотребление 5-15W. Тактовая частота (1.2 Ghz) этого процессора даже ниже, чем у современных "эльбрусов", но, очевидно, это еще ни о чем не говорит, правильно?

Почитайте того же Д. Паттерсона -- он считает VLIW-архитектуры вполне перспективными и для будущих domain specific architectures. Даже в популярной архитектуре RISC-V нашлось место стандартному VLIW-расширению.

И я уже не говорю о том, что сама классификация RISC/CISC уже сильно устарела. Есть хорошая фраза в одной недавней статье: "CPUs are gradually becoming sets of discrete accelerators around a shared register file".

По поводу целесообразности создания собственных архитектур. Работа в проекте по созданию процессора с оригинальной архитектурой -- это ценнейший практический опыт для представителей целого ряда редких профессий (RTL-дизайнеры, топологи, компиляторщики, ...). Это важно и для развития академических исследований. В мире количество экзотических процессорных архитектур только растет. Из свежего могу, к примеру, вспомнить Ascenium Aptos и Tenstorrent Tensix. В целом, отмена закона Деннарда, замедление выполнения закона Мура -- побуждают искать новые решения в области процессорных архитектур. Современные технологии компиляции и средства разработки компиляторов (те же LLVM/MLIR) сильно снижают остроту проблемы "процессор-то мы спроектируем, а где оптимизирующий компилятор взять".

Уверен, что заметка получилась бы лучше, если бы автор сконцентрировался исключительно на критической оценке "эльбрусов" в конкретной области их применения.

Сам подход процедурного порождения палитр используется уже давно. Используется в некоторых ограниченных по ресурсам системах. Конечно же, яркий пример здесь — демосцена. Вот ссылка на классическую уже работу в этой области (интересно, знаком ли с ней автор?).

www.iquilezles.org/www/articles/palettes/palettes.htm
Я вижу, что Вы проигнорировали приведенный выше код и это меня, признаюсь, несколько огорчило. Но попробую объяснить на словах.

Комбинаторы — удобный способ создавать простые eDSL на языке, который поддерживает механизм лексических замыканий. Соответственно, комбинаторами мы можем описать БНФ-грамматику, разбор для которой может быть на деле совершенно произвольным.

По-настоящему популярным подход без выделенной стадии лексического анализа стал с появлением работ по PEG (напомню, что одна из сильных сторон scannerless-подхода — удобное описание вложенных грамматик). Соответственно, далее я буду рассматривать PEG-комбинаторы. Если мы посмотрим на классическую уже статью Форда, то увидим в одном из примеров набор правил, часть которых относится к уровню лексического разбора, а другая — к синтаксическому разбору.

...
DOT <- ’.’ Spacing
Spacing <- (Space / Comment)*
Comment <- ’#’ (!EndOfLine .)* EndOfLine
...


Здесь сразу становится понятно, что как отдельную сущность, в духе Вашего примера на Scala, комментарии выносить на уровень синтаксических правил совершенно излишне. Но остается Spacing, который действительно повторяется достаточно часто.

В таких системах, как Ometa и Ohm, Spacing неявно вызывается при указании правила для соотв. токена. Например, в Ometa Spacing будет вызван, если Вы в качестве имени правила указали класс токена в кавычках. Комбинаторы же сильны своей программируемостью и мы всегда можем задать удобную для нас функцию высшего порядка, в духе:

seq(kw("if"), op("("), expr, op(")") ...

Здесь, kw и op занимаются, в том числе, разбором пробельных элементов. Ну а Ваш пример будет выглядеть следующим образом:

args = list_of(expr, op(","))

В целом, я бы порекомендовал перед использованием готовых комбинаторов поупражняться в создании игрушечной системы на основе PEG. Поскольку, как я уже сказал выше, комбинаторы хороши своей программируемостью и Вы мало выиграете, если будете только пассивно пользоваться готовыми возможностями.
Подход официально называется scannerless parsing. При использовании передовых генераторов синтаксического разбора (см., например, SDF3 и статью) такой подход показывает себя наилучшим образом.

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

github.com/true-grue/PigletC/blob/master/src/parse.py
Вирт, прежде всего, это ученый и учитель. В этом смысле не так важно, какой путь избрала индустрия. Можно критиковать тот же «Проект Оберон» за непрактичность и проч., и большая часть критики будет справедлива. Но, важное уточнение, ведь это учебный проект. И, как мне кажется, будет очень хорошо, если вчерашний студент придет в индустрию, имея в том числе, опыт работы на 1-2 курсе над чем-то подобным «проекту Оберон».

В целом ведь дело не в самодовлеющей простоте и минималистичности. Помните виртовский метод пошагового уточнения/улучшения программы? Это применимо и к языкам. Представьте себе язык программирования, стандарт на который с каждой версией становится все тоньше, все яснее. На каждой итерации выделяются более мощные, общие языковые механизмы, а все не нужное отсекается. В этом смысле Оберон хорош даже не как конкретный ЯП, а как идея подхода к разработке ЯП.

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

Information

Rating
Does not participate
Location
Россия
Registered
Activity