all.html


<!doctype html>
<html lang="en" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      
      
      <link rel="shortcut icon" href="assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1.2, mkdocs-material-6.2.6">
    
    
        <title>ALL - PLComp</title>
      
    
      <link rel="stylesheet" href="assets/stylesheets/main.cb6bc1d0.min.css">
      
        
        <link rel="stylesheet" href="assets/stylesheets/palette.39b8e14a.min.css">
        
          
          <meta name="theme-color" content="#000000">
        
      
        <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto",-apple-system,BlinkMacSystemFont,Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono",SFMono-Regular,Consolas,Menlo,monospace}</style>
      
    
  </head>
  
  
    <body dir="ltr" data-md-color-scheme="" data-md-color-primary="black" data-md-color-accent="">
      
  
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" for="__drawer"></label>
    <div data-md-component="skip">
      
        
        <a href="#12032021-alexander-tchitchigin" class="md-skip">
          Skip to content
        </a>
      
    </div>
    <div data-md-component="announce">
      
    </div>
    
      
<header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid" aria-label="Header">
    <a href="./index.html" title="PLComp" class="md-header-nav__button md-logo" aria-label="PLComp">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 003-3 3 3 0 00-3-3 3 3 0 00-3 3 3 3 0 003 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54z"/></svg>

    </a>
    <label class="md-header-nav__button md-icon" for="__drawer">
      <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 6h18v2H3V6m0 5h18v2H3v-2m0 5h18v2H3v-2z"/></svg>
    </label>
    <div class="md-header-nav__title" data-md-component="header-title">
      <div class="md-header-nav__ellipsis">
        <div class="md-header-nav__topic">
          <span class="md-ellipsis">
            PLComp
          </span>
        </div>
        <div class="md-header-nav__topic">
          <span class="md-ellipsis">
            
              ALL
            
          </span>
        </div>
      </div>
    </div>
    
    
  </nav>
</header>
    
    <div class="md-container" data-md-component="container">
      
      
      <main class="md-main" data-md-component="main">
        <div class="md-main__inner md-grid">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation" >
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    

<nav class="md-nav md-nav--primary" aria-label="Navigation" data-md-level="0">
  <label class="md-nav__title" for="__drawer">
    <a href="./index.html" title="PLComp" class="md-nav__button md-logo" aria-label="PLComp">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 003-3 3 3 0 00-3-3 3 3 0 00-3 3 3 3 0 003 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54z"/></svg>

    </a>
    PLComp
  </label>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
    <li class="md-nav__item">
      <a href="index.html" class="md-nav__link">
        NEW
      </a>
    </li>
  

    <li class="md-nav__item md-nav__item--active">
      
      <input class="md-nav__toggle md-toggle" data-md-toggle="toc" type="checkbox" id="__toc">
      
        
      <a href="all.html" class="md-nav__link md-nav__link--active">
        ALL
      </a>
      
    </li>
  

    <li class="md-nav__item">
      <a href="analysis.html" class="md-nav__link">
        #analysis
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="registerallocation.html" class="md-nav__link">
        #registerallocation
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="history.html" class="md-nav__link">
        #history
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="smt.html" class="md-nav__link">
        #smt
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="parsing.html" class="md-nav__link">
        #parsing
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="conf.html" class="md-nav__link">
        #conf
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="synthesis.html" class="md-nav__link">
        #synthesis
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="jit.html" class="md-nav__link">
        #jit
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="ocaml.html" class="md-nav__link">
        #ocaml
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="optimization.html" class="md-nav__link">
        #optimization
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="garbagecollection.html" class="md-nav__link">
        #garbagecollection
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="dsl.html" class="md-nav__link">
        #dsl
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="semantics.html" class="md-nav__link">
        #semantics
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="ssa.html" class="md-nav__link">
        #ssa
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="compiler.html" class="md-nav__link">
        #compiler
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="lisp.html" class="md-nav__link">
        #lisp
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="modules.html" class="md-nav__link">
        #modules
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="llvm.html" class="md-nav__link">
        #llvm
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="stratego.html" class="md-nav__link">
        #stratego
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="linearscan.html" class="md-nav__link">
        #linearscan
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="bpf.html" class="md-nav__link">
        #bpf
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="lua.html" class="md-nav__link">
        #lua
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="datalog.html" class="md-nav__link">
        #datalog
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="machinelearning.html" class="md-nav__link">
        #machinelearning
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="gc.html" class="md-nav__link">
        #gc
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="fp.html" class="md-nav__link">
        #fp
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="haskell.html" class="md-nav__link">
        #haskell
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="rust.html" class="md-nav__link">
        #rust
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="education.html" class="md-nav__link">
        #education
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="leroy.html" class="md-nav__link">
        #leroy
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="classic.html" class="md-nav__link">
        #classic
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="sml.html" class="md-nav__link">
        #sml
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="constraintprogramming.html" class="md-nav__link">
        #constraintprogramming
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="unison.html" class="md-nav__link">
        #unison
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="registeralloc.html" class="md-nav__link">
        #registeralloc
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="instructionscheduling.html" class="md-nav__link">
        #instructionscheduling
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="separatecompilation.html" class="md-nav__link">
        #separatecompilation
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="stlc.html" class="md-nav__link">
        #stlc
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="linking.html" class="md-nav__link">
        #linking
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="scheme.html" class="md-nav__link">
        #scheme
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="trace.html" class="md-nav__link">
        #trace
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="jvm.html" class="md-nav__link">
        #jvm
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="graalvm.html" class="md-nav__link">
        #graalvm
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="bliss.html" class="md-nav__link">
        #bliss
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="lcc.html" class="md-nav__link">
        #lcc
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="fortran.html" class="md-nav__link">
        #fortran
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="ghc.html" class="md-nav__link">
        #ghc
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="grin.html" class="md-nav__link">
        #grin
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="survey.html" class="md-nav__link">
        #survey
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="ag.html" class="md-nav__link">
        #ag
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="types.html" class="md-nav__link">
        #types
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="spoofax.html" class="md-nav__link">
        #spoofax
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="gradual.html" class="md-nav__link">
        #gradual
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="art.html" class="md-nav__link">
        #art
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="android.html" class="md-nav__link">
        #android
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="dex.html" class="md-nav__link">
        #dex
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="isa.html" class="md-nav__link">
        #isa
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="verification.html" class="md-nav__link">
        #verification
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="vm.html" class="md-nav__link">
        #vm
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="ml.html" class="md-nav__link">
        #ml
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="transpilation.html" class="md-nav__link">
        #transpilation
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="solver.html" class="md-nav__link">
        #solver
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="vliw.html" class="md-nav__link">
        #vliw
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="superoptimizer.html" class="md-nav__link">
        #superoptimizer
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="autotuning.html" class="md-nav__link">
        #autotuning
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="editor.html" class="md-nav__link">
        #editor
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="emacs.html" class="md-nav__link">
        #emacs
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="smie.html" class="md-nav__link">
        #smie
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="indentation.html" class="md-nav__link">
        #indentation
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="nanopass.html" class="md-nav__link">
        #nanopass
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="langworkbench.html" class="md-nav__link">
        #langworkbench
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="cps.html" class="md-nav__link">
        #cps
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="pe.html" class="md-nav__link">
        #pe
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="python.html" class="md-nav__link">
        #python
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="cpp.html" class="md-nav__link">
        #cpp
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="comparison.html" class="md-nav__link">
        #comparison
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="implementation.html" class="md-nav__link">
        #implementation
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="scala.html" class="md-nav__link">
        #scala
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="metacompiler.html" class="md-nav__link">
        #metacompiler
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="interpreter.html" class="md-nav__link">
        #interpreter
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="multicore.html" class="md-nav__link">
        #multicore
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="synth.html" class="md-nav__link">
        #synth
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="codegen.html" class="md-nav__link">
        #codegen
      </a>
    </li>
  

  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
              <div class="md-sidebar md-sidebar--secondary" data-md-component="toc" >
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    
<nav class="md-nav md-nav--secondary" aria-label="Table of contents">
  
  
</nav>
                  </div>
                </div>
              </div>
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                <h1 id="12032021-alexander-tchitchigin"><span style="font-weight:normal;font-style:italic;font-size:medium">12/03/2021, Alexander Tchitchigin</span><a class="headerlink" href="#12032021-alexander-tchitchigin" title="Permanent link">&para;</a></h1>
<p><a href="https://hal.inria.fr/hal-01499946/document">https://hal.inria.fr/hal-01499946/document</a>
&ldquo;A modular module system&rdquo;, Xavier Leroy</p>
<p>Утверждение, что (ML-style) система модулей не зависит от &ldquo;базового&rdquo; языка программирования, и может быть реализована почти для любого, а не только ML, широко известно и озвучивалось в литературе. Данная статья приводит конструктивное доказательство этого тезиса, реализуя такую (слегка упрощённую) систему модулей, в виде, явно параметризованном относительно синтаксиса и системы типов базового языка.</p>
<p>Несмотря на ряд упрощений по сравнению с системой модулей того же Standard ML, представленная модельная система содержит (и корректно реализует) все базовые возможности, включая структурную типизацию модулей, абстрактные типы, функторы, зависимость (типа) результата функтора от (типа) аргумента а также равенства между (абстрактными) типами.</p>
<blockquote>
<p>All in all, module type matching resembles subtyping in a functional language with records, with some extra complications due to the dependencies in functor types and signatures.</p>
</blockquote>
<p>Статья составлена в духе Literate Programming, перемежая пояснительный текст и реальный рабочий код на языке OCaml. Реализация системы модулей ML с помощью системы модулей ML отсылает к традиции метациркулярных интерпретаторов Лисп. Леруа выражает надежду, что такой способ представления материала не только не запутает читателя, но и дополнительно прояснит связь конкретного и абстрактного синтаксиса как и практическую полезность (и даже необходимость) всех возможностей представленной системы. (По-видимому, метациркулярность системы не оставила Лисперов равнодушными, что привело к появлению реализации MiniML с полноценной системой модулей на Scheme: <a href="http://wiki.call-cc.org/eggref/4/miniML">http://wiki.call-cc.org/eggref/4/miniML</a> 😊)</p>
<p>Для иллюстрации приводятся два примера &ldquo;надстраивания&rdquo; реализованной системы модулей над &ldquo;упрощённым C&rdquo; в качестве императивного (процедурного) базового языка и Mini-ML в качестве функционального, приближенного к используемым на практике, в частности, реализующего типы высших порядков (Higher-Kinded Types).</p>
<p>Кратко обсуждаются вопросы (модульной) компиляции таких модулей. Упоминаются три основных варианта: компиляция самих модулей в виде структур данных, а функторов — в виде (полиморфных) функций, специализация функторов для всех применений в духе C++ templates и полное стирание модулей во время компиляции (аналогично девиртуализации вызовов методов в ООП). Но за деталями интересующиеся читатели отсылаются к соответствующим публикациям.</p>
<p>В заключительной части Леруа обсуждает ряд расширений модельной системы модулей — как реализованных на практике, так и не до конца проработанных даже в теории — но уже без фактической реализации.</p>
<p>Таким образом, статья представляет собой практическое введение в ML-style системы модулей и связанные вопросы, полезное как для пользователей таких систем, так и для авторов языков программирования, желающих реализовать собственную систему модулей. 😊</p>
<p><a href="leroy.html">#leroy</a> <a href="modules.html">#modules</a> <a href="classic.html">#classic</a> <a href="ocaml.html">#ocaml</a> <a href="sml.html">#sml</a></p>
<hr />
<h1 id="17022021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">17/02/2021, Vladimir Kazanov</span><a class="headerlink" href="#17022021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи NP-полны и связаны между собой: распределение может внести в код новые инструкции, планирование же меняет инструкции местами. Несмотря на это в популярных компиляторах решаются они, как правило, раздельно и используют эвристические подходы.</p>
<p>Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.</p>
<p>Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.</p>
<p>Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.</p>
<p>В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.</p>
<p>Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.</p>
<p>Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.</p>
<p>Презентация на конференции LLVM (2017): <a href="https://www.youtube.com/watch?v=kx64V74Mba0">https://www.youtube.com/watch?v=kx64V74Mba0</a></p>
<p>Обобщающая исследования Лозано диссертация (2018 год): <a href="http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf">http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf</a></p>
<p>Оценка производительности Unison (2017): <a href="https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf">https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf</a> </p>
<p>Сайт проекта: <a href="https://unison-code.github.io/">https://unison-code.github.io/</a></p>
<p>Программирование в ограничениях: <a href="https://ru.wikipedia.org/wiki/Программирование_в_ограничениях">https://ru.wikipedia.org/wiki/Программирование_в_ограничениях</a></p>
<p>Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих  компиляторах: <a href="https://arxiv.org/pdf/1809.02161.pdf">https://arxiv.org/pdf/1809.02161.pdf</a></p>
<p><a href="constraintprogramming.html">#constraintprogramming</a> <a href="unison.html">#unison</a> <a href="registeralloc.html">#registeralloc</a> <a href="instructionscheduling.html">#instructionscheduling</a> <a href="llvm.html">#llvm</a></p>
<hr />
<h1 id="13022021-alexander-tchitchigin"><span style="font-weight:normal;font-style:italic;font-size:medium">13/02/2021, Alexander Tchitchigin</span><a class="headerlink" href="#13022021-alexander-tchitchigin" title="Permanent link">&para;</a></h1>
<p><a href="https://grosskurth.ca/bib/1997/cardelli.pdf">https://grosskurth.ca/bib/1997/cardelli.pdf</a>
&ldquo;Program Fragments, Linking, and Modularization&rdquo; Luca Cardelli.</p>
<p>Статья поднимает вопрос <em>корректности</em> раздельной компиляции и линковки, и потому — я считаю — обязательна к прочтению для всех авторов языков программирования! 😃</p>
<p>Уже во введении на простейшем примере создания воображаемой программы, состоящей всего из двух модулей, разрабатываемых независимо, автор иллюстрирует, наверное, в<em>се </em>проблемы, при этом возникающие. Между делом Карделли упоминает п<em>убличные репозитории артефактов </em>(типа Maven Central или Nuget. Напомню, что статья опубликована в 1996 году!). Многие из обозначенных проблем линковки раздельно скомпилированных модулей до сих пор не решены ни в мейнстримных, ни в исследовательских языках.</p>
<p>В качестве основного результата Карделли предлагает, вероятно, первую формальную модель раздельной компиляции и последующей линковки, позволяющую строго рассмотреть вопрос о корректности этих процессов. Корректность в этом смысле приведённой простейшей системы модулей для просто типизированного лямбда-исчисления (в качестве модельного языка) формально д<em>оказывается.</em> Автор, конечно же, указывает на необходимость расширения модели как в сторону более развитых языков (параметрический полиморфизм, ООП), так и в сторону более сложных систем модулей (параметризованные модули, &ldquo;функторы&rdquo; в духе Standard ML, первоклассные модули). Существуют ли такие работы, непосредственно продолжающие это исследование, мне не известно.</p>
<p>Однако, в качестве related work и дальнейшего чтения могу указать на работы по формализации (и доказательству корректности) раздельной компиляции для языка C в рамках проекта CompCert.</p>
<p><a href="separatecompilation.html">#separatecompilation</a> <a href="modules.html">#modules</a> <a href="stlc.html">#stlc</a> <a href="linking.html">#linking</a></p>
<hr />
<h1 id="07022021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">07/02/2021, Vladimir Kazanov</span><a class="headerlink" href="#07022021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>На Хабре несколько дней назад появилась  статья, популярно поясняющая знаменитую технику реализации языка Scheme - Cheney on the M.T.A. Статья излагает историю названия и объясняет работу остроумного подхода к сборке мусора.</p>
<p>Исходный код Scheme здесь сначала должен быть преобразован в представление с <em>продолжениями</em> (см., например, книгу Compiling with Continuations). Функции этого представления один к одному компилируются в функции на языке C. Многочисленные временные значения, характерные для Scheme, сначала размещаются на стеке вызовов C. Во время работы программы стек вызовов функций C будет расти, так как при компиляции с продолжениями функции не возвращаются к точке исходного вызова.</p>
<p>При превышении допустимого размера стек сбрасывается вызовом longjmp. Размер проверяется, например, через численное значение адреса временной переменной. Перед сбросом живые значения из стека перемещаются в кучу для зачистки алгоритмом Чейни, мертвые же значения отбрасываются автоматически.</p>
<p>Техника сильно упрощает компиляцию Scheme в C (например, рекурсивные вызовы и их оптимизацию, легко выражаются продолжения), из-за чего ее используют минимум два популярных компилятора: Cyclone и Chicken.</p>
<p>Статья на Хабре: <a href="https://habr.com/ru/company/ruvds/blog/540502/">https://habr.com/ru/company/ruvds/blog/540502/</a></p>
<p>Подробности реализации техники от разработчика Chicken Scheme:
<a href="https://www.more-magic.net/posts/internals-gc.html">https://www.more-magic.net/posts/internals-gc.html</a></p>
<p>Реализация Cyclone: <a href="https://justinethier.github.io/cyclone/docs/Garbage-Collector">https://justinethier.github.io/cyclone/docs/Garbage-Collector</a></p>
<p>Оригинальная публикация по Cheney on the MTA: <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3A988CF024FE807165D1CFA957445BC8?doi=10.1.1.54.7143&amp;rep=rep1&amp;type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3A988CF024FE807165D1CFA957445BC8?doi=10.1.1.54.7143&amp;rep=rep1&amp;type=pdf</a></p>
<p>Алгоритм сборки мусора Чейни: <a href="https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p677-cheney.pdf">https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p677-cheney.pdf</a></p>
<p>Компиляторы, использующий другие подходы к компиляции в язык C:</p>
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.8424&amp;rep=rep1&amp;type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.8424&amp;rep=rep1&amp;type=pdf</a> - Bigloo - компилятор Scheme и Standard ML</p>
<p><a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.8788&amp;rep=rep1&amp;type=pdf">https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.8788&amp;rep=rep1&amp;type=pdf</a> - Gambit - компилятор Scheme</p>
<p><a href="garbagecollection.html">#garbagecollection</a> <a href="scheme.html">#scheme</a></p>
<hr />
<h1 id="27012021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">27/01/2021, Vladimir Kazanov</span><a class="headerlink" href="#27012021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Распределение регистров - одна из старейших проблем построения компиляторов, первые работы по которой появились еще в 50-ые годы прошлого века. Как и в других NP-полных задачах недостатка в эвристических решениях нет. Тем не менее, в последние десятилетия разработчики все чаще используют один из двух <em>глобальных</em> подходов: линейное сканирование в динамических (JIT) компиляторах и раскраску графа в статических (AOT) компиляторах.</p>
<p>В своей диссертации Йозеф Эйсель (Josef Eisl) предлагает новый <em>субглобальный</em> подход к распределению регистров в динамических компиляторах, имеющий в основе следующие наблюдения:</p>
<ol>
<li>
<p>Глобальные методы тратят много времени на редко исполняемый (холодный) код.</p>
</li>
<li>
<p>В современных динамически компилируемых языках после агрессивного встраивания функций (inline) появляются большие функции, где много холодного кода.</p>
</li>
<li>
<p>Крупные функции при глобальном охвате занимают много времени.</p>
</li>
</ol>
<p>Выходит, что если сконцентрировать внимание алгоритма на горячих участках в ущерб холодным, то можно за то же время найти эффективное (или даже оптимальное!) распределение на отдельных важных участках кода.</p>
<p>В качестве важных участков Эйсель выбрал <em>непересекающиеся</em> последовательности базовых блоков - трассы (traces). Каждая трасса в зависимости от популярности получает свою политику распределения - быструю и неэффективную, долгую и эффективную, компромиссную или даже специализированную.</p>
<p>Интересно, что схожий подход уже применялся в трассирующих jit-компиляторах, но там трассы компилировались целиком, тогда как у Эйселя трассы выделяются только для распределения регистров.</p>
<p>Эйсель в сотрудничестве с Oracle реализовал подход в GraalVM, нового jit-компилятора для JVM, где тот показал сравнимую с актуальными версиями линейного сканирования производительность порожденного кода при меньшем времени РР. При этом распределение на трассах позволяет искать баланс между временем компиляции и производительностью распределения, а также открывает возможности для  <em>параллельной</em> работы над трассами.</p>
<p>В настоящий момент код по умолчанию выключен, но доступен в Java версий от 10 и новее через опции </p>
<pre>java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -Dgraal.TraceRA=true
</pre>
<p>.</p>
<p><a href="https://ssw.jku.at/General/Staff/Eisl/papers/phdthesis.pdf">https://ssw.jku.at/General/Staff/Eisl/papers/phdthesis.pdf</a></p>
<p><a href="trace.html">#trace</a> <a href="jvm.html">#jvm</a> <a href="registerallocation.html">#registerallocation</a> <a href="graalvm.html">#graalvm</a></p>
<hr />
<h1 id="13012021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">13/01/2021, Vladimir Kazanov</span><a class="headerlink" href="#13012021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>BLISS - один из самых ранних портативных языков для системного программирования, первая версия которого (BLISS-10) была выпущена для PDP-10 еще в 1970-ом году. Наиболее широкое применение язык нашел во внутренних разработках компании DEC, где на BLISS вплоть до 90-х создавались компиляторы, операционные системы и низкоуровневые утилиты. </p>
<p>Но прославился этот язык благодаря версии для PDP-11, вышедшей в 1975 году. Компилятор BLISS-11 был на голову выше конкурентов вроде ранних компиляторов C и поражал воображение разработчиков (&ldquo;we&rsquo;d sit and chuckle at what it had done&rdquo;). Реализацию описывали несколько диссертаций (одна из них - за авторством будущего <a href="https://en.wikipedia.org/wiki/Charles_Geschke">основателя</a> Adobe) и книга. Пример инновационности BLISS-11 - анализ жизни переменных в применении к глобальному распределению регистров.</p>
<p>Книга описывает собственный подход к анализу областей жизни переменных (потому что &ldquo;no truly satisfactory solution exists in the literature&rdquo;). Найденные области обозначались каждая двумя координатами в двухмерном пространстве. Координаты задавали вершины прямоугольников. Если области-прямоугольники времени жизни переменных пересекались, то такие области не должны были оказываться в одном регистре.</p>
<p>Каждая переменная получала рейтинг на основе расположения в коде (напр. глубины вложения циклов) и размера области жизни (меньше - лучше). Переменные сортировались по рейтингу, и за один проход одна за другой сопоставлялись с регистрами, если только при этом не случалось пересечения с уже сопоставленными с регистром переменными.</p>
<p>Позже эта проблема была сведена к NP-сложной задаче об упаковке в контейнеры; и в следующих версиях BLISS разработчики развили подход в семейство алгоритмов binpacking, к которым относится и популярный алгоритм линейного сканирования.</p>
<p>С закатом DEC зашла и звезда BLISS. Но в истории компиляторов реализация языка оставила значимый след: книга The Design of an Optimizing Compiler (1975) стала классикой, и без BLISS любое обсуждение истории компиляторов будет неполным.</p>
<p>Wulf, W.A., 1975. <a href="https://s3-eu-west-1.amazonaws.com/pstorage-cmu-348901238291901/12102674/file.pdf">The design of an optimizing compiler</a>. </p>
<p>Brender, Ronald F. 2002. <a href="https://www.cs.tufts.edu/~nr/cs257/archive/ronald-brender/bliss.pdf">The BLISS programming language: a history  </a></p>
<p><a href="bliss.html">#bliss</a> <a href="history.html">#history</a> <a href="registerallocation.html">#registerallocation</a></p>
<hr />
<h1 id="08012021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">08/01/2021, Vladimir Kazanov</span><a class="headerlink" href="#08012021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Некоторые разработки получают известность не в силу новаторских решений, а благодаря качественной инженерной работе и удобной сопроводительной документации. Пример - портативный компилятор lcc, ставший прообразом 8cc, chibicc, tcc и других свободно доступных небольших компиляторов.</p>
<p>Разработчики lcc задались целью сделать не просто полноценный компилятор языка Си, но еще и подробно документированный: проект написан в стиле &ldquo;литературного программирования&rdquo; Д.Кнута, когда код интегрирован в документацию (а не наоборот).</p>
<p>Более того, из такого &ldquo;художественного&rdquo; исходного кода можно собрать полноценную книгу, изданную под названием A Retargetable C Compiler: Design and Implementation. Вместе с книгой для разъяснения ключевых технических решений авторы опубликовали статьи, посвященные, например, распределению регистров и порождению кода.</p>
<p>lcc можно отнести к промежуточному варианту между простыми компиляторами, описываемыми в популярных книгах для программистов, и серьезными оптимизирующими компиляторами. Здесь есть внутреннее представление (лес ациклических графов внутри базовых блоков графа потока исполнения), используются отдельные популярные оптимизации.</p>
<p>Характерное для компилятора решение - распределение регистров. Оно локальное и восходящее, то есть проводится внутри базового блока проходом по списку инструкций. Регистры один за другим выделяются под значения до тех пор, пока не приходится искать значение для вытеснения в память. Вытесняются те значения, следующее использование которых в списке инструкций находится дальше всего.</p>
<p>В результате компилятор был портирован на множество платформ, стал основой для бесчисленных форков и даже использовался для скриптования популярного игрового движка id Tech 3 (см. Quake 3 Arena) компании idSoftware. </p>
<p><a href="https://en.wikipedia.org/wiki/LCC_(compiler)">https://en.wikipedia.org/wiki/LCC_(compiler)</a></p>
<p><a href="https://github.com/drh/lcc">https://github.com/drh/lcc</a></p>
<p><a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&amp;rep=rep1&amp;type=pdf">https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&amp;rep=rep1&amp;type=pdf</a></p>
<p><a href="https://en.wikipedia.org/wiki/Id_Tech_3">https://en.wikipedia.org/wiki/Id_Tech_3</a></p>
<p><a href="history.html">#history</a> <a href="lcc.html">#lcc</a> <a href="registerallocation.html">#registerallocation</a></p>
<hr />
<h1 id="07012021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">07/01/2021, Vladimir Kazanov</span><a class="headerlink" href="#07012021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Самый ранний и задавший главные направления исследований в области компиляторов проект это, безусловно, оптимизирующий компилятор языка Fortran I. Работы над ним велись в середине 1950-х и примененные в компиляторе техники устарели, но, например, остроумный механизм распределения регистров продержался в Fortran еще много лет.</p>
<p>Распределение регистров в Фортране 1 проводится в два этапа. На вход первого этапа поступает список инструкций, использующих неограниченное число символьных регистров. Список разбивается на базовые блоки, то есть строится граф потока исполнения. При этом во всех ветвлениях (IF, вычисляемых GOTO) программисты на языке должны были сами (!) расставить вероятность перехода по каждой из ветвей. Вероятности впоследствии используются для моделирования частоты базовых блоков метдом Монте-Карло.</p>
<p>Во втором этапе, начиная от самого &ldquo;горячего&rdquo; из оставшихся необработанных блоков, строится регион, внутри которого будет проводится распределение регистров. Регион расширяется самым горячим из соседних базовых блоков до тех пор, пока не упирается в другие регионы или начало/конец графа. Специальным образом обрабатывается закольцованные регионы, то есть циклы.</p>
<p>Само выделение регистров происходит внутри каждого такого региона; при необходимости вытесняются регистры, наименее востребованные в оставшейся части региона (например, мертвые).</p>
<p>Материалы для интересующихся историей компиляторов:</p>
<p><a href="https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf">https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf</a> - краткий современный обзор компилятора</p>
<p><a href="http://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf">http://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf</a> - оригинальная публикация 1957-го года.</p>
<p><a href="fortran.html">#fortran</a> <a href="history.html">#history</a> <a href="registerallocation.html">#registerallocation</a></p>
<hr />
<h1 id="07012021-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">07/01/2021, Peter Sovietov</span><a class="headerlink" href="#07012021-peter-sovietov" title="Permanent link">&para;</a></h1>
<p><strong>Next-gen Haskell Compilation Techniques</strong></p>
<p>На мой взгляд, презентация интересна будет многим компиляторщикам. Автор приводит массу академических ссылок. В целом, речь идет о проблематике организации архитектуры современного компилятора. Мне, например, очень понравилась идея с использованием Datalog, которая дополнительно себя оправдала и с точки зрения производительности статического анализа.</p>
<p><a href="https://docs.google.com/presentation/u/0/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ/mobilepresent">https://docs.google.com/presentation/u/0/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ/mobilepresent</a></p>
<p><a href="ghc.html">#ghc</a> <a href="grin.html">#grin</a></p>
<hr />
<h1 id="06012021-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">06/01/2021, Peter Sovietov</span><a class="headerlink" href="#06012021-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>И мой комментарий к комментарию <a href="https://t.me/plcomp/64">https://t.me/plcomp/64</a> по &ldquo;A Survey on Register Allocation&rdquo;.</p>
<p>Статья-обзор по алгоритмам распределения регистров. Автор старается простыми словами объяснить на ходу базовую терминологию, чтобы читателю не пришлось на каждом шагу сверяться с другими источниками. В этом смысле содержание обзора можно было бы назвать доходчивым. Но, казалось бы, это не большое достижение &ndash; на тему распределения регистров есть разделы в известных учебниках, а проект LLVM, кажется, вообще закрыл эту тему для компиляторщиков, мол, бери готовое и не думай, как оно устроено.</p>
<p>А теперь перейду к сути. Fernando M Q Pereira, автор рассматриваемого обзора, один из признанных современных специалистов в области распределения регистров. F.M.Q. — автор передового алгоритма Puzzle Solving и даже имеет патент на него. Что касается самого обзора, то это, на мой взгляд, обязательное чтение для компиляторщика-профессионала, которого интересуют вопросы порождения целевого кода, особенно для нетрадиционных, неортогональных архитектур. И при всей своей внешней доходчивости это нелегкое чтение, требующее серьезной квалификации.</p>
<p>В обзоре рассматриваются как классические подходы, так и подходы передовые, специализированные. Передовые настолько, что в реализации LLVM вы их не встретите. Речь, например, о распределении регистров прямо в форме SSA, а также о более экзотических техниках, в духе PBQP.</p>
<p>Важно, что перед нами действительно научный обзор, поэтому автор не скупится на изложение важных теоретических результатов. На этот счет, в частности, есть очень ценный, заключительный раздел по NP-полным (современным!) результатам из области распределения регистров.</p>
<p><a href="registerallocation.html">#registerallocation</a></p>
<hr />
<h1 id="06012021-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">06/01/2021, Vladimir Kazanov</span><a class="headerlink" href="#06012021-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Размещение сотен промежуточных значений современных программ в десятках регистров типичных процессоров - одна из первых проблем, с которой столкнулись разработчики языков высокого яровня. Со временем было показано, что в общем случае задача распределения регистров является NP-полной, что предполагает множество эвристических и частичных решений.</p>
<p>&ldquo;A survey on register allocation&rdquo; - обзор темы РР на 2008 год с пояснением ключевой терминологи и перечислением наиболее эффективных подходов к проблеме.</p>
<p>Много внимания уделяется вариантам алгоритмов раскраски графа, линейного сканирования (linear scan) и перспективным на момент написания статьи альтернативным подходам (целочисленное линейное программирование, multi-commodity flow problem и др.).</p>
<p>В 2008 году все крупные компиляторы перешли к использованию внутренних представляний со статически однократным присваиванием (SSA). Поэтому естественно, что половина обзора посвящена рассмотрению полезных в РР свойств популярнейшего представления и адаптации ключевых алгоритмов к нему.</p>
<p>Интересно, что в обзоре почти не упоминаются легковесное локальное (внутри базовых блоков) РР и тяжелое точное РР; рассматриваются прежде всего популярные в больших промышленных компиляторах решения.</p>
<p>Материал написан доступно и явно ориентирован на введение в курс дела старшекурсников или аспирантов; автор не только разбирается в материале, но и умеет его донести.</p>
<p><a href="http://compilers.cs.ucla.edu/fernando/publications/drafts/survey.pdf">http://compilers.cs.ucla.edu/fernando/publications/drafts/survey.pdf</a></p>
<p><a href="survey.html">#survey</a> <a href="registerallocation.html">#registerallocation</a></p>
<hr />
<h1 id="29122020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">29/12/2020, Peter Sovietov</span><a class="headerlink" href="#29122020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Поздравляю читателей PLComp с предстоящими праздниками! Подведу некоторые итоги этого года.</p>
<ol>
<li>
<p>Выход очередного, четвертого тома <strong>HOPL</strong>. <a href="https://t.me/plcomp/6">https://t.me/plcomp/6</a>
Замечательное, увлекательное чтение для всех, кто интересуется историей разработки ЯП.</p>
</li>
<li>
<p>Развитие подхода <strong>E-Graphs</strong> для создания систем оптимизации и синтеза программ. <a href="https://t.me/plcomp/8">https://t.me/plcomp/8</a>
Именно в этом году появились доступные реализации E-Graphs, в том числе и учебные. Следует ожидать постепенного внедрения подхода в компиляторы.</p>
</li>
<li>
<p>Практические применения <strong>SyGuS</strong> (синтаксически-управляемый синтез программ) в компиляторах.
Для BPF (<a href="https://t.me/plcomp/51">https://t.me/plcomp/51</a>), для сетевых процессоров (<a href="https://dl.acm.org/doi/abs/10.1145/3387514.3405852">https://dl.acm.org/doi/abs/10.1145/3387514.3405852</a>) и для DSP (<a href="https://www.cs.utexas.edu/~bornholt/papers/diospyros-lctes20.pdf">https://www.cs.utexas.edu/~bornholt/papers/diospyros-lctes20.pdf</a> ).</p>
</li>
</ol>
<p>В будущем году, надеюсь, мы в PLComp также сможем оперативно реагировать на основные события в компиляторной/языковой тематике. Пока же предлагаю &ldquo;заглянуть в будущее&rdquo;, посмотреть на работы предстоящих конференций.</p>
<ol>
<li>
<p><strong>ASPLOS 2021</strong>. <a href="https://asplos-conference.org/papers/">https://asplos-conference.org/papers/</a></p>
</li>
<li>
<p><strong>POPL 2021</strong>. <a href="https://popl21.sigplan.org/program/program-POPL-2021">https://popl21.sigplan.org/program/program-POPL-2021</a></p>
</li>
<li>
<p><strong>CGO 2021</strong>. <a href="https://conf.researchr.org/info/cgo-2021/accepted-papers">https://conf.researchr.org/info/cgo-2021/accepted-papers</a></p>
</li>
</ol>
<p><a href="conf.html">#conf</a></p>
<hr />
<h1 id="17122020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">17/12/2020, Peter Sovietov</span><a class="headerlink" href="#17122020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Работа <strong>Strategic Tree Rewriting in Attribute Grammars</strong> заслуживает внимания попыткой объединения стратегического переписывания термов с атрибутными грамматиками.</p>
<p><a href="https://www-users.cs.umn.edu/~evw/pubs/kramer20sle/kramer20sle.pdf">https://www-users.cs.umn.edu/~evw/pubs/kramer20sle/kramer20sle.pdf</a></p>
<p>В последнее время интерес к забытым когда-то атрибутным грамматикам (АГ), похоже, вновь возрастает. Напомню, что АГ, формализованные Д. Кнутом еще в 1968 году, позволяют элегантным образом описывать задачи (статической) семантики и не сводятся только лишь к семантическим действиям какого-нибудь YACC. В случае АГ у нас, в общем случае, имеются как синтезированные, так и унаследованные атрибуты, позволяющие учесть контекст (это может быть, к примеру, таблица имен) при семантических вычислениях. Сами же вычисления могут производиться на графе, по готовности аргументов-атрибутов.</p>
<p>Существует ряд современных систем быстрого прототипирования DSL-компиляторов с использованием АГ, это, в частности, JastAdd, Kiama и Silver. В рассматриваемой статье система Silver (<a href="http://melt.cs.umn.edu/silver/">http://melt.cs.umn.edu/silver/</a> ) используется для реализации стратегий в виде атрибутов высшего порядка. Зачем это нужно? Дело в том, что на уровне стратегического переписывания тяжело работать с контекстной информацией. К  примеру, классический подход от E. Visser предполагает динамическое создание правил в зависимости от контекста, что не назовешь элегантным решением. На уровне атрибутов с контекстом работать значительно удобнее, в то время, как преобразования программ выразительнее осуществляются с использованием стратегий.</p>
<p>В статье демонстрируется ряд примеров использования такого &ldquo;смешанного&rdquo; подхода, среди которых: оптимизация регулярных выражений на основе производных Бржозовского и нормализация for-цикла для Halide-подобного языка. Сложно сказать, насколько предложенный подход окажется успешным, но сама по себе система Silver в любом случае представляет интерес [1].</p>
<ol>
<li>Язык AbleC (расширение C11): <a href="http://melt.cs.umn.edu/ableC/">http://melt.cs.umn.edu/ableC/</a></li>
</ol>
<p><a href="dsl.html">#dsl</a> <a href="stratego.html">#stratego</a> <a href="semantics.html">#semantics</a> <a href="ag.html">#ag</a></p>
<hr />
<h1 id="11122020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">11/12/2020, Peter Sovietov</span><a class="headerlink" href="#11122020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>В среде компиляторщиков можно встретить утверждения в духе &ldquo;SSA это функциональное программирование&rdquo; и &ldquo;в теории нет разницы между phi-функциями и базовыми блоками с параметрами&rdquo;. С инженерной же точки зрения различия, все-таки, имеются. В заметке ниже показан пример этих различий со сравнением императивного и функционального подходов к разработке компилятора:</p>
<p><a href="http://blog.ezyang.com/2020/10/the-hidden-problem-with-basic-block-procedures-in-ssa/">http://blog.ezyang.com/2020/10/the-hidden-problem-with-basic-block-procedures-in-ssa/</a></p>
<p>Добавлю, что нельзя сказать, что одно из этих представлений в общем случае лучше, чем другое, с точки зрения вариантов проводимого анализа (см. также <a href="https://news.ycombinator.com/item?id=24872752">https://news.ycombinator.com/item?id=24872752</a> ). Но, в целом, можно отметить тенденцию использования базовых блоков с параметрами в высокоуровневых IR и для межпроцедурных преобразований, а phi-функций &ndash; в низкоуровневых представлениях (вплоть до реализации мультиплексоров в описании генерируемой цифровой схемы).</p>
<p><a href="ssa.html">#ssa</a></p>
<hr />
<h1 id="01122020-alexander-tchitchigin"><span style="font-weight:normal;font-style:italic;font-size:medium">01/12/2020, Alexander Tchitchigin</span><a class="headerlink" href="#01122020-alexander-tchitchigin" title="Permanent link">&para;</a></h1>
<p><a href="https://www.jeffsmits.net/assets/articles/sle20-paper4.pdf">https://www.jeffsmits.net/assets/articles/sle20-paper4.pdf</a>
Gradually Typing Strategies</p>
<p>Статья рассказывает о применении популярной техники постепенной типизации (Gradual Typing) в необычной области &ndash; к языку переписывания термов Stratego (который используется для &ldquo;program normalization, type checkers, program analyses, code generators, and more&rdquo;). Несмотря на отсутствие проверки типов в Stratego до сего момента, он тем не менее послужил для вдохновения авторов Haskell фреймворка SYB.</p>
<p>Использование Gradual Typing (постепенной типизации) мотивировано двумя факторами. Первый &ndash; обратная совместимость, так как Stratego (в составе фреймворков Stratego/XT и Spoofax) используется в production-системах, разрабатываемых как в академии (<a href="researchr.org">researchr.org</a>, <a href="conf.researchr.org">conf.researchr.org</a>, платформа онлайн-курсов TU Delft), так и в индустрии (где-то в недрах Oracle Labs). Второй &ndash; высокая &ldquo;динамичность&rdquo; переписывания термов, которая в некоторых случаях используется (а кто-то скажет &ldquo;эксплуатируется&rdquo;) для (временного) порождения нетипизируемых термов и превращения их обратно в типизируемые.</p>
<p>Дополнительно задача осложняется наличием в Stratego правил переписывания &ldquo;высшего порядка&rdquo; (называемых &ldquo;стратегиями переписывания&rdquo;), принимающих и применяющих другие правила переписывания (или стратегии). Отсюда возникает понятие Type-Preserving стратегий, реализующее ограниченную форму Higher-Kinded Types.</p>
<p>Кроме того, авторы применяют механизм &ldquo;прозрачных&rdquo; во время исполнения прокси-типов для того чтобы избежать накапливания лишних динамических преобразований типов при передаче правил переписывания из статически-типизированных стратегий в динамически-типизированные и обратно.</p>
<p>Проверка полученной системы типов на существующем проекте (учебный ассемблер для Java-байткода) продемонстрировала два достаточно ожидаемых результата: а) корректный динамический код написан так как если бы был статически типизирован, поэтому его легко аннотировать явными типами и почти не приходится при этом рефакторить; б) плохо протестированный динамический код содержит ошибки, которые легко обнаруживаются тайп-чекером (например, возврат списка вместо элемента — классика, сам на таком попадался).</p>
<p><a href="stratego.html">#stratego</a> <a href="types.html">#types</a> <a href="spoofax.html">#spoofax</a> <a href="gradual.html">#gradual</a></p>
<hr />
<h1 id="27112020-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">27/11/2020, Vladimir Kazanov</span><a class="headerlink" href="#27112020-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Популярный алгоритм распределения регистров линейным сканированием (Linear Scan Register Allocation, 1999) определен на живых интервалах (live intervals) и линейном списке инструкций. Построение и хранение списка интервалов в виде пар индексов инструкций занимает время и память, поэтому исследователи продолжали искать возможность не строить явно список интервалов.</p>
<p>Авторы Efficient Global Register Allocation (2020) предложили алгоритм из того же семейства, но определенный на графе потока исполнения (control flow graph). Ключевые идеи здесь две:</p>
<ol>
<li>
<p>Список живых интервалов здесь отслеживаются неявно, на каждом из базовых блоков и инструкций внутри блоков.</p>
</li>
<li>
<p>Проход по отдельным инструкциям позволяет не только не строить в явном виде интервалы, но и высвобождать временно регистры внутри блоков, что решает проблему &ldquo;пустот в живости&rdquo; (liveness holes).</p>
</li>
</ol>
<p>Алгоритм сравним по производительности порожденного кода с актуальными реализациями линейного сканирования, немного выигрывая в ресурсах на этапе компиляции. Из работы следует, что основное преимущество подхода заключается в возможностях специальных оптимизаций.</p>
<p>В настоящий момент этот вариант линейного сканирования используется при порождении регистрового байткода dex для виртуальной машины ART, используемый в Android.</p>
<p><a href="https://arxiv.org/pdf/2011.05608.pdf">https://arxiv.org/pdf/2011.05608.pdf</a></p>
<p><a href="art.html">#art</a> <a href="registerallocation.html">#registerallocation</a> <a href="android.html">#android</a> <a href="dex.html">#dex</a> <a href="linearscan.html">#linearscan</a></p>
<hr />
<h1 id="26112020-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">26/11/2020, Vladimir Kazanov</span><a class="headerlink" href="#26112020-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Распределение регистров - краеугольная задача любого порождающего машинный код компилятора. В работе Linear Scan Register Allocation (1999) был представлен один из двух популярнейших алгоритмов распределения регистров. </p>
<p>По сравнению с алгоритмами на основе раскраски графов алгоритм линейного сканирования отличается простотой в реализации, высокой скоростью работы самого алгоритма и эффективностью выходного кода. Авторы пишут, что даже простейший вариант алгоритма, представленный в публикации,  порождает код, лишь немного уступающий в производительности алгоритмам на основе раскраски графов. </p>
<p>Благодаря своим свойствам алгоритм стал стандартным решением в динамических (just-in-time) и легковесных компиляторах.</p>
<p>Из известных компиляторов линейное сканирование используется, например, в luajit или Hotspot.</p>
<p><a href="linearscan.html">#linearscan</a> <a href="history.html">#history</a> <a href="registerallocation.html">#registerallocation</a></p>
<hr />
<h1 id="24112020-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">24/11/2020, Vladimir Kazanov</span><a class="headerlink" href="#24112020-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Классический редактор GNU Emacs в скором времени получит, наконец, нативный компилятор для своего языка расширений Emacs Lisp. Это уже третья попытка решить сопутствующие проблемы, но Andrea Corallo за последний год построил на базе libgccjit компилятор, показывающий достойный результат в пакете elisp-benchmarks. Уже сейчас компилятор готовится к вливанию в основную ветку репозитория GNU Emacs.</p>
<p>Презентация автора на Linux Plumbers Conference 2020: 
<a href="http://akrl.sdf.org/Kludging_LPC_2020.pdf">http://akrl.sdf.org/Kludging_LPC_2020.pdf</a></p>
<p>Дневник разработки:
<a href="http://akrl.sdf.org/gccemacs.html">http://akrl.sdf.org/gccemacs.html</a></p>
<p>Обсуждение (в положительном ключе) состояния ветки репозитории:
<a href="https://debbugs.gnu.org/cgi/bugreport.cgi?bug=43725">https://debbugs.gnu.org/cgi/bugreport.cgi?bug=43725</a></p>
<hr />
<h1 id="12112020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">12/11/2020, Peter Sovietov</span><a class="headerlink" href="#12112020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>(Это мой старый перечень, но интерес, как мне кажется, он все еще представляет) Ниже я хочу представить краткий список полновесных книг по <strong>специальным вопросам</strong> компиляции. Эти книги много дали лично мне. Надеюсь, они окажутся в соответствующий момент полезными и вам.</p>
<ol>
<li>Automatic Algorithm Recognition and Replacement. A New Approach to Program Optimization (<a href="https://mitpress.mit.edu/books/automatic-algorithm-recognition-and-replacement?cr=reset">https://mitpress.mit.edu/books/automatic-algorithm-recognition-and-replacement?cr=reset</a>). </li>
</ol>
<p>Тема распознавания алгоритмов очень мало изучена. Но перспективы здесь самые впечатляющие. Оптимизации на уровне алгоритмов, автоматическое распараллеливание и проч. Весьма вдохновляющее чтение. </p>
<ol>
<li>Reasoning About Program Transformations. Imperative Programming and Flow of Data. (<a href="https://www.springer.com/us/book/9780387953915">https://www.springer.com/us/book/9780387953915</a>). </li>
</ol>
<p>Очень нетипичная книга по анализу и преобразованиям программ. Доходчиво написано, автор предмет понимает настолько глубоко, что не стесняется быть субъективным, оригинальным в изложении традиционной теории. Рассматривается в том числе полиэдральная модель программы.</p>
<ol>
<li>Instruction Selection. Principles, Methods, and Applications. (<a href="https://www.springer.com/us/book/9783319340173">https://www.springer.com/us/book/9783319340173</a>). </li>
</ol>
<p>Такого подробного, эницклопедического обзора подходов к выбору инструкций не хватало давно. Автор систематизировал различные приемы, использовал в изложении исторический контекст. </p>
<ol>
<li>Partial Evaluation and Automatic Program Generation (<a href="https://www.itu.dk/~sestoft/pebook/">https://www.itu.dk/~sestoft/pebook/</a>). </li>
</ol>
<p>В наше время все чаще на практике используются давние результаты Турчина, Футамуры, Ершова и других исследователей в области частичных вычислений/метапрограммирования. В какой-то момент, после прочтения очередной заметки в блоге с упоминанием проекций Футамуры (PyPy, Truffle и так далее), нелишне будет открыть и эту книгу, где подробно изложены все эти темы.</p>
<hr />
<h1 id="02112020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">02/11/2020, Peter Sovietov</span><a class="headerlink" href="#02112020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Очередная работа от John Regehr со товарищи на тему супероптимизации.</p>
<p><strong>Dataflow-based Pruning for Speeding up Superoptimization </strong>
<a href="https://www.cs.utah.edu/~regehr/dataflow-pruning.pdf">https://www.cs.utah.edu/~regehr/dataflow-pruning.pdf</a></p>
<p>Заметно, как первая эйфория от полностью автоматического применения SMT-решателя и метода CEGIS уходит. Оказывается, для задач реалистичных размерностей все равно приходится придумывать если не полностью собственную процедуру поиска с учетом эвристик из предметной области, то хотя бы ее элементы &ndash; иначе SMT-решателю справиться будет тяжело. </p>
<p>Ключевая идея авторов &ndash; прежде чем передавать на вход SMT-решателю очередную программу-кандидат из пространства поиска, полезно эту недооформленную программу (описывающую целое семейство конкретных программ) проверить на соответствие спецификации с помощью абстрактной интерпретации (анализ потоков данных на предмет known bits, int. ranges и так далее). В том числе, на конкретных тестовых входах.</p>
<p>В завершающей части статьи есть краткий и полезный обзор современного положения дел в области синтеза программ.</p>
<p><a href="analysis.html">#analysis</a> <a href="synthesis.html">#synthesis</a> <a href="smt.html">#smt</a></p>
<hr />
<h1 id="01112020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">01/11/2020, Peter Sovietov</span><a class="headerlink" href="#01112020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Известно, что в компиляторе IR выбирается таким образом, чтобы облегчить порождение кода для выбранного класса целевых архитектур. Но бывает ли так, чтобы уже само абстрактное IR оказывало влияние на набор команд процессора? Оказывается, и такое существует, причем речь здесь не идет о предметно-ориентированном наборе команд или поддержке конструкций входного языка. Ниже два характерных примера.</p>
<p><strong>BasicBlocker: Redesigning ISAs to Eliminate Speculative-Execution Attacks </strong>
<a href="https://arxiv.org/pdf/2007.15919.pdf">https://arxiv.org/pdf/2007.15919.pdf</a></p>
<p>В этой работе предлагается добавить к ISA процессора специальную команду, отмечающую начало линейного участка (basic block) с указанием его длины. Это нужно для предотвращения Spectre-подобных атак. Здесь мы видим, как черты абстрактного управляющего графа (CFG) проступают в машинном коде.</p>
<p><strong>Hardware Acceleration for Programs in SSA Form </strong>
<a href="https://pp.ipd.kit.edu/uploads/publikationen/mohr13cases.pdf">https://pp.ipd.kit.edu/uploads/publikationen/mohr13cases.pdf</a></p>
<p>В современных компиляторах форму SSA стараются сохранять настолько долго, насколько возможно, включая и фазу распределения регистров. Тем не менее, в какой-то момент из формы SSA приходится выходить и выход это достаточно болезнен, поскольку требует формирования дополнительных машинных команд. Особенно это касается phi-инструкций, имитировать которые приходится с помощью команд, заменяющих параллельные копирования/перестановки регистровых значений. А если попробовать реализовать phi-инструкцию аппаратным образом? При этом вместо реального копирования часто можно обойтись перестановками, которые на аппаратном уровне заключаются в переименовании регистров. Здесь в ISA процессора появляются черты абстрактной phi-инструкции из формы SSA.</p>
<p><a href="ssa.html">#ssa</a> <a href="isa.html">#isa</a></p>
<hr />
<h1 id="22102020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">22/10/2020, Peter Sovietov</span><a class="headerlink" href="#22102020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Очередной выпад в сторону классического подхода к преподаванию синтаксического разбора. Простое и изящное в части содержания пособие по написанию разбора арифметических выражений. Автор красиво и плавно приводит к идее использования рекурсивного спуска совместно с парсером Пратта.</p>
<p><strong>Just write the #!%/* parser</strong>
<a href="https://tiarkrompf.github.io/notes/?/just-write-the-parser/">https://tiarkrompf.github.io/notes/?/just-write-the-parser</a>/</p>
<p>На первый взгляд эта новость не слишком подходит для PLComp, но обращает на себя внимание личность автора (Tiark Rompf — один из лучших специалистов в области DSL-компиляции) и идеологическая спорность его подхода.</p>
<p>Действительно ли это правильный путь — перейти в обучении сразу к нюансам низкоуровневого кодирования, оставив за бортом вопросы формальной спецификации языка, его синтаксиса? Известные примеры реальных проектов, безусловно, говорят, мол, да, так оно и происходит на практике. И даже если есть спецификация, то она остается «на бумаге» и со временем расходится с реализацией все больше и больше.</p>
<p><a href="parsing.html">#parsing</a></p>
<hr />
<h1 id="21102020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">21/10/2020, Peter Sovietov</span><a class="headerlink" href="#21102020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Очередное подтверждение тому факту, что работа над компиляторами &ndash; это не только  известные проекты-бегемоты в духе LLVM/GCC для 2-3 популярных архитектур и виртуальных машин. </p>
<p>Вы слышали о BPF? Впрочем, что я говорю, если читаете внимательно PLComp, то, конечно, слышали. Но, в любом случае, есть замечательная заметка, которая вводит в предмет: </p>
<p><strong>BPF, XDP, Packet Filters and UDP </strong>
<a href="https://fly.io/blog/bpf-xdp-packet-filters-and-udp/">https://fly.io/blog/bpf-xdp-packet-filters-and-udp/</a></p>
<p>Посмотрите, сколько всего интересного! Узкая предметная область, виртуальные машины, JIT-компиляция, статический анализ кода, верификация.</p>
<p>В заметке есть ссылка на хорошую статью 1999 года: </p>
<p><strong>BPF+: Exploiting Global Data-flow Optimization in a Generalized Packet Filter Architecture </strong>
<a href="https://andrewbegel.com/papers/bpf.pdf">https://andrewbegel.com/papers/bpf.pdf</a></p>
<p>Ничего себе, да? Такие-то технологии для, вроде бы, заурядной задачи фильтрации пакетов!</p>
<p>И вот кульминация, статья уже совсем свежая:</p>
<p><strong>Specification and verification in the field: Applying formal methods to BPF just-in-time compilers in the Linux kernel </strong>
<a href="https://unsat.cs.washington.edu/papers/nelson-jitterbug.pdf">https://unsat.cs.washington.edu/papers/nelson-jitterbug.pdf</a></p>
<p>Складывается ощущение, что BPF &ndash; своеобразный полигон для обкатки перспективных технологий компиляции. Это объяснимо: на исходный язык и вычисления накладываются жесткие ограничения, сама виртуальная машина простая &ndash; есть где развернуться и применить что-нибудь изощренное. И, разумеется, интересны перспективы использования BPF в специализированных аппаратных решениях.</p>
<p>P.S. Вообще, в области обработки сетевых пакетов компиляторные технологии в целом развиваются очень интересным образом, существуют работающие подходы из области синтеза программ и я к этой теме еще обязательно вернусь.</p>
<p><a href="bpf.html">#bpf</a> <a href="analysis.html">#analysis</a> <a href="verification.html">#verification</a> <a href="jit.html">#jit</a> <a href="vm.html">#vm</a></p>
<hr />
<h1 id="16102020-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">16/10/2020, Vladimir Kazanov</span><a class="headerlink" href="#16102020-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Обсуждения вокруг эффективности интерпретатора и компилятора LuaJIT не утихают в нишевых сообществах до сих пор, при этом сам автор развернутых пояснений так и не оставил. Отдельные его комментарии можно найти на Reddit и в рассылке lua:</p>
<p><a href="http://lua-users.org/lists/lua-l/2008-07/msg00651.html">http://lua-users.org/lists/lua-l/2008-07/msg00651.html</a>
<a href="http://lua-users.org/lists/lua-l/2010-11/msg00437.html">http://lua-users.org/lists/lua-l/2010-11/msg00437.html</a>
<a href="http://lua-users.org/lists/lua-l/2011-02/msg00671.html">http://lua-users.org/lists/lua-l/2011-02/msg00671.html</a>
<a href="http://lua-users.org/lists/lua-l/2011-02/msg00742.html">http://lua-users.org/lists/lua-l/2011-02/msg00742.html</a>
<a href="https://www.reddit.com/r/programming/comments/hkzg8/author_of_luajit_explains_why_compilers_cant_beat/c1w8xyz/?context=3">https://www.reddit.com/r/programming/comments/hkzg8/author_of_luajit_explains_why_compilers_cant_beat/c1w8xyz/?context=3</a>
<a href="https://www.reddit.com/r/programming/comments/badl2/luajit_2_beta_3_is_out_support_both_x32_x64/c0lrus0/">https://www.reddit.com/r/programming/comments/badl2/luajit_2_beta_3_is_out_support_both_x32_x64/c0lrus0/</a></p>
<h1 id="jit-lua">JIT #Lua<a class="headerlink" href="#jit-lua" title="Permanent link">&para;</a></h1>
<p><a href="jit.html">#jit</a> <a href="lua.html">#lua</a></p>
<hr />
<h1 id="16102020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">16/10/2020, Peter Sovietov</span><a class="headerlink" href="#16102020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Пособие по реализации проверки для refinement-типов. В духе разработки компиляторов на основе техники nanopass. Предикаты проверяются с помощью SMT-решателя Z3.</p>
<p><strong>Refinement Types: A Tutorial </strong>
<a href="https://arxiv.org/abs/2010.07763">https://arxiv.org/abs/2010.07763</a>
<a href="https://github.com/ranjitjhala/sprite-lang">https://github.com/ranjitjhala/sprite-lang</a></p>
<p><a href="analysis.html">#analysis</a> <a href="smt.html">#smt</a></p>
<hr />
<h1 id="08082020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">08/08/2020, Peter Sovietov</span><a class="headerlink" href="#08082020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Formulog &ndash; выразительный DSL для задач статического анализа.
Основан на Datalog и ML, реализация использует SMT-решатель.</p>
<p><strong>Formulog: ML + Datalog + SMT </strong>
<a href="http://www.weaselhat.com/2020/08/07/formulog-ml-datalog-smt/">http://www.weaselhat.com/2020/08/07/formulog-ml-datalog-smt/</a></p>
<p><a href="datalog.html">#datalog</a> <a href="analysis.html">#analysis</a> <a href="smt.html">#smt</a></p>
<hr />
<h1 id="25072020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">25/07/2020, Peter Sovietov</span><a class="headerlink" href="#25072020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Детальный анализ трассирующего JIT-компилятора Lua</p>
<p><strong>LuaJIT  </strong>
<a href="https://github.com/MethodicalAcceleratorDesign/MADdocs/blob/master/luajit/luajit-doc.pdf">https://github.com/MethodicalAcceleratorDesign/MADdocs/blob/master/luajit/luajit-doc.pdf</a></p>
<h1 id="jit">JIT<a class="headerlink" href="#jit" title="Permanent link">&para;</a></h1>
<p><a href="jit.html">#jit</a> <a href="lua.html">#lua</a></p>
<hr />
<h1 id="03072020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">03/07/2020, Peter Sovietov</span><a class="headerlink" href="#03072020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Впечатляющая подборка материалов от серьезно настроенного исследователя.</p>
<p>По вопросам корректности компиляторов: <a href="https://github.com/MattPD/cpplinks/blob/master/compilers.correctness.md">https://github.com/MattPD/cpplinks/blob/master/compilers.correctness.md</a></p>
<p>По статическому и динамическому анализу: <a href="https://gist.github.com/MattPD/00573ee14bf85ccac6bed3c0678ddbef">https://gist.github.com/MattPD/00573ee14bf85ccac6bed3c0678ddbef</a></p>
<p>По компиляторам в целом: <a href="https://github.com/MattPD/cpplinks/blob/master/compilers.md">https://github.com/MattPD/cpplinks/blob/master/compilers.md</a></p>
<hr />
<h1 id="26062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">26/06/2020, Peter Sovietov</span><a class="headerlink" href="#26062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Небольшая заметка на тему вопросов канонизации внутренних представлений в компиляторах. Тема затронута очень поверхностно, но даже в таком виде, думаю, заслуживает более пристального внимания со стороны компиляторщиков.</p>
<p><strong>Canonicalization </strong>
<a href="https://sunfishcode.github.io/blog/2018/10/22/Canonicalization.html">https://sunfishcode.github.io/blog/2018/10/22/Canonicalization.html</a></p>
<hr />
<h1 id="23062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">23/06/2020, Peter Sovietov</span><a class="headerlink" href="#23062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Два небольших доклада об инструментах статического анализа, основанных на Datalog. </p>
<p><strong>DOOP </strong>
<a href="https://www.youtube.com/watch?v=FQRLB2xJC50">https://www.youtube.com/watch?v=FQRLB2xJC50</a></p>
<p><strong>Soufflé </strong>
<a href="https://www.youtube.com/watch?v=Qp3zfM-JSx8">https://www.youtube.com/watch?v=Qp3zfM-JSx8</a></p>
<p><a href="datalog.html">#datalog</a> <a href="analysis.html">#analysis</a></p>
<hr />
<h1 id="17062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">17/06/2020, Peter Sovietov</span><a class="headerlink" href="#17062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>В рамках PLDI Alex Aiken (известный многим по курсам компиляторостроения) рассказал о проекте TASO &ndash; это автоматический синтез графовых оптимизирующих преобразований для нейросетевых фреймворков. Перечисляются все графы-шаблоны нейросетевых операций до фиксированного размера, между графами устанавливается соответствие с помощью Z3, преобразования графов программ происходят с помощью механизма отката и стоимостной модели. В целом, рассказ повторяет эту статью:</p>
<p><strong>TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions </strong>
<a href="https://cs.stanford.edu/~padon/taso-sosp19.pdf">https://cs.stanford.edu/~padon/taso-sosp19.pdf</a></p>
<p><a href="synthesis.html">#synthesis</a> <a href="smt.html">#smt</a></p>
<hr />
<h1 id="15062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">15/06/2020, Peter Sovietov</span><a class="headerlink" href="#15062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Подход к выявлению &ldquo;семантического клонов&rdquo; в программе. Основан на насыщении равенствами и забытой концепции Programmer’s Apprentice. Утверждается, что работает лучше, чем популярное в этой области представление PDG.</p>
<p><strong>Semantic Code Search via Equational Reasoning </strong>
<a href="https://dl.acm.org/doi/pdf/10.1145/3385412.3386001">https://dl.acm.org/doi/pdf/10.1145/3385412.3386001</a></p>
<p><a href="analysis.html">#analysis</a></p>
<hr />
<h1 id="10062020-alekum"><span style="font-weight:normal;font-style:italic;font-size:medium">10/06/2020, alekum</span><a class="headerlink" href="#10062020-alekum" title="Permanent link">&para;</a></h1>
<p><strong>Unsupervised Translation of Programming Languages  </strong>
Довольно любопытная статья на тему создания транскомпилятора от исследователей из Facebook AI Research.
Путем тренировки модели, на корпусе программ из Github, транслируют код языков C++, Java, Python. </p>
<p>Авторы  показывают, что их модель превосходит работы в данной области, основанные на подходе 
использования правил. Из интересного, прямой цитатой  из статьи:</p>
<pre>• 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.

</pre>
<p>В видео можно послушать комментарии.</p>
<p>Paper:
<a href="https://arxiv.org/pdf/2006.03511">https://arxiv.org/pdf/2006.03511</a></p>
<p>Video:
<a href="https://www.youtube.com/watch?v=xTzFJIknh7E&amp;app=desktop">https://www.youtube.com/watch?v=xTzFJIknh7E&amp;app=desktop</a></p>
<p><a href="ml.html">#ml</a> <a href="analysis.html">#analysis</a> <a href="transpilation.html">#transpilation</a></p>
<hr />
<h1 id="10062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">10/06/2020, Peter Sovietov</span><a class="headerlink" href="#10062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Авторы оценивают верхнюю и нижнюю границы вычислительной сложности статического анализа указателей Андерсена (APA) и приводят свои варианты реализации APA.</p>
<p><strong>The Fine-Grained Complexity of Andersen’s Pointer Analysis </strong>
<a href="https://arxiv.org/pdf/2006.01491.pdf">https://arxiv.org/pdf/2006.01491.pdf</a></p>
<p><a href="analysis.html">#analysis</a></p>
<hr />
<h1 id="10062020-peter-sovietov_1"><span style="font-weight:normal;font-style:italic;font-size:medium">10/06/2020, Peter Sovietov</span><a class="headerlink" href="#10062020-peter-sovietov_1" title="Permanent link">&para;</a></h1>
<p>Автоматическое извлечение КС-грамматики на основе динамического анализа управляющего графа программы на примерах входных данных. Любопытно, что авторы не стали даже упоминать грамматическое сжатие.</p>
<p><strong>Mining Input Grammars from Dynamic Control Flow </strong>
<a href="https://publications.cispa.saarland/3101/1/fse2020-mimid.pdf">https://publications.cispa.saarland/3101/1/fse2020-mimid.pdf</a></p>
<p><a href="analysis.html">#analysis</a> <a href="parsing.html">#parsing</a></p>
<hr />
<h1 id="07062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">07/06/2020, Peter Sovietov</span><a class="headerlink" href="#07062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Любопытная заметка от Intel на тему использования внешнего решателя задач целочисленного программирования в LLVM.
Речь идет об оптимальной расстановке команды LFENCE в управляющем графе. Это нужно для предотвращения LVI-атак.</p>
<p><strong>An Optimized Mitigation Approach for Load Value Injection </strong>
<a href="https://software.intel.com/security-software-guidance/insights/optimized-mitigation-approach-load-value-injection">https://software.intel.com/security-software-guidance/insights/optimized-mitigation-approach-load-value-injection</a></p>
<p>ILP-решатель для автоматической вставки fence применяли и ранее. См., например, работу <strong>Don’t sit on the fence. A static analysis approach to automatic fence insertion</strong>:
<a href="https://arxiv.org/pdf/1312.1411.pdf">https://arxiv.org/pdf/1312.1411.pdf</a></p>
<p><a href="analysis.html">#analysis</a> <a href="solver.html">#solver</a></p>
<hr />
<h1 id="07062020-alex"><span style="font-weight:normal;font-style:italic;font-size:medium">07/06/2020, Alex</span><a class="headerlink" href="#07062020-alex" title="Permanent link">&para;</a></h1>
<p>Опубликовано &ldquo;Руководство по эффективному программированию на платформе «Эльбрус»&rdquo;.</p>
<p>Это первая версия руководства, содержащая в себе общие сведения о платформе, <strong>описание важных оптимизаций компилятора</strong> и способы увеличения производительности. Кроме того, в нём содержатся сведения о наиболее распространённых инструкциях процессора, что официально публикуется впервые. Руководство позволит как ознакомиться с устройством самого процессора и сравнить его с популярными архитектурами, посмотреть как на практике решаются проблемы работы на нестандартной архитектуре.</p>
<p>Эльбрус - процессор общего назначения, разрабатываемый фирмой МЦСТ, с архитектурой на основе широкого командного слова (VLIW).</p>
<p><a href="http://www.mcst.ru/elbrus_prog">http://www.mcst.ru/elbrus_prog</a></p>
<p><a href="vliw.html">#vliw</a></p>
<hr />
<h1 id="05062020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">05/06/2020, Peter Sovietov</span><a class="headerlink" href="#05062020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Доклад <strong>Improving Compiler Construction Using Formal Methods</strong> (Jubi Taneja)
Обзор работ по теме использования супероптимизатора Souper в различных фазах компиляции (статический анализ, автоматизация создания правил локальной оптимизации).
<a href="https://www.youtube.com/watch?v=de8Ak0nY1hA">https://www.youtube.com/watch?v=de8Ak0nY1hA</a></p>
<p><a href="superoptimizer.html">#superoptimizer</a> <a href="smt.html">#smt</a></p>
<hr />
<h1 id="02062020-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">02/06/2020, Vladimir Kazanov</span><a class="headerlink" href="#02062020-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Сопоставление с образом (pattern matching) в наши дни упоминается прежде всего в контексте функциональных языков программирования семейства ML. Но техника эта имеет гораздо более широкое применение, в том числе и вне контекста разработки ЯП. Интереснейший из классических результатов - алгоритм Rete, позволяющий эффективно сопоставлять тысячи образов с тысячами же объектов. </p>
<p><strong>Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem</strong></p>
<hr />
<h1 id="01062020-alex-gryzlov"><span style="font-weight:normal;font-style:italic;font-size:medium">01/06/2020, Alex Gryzlov</span><a class="headerlink" href="#01062020-alex-gryzlov" title="Permanent link">&para;</a></h1>
<p>Очередная работа Мюнш-Макканьони по превращению Окамла в своеобразный конкурент Раста, черновик предложения о добавлении возможности работы с off-heap указателями:</p>
<p><strong>Towards better systems programming in OCaml with out-of-heap allocation (draft)</strong>
<a href="https://github.com/gadmm/RFCs/blob/interop/rfcs/interop.md">https://github.com/gadmm/RFCs/blob/interop/rfcs/interop.md</a></p>
<p><a href="ocaml.html">#ocaml</a></p>
<hr />
<h1 id="30052020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">30/05/2020, Peter Sovietov</span><a class="headerlink" href="#30052020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Использование рекомендательных систем для автонастройки компилятора, с учетом собранной ранее информации. Результаты внушают оптимизм.
<strong>A Collaborative Filtering Approach for the Automatic Tuning of Compiler Optimisations </strong>
<a href="https://arxiv.org/pdf/2005.04092.pdf">https://arxiv.org/pdf/2005.04092.pdf</a></p>
<p><a href="autotuning.html">#autotuning</a> <a href="optimization.html">#optimization</a> <a href="compiler.html">#compiler</a> <a href="machinelearning.html">#machinelearning</a></p>
<hr />
<h1 id="28052020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">28/05/2020, Peter Sovietov</span><a class="headerlink" href="#28052020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>SSA в историческом контексте. Очень хорошая систематизация знаний по теме.
<strong>Program Analisys and Transformation Survey and Links </strong>
<a href="https://github.com/pfalcon/awesome-program-analysis">https://github.com/pfalcon/awesome-program-analysis</a></p>
<p><a href="analysis.html">#analysis</a> <a href="ssa.html">#ssa</a></p>
<hr />
<h1 id="28052020-vladimir-kazanov"><span style="font-weight:normal;font-style:italic;font-size:medium">28/05/2020, Vladimir Kazanov</span><a class="headerlink" href="#28052020-vladimir-kazanov" title="Permanent link">&para;</a></h1>
<p>Синтаксический анализ программ считается давно изученной и почти даже скучной областью. Но при применении теории к практике текстовых редакторов часто выясняется, что привычные формализмы работают плохо и разработчикам приходится предлагать неординарные решения. В своей статье &ldquo;<strong>SMIE: Simple Minded Indentation Engine</strong>&rdquo; Стефан Монье излагает суть проблемы автоматического расставления отступов и описывает решение на базе  грамматик с операторным предшествованием (operator-precedence grammars), используемое в Емаксе.</p>
<p><a href="http://www-labs.iro.umontreal.ca/~monnier/smie.pdf">http://www-labs.iro.umontreal.ca/~monnier/smie.pdf</a></p>
<p><a href="editor.html">#editor</a> <a href="emacs.html">#emacs</a> <a href="smie.html">#smie</a> <a href="indentation.html">#indentation</a> <a href="parsing.html">#parsing</a></p>
<hr />
<h1 id="27052020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">27/05/2020, Peter Sovietov</span><a class="headerlink" href="#27052020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Очень доходчивый и практико-ориентированный разбор одной из ключевых статей в области супероптимизации на основе метода CEGIS. Автор даже не поленился расшифровать формулы из статьи для тех, кто сторонится математической нотации.
<strong>Synthesizing Loop-Free Programs with Rust and Z3 </strong>
<a href="https://fitzgeraldnick.com/2020/01/13/synthesizing-loop-free-programs.html">https://fitzgeraldnick.com/2020/01/13/synthesizing-loop-free-programs.html</a></p>
<p><a href="synthesis.html">#synthesis</a> <a href="smt.html">#smt</a></p>
<hr />
<h1 id="26052020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">26/05/2020, Peter Sovietov</span><a class="headerlink" href="#26052020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Halide — яркий пример современного и популярного DSL для высокопроизводительных вычислений (обработка изображений, нейросети). В работе по ссылке ниже представлена его формальная семантика. Достаточная, по большому счету, для разработки собственного компилятора Halide. Любопытно, что в описании трансляции в императивное представление использован формализм из области синтеза программ.
<strong>Formal Semantics for the Halide Language </strong>
<a href="https://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-40.pdf">https://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-40.pdf</a></p>
<p><a href="synthesis.html">#synthesis</a> <a href="semantics.html">#semantics</a> <a href="dsl.html">#dsl</a></p>
<hr />
<h1 id="25052020-peter-sovietov"><span style="font-weight:normal;font-style:italic;font-size:medium">25/05/2020, Peter Sovietov</span><a class="headerlink" href="#25052020-peter-sovietov" title="Permanent link">&para;</a></h1>
<p>Любопытная работа по применению методов машинного обучения без учителя (Q learning) для разработки адаптивного сборщика мусора. Впрочем, полученные в статье результаты пока не очень впечатляют.
<strong>Learned Garbage Collection </strong>
<a href="https://arxiv.org/pdf/2004.13301.pdf">https://arxiv.org/pdf/2004.13301.pdf</a></p>
<p><a href="garbagecollection.html">#garbagecollection</a> <a href="gc.html">#gc</a> <a href="machinelearning.html">#machinelearning</a></p>
<hr />
<h1 id="23052020"><span style="font-weight:normal;font-style:italic;font-size:medium">23/05/2020</span><a class="headerlink" href="#23052020" title="Permanent link">&para;</a></h1>
<p>Интересное сравнение Rust и Haskell на поле написания компиляторов для функциональных языков, с ссылками на бенчмарки:</p>
<p><a href="https://old.reddit.com/r/haskell/comments/gok70o/simple_haskell_is_best_haskell/frj9hty/">https://old.reddit.com/r/haskell/comments/gok70o/simple_haskell_is_best_haskell/frj9hty/</a></p>
<p><a href="fp.html">#fp</a> <a href="haskell.html">#haskell</a> <a href="rust.html">#rust</a> <a href="compiler.html">#compiler</a> <a href="education.html">#education</a></p>
<hr />
<h1 id="22052020"><span style="font-weight:normal;font-style:italic;font-size:medium">22/05/2020</span><a class="headerlink" href="#22052020" title="Permanent link">&para;</a></h1>
<p>Возможно, вы уже слышали новость о древнем GW-BASIC. Компания Microsoft выложила исходники интерпретатора на github: <a href="https://devblogs.microsoft.com/commandline/microsoft-open-sources-gw-basic/">https://devblogs.microsoft.com/commandline/microsoft-open-sources-gw-basic/</a></p>
<p>В заметке по ссылке есть одна интригующая фраза: &ldquo;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.)&rdquo;. И действительно, текст на языке ассемблера для 8088 был получен автоматически с помощью специального транслятора. При этом даже комментарии в коде остались нетронутыми, там речь идет, судя по всему, о 8080.</p>
<p>В статье из журнала Byte за 1982 год сравниваются возможности трех трансляторов, которые автоматически преобразуют код 8-битных процессоров 8080/Z80 для CP/M в 16-битный код 8088/8086 для MS-DOS: <a href="https://tech-insider.org/personal-computers/research/acrobat/8206-b.pdf">https://tech-insider.org/personal-computers/research/acrobat/8206-b.pdf</a></p>
<p>Особенно выделяется среди этих трансляторов <strong>XLT86</strong> (8080 -&gt; 8086) от компании Digital Research. Этот транслятор — детище Гэри Килдалла, о котором специально говорить, наверное, нет необходимости. В области построения компиляторов Килдалл известен своей работой A unified approach to global program optimization (1973): <a href="https://dl.acm.org/doi/pdf/10.1145/512927.512945">https://dl.acm.org/doi/pdf/10.1145/512927.512945</a></p>
<p>Статья Килдалла до сих пор находится в числе самых цитируемых по компиляторной тематике и речь идет об алгоритме анализа потока данных, который позже был описан во множестве учебников и применяется в самых современных компиляторах: <a href="http://compcert.inria.fr/doc-1.6/html/Kildall.html">http://compcert.inria.fr/doc-1.6/html/Kildall.html</a></p>
<p>Вернемся, однако, к XLT86. К счастью, сохранилась документация к транслятору: <a href="http://www.s100computers.com/Software%20Folder/Assembler%20Collection/Digital%20Research%20XLT86%20Manual.pdf">http://www.s100computers.com/Software%20Folder/Assembler%20Collection/Digital%20Research%20XLT86%20Manual.pdf</a></p>
<p>Из нее можно узнать, в частности, что:</p>
<ol>
<li>Трансляция состоит из 5 фаз.</li>
<li>В начале определяются линейные участки и строится граф потока управления. Затем проводится глобальный анализ потока данных для определения &ldquo;живых&rdquo; регистров и флагов процессора.</li>
<li>Сам процесс &ldquo;выбора команд&rdquo; элегантно описан табличным образом. Некоторые правила преобразований являются условными и зависят от ранее полученных результатов анализа потока данных.</li>
<li>Транслятор написан на ЯП PL/I-80 и имеет ограничение на размер входной программы — не более 6 Kбайт.</li>
</ol>
<p><a href="analysis.html">#analysis</a> <a href="history.html">#history</a></p>
<hr />
<h1 id="21052020"><span style="font-weight:normal;font-style:italic;font-size:medium">21/05/2020</span><a class="headerlink" href="#21052020" title="Permanent link">&para;</a></h1>
<p>Особенно же интересными (субъективно, разумеется) событиями симпозиума по Лиспу оказались: доклад и семинар по передовому фреймворку (набор eDSL на языке Scheme) для быстрой разработки компиляторов Nanopass. По Nanopass как раз не хватало свежей, актуальной информации в авторском изложении.</p>
<p>Доклад <strong>The Nanopass Framework as a Nanopass Compiler </strong>
Слайды: <a href="https://www.european-lisp-symposium.org/static/2020/keep-slides-keynote.pdf">https://www.european-lisp-symposium.org/static/2020/keep-slides-keynote.pdf</a>
Видео: <a href="https://www.youtube.com/watch?v=lqVN1fGNpZw">https://www.youtube.com/watch?v=lqVN1fGNpZw</a></p>
<p>Семинар <strong>Mixing Mutability into the Nanopass Framework </strong>
Слайды: <a href="https://www.european-lisp-symposium.org/static/2020/keep-slides-workshop.pdf">https://www.european-lisp-symposium.org/static/2020/keep-slides-workshop.pdf</a>
Видео: <a href="https://www.youtube.com/watch?v=wTGlKCfP90A">https://www.youtube.com/watch?v=wTGlKCfP90A</a></p>
<p><a href="dsl.html">#dsl</a> <a href="nanopass.html">#nanopass</a> <a href="langworkbench.html">#langworkbench</a></p>
<hr />
<h1 id="21052020_1"><span style="font-weight:normal;font-style:italic;font-size:medium">21/05/2020</span><a class="headerlink" href="#21052020_1" title="Permanent link">&para;</a></h1>
<p>Недавно (27-28 апреля, 2020) состоялся европейский симпозиум по Лиспу.</p>
<p><strong>European Lisp Symposium </strong>
<a href="https://www.european-lisp-symposium.org/2020/">https://www.european-lisp-symposium.org/2020/</a>
Видеозаписи докладов: <a href="https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga">https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga</a></p>
<p>Ниже краткая информация о 3 докладах по околокомпиляторной тематике:</p>
<p><strong>Partial Evaluation Based CPS Transformation: An Implementation Case Study </strong>
Описание компилятора для диалекта Лиспа pLisp. В компиляторе используются частичные вычисления и CPS.
Слайды: <a href="https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf">https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf</a>
Текст доклада в сборнике: <a href="https://www.european-lisp-symposium.org/static/proceedings/2020.pdf">https://www.european-lisp-symposium.org/static/proceedings/2020.pdf</a></p>
<p><strong>LLVM Code Generation for Open Dylan </strong>
Dylan — это диалект Лиспа с Алгол-подобным синтаксисом. В начале 90-х этот язык развивался компанией Apple. В докладе представлено описание генератора кода для Dylan на основе LLVM.
Слайды: <a href="https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf">https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf</a>
Текст доклада в сборнике: <a href="https://www.european-lisp-symposium.org/static/proceedings/2020.pdf">https://www.european-lisp-symposium.org/static/proceedings/2020.pdf</a></p>
<p><strong>Later Binding: Just in Time Compilation of a Younger Dynamic Programming Language </strong>
Краткий анализ компилятора LuaJIT
Видео выступления: <a href="https://www.youtube.com/watch?v=FBk5XAEhu2s">https://www.youtube.com/watch?v=FBk5XAEhu2s</a>
Текст доклада в сборнике: <a href="https://www.european-lisp-symposium.org/static/proceedings/2020.pdf">https://www.european-lisp-symposium.org/static/proceedings/2020.pdf</a></p>
<p><a href="cps.html">#cps</a> <a href="pe.html">#pe</a> <a href="jit.html">#jit</a> <a href="conf.html">#conf</a> <a href="llvm.html">#llvm</a></p>
<hr />
<h1 id="21052020_2"><span style="font-weight:normal;font-style:italic;font-size:medium">21/05/2020</span><a class="headerlink" href="#21052020_2" title="Permanent link">&para;</a></h1>
<p>На этой неделе появился официальный self-hosted дистрибутив функционального языка с зависимыми типами <strong>Idris 2</strong>. </p>
<p>На текущем этапе он использует в качестве бэкенда один из трех компиляторов Scheme: Chez, Racket или Gambit. Как и в первой версии Idris, есть инфраструктура для создания собственных бэкендов на основе нескольких IR c лямбдами (обычный LC, lifted форма, ANF, виртуальная машина с замыканиями). </p>
<p><a href="https://github.com/idris-lang/Idris2/">https://github.com/idris-lang/Idris2/</a></p>
<p><strong>Why is Idris 2 so much faster than Idris 1? </strong>
<a href="https://www.type-driven.org.uk/edwinb/why-is-idris-2-so-much-faster-than-idris-1.html">https://www.type-driven.org.uk/edwinb/why-is-idris-2-so-much-faster-than-idris-1.html</a></p>
<p><a href="fp.html">#fp</a></p>
<hr />
<h1 id="20052020"><span style="font-weight:normal;font-style:italic;font-size:medium">20/05/2020</span><a class="headerlink" href="#20052020" title="Permanent link">&para;</a></h1>
<p><strong>A Language for Describing Optimization Strategies </strong>
Пример использования стратегического переписывания термов в духе Stratego. В статье демонстрируются оптимизирующие преобразования на Scala, для GPU и других ускорителей.
<a href="https://arxiv.org/pdf/2002.02268.pdf">https://arxiv.org/pdf/2002.02268.pdf</a></p>
<p><a href="optimization.html">#optimization</a></p>
<hr />
<h1 id="19052020"><span style="font-weight:normal;font-style:italic;font-size:medium">19/05/2020</span><a class="headerlink" href="#19052020" title="Permanent link">&para;</a></h1>
<p>Работа по синтезу программ с использованием Rosette (Racket). Cинтезируется JIT-компилятор DSL BPF (ядро Linux) в машинный код (в примере использован RISC-V)
<strong>Synthesizing JIT Compilers for In-Kernel DSLs </strong>
<a href="https://www.cs.utexas.edu/~isil/jitsynth.pdf">https://www.cs.utexas.edu/~isil/jitsynth.pdf</a></p>
<p>Подробности о BPF VM:
<strong>BPF: A New Type of Software </strong>
<a href="http://www.brendangregg.com/blog/2019-12-02/bpf-a-new-type-of-software.html">http://www.brendangregg.com/blog/2019-12-02/bpf-a-new-type-of-software.html</a></p>
<p><a href="jit.html">#jit</a> <a href="synthesis.html">#synthesis</a> <a href="bpf.html">#bpf</a></p>
<hr />
<h1 id="19052020_1"><span style="font-weight:normal;font-style:italic;font-size:medium">19/05/2020</span><a class="headerlink" href="#19052020_1" title="Permanent link">&para;</a></h1>
<p>Полезная ссылка для участия в спорах на тему, какой ЯП выбрать для реализации компилятора
<strong>Comparing the Same Project in Rust, Haskell, C++, Python, Scala and OCaml </strong>
<a href="https://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/">https://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/</a></p>
<p><a href="python.html">#python</a> <a href="cpp.html">#cpp</a> <a href="haskell.html">#haskell</a> <a href="rust.html">#rust</a> <a href="comparison.html">#comparison</a> <a href="compiler.html">#compiler</a> <a href="implementation.html">#implementation</a> <a href="scala.html">#scala</a> <a href="education.html">#education</a> <a href="ocaml.html">#ocaml</a></p>
<hr />
<h1 id="19052020_2"><span style="font-weight:normal;font-style:italic;font-size:medium">19/05/2020</span><a class="headerlink" href="#19052020_2" title="Permanent link">&para;</a></h1>
<p>Работы Ian Piumarta, участника проекта STEPS</p>
<p><strong>Maru </strong>
Миниатюрный расширяемый Лисп-подобный язык с компилятором в IA32-код. Использовался в проекте STEPS.
Open, extensible composition models
<a href="https://www.piumarta.com/freeco11/freeco11-piumarta-oecm.pdf">https://www.piumarta.com/freeco11/freeco11-piumarta-oecm.pdf</a>
STEPS Toward the Reinvention of Programming, 2012 Final Report
<a href="http://www.vpri.org/pdf/tr2012001_steps.pdf">http://www.vpri.org/pdf/tr2012001_steps.pdf</a></p>
<p><strong>PEG-based transformer provides front-, middleand back-end stages in a simple compiler </strong>
<a href="http://www.vpri.org/pdf/tr2010003_PEG.pdf">http://www.vpri.org/pdf/tr2010003_PEG.pdf</a>
Шедевр изящества и миниатюризации в области генераторов компиляторов.</p>
<p><a href="lisp.html">#lisp</a> <a href="metacompiler.html">#metacompiler</a></p>
<hr />
<h1 id="19052020_3"><span style="font-weight:normal;font-style:italic;font-size:medium">19/05/2020</span><a class="headerlink" href="#19052020_3" title="Permanent link">&para;</a></h1>
<p><strong>Femtolisp</strong> — минималистичный интерпретатор диалекта LISP. 
<a href="https://github.com/JeffBezanson/femtolisp">https://github.com/JeffBezanson/femtolisp</a>
Автор стал впоследствии работать над Julia.  На femtolisp написаны лексер и парсер Julia.</p>
<p><a href="lisp.html">#lisp</a> <a href="interpreter.html">#interpreter</a></p>
<hr />
<h1 id="18052020"><span style="font-weight:normal;font-style:italic;font-size:medium">18/05/2020</span><a class="headerlink" href="#18052020" title="Permanent link">&para;</a></h1>
<p>В стадии call for papers</p>
<p>Конференция по ЯП с управляемым кодом и VM
<strong>MPLR 2020 </strong>
Ноябрь 4-6, 2020
<a href="https://mplr2020.cs.manchester.ac.uk/index.php/mplr/call-for-papers">https://mplr2020.cs.manchester.ac.uk/index.php/mplr/call-for-papers</a></p>
<p>Симпозиум по ЯП и системам
<strong>APLAS 2020 </strong>
30 ноября 2020
<a href="https://conf.researchr.org/home/aplas-2020">https://conf.researchr.org/home/aplas-2020</a></p>
<p><a href="conf.html">#conf</a></p>
<hr />
<h1 id="18052020_1"><span style="font-weight:normal;font-style:italic;font-size:medium">18/05/2020</span><a class="headerlink" href="#18052020_1" title="Permanent link">&para;</a></h1>
<p>В <strong>Retrofitting Parallelism onto OCaml </strong>авторы разбирают технические решения и компромисссы Multicore Ocaml, основное внимание уделяя сборщику мусора: 
<a href="https://arxiv.org/pdf/2004.11663.pdf">https://arxiv.org/pdf/2004.11663.pdf</a></p>
<p><a href="multicore.html">#multicore</a> <a href="garbagecollection.html">#garbagecollection</a> <a href="ocaml.html">#ocaml</a> <a href="gc.html">#gc</a></p>
<hr />
<h1 id="15052020"><span style="font-weight:normal;font-style:italic;font-size:medium">15/05/2020</span><a class="headerlink" href="#15052020" title="Permanent link">&para;</a></h1>
<p>Необычный подход к построению PEG-подобного парсера на основе восходящего разбора.
<strong>Pika parsing: parsing in reverse solves the left recursion and error recovery problems </strong>
<a href="https://arxiv.org/pdf/2005.06444.pdf">https://arxiv.org/pdf/2005.06444.pdf</a></p>
<p><a href="parsing.html">#parsing</a></p>
<hr />
<h1 id="14052020"><span style="font-weight:normal;font-style:italic;font-size:medium">14/05/2020</span><a class="headerlink" href="#14052020" title="Permanent link">&para;</a></h1>
<p>Две недавние статьи с участием Alessandro Warth. A. Warth — разработчик системы oMeta и автор известной работы по адаптации Packrat-парсеров для поддержки левосторонней рекурсии.</p>
<p><strong>Incremental Packrat Parsing</strong> (оригинальная идея по использованию Pakrat-таблицы для реализации инкрементального разбора)
<a href="https://dl.acm.org/doi/pdf/10.1145/3136014.3136022">https://dl.acm.org/doi/pdf/10.1145/3136014.3136022</a></p>
<p><strong>Recognising and Generating Terms using Derivatives of Parsing Expression Grammars </strong>
Использование производных Бржозовского в PEG-парсере для порождения предложений описываемого языка. Может использоваться в задаче тестирования компилятора (fuzzing). Но особенно интересно расширить эту идею на PEG с иерархическими структурами данных &ndash; и порождать тестовые примеры для них.
<a href="https://arxiv.org/pdf/1801.10490.pdf">https://arxiv.org/pdf/1801.10490.pdf</a></p>
<p><a href="parsing.html">#parsing</a></p>
<hr />
<h1 id="12052020"><span style="font-weight:normal;font-style:italic;font-size:medium">12/05/2020</span><a class="headerlink" href="#12052020" title="Permanent link">&para;</a></h1>
<p>О вычислительной универсальности PEG-парсеров.
<strong>The computational power of Parsing Expression Grammars </strong>
<a href="https://arxiv.org/pdf/1902.08272.pdf">https://arxiv.org/pdf/1902.08272.pdf</a></p>
<p><a href="parsing.html">#parsing</a></p>
<hr />
<h1 id="12052020_1"><span style="font-weight:normal;font-style:italic;font-size:medium">12/05/2020</span><a class="headerlink" href="#12052020_1" title="Permanent link">&para;</a></h1>
<p><strong>Program Analysis </strong>
Свежий (весна 2020) курс по анализу программ, с неплохим выбором тем.
<a href="https://cmu-program-analysis.github.io/">https://cmu-program-analysis.github.io/</a></p>
<p><a href="analysis.html">#analysis</a></p>
<hr />
<h1 id="12052020_2"><span style="font-weight:normal;font-style:italic;font-size:medium">12/05/2020</span><a class="headerlink" href="#12052020_2" title="Permanent link">&para;</a></h1>
<p>Основные работы по методу насыщения равенствами (equality saturation)</p>
<p><strong>Denali: A Goal-directed Superoptimizer</strong> (в работе описывается применение E-Graphs для задач оптимизации программ)
<a href="https://courses.cs.washington.edu/courses/cse501/15sp/papers/joshi.pdf">https://courses.cs.washington.edu/courses/cse501/15sp/papers/joshi.pdf</a></p>
<p><strong>Equality Saturation: A New Approach to Optimization</strong> (вместо E-Graphs используются PEG/E-PEG, поддерживающие управляющие конструкции)
<a href="https://www.cs.cornell.edu/~ross/publications/eqsat/">https://www.cs.cornell.edu/~ross/publications/eqsat/</a></p>
<p><strong>&ldquo;Доказательство свойств функциональных программ методом насыщения равенствами&rdquo;</strong> (диссертация на русском языке)
<a href="https://keldysh.ru/council/1/2017-grechanik/diss.pdf">https://keldysh.ru/council/1/2017-grechanik/diss.pdf</a></p>
<p><a href="synth.html">#synth</a> <a href="optimization.html">#optimization</a></p>
<hr />
<h1 id="11052020"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020" title="Permanent link">&para;</a></h1>
<p>Работы по практическому применению передовых подходов E-Graphs (дедуктивный синтез программ) и Equality Saturation (решение для проблемы phase ordering).</p>
<p>Особенно интересно, что для серьезных примеров использования взяты области, далекие от традиционных целевых представлений компиляторов. Это показывает, что компиляторные технологии имеют более широкое применение, чем иногда принято думать.</p>
<p><strong>Carpentry Compiler </strong>
<a href="https://grail.cs.washington.edu/projects/carpentrycompiler/files/CarpentryCompiler.pdf">https://grail.cs.washington.edu/projects/carpentrycompiler/files/CarpentryCompiler.pdf</a></p>
<p><strong>Synthesizing Structured CAD Models with Equality Saturation and Inverse Transformations </strong>
<a href="https://jamesrwilcox.com/szalinski.pdf">https://jamesrwilcox.com/szalinski.pdf</a></p>
<p>Для работы с E-Graphs авторами разработана библиотека egg (есть веб-демо).</p>
<p><strong>egg: Easy, Efficient, and Extensible E-graphs </strong>
<a href="https://arxiv.org/pdf/2004.03082.pdf">https://arxiv.org/pdf/2004.03082.pdf</a></p>
<p><a href="https://github.com/mwillsey/egg">https://github.com/mwillsey/egg</a></p>
<p><a href="optimization.html">#optimization</a></p>
<hr />
<h1 id="11052020_1"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020_1" title="Permanent link">&para;</a></h1>
<p>Авторы экспериментального компилятора для Emacs Lisp на базе libgccjit опубликовали работу, описывающие основные фазы работы компилятора</p>
<p><strong>Bringing GNU Emacs to Native Code</strong>:
<a href="https://zenodo.org/record/3736363/files/GCCEMACS_proceeding.pdf?download=1">https://zenodo.org/record/3736363/files/GCCEMACS_proceeding.pdf?download=1</a></p>
<p><a href="lisp.html">#lisp</a></p>
<hr />
<h1 id="11052020_2"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020_2" title="Permanent link">&para;</a></h1>
<p>Крупнейшая конференция по истории ЯП - HOPL IV - была перенесена, но некоторые интересные ретроспективные обзоры уже доступны:</p>
<p><strong>The History of Standard ML </strong>
<a href="https://smlfamily.github.io/history/SML-history.pdf">https://smlfamily.github.io/history/SML-history.pdf</a></p>
<p><strong>Evolution of Emacs Lisp </strong>
<a href="https://www.iro.umontreal.ca/~monnier/hopl-4-emacs-lisp.pdf">https://www.iro.umontreal.ca/~monnier/hopl-4-emacs-lisp.pdf</a></p>
<p><strong>History of Logo </strong>
<a href="https://escholarship.org/uc/item/1623m1p3">https://escholarship.org/uc/item/1623m1p3</a></p>
<p><strong>The Early History of F# </strong>
<a href="https://fsharp.org/history/hopl-final/hopl-fsharp.pdf">https://fsharp.org/history/hopl-final/hopl-fsharp.pdf</a></p>
<p><strong>A History of Clojure </strong>
<a href="https://clojure.org/about/history">https://clojure.org/about/history</a></p>
<p><strong>A History of the Oz Multiparadigm Language </strong>
<a href="https://www.info.ucl.ac.be/~pvr/hopl20main-p14-p-329dcad--final.pdf">https://www.info.ucl.ac.be/~pvr/hopl20main-p14-p-329dcad&ndash;final.pdf</a></p>
<p><strong>Thriving in a Crowded and Changing World: C++ 2006–2020 </strong>
<a href="https://www.stroustrup.com/hopl20main-p5-p-bfc9cd4--final.pdf">https://www.stroustrup.com/hopl20main-p5-p-bfc9cd4&ndash;final.pdf</a></p>
<p>Остальные доклады: <a href="https://dl.acm.org/toc/pacmpl/2020/4/HOPL">https://dl.acm.org/toc/pacmpl/2020/4/HOPL</a></p>
<p><a href="history.html">#history</a> <a href="conf.html">#conf</a></p>
<hr />
<h1 id="11052020_3"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020_3" title="Permanent link">&para;</a></h1>
<p><strong>Programming Paradigms for Dummies: What Every Programmer Should Know </strong>
Ликбез по основным принципам ЯП: классификация, вопросы представления состояния, конкурентности и параллелизма.
<a href="https://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf">https://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf</a></p>
<hr />
<h1 id="11052020_4"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020_4" title="Permanent link">&para;</a></h1>
<p><strong>CBS</strong> — система для описания компонентной спецификации ЯП.
В каком-то смысле это аналог LLVM для формальной семантики. Идея в том, чтобы транслировать ЯП в элементарные, строго определенные конструкции, называемые funcons. 
<a href="https://plancomps.github.io/CBS-beta/">https://plancomps.github.io/CBS-beta/</a></p>
<p><a href="semantics.html">#semantics</a></p>
<hr />
<h1 id="11052020_5"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020_5" title="Permanent link">&para;</a></h1>
<p>Статьи по современным легковесным методам порождения кода</p>
<p><strong>Destination-Driven Code Generation </strong>
<a href="https://pdfs.semanticscholar.org/dcb8/8719880e1f76ad71fb1c5aebb118e2ecfe71.pdf">https://pdfs.semanticscholar.org/dcb8/8719880e1f76ad71fb1c5aebb118e2ecfe71.pdf</a></p>
<p><strong>One-pass Code Generation in V8 </strong>
<a href="https://github.com/eatonphil/one-pass-code-generation-in-v8/blob/master/One-pass%20Code%20Generation%20in%20V8.pdf">https://github.com/eatonphil/one-pass-code-generation-in-v8/blob/master/One-pass%20Code%20Generation%20in%20V8.pdf</a></p>
<p><strong>HotpathVM: An Effective JIT Compiler for Resource-constrained Devices </strong>
<a href="https://static.usenix.org/events/vee06/full_papers/p144-gal.pdf">https://static.usenix.org/events/vee06/full_papers/p144-gal.pdf</a></p>
<p><a href="codegen.html">#codegen</a></p>
<hr />
<h1 id="11052020_6"><span style="font-weight:normal;font-style:italic;font-size:medium">11/05/2020</span><a class="headerlink" href="#11052020_6" title="Permanent link">&para;</a></h1>
<p>Недавние конференции (статьи доступны)</p>
<p><strong>CGO 2020</strong> (порождение кода и оптимизация)
<a href="https://cgo-conference.github.io/cgo2020/program/">https://cgo-conference.github.io/cgo2020/program/</a></p>
<p><strong>СС 2020</strong> (построение компиляторов)
<a href="https://conf.researchr.org/program/CC-2020/program-CC-2020">https://conf.researchr.org/program/CC-2020/program-CC-2020</a></p>
<p><strong>PLDI 2020</strong> (проектирование и реализация языков программирования)
<a href="https://pldi20.sigplan.org/program/program-pldi-2020">https://pldi20.sigplan.org/program/program-pldi-2020</a></p>
<p><strong>HOPL IV</strong> (история языков программирования)
<a href="https://hopl4.sigplan.org/track/hopl-4-papers#List-of-Accepted-Papers">https://hopl4.sigplan.org/track/hopl-4-papers#List-of-Accepted-Papers</a></p>
<p><a href="conf.html">#conf</a></p>
                
              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid" aria-label="Footer">
        
          <a href="index.html" class="md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-footer-nav__button md-icon">
              <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
            </div>
            <div class="md-footer-nav__title">
              <div class="md-ellipsis">
                <span class="md-footer-nav__direction">
                  Previous
                </span>
                NEW
              </div>
            </div>
          </a>
        
        
          <a href="analysis.html" class="md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-footer-nav__title">
              <div class="md-ellipsis">
                <span class="md-footer-nav__direction">
                  Next
                </span>
                #analysis
              </div>
            </div>
            <div class="md-footer-nav__button md-icon">
              <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M4 11v2h12l-5.5 5.5 1.42 1.42L19.84 12l-7.92-7.92L10.5 5.5 16 11H4z"/></svg>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
        Made with
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs
        </a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="assets/javascripts/vendor.53cc9318.min.js"></script>
      <script src="assets/javascripts/bundle.e9c9f54f.min.js"></script><script id="__lang" type="application/json">{"clipboard.copy": "Copy to clipboard", "clipboard.copied": "Copied to clipboard", "search.config.lang": "en", "search.config.pipeline": "trimmer, stopWordFilter", "search.config.separator": "[\\s\\-]+", "search.placeholder": "Search", "search.result.placeholder": "Type to start searching", "search.result.none": "No matching documents", "search.result.one": "1 matching document", "search.result.other": "# matching documents", "search.result.more.one": "1 more on this page", "search.result.more.other": "# more on this page", "search.result.term.missing": "Missing"}</script>
      
      <script>
        app = initialize({
          base: ".",
          features: [],
          search: Object.assign({
            worker: "assets/javascripts/worker/search.9c0e82ba.min.js"
          }, typeof search !== "undefined" && search)
        })
      </script>
      
    
  </body>
</html>