給 Idris 寫 JS 后端

MauHerrick 7年前發布 | 17K 次閱讀 JavaScript開發 JavaScript

在默認狀況下，Idris 編譯器會使用 C 后端生成 Native binary（我還給它的 RTS 上過代碼……）。然后 EB 寫了一個 JS 后端，只是這個后端寫的實在不敢恭維： 它內嵌了一個堆棧式的虛擬機，然后使用 Tracing 的方式解釋字節碼 。雖然和 C 版行為最一致，但性能和「可理解性」方面都遠遠不如其他的 Functional-to-js 編譯器，像下面這段：

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 源碼給 Idris 寫 JS 后端上圖右側的三個部分，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);
};

來自：https://zhuanlan.zhihu.com/p/26544417

本文由用戶 MauHerrick 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1493176048475.html

JavaScript開發 JavaScript

給 Idris 寫 JS 后端

Idris 的編譯流程

Lang 層的結構

去 Curry 化

對象的表示

結果

相關經驗

相關資訊

相關文檔

目錄