给 Idris 写 JS 后端

在默认状况下，Idris 编译器会使用 C 后端生成 Native binary（我还给它的 RTS 上过代码……）。然后 EB 写了一个 JS 后端，只是这个后端写的实在不敢恭维：它内嵌了一个堆栈式的虚拟机，然后使用 Tracing 的方式解释字节码。虽然和 C 版行为最一致，但性能和「可理解性」方面都远远不如其他的 Functional-to-js 编译器，像下面这段：module Mai

Joker_Ye

1354人浏览 · 2017-04-27 09:15:06

Joker_Ye · 2017-04-27 09:15:06 发布

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

使用官方后端的话 testProg 相关的部分会变成这个德行（Idris 因为是全程序编译的，所以 JS 里面还带有 Prelude 的部分）：

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]);
}

对比下@张宏波每天广告的 Bucklescript

// 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;

这是何等的差距……

不过好在，Idris 在设计的时候就考虑了对接多种后端，而且也确实有很多人在做后端的工作，那么，如果官方后端不够好的话，自己写一个不就行了么……（当然了，认为官方后端烂的不只我一个，没有必要真的从头去写。）

项目在这： idris-codegen-js ，分化自上游的 rbarreiro/idrisjs 。 idris-codegen-js 的目标就是打造一个高效和易于理解的 JS backend。

Idris 的编译流程

OK 说正经的吧，Idris 的编译流程大体如下图：

上图右侧的三个部分，LoadSource 的部分为 Idris 本身的前端。在这个步骤中，Idris 使用一种类似 Coq 中执行 LTac 的方式将「上位」的 .idr 源码上图右侧的三个部分，LoadSource 的部分为 Idris 本身的前端。在这个步骤中，Idris 使用一种类似 Coq 中执行 LTac 的方式将「上位」的 .idr 源码繁饰（Elaboration）成一个下位的语言 TT

繁饰完成的 TT 会被写入相应的 .ibc 文件，同时也被 Idris REPL 使用。

而第二个部分，Compile，则是从 TT 开始一步一步地进行一系列语法变换，最终交给 Codegen 生成目标文件。这个步骤是在一个单独的进程中运行的，程序名 idris-codegen-#.exe，由 Idris 主程序调用，输入一组 .ibc，输出一个目标文件。给 Idris 写后端实际上就是写一个新的「idris-codegen-#.exe」，放在 idris 主程序相同目录下，然后就可以用了……

因此，如果你愿意的话完全可以想办法自己读 .ibc 文件，自己变换自己输出，可惜 ibc 不仅是二进制文件而且格式也没文档，这种想法也就真的是想想而已了。

更加务实的手段是复用 Idris 的架构，也即上图中的若干框里的表示，这些中间表示位于 IRTS 下的若干模块中：

TT，这个是类型信息最完整的，但是较为复杂，而且还用了 HOAS 之类的高端特性，拿来做类型检查很合适，给后端用就未必了。
LDecl，这个是 TT 编译后的结果，一种类似 UTLC 的语言，但所有的函数调用都只会调用变量，但 Arity 可能不匹配，即可能产生闭包，也可能调用传入的参数。
DDecl，这个是在 LDecl 的基础上进行 Defunctinalize，通过显式构造数据结构消除闭包构造的产物。到了这一步，所有的函数调用不仅只调用顶层声明，还抱着 Arity 严格匹配。
SDecl 则在 DDecl 上进一步简化，所有的嵌套函数调用都被提出成 let 的形式。
字节码，这个没有在 IRTS.CodegenCommon.CodegenInfo 中直接给出，需要自己生成，官方的 C 后端就使用了字节码。

TT、LDecl、DDecl、SDecl 到字节码可以看作一个函数式语言一步一步走向机器底层的路程。在 LDecl、DDecl、SDecl、字节码这四者中，LDecl 和各种脚本语言的模式最为相似；DDecl 的模型则接近于 C；SDecl 接近一些 SSA IR；字节码就不用说了。在写后端的时候可以使用其中任意一种作为处理。

考虑到现在是 target 到 JavaScript，属于一个带有原生闭包支持的脚本语言，因此使用 LDecl 对应的 Lang 层进行最为合适，不过我们会做一些优化，比如 uncurry 干掉嵌套函数之类。

Lang 层的结构

Lang 层的模块名是 IRTS.Lang，其核心部分是 LExp 和 LDecl，定义如下：

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

LExp 大体上就是一个支持闭包的脚本语言的样子，LDecl 则包含「函数」声明以及构造器声明两类（Name 是 Idris TT 层的类型，表示各种各样的名称，十分复杂）。不过你别看 LExp 分支那么多，实际上在 Lang 层的 Lambda lifting 之后，LLam 不会给你拿到，真正能出现的组合只有以下这么几类：

(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)

即使配合上 TCO（LApp 第一个字段就是是否为 tail call），一个 backend 也就大约 1000 行 Haskell 的篇幅，当然如果你把优化全去掉的话会更短，不过生成出来的 JS 会更慢就是了。

去 Curry 化

Idris 和其他一票函数式语言一样都是默认 Curry 化的，想要消除的话需要记录顶层声明的 Arity，然后在编译 LApp 的时候比对 args 的长度：

如果两者相等，很好，生成一个简单的 JS 函数调用，返回即可；
如果声明的 arity 比传入的大，那么就需要刷一个 lambda，同时进行 curry；
如果声明的 arity 小于传入的，那么在「正常」的调用之后，生成一系列的 JS 调用，每次一个参数。

IRTS 从 L 层到 D 层的实现也与之相似。

对象的表示

由于 Idris 大量使用 datatype，对于 LCon 可以做一个有趣的优化：如果某个构造是 0 元的，就不去刷出一个新对象出来，而是直接返回 tag 的数值，减少构造和解构的开销。

事实上，如果不考虑 LProj 的话，可以再这里做更多的 specialize，比如把 Idris 的 List 映射到 JS 的数组等等，不过最简单的 specialize 就是把 Idris 的 Bool 映射成 JS 的 Boolean，实现非常简单：查询出 constructor declaration 之后，如果它是 True 或者 False，改掉实现即可。

目前 idris-codegen-js 使用 {type:tag,$1:arg1,$2:arg2,...} 生成 Idris 的对象，以后则会迁移到对每个构造器生成特化的类来实现。

结果

使用现在的 idris-codegen-js 编译和上文同一段 Idris 结果是这样：

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))
})()

可以看出几点：

Idris 的编译器有内联的能力，同时会尽力消除重载函数的 dict passing 开销，这点比 purescript 强太多……
testProg 被内联了，连定义都不再导出。testProg 里的 loop 被提出同时改成了两个参数，lmt 也被提出，成为了函数。
常数 range 也被内联了。
Type term 和 Proof term 都在 LDecl 前消除，成为 null。

对 idris-codegen-js 感兴趣的可以去这儿拉源码编译、上 PR 等等。JS Binding 可以去上游 rbarreiro/idrisjs 获取

感谢@Canto Ostinato 帮忙配 stack。

————————————————————————————————————————

附录：

Purescript 等效代码

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

Purescript 生成结果

"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
};

Elm 等效代码

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

Elm 输出 JS

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);
};