给 Idris 写 JS 后端
MauHerrick
7年前
<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>