path: root/2024/01/23/G-Machine/index.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">

    <meta name="author" content="韩暮秋">
    
        
            <meta name="subtitle" content="暮秋小屋">
            
                
                    <meta name="description" content="这里是暮秋小屋，思念和灵感的寄存处">
                    
                        
                            <meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan">
                            

                                

                                    <title>
                                        
                                            G-Machine | 
                                                    暮秋小屋
                                    </title>

                                    
                                        
                                            <link rel="icon" href="/favicon.ico">
                                            

                                                <style>
                                                    @font-face {
                                                        font-family: CarroisSong;
                                                        src: url('/fonts/CarroisSong.ttf');
                                                    }
                                                </style>

                                                
                                                    
                                                        <!-- stylesheets list from _config.yml -->
                                                        
                                                            <link rel="stylesheet" href="/css/style.css">
                                                            
                                                                

                                                                    
                                                                        
                                                                            <!-- scripts list from _config.yml -->
                                                                            
                                                                                <script
                                                                                    src="/js/menu.js"></script>
                                                                                
                                                                                    

                                                                                        
                                                                                            
                                                                                                <script
                                                                                                    src="https://polyfill.alicdn.com/polyfill.js?features=es6"></script>
                                                                                                <script
                                                                                                    id="MathJax-script"
                                                                                                    async
                                                                                                    src="https://lf6-cdn-tos.bytecdntp.com/cdn/expire-1-M/mathjax/3.2.0/es5/tex-mml-chtml.js"></script>
                                                                                                

                                                                                                    
                                                                                                        
  <meta name="generator" content="Hexo 6.3.0"></head>
  <body>
    <div class="mask-border">
    </div>

    <div class="wrapper">

      <div class="header">
  <div class="flex-container">
    <div class="header-inner">
      <div class="site-brand-container">
        <a href="/">
          
              暮秋小屋
                
        </a>
      </div>
      <div id="menu-btn" class="menu-btn" onclick="toggleMenu()">
        Menu
      </div>
      <nav class="site-nav">
        <ul class="menu-list">
          
            
                <li class="menu-item">
                  <a href="/">
                    主页
                  </a>
                </li>
                
                  
            
                <li class="menu-item">
                  <a href="/categories/gallery/">
                    日记本
                  </a>
                </li>
                
                  
            
                <li class="menu-item">
                  <a href="/tags/Medicine/">
                    医学
                  </a>
                </li>
                
                  
            
                <li class="menu-item">
                  <a href="/tags/Technique/">
                    计算机/互联网
                  </a>
                </li>
                
                  
            
                <li class="menu-item">
                  <a href="/tags/Life/">
                    生活
                  </a>
                </li>
                
                  
            
                <li class="menu-item">
                  <a href="/archives">
                    全部
                  </a>
                </li>
                
                  
            
                <li class="menu-item">
                  <a href="/about">
                    关于
                  </a>
                </li>
                
                  
                    
                      <li class="menu-item search-btn">
                        <a href="#">Search</a>
                      </li>
                      
        </ul>
      </nav>
    </div>
  </div>
</div>

      <div class="main">
        <div class="flex-container">
          <article id="post">

  
    <div class="post-head">
    <div class="post-info">
        <div class="tag-list">
            
                
                    <span class="post-tag">
                        <a href="/tags/Technique/">
                            Technique
                        </a>
                    </span>    
                           
            
        </div>
        <div class="post-title">
            
            
                G-Machine
            
            
        </div>
        <span class="post-date">
            Jan 23, 2024
        </span>
    </div>
    <div class="post-img">
        
            <div class="h-line-primary"></div>
              
    </div>
</div>
    <div class="post-content">
    <ul>
