PLComp

Возможно, вы уже слышали новость о древнем 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

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

Недавно (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

На этой неделе появился официальный 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

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

Работа по синтезу программ с использованием 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

Полезная ссылка для участия в спорах на тему, какой ЯП выбрать для реализации компилятора 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

Работы 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

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

В стадии 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

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

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

Две недавние статьи с участием 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-парсеров. The computational power of Parsing Expression Grammars https://arxiv.org/pdf/1902.08272.pdf #parsing

Program Analysis Свежий (весна 2020) курс по анализу программ, с неплохим выбором тем. https://cmu-program-analysis.github.io/ #analysis

Основные работы по методу насыщения равенствами (equality saturation) Denali: A Goal-directed Superoptimizer (в работе описывается применение E-Graphs для задач оптимизации программ) https://courses.cs.washington.edu/courses/cse501/15sp/papers/joshi.pdf Equality Saturation: A New Approach to Optimization (вместо E-Graphs используются PEG/E-PEG, поддерживающие управляющие конструкции) https://www.cs.cornell.edu/~ross/publications/eqsat/ "Доказательство свойств функциональных программ методом насыщения равенствами" (диссертация на русском языке) https://keldysh.ru/council/1/2017-grechanik/diss.pdf #optimization #synth

Работы по практическому применению передовых подходов E-Graphs (дедуктивный синтез программ) и Equality Saturation (решение для проблемы phase ordering). Особенно интересно, что для серьезных примеров использования взяты области, далекие от традиционных целевых представлений компиляторов. Это показывает, что компиляторные технологии имеют более широкое применение, чем иногда принято думать. Carpentry Compiler https://grail.cs.washington.edu/projects/carpentrycompiler/files/CarpentryCompiler.pdf Synthesizing Structured CAD Models with Equality Saturation and Inverse Transformations https://jamesrwilcox.com/szalinski.pdf Для работы с E-Graphs авторами разработана библиотека egg (есть веб-демо). egg: Easy, Efficient, and Extensible E-graphs https://arxiv.org/pdf/2004.03082.pdf https://github.com/mwillsey/egg #optimization

Авторы экспериментального компилятора для Emacs Lisp на базе libgccjit опубликовали работу, описывающие основные фазы работы компилятора Bringing GNU Emacs to Native Code: https://zenodo.org/record/3736363/files/GCCEMACS_proceeding.pdf?download=1 #lisp

Крупнейшая конференция по истории ЯП - HOPL IV - была перенесена, но некоторые интересные ретроспективные обзоры уже доступны: The History of Standard ML https://smlfamily.github.io/history/SML-history.pdf Evolution of Emacs Lisp https://www.iro.umontreal.ca/~monnier/hopl-4-emacs-lisp.pdf History of Logo https://escholarship.org/uc/item/1623m1p3 The Early History of F# https://fsharp.org/history/hopl-final/hopl-fsharp.pdf A History of Clojure https://clojure.org/about/history A History of the Oz Multiparadigm Language https://www.info.ucl.ac.be/~pvr/hopl20main-p14-p-329dcad--final.pdf Thriving in a Crowded and Changing World: C++ 2006–2020 https://www.stroustrup.com/hopl20main-p5-p-bfc9cd4--final.pdf Остальные доклады: https://dl.acm.org/toc/pacmpl/2020/4/HOPL #conf #history

Programming Paradigms for Dummies: What Every Programmer Should Know Ликбез по основным принципам ЯП: классификация, вопросы представления состояния, конкурентности и параллелизма. https://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf