Две недавние статьи с участием Alessandro Warth. A. Warth — разработчик системы oMeta и автор известной работы по адаптации Packrat-парсеров для поддержки левосторонней рекурсии.

Incremental Packrat Parsing (оригинальная идея по использованию Pakrat-таблицы для реализации инкрементального разбора)
https://dl.acm.org/doi/pdf/10.1145/3136014.3136022

Recognising and Generating Terms using Derivatives of Parsing Expression Grammars
Использование производных Бржозовского в PEG-парсере для порождения предложений описываемого языка. Может использоваться в задаче тестирования компилятора (fuzzing). Но особенно интересно расширить эту идею на PEG с иерархическими структурами данных -- и порождать тестовые примеры для них.
https://arxiv.org/pdf/1801.10490.pdf

#parsing

Необычный подход к построению PEG-подобного парсера на основе восходящего разбора.
Pika parsing: parsing in reverse solves the left recursion and error recovery problems
https://arxiv.org/pdf/2005.06444.pdf

#parsing

В Retrofitting Parallelism onto OCaml авторы разбирают технические решения и компромисссы Multicore Ocaml, основное внимание уделяя сборщику мусора:
https://arxiv.org/pdf/2004.11663.pdf

#ocaml #gc #garbagecollection #multicore

В стадии call for papers

Конференция по ЯП с управляемым кодом и VM
MPLR 2020
Ноябрь 4-6, 2020
https://mplr2020.cs.manchester.ac.uk/index.php/mplr/call-for-papers

Симпозиум по ЯП и системам
APLAS 2020
30 ноября 2020
https://conf.researchr.org/home/aplas-2020

#conf

Femtolisp — минималистичный интерпретатор диалекта LISP.
https://github.com/JeffBezanson/femtolisp
Автор стал впоследствии работать над Julia. На femtolisp написаны лексер и парсер Julia.

#lisp #interpreter

Работы Ian Piumarta, участника проекта STEPS

Maru
Миниатюрный расширяемый Лисп-подобный язык с компилятором в IA32-код. Использовался в проекте STEPS.
Open, extensible composition models
https://www.piumarta.com/freeco11/freeco11-piumarta-oecm.pdf
STEPS Toward the Reinvention of Programming, 2012 Final Report
http://www.vpri.org/pdf/tr2012001_steps.pdf

PEG-based transformer provides front-, middleand back-end stages in a simple compiler
http://www.vpri.org/pdf/tr2010003_PEG.pdf
Шедевр изящества и миниатюризации в области генераторов компиляторов.

#lisp #metacompiler

Полезная ссылка для участия в спорах на тему, какой ЯП выбрать для реализации компилятора
Comparing the Same Project in Rust, Haskell, C++, Python, Scala and OCaml
https://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/

#compiler #implementation #comparison #education #rust #haskell #cpp #python #scala #ocaml

Работа по синтезу программ с использованием Rosette (Racket). Cинтезируется JIT-компилятор DSL BPF (ядро Linux) в машинный код (в примере использован RISC-V)
Synthesizing JIT Compilers for In-Kernel DSLs
https://www.cs.utexas.edu/~isil/jitsynth.pdf

Подробности о BPF VM:
BPF: A New Type of Software
http://www.brendangregg.com/blog/2019-12-02/bpf-a-new-type-of-software.html

#synthesis #jit #bpf

A Language for Describing Optimization Strategies
Пример использования стратегического переписывания термов в духе Stratego. В статье демонстрируются оптимизирующие преобразования на Scala, для GPU и других ускорителей.
https://arxiv.org/pdf/2002.02268.pdf

#optimization

На этой неделе появился официальный self-hosted дистрибутив функционального языка с зависимыми типами Idris 2.

На текущем этапе он использует в качестве бэкенда один из трех компиляторов Scheme: Chez, Racket или Gambit. Как и в первой версии Idris, есть инфраструктура для создания собственных бэкендов на основе нескольких IR c лямбдами (обычный LC, lifted форма, ANF, виртуальная машина с замыканиями).

https://github.com/idris-lang/Idris2/

Why is Idris 2 so much faster than Idris 1?
https://www.type-driven.org.uk/edwinb/why-is-idris-2-so-much-faster-than-idris-1.html

#fp

Недавно (27-28 апреля, 2020) состоялся европейский симпозиум по Лиспу.

European Lisp Symposium
https://www.european-lisp-symposium.org/2020/
Видеозаписи докладов: https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga

Ниже краткая информация о 3 докладах по околокомпиляторной тематике:

Partial Evaluation Based CPS Transformation: An Implementation Case Study
Описание компилятора для диалекта Лиспа pLisp. В компиляторе используются частичные вычисления и CPS.
Слайды: https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf

LLVM Code Generation for Open Dylan
Dylan — это диалект Лиспа с Алгол-подобным синтаксисом. В начале 90-х этот язык развивался компанией Apple. В докладе представлено описание генератора кода для Dylan на основе LLVM.
Слайды: https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf

Later Binding: Just in Time Compilation of a Younger Dynamic Programming Language
Краткий анализ компилятора LuaJIT
Видео выступления: https://www.youtube.com/watch?v=FBk5XAEhu2s
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf

#conf #jit #llvm #cps #pe

Особенно же интересными (субъективно, разумеется) событиями симпозиума по Лиспу оказались: доклад и семинар по передовому фреймворку (набор 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