<li><a target="_blank" rel="noopener" href="https://link.springer.com/chapter/10.1007/3-540-15975-4_50">The G-machine: A fast, graph-reduction evaluator</a></li>
</ul>
<p>G-Machine 是一种通过图规约来对函数式语言程序求值的抽象架构。<br>与组合子规约不同，组合子规约的control是从表达式图本身动态导出的，而G-Machine是由通过编译Application表达式导出的指令序列指定的。</p>
<hr>
<p>FP的程序基本上都可以用一个表达式的图表示，图计算机就是对这个图求值的机器，总的说来对图的求值是一个不停合并图上的节点生产新节点的过程。</p>
<p>例如：</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> x = <span class="number">2</span> + <span class="number">3</span> <span class="keyword">in</span> </span><br><span class="line">  x * x</span><br></pre></td></tr></table></figure>

<p>先计算出5，然后创建一个新的节点 <code>5 * 5</code>，然后再对这个节点求值，于是求值过程中就产生了很多临时的节点，这些中间节点也被叫做是 spine，求值过程是沿着 spine 进行的。</p>
<p>但是这样就产生了很多额外的开销，lambda lifting 里提到：可以把程序里，很多捕捉了外围绑定的闭包函数中的这些绑定，转换成函数的参数，从而消除闭包，得到的这个函数就可以自由脱离作用域，被静态的编译到机器码里。这些被 float out 的函数也叫 supercombinator.</p>
<p>在上面的代码中，如果不创建新的节点，顺序计算完了第一个 <code>x</code>，第二个 <code>x</code> 还会再被算一遍。</p>
<p>Spineless reduction 的概念：只有当面临需要重复计算的情况时，才去创建节点，不然就一路顺序算下去</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Graph_reduction">Graph reduction</a></li>
<li><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Graph_reduction_machine">Graph reduction machine</a></li>
<li><a target="_blank" rel="noopener" href="https://www.zhihu.com/question/54834531/answer/144213668">https://www.zhihu.com/question/54834531/answer/144213668</a></li>
</ul>

</div> 

<script>
    window.onload = detectors();
</script>
    <div class="post-footer">
    <div class="h-line-primary"></div>
    <nav class="post-nav">
        <div class="prev-item">
           
                <div class="icon arrow-left"></div>
                <div class="post-link">
                    <a href="/2024/01/25/%E6%80%A5%E8%AF%8A%E4%B8%8E%E7%81%BE%E9%9A%BE%E5%8C%BB%E5%AD%A6-%E7%83%A7%E4%BC%A4/">Prev</a>
                </div>
            
        </div>
        <div class="next-item">
            
                <div class="icon arrow-right"></div>
                <div class="post-link">
                  <a href="/2024/01/23/%E6%85%A2%E6%80%A7%E8%82%BA%E6%BA%90%E6%80%A7%E5%BF%83%E8%84%8F%E7%97%85/">Next</a>  
                </div>  
            
        </div>
    </nav>
</div>

    
      <div class="post-comment">

     

     
    
    

</div>
     
  
</article>
        </div>
      </div>
      
      <div class="footer">
    <div class="flex-container">
        <div class="footer-text">
            
            
                韩暮秋 | 
            
            
                希望路过的人可以添点柴火让这里暖和点
                
        </div>
    </div>
</div>

    </div>

    
      <div class="search-popup">
    <div class="search-popup-overlay">  
    </div>
    <div class="search-popup-window" >
        <div class="search-header">
            <div class="search-input-container">
              <input autocomplete="off" autocapitalize="off" maxlength="80"
                     placeholder="Search Anything" spellcheck="false"
                     type="search" class="search-input">
            </div>
            <div class="search-close-btn">
                <div class="icon close-btn"></div>
            </div>
        </div>
        <div class="search-result-container">
        </div>
    </div>
</div>

<script>
    const searchConfig = {
        path             : "/search.xml",
        top_n_per_article: "1",
        unescape         : "false",
        trigger: "auto",
        preload: "false"
    }
</script>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script>
<script src="/js/search.js"></script>
    
    

  </body>
</html>