Особенно же интересными (субъективно, разумеется) событиями симпозиума по Лиспу оказались: доклад и семинар по передовому фреймворку (набор eDSL на языке Scheme) для быстрой разработки компиляторов Nanopass. По Nanopass как раз не хватало свежей, актуальной информации в авторском изложении.

Доклад The Nanopass Framework as a Nanopass Compiler
Слайды: https://www.european-lisp-symposium.org/static/2020/keep-slides-keynote.pdf
Видео: https://www.youtube.com/watch?v=lqVN1fGNpZw

Семинар Mixing Mutability into the Nanopass Framework
Слайды: https://www.european-lisp-symposium.org/static/2020/keep-slides-workshop.pdf
Видео: https://www.youtube.com/watch?v=wTGlKCfP90A

#langworkbench #dsl #nanopass

Возможно, вы уже слышали новость о древнем GW-BASIC. Компания Microsoft выложила исходники интерпретатора на github: https://devblogs.microsoft.com/commandline/microsoft-open-sources-gw-basic/

В заметке по ссылке есть одна интригующая фраза: "Microsoft was able to generate a substantial amount of the code for a port from the sources of a master implementation. (Alas, sorry, we’re unable to open-source the ISA translator.)". И действительно, текст на языке ассемблера для 8088 был получен автоматически с помощью специального транслятора. При этом даже комментарии в коде остались нетронутыми, там речь идет, судя по всему, о 8080.

В статье из журнала Byte за 1982 год сравниваются возможности трех трансляторов, которые автоматически преобразуют код 8-битных процессоров 8080/Z80 для CP/M в 16-битный код 8088/8086 для MS-DOS: https://tech-insider.org/personal-computers/research/acrobat/8206-b.pdf

Особенно выделяется среди этих трансляторов XLT86 (8080 -> 8086) от компании Digital Research. Этот транслятор — детище Гэри Килдалла, о котором специально говорить, наверное, нет необходимости. В области построения компиляторов Килдалл известен своей работой A unified approach to global program optimization (1973): https://dl.acm.org/doi/pdf/10.1145/512927.512945

Статья Килдалла до сих пор находится в числе самых цитируемых по компиляторной тематике и речь идет об алгоритме анализа потока данных, который позже был описан во множестве учебников и применяется в самых современных компиляторах: http://compcert.inria.fr/doc-1.6/html/Kildall.html

Вернемся, однако, к XLT86. К счастью, сохранилась документация к транслятору: http://www.s100computers.com/Software%20Folder/Assembler%20Collection/Digital%20Research%20XLT86%20Manual.pdf

Из нее можно узнать, в частности, что:

1. Трансляция состоит из 5 фаз.
2. В начале определяются линейные участки и строится граф потока управления. Затем проводится глобальный анализ потока данных для определения "живых" регистров и флагов процессора.
3. Сам процесс "выбора команд" элегантно описан табличным образом. Некоторые правила преобразований являются условными и зависят от ранее полученных результатов анализа потока данных.
4. Транслятор написан на ЯП PL/I-80 и имеет ограничение на размер входной программы — не более 6 Kбайт.

#history #analysis

Интересное сравнение Rust и Haskell на поле написания компиляторов для функциональных языков, с ссылками на бенчмарки:

https://old.reddit.com/r/haskell/comments/gok70o/simple_haskell_is_best_haskell/frj9hty/

#fp #haskell #rust #compiler #education

Любопытная работа по применению методов машинного обучения без учителя (Q learning) для разработки адаптивного сборщика мусора. Впрочем, полученные в статье результаты пока не очень впечатляют.
Learned Garbage Collection
https://arxiv.org/pdf/2004.13301.pdf

#gc #garbagecollection #machinelearning

Halide — яркий пример современного и популярного DSL для высокопроизводительных вычислений (обработка изображений, нейросети). В работе по ссылке ниже представлена его формальная семантика. Достаточная, по большому счету, для разработки собственного компилятора Halide. Любопытно, что в описании трансляции в императивное представление использован формализм из области синтеза программ.
Formal Semantics for the Halide Language
https://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-40.pdf

#dsl #semantics #synthesis

Очень доходчивый и практико-ориентированный разбор одной из ключевых статей в области супероптимизации на основе метода CEGIS. Автор даже не поленился расшифровать формулы из статьи для тех, кто сторонится математической нотации.
Synthesizing Loop-Free Programs with Rust and Z3
https://fitzgeraldnick.com/2020/01/13/synthesizing-loop-free-programs.html

#synthesis #smt

Синтаксический анализ программ считается давно изученной и почти даже скучной областью. Но при применении теории к практике текстовых редакторов часто выясняется, что привычные формализмы работают плохо и разработчикам приходится предлагать неординарные решения. В своей статье "SMIE: Simple Minded Indentation Engine" Стефан Монье излагает суть проблемы автоматического расставления отступов и описывает решение на базе грамматик с операторным предшествованием (operator-precedence grammars), используемое в Емаксе.

http://www-labs.iro.umontreal.ca/~monnier/smie.pdf

#parsing #editor #indentation #emacs #smie

SSA в историческом контексте. Очень хорошая систематизация знаний по теме.
Program Analisys and Transformation Survey and Links
https://github.com/pfalcon/awesome-program-analysis

#analysis #ssa

Использование рекомендательных систем для автонастройки компилятора, с учетом собранной ранее информации. Результаты внушают оптимизм.
A Collaborative Filtering Approach for the Automatic Tuning of Compiler Optimisations
https://arxiv.org/pdf/2005.04092.pdf

#autotuning #machinelearning #compiler #optimization

Очередная работа Мюнш-Макканьони по превращению Окамла в своеобразный конкурент Раста, черновик предложения о добавлении возможности работы с off-heap указателями:

Towards better systems programming in OCaml with out-of-heap allocation (draft)
https://github.com/gadmm/RFCs/blob/interop/rfcs/interop.md

#ocaml

Сопоставление с образом (pattern matching) в наши дни упоминается прежде всего в контексте функциональных языков программирования семейства ML. Но техника эта имеет гораздо более широкое применение, в том числе и вне контекста разработки ЯП. Интереснейший из классических результатов - алгоритм Rete, позволяющий эффективно сопоставлять тысячи образов с тысячами же объектов.


Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem

Доклад Improving Compiler Construction Using Formal Methods (Jubi Taneja)
Обзор работ по теме использования супероптимизатора Souper в различных фазах компиляции (статический анализ, автоматизация создания правил локальной оптимизации).
https://www.youtube.com/watch?v=de8Ak0nY1hA

#smt #superoptimizer

Опубликовано "Руководство по эффективному программированию на платформе «Эльбрус»".

Это первая версия руководства, содержащая в себе общие сведения о платформе, описание важных оптимизаций компилятора и способы увеличения производительности. Кроме того, в нём содержатся сведения о наиболее распространённых инструкциях процессора, что официально публикуется впервые. Руководство позволит как ознакомиться с устройством самого процессора и сравнить его с популярными архитектурами, посмотреть как на практике решаются проблемы работы на нестандартной архитектуре.

Эльбрус - процессор общего назначения, разрабатываемый фирмой МЦСТ, с архитектурой на основе широкого командного слова (VLIW).

http://www.mcst.ru/elbrus_prog

#vliw

Любопытная заметка от Intel на тему использования внешнего решателя задач целочисленного программирования в LLVM.
Речь идет об оптимальной расстановке команды LFENCE в управляющем графе. Это нужно для предотвращения LVI-атак.

An Optimized Mitigation Approach for Load Value Injection
https://software.intel.com/security-software-guidance/insights/optimized-mitigation-approach-load-value-injection

ILP-решатель для автоматической вставки fence применяли и ранее. См., например, работу Don’t sit on the fence. A static analysis approach to automatic fence insertion:
https://arxiv.org/pdf/1312.1411.pdf

#solver #analysis

Автоматическое извлечение КС-грамматики на основе динамического анализа управляющего графа программы на примерах входных данных. Любопытно, что авторы не стали даже упоминать грамматическое сжатие.

Mining Input Grammars from Dynamic Control Flow
https://publications.cispa.saarland/3101/1/fse2020-mimid.pdf

#analysis #parsing

Авторы оценивают верхнюю и нижнюю границы вычислительной сложности статического анализа указателей Андерсена (APA) и приводят свои варианты реализации APA.

The Fine-Grained Complexity of Andersen’s Pointer Analysis
https://arxiv.org/pdf/2006.01491.pdf

#analysis

Unsupervised Translation of Programming Languages

Довольно любопытная статья на тему создания транскомпилятора от исследователей из Facebook AI Research.
Путем тренировки модели, на корпусе программ из Github, транслируют код языков C++, Java, Python.

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

• We introduce a new approach to translate functions from a programming language to another,
that is purely based on monolingual source code.
• We show that TransCoder successfully manages to grasp complex patterns specific to each
language, and to translate them to other languages.
• We show that a fully unsupervised method can outperform commercial systems that leverage
rule-based methods and advanced programming knowledge.
• We build and release a validation and a test set composed of 852 parallel functions in 3
languages, along with unit tests to evaluate the correctness of generated translations.
• We will make our code and pretrained models publicly available.

В видео можно послушать комментарии.

Paper:
https://arxiv.org/pdf/2006.03511

Video:
https://www.youtube.com/watch?v=xTzFJIknh7E&app=desktop

#ml #analysis #transpilation

Подход к выявлению "семантического клонов" в программе. Основан на насыщении равенствами и забытой концепции Programmer’s Apprentice. Утверждается, что работает лучше, чем популярное в этой области представление PDG.

Semantic Code Search via Equational Reasoning
https://dl.acm.org/doi/pdf/10.1145/3385412.3386001

#analysis

В рамках PLDI Alex Aiken (известный многим по курсам компиляторостроения) рассказал о проекте TASO -- это автоматический синтез графовых оптимизирующих преобразований для нейросетевых фреймворков. Перечисляются все графы-шаблоны нейросетевых операций до фиксированного размера, между графами устанавливается соответствие с помощью Z3, преобразования графов программ происходят с помощью механизма отката и стоимостной модели. В целом, рассказ повторяет эту статью:

TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions
https://cs.stanford.edu/~padon/taso-sosp19.pdf

#synthesis #smt