<p>在默认状况下，Idris 编译器会使用 C 后端生成 Native binary（我还给它的 RTS 上过代码……）。然后 EB 写了一个 JS 后端，只是这个后端写的实在不敢恭维： <strong>它内嵌了一个堆栈式的虚拟机，然后使用 Tracing 的方式解释字节码</strong> 。虽然和 C 版行为最一致，但性能和「可理解性」方面都远远不如其他的 Functional-to-js 编译器，像下面这段：</p>    <pre>  <code class="language-javascript">module Main    range : Int  range = 1000    testProg : Int -> Int  testProg n = loop n  where   lmt : Int   lmt = min (n + 100) range     loop : Int -> Int   loop i = if i >= lmt then i else loop (i + 1)    main : IO()  main = printLn $ testProg 0</code></pre>    <p>使用官方后端的话 testProg 相关的部分会变成这个德行（Idris 因为是全程序编译的，所以 JS 里面还带有 Prelude 的部分）：</p>    <pre>  <code class="language-javascript">var _idris_Main_46_testProg_58_lmt_58_0 = function(oldbase){    var myoldbase = new i$POINTER();    i$valstack_top += 2;    i$valstack[i$valstack_base + 1] = 100;    i$valstack[i$valstack_base + 1] = i$valstack[i$valstack_base] + i$valstack[i$valstack_base + 1];    i$valstack[i$valstack_base + 2] = 1000;    i$valstack[i$valstack_top] = i$valstack[i$valstack_base + 1];    i$valstack[i$valstack_top + 1] = i$valstack[i$valstack_base + 2];    i$SLIDE(2);    i$valstack_top = i$valstack_base + 2;    i$CALL(_idris_Prelude_46_Interfaces_46_Prelude_46_Interfaces_46__64_Prelude_46_Interfaces_46_Ord_36_Int_58__33_min_58_0,[oldbase]);  }  var _idris_Main_46_testProg_58_loop_58_0$1 = function(oldbase,myoldbase){    i$valstack[i$valstack_base + 2] = i$ret;    switch(i$valstack[i$valstack_base + 2].tag){      case 0:        i$valstack[i$valstack_base + 3] = 1;        i$valstack[i$valstack_base + 3] = i$valstack[i$valstack_base + 1] + i$valstack[i$valstack_base + 3];        i$valstack[i$valstack_top] = i$valstack[i$valstack_base];        i$valstack[i$valstack_top + 1] = i$valstack[i$valstack_base + 3];        i$SLIDE(2);        i$valstack_top = i$valstack_base + 2;        i$CALL(_idris_Main_46_testProg_58_loop_58_0,[oldbase]);        break;      case 1:        i$ret = i$valstack[i$valstack_base + 1];        i$valstack_top = i$valstack_base;        i$valstack_base = oldbase.addr;        break;    };  }  var _idris_Main_46_testProg_58_loop_58_0$0 = function(oldbase,myoldbase){    i$valstack[i$valstack_base + 2] = i$ret;    i$valstack[i$valstack_top] = i$valstack[i$valstack_base + 1];    i$valstack[i$valstack_top + 1] = i$valstack[i$valstack_base + 2];    myoldbase.addr = i$valstack_base;    i$valstack_base = i$valstack_top;    i$valstack_top += 2;    i$CALL(_idris_Main_46_testProg_58_loop_58_0$1,[oldbase,myoldbase]);    i$CALL(_idris_Prelude_46_Interfaces_46_Prelude_46_Interfaces_46__64_Prelude_46_Interfaces_46_Ord_36_Int_58__33__62__61__58_0,[myoldbase]);  }  var _idris_Main_46_testProg_58_loop_58_0 = function(oldbase){    var myoldbase = new i$POINTER();    i$valstack_top += 2;    i$valstack[i$valstack_top] = i$valstack[i$valstack_base];    myoldbase.addr = i$valstack_base;    i$valstack_base = i$valstack_top;    i$valstack_top += 1;    i$CALL(_idris_Main_46_testProg_58_loop_58_0$0,[oldbase,myoldbase]);    i$CALL(_idris_Main_46_testProg_58_lmt_58_0,[myoldbase]);  }</code></pre>    <p>对比下@张宏波 每天广告的 Bucklescript</p>    <pre>  <code class="language-javascript">// Generated by BUCKLESCRIPT VERSION 1.2.1 , PLEASE EDIT WITH CARE  'use strict';    var Pervasives = require("stdlib/pervasives");    function testProg(n) {    var lmt = Pervasives.min(n + 100 | 0, 1000);    var _i = n;    while(true) {      var i = _i;      if (i >= lmt) {        return i;      }      else {        _i = i + 1 | 0;        continue ;              }    };  }    var range = 1000;    exports.range    = range;  exports.testProg = testProg;</code></pre>    <p>这是何等的差距……</p>    <p>不过好在，Idris 在设计的时候就考虑了对接多种后端，而且也确实有很多人在做后端的工作，那么，如果官方后端不够好的话，自己写一个不就行了么……（当然了，认为官方后端烂的不只我一个，没有必要真的从头去写。）</p>    <p>项目在这： <a href="/misc/goto?guid=4959748051724815635" rel="nofollow,noindex"> idris-codegen-js </a> ，分化自上游的 <a href="/misc/goto?guid=4959748051817110635" rel="nofollow,noindex"> rbarreiro/idrisjs </a> 。 <a href="/misc/goto?guid=4959748051724815635" rel="nofollow,noindex"> idris-codegen-js </a> 的目标就是打造一个高效和易于理解的 JS backend。</p>    <h2>Idris 的编译流程</h2>    <p>OK 说正经的吧，Idris 的编译流程大体如下图：</p>    <p> </p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/ee69f540d7ea91d27957ec70e21de9a6.png"></p>    <p>上图右侧的三个部分，LoadSource 的部分为 Idris 本身的前端。在这个步骤中，Idris 使用一种类似 Coq 中执行 LTac 的方式将「上位」的 .idr 源码 <img src="https://simg.open-open.com/show/84b2c84cfdc0d1ccc52aa648d6ea8edb.png" alt="给 Idris 写 JS 后端" width="550" height="926"> 上图右侧的三个部分，LoadSource 的部分为 Idris 本身的前端。在这个步骤中，Idris 使用一种类似 Coq 中执行 LTac 的方式将「上位」的 .idr 源码 <strong>繁饰</strong> （Elaboration）成一个下位的语言 TT</p>    <p>繁饰完成的 TT 会被写入相应的 .ibc 文件，同时也被 Idris REPL 使用。</p>    <p>而第二个部分，Compile，则是从 TT 开始一步一步地进行一系列语法变换，最终交给 Codegen 生成目标文件。这个步骤是在一个单独的进程中运行的，程序名 idris-codegen-#.exe，由 Idris 主程序调用，输入一组 .ibc，输出一个目标文件。给 Idris 写后端实际上就是写一个新的「idris-codegen-#.exe」，放在 idris 主程序相同目录下，然后就可以用了……</p>    <p>因此，如果你愿意的话完全可以想办法自己读 .ibc 文件，自己变换自己输出，可惜 ibc 不仅是二进制文件而且格式也没文档，这种想法也就真的是想想而已了。</p>    <p>更加务实的手段是复用 Idris 的架构，也即上图中的若干框里的表示，这些中间表示位于 IRTS 下的若干模块中：</p>    <ul>     <li>TT，这个是类型信息最完整的，但是较为复杂，而且还用了 HOAS 之类的高端特性，拿来做类型检查很合适，给后端用就未必了。</li>     <li>LDecl，这个是 TT 编译后的结果，一种类似 UTLC 的语言，但所有的函数调用都只会调用变量，但 Arity 可能不匹配，即可能产生闭包，也可能调用传入的参数。</li>     <li>DDecl，这个是在 LDecl 的基础上进行 Defunctinalize，通过显式构造数据结构消除闭包构造的产物。到了这一步，所有的函数调用不仅只调用顶层声明，还抱着 Arity 严格匹配。</li>     <li>SDecl 则在 DDecl 上进一步简化，所有的嵌套函数调用都被提出成 let 的形式。</li>     <li>字节码，这个没有在 IRTS.CodegenCommon.CodegenInfo 中直接给出，需要自己生成，官方的 C 后端就使用了字节码。</li>    </ul>    <p>TT、LDecl、DDecl、SDecl 到字节码可以看作一个函数式语言一步一步走向机器底层的路程。在 LDecl、DDecl、SDecl、字节码这四者中，LDecl 和各种脚本语言的模式最为相似；DDecl 的模型则接近于 C；SDecl 接近一些 SSA IR；字节码就不用说了。在写后端的时候可以使用其中任意一种作为处理。</p>    <p>考虑到现在是 target 到 JavaScript，属于一个带有原生闭包支持的脚本语言，因此使用 LDecl 对应的 Lang 层进行最为合适，不过我们会做一些优化，比如 uncurry 干掉嵌套函数之类。</p>    <h2>Lang 层的结构</h2>    <p>Lang 层的模块名是 IRTS.Lang，其核心部分是 LExp 和 LDecl，定义如下：</p>    <pre>  <code class="language-javascript">data LVar = Loc Int | Glob Name    deriving (Show, Eq)    data LExp = LV LVar            | LApp Bool LExp [LExp]    -- True = tail call            | LLazyApp Name [LExp]     -- True = tail call            | LLazyExp LExp            -- lifted out before compiling            | LForce LExp              -- make sure Exp is evaluted            | LLet Name LExp LExp      -- name just for pretty printing            | LLam [Name] LExp         -- lambda, lifted out before compiling            | LProj LExp Int           -- projection            | LCon (Maybe LVar)        -- Location to reallocate, if available                   Int Name [LExp]            | LCase CaseType LExp [LAlt]            | LConst Const            | LForeign FDesc           -- Function descriptor (usually name as string)                       FDesc           -- Return type descriptor                       [(FDesc, LExp)] -- first LExp is the FFI type description            | LOp PrimFn [LExp]            | LNothing            | LError String    deriving Eq    -- 中间省略 FFI 和 PrimFn 的部分    data LAlt' e = LConCase Int Name [Name] e               | LConstCase Const e               | LDefaultCase e    deriving (Show, Eq, Functor)    type LAlt = LAlt' LExp    data LDecl = LFun [LOpt] Name [Name] LExp -- options, name, arg names, def             | LConstructor Name Int Int    -- constructor name, tag, arity    deriving (Show, Eq)    type LDefs = Ctxt LDecl</code></pre>    <p>LExp 大体上就是一个支持闭包的脚本语言的样子，LDecl 则包含「函数」声明以及构造器声明两类（Name 是 Idris TT 层的类型，表示各种各样的名称，十分复杂）。不过你别看 LExp 分支那么多，实际上在 Lang 层的 Lambda lifting 之后，LLam 不会给你拿到，真正能出现的组合只有以下这么几类：</p>    <pre>  <code class="language-javascript">(LV (Glob n))  (LApp tc (LV (Glob n)) args)  (LLazyApp n args)  (LForce e)  (LLet n v sc)  (LCon loc i n args)  (LProj t i)  (LCase up e alts)  (LConst c)  (LForeign t n args)  (LOp f args)  LNothing  (LError e)</code></pre>    <p>即使配合上 TCO（LApp 第一个字段就是是否为 tail call），一个 backend 也就大约 1000 行 Haskell 的篇幅，当然如果你把优化全去掉的话会更短，不过生成出来的 JS 会更慢就是了。</p>    <h2>去 Curry 化</h2>    <p>Idris 和其他一票函数式语言一样都是默认 Curry 化的，想要消除的话需要记录顶层声明的 Arity，然后在编译 LApp 的时候比对 args 的长度：</p>    <ol>     <li>如果两者相等，很好，生成一个简单的 JS 函数调用，返回即可；</li>     <li>如果声明的 arity 比传入的大，那么就需要刷一个 lambda，同时进行 curry；</li>     <li>如果声明的 arity 小于传入的，那么在「正常」的调用之后，生成一系列的 JS 调用，每次一个参数。</li>    </ol>    <p>IRTS 从 L 层到 D 层的实现也与之相似。</p>    <h2>对象的表示</h2>    <p>由于 Idris 大量使用 datatype，对于 LCon 可以做一个有趣的优化：如果某个构造是 0 元的，就不去刷出一个新对象出来，而是直接返回 tag 的数值，减少构造和解构的开销。</p>    <p>事实上，如果不考虑 LProj 的话，可以再这里做更多的 specialize，比如把 Idris 的 List 映射到 JS 的数组等等，不过最简单的 specialize 就是把 Idris 的 Bool 映射成 JS 的 Boolean，实现非常简单：查询出 constructor declaration 之后，如果它是 True 或者 False，改掉实现即可。</p>    <p>目前 idris-codegen-js 使用 {type:tag,$1:arg1,$2:arg2,...} 生成 Idris 的对象，以后则会迁移到对每个构造器生成特化的类来实现。</p>    <h2>结果</h2>    <p>使用现在的 idris-codegen-js 编译和上文同一段 Idris 结果是这样：</p>    <pre>  <code class="language-javascript">function x_Main_46_testProg_58_lmt_58_0(_e$0){     return q_Prelude$Interfaces$$Prelude_46_Interfaces_46__64_Prelude_46_Interfaces_46_Ord_36_Int_58__33_min_58_0((_e$0 + 100), 1000)  }    function x_Main_46_testProg_58_loop_58_0(_e$0, _e$1){     for(;;) {        var cgIdris_2 = q_Prelude$Interfaces$$Prelude_46_Interfaces_46__64_Prelude_46_Interfaces_46_Ord_36_Int_58__33__62__61__58_0(_e$1, x_Main_46_testProg_58_lmt_58_0(_e$0));        if(( !cgIdris_2)) {           var cgIdris_3 = _e$0;           var cgIdris_4 = (_e$1 + 1);           _e$0 = cgIdris_3;           _e$1 = cgIdris_4;           continue        } else {           return _e$1        }        ;        break     }  }    var q_Main$$main = (function(){     return q_Prelude$Interactive$$putStr_39_(null, (q_Prelude$Show$$primNumShow(null, u_prim____toStrInt, 0, x_Main_46_testProg_58_loop_58_0(0, 0)) + "\n"))  })()    var _runMain$0 = (function(){     return js_idris_force(q_Main$$main(null))  })()</code></pre>    <p>可以看出几点：</p>    <ol>     <li>Idris 的编译器有内联的能力，同时会尽力消除重载函数的 dict passing 开销，这点比 purescript 强太多……</li>     <li>testProg 被内联了，连定义都不再导出。testProg 里的 loop 被提出同时改成了两个参数，lmt 也被提出，成为了函数。</li>     <li>常数 range 也被内联了。</li>     <li>Type term 和 Proof term 都在 LDecl 前消除，成为 null。</li>    </ol>    <p>对 idris-codegen-js 感兴趣的可以去这儿拉源码编译、上 PR 等等。JS Binding 可以去上游 rbarreiro/idrisjs 获取</p>    <p>感谢@Canto Ostinato 帮忙配 stack。</p>    <p>————————————————————————————————————————</p>    <p>附录：</p>    <p>Purescript 等效代码</p>    <pre>  <code class="language-javascript">module Main where  import Prelude  range = 1000    testProg n = -- do some work    let lmt = min (n + 100) range     in    let loop i =         if i >= lmt           then i          else loop (i + 1)     in    loop n</code></pre>    <p>Purescript 生成结果</p>    <pre>  <code class="language-javascript">"use strict";  var Prelude = require("../Prelude");  var Data_Ord = require("../Data.Ord");  var Data_Semiring = require("../Data.Semiring");  var range = 1000000000;  var testProg = function (n) {      var lmt = Data_Ord.min(Data_Ord.ordInt)(n + 100000000 | 0)(range);      var loop = function (__copy_i) {          var i = __copy_i;          tco: while (true) {              var $0 = i >= lmt;              if ($0) {                  return i;              };              if (!$0) {                  var __tco_i = i + 1 | 0;                  i = __tco_i;                  continue tco;              };              throw new Error("Failed pattern match at Main line 9, column 8 - line 11, column 26: " + [ $0.constructor.name ]);          };      };      return loop(n);  };  module.exports = {      range: range,       testProg: testProg  };</code></pre>    <p>Elm 等效代码</p>    <pre>  <code class="language-javascript">range : Int  range = 1000    testProg : Int -> Int  testProg n = -- do some work    let lmt = min (n + 100) range in    let loop i =      if i >= lmt then i else      loop (i + 1) in loop n</code></pre>    <p>Elm 输出 JS</p>    <pre>  <code class="language-javascript">var _user$project$Temp1482759649866537$range = 1000000000;  var _user$project$Temp1482759649866537$testProg = function (n) {   var lmt = A2(_elm_lang$core$Basics$min, n + 10000000000, _user$project$Temp1482759649866537$range);   var loop = function (i) {    loop:    while (true) {     if (_elm_lang$core$Native_Utils.cmp(i, lmt) > -1) {      return i;     } else {      var _v0 = i + 1;      i = _v0;      continue loop;     }    }   };   return loop(n);  };</code></pre>    <p> </p>    <p>来自：https://zhuanlan.zhihu.com/p/26544417</p>    <p> </p>