stratego.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>#stratego - 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="#17122020-peter-sovietov" 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">
            
              #stratego
            
          </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">
      <a href="all.html" class="md-nav__link">
        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 md-nav__item--active">
      
      <input class="md-nav__toggle md-toggle" data-md-toggle="toc" type="checkbox" id="__toc">
      
        
      <a href="stratego.html" class="md-nav__link md-nav__link--active">
        #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="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="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>
                
              
            </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="llvm.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>
                #llvm
              </div>
            </div>
          </a>
        
        
          <a href="linearscan.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>
                #linearscan
              </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>