前言

本篇文章主要是記錄一下在 GScript 中實現(xiàn)遞歸調(diào)用時所遇到的坑，類似的問題在中文互聯(lián)網(wǎng)上我?guī)缀鯖]有找到相關(guān)的內(nèi)容，所以還是很有必要記錄一下。

在開始之前還是簡單介紹下本次更新的 GScript v0.0.9 所包含的內(nèi)容：

• 支持可變參數(shù)
• 優(yōu)化append 函數(shù)語義
• 優(yōu)化編譯錯誤信息
• 最后一個就是支持遞歸調(diào)用

先看第一個可變參數(shù)：

printf(string format, any ...a){}
string sprintf(string format, any ...a){}

以上是隨著本次更新新增的兩個標(biāo)準(zhǔn)函數(shù)，均支持可變參數(shù)，其中使用 ... 表示可變參數(shù)，調(diào)用時如下：

printf("hello %s ","123");
printf("hello-%s-%s ","123","abc");
printf("hello-%s-%d ","123",123);
string format = "this is %s ";
printf(format, "gscript");
string s = sprintf("nice to meet %s", "you");
assertEqual(s,"nice to meet you");

與大部分語言類似，可變參數(shù)本質(zhì)上就是一個數(shù)組，所以可以拿來循環(huán)遍歷：

int add(string s, int ...num){
 println(s);
 int sum = 0;
 for(int i=0;i<len(num);i++){
  int v = num[i];
  sum = sum+v;
 }
 return sum;
}
int x = add("abc", 1,2,3,4);
println(x);
assertEqual(x, 10);

append(any[] a, any v){}

之后是優(yōu)化了內(nèi)置函數(shù) append() 的語義，本次優(yōu)化來自于 issue12 的建議：https://github.com/crossoverJie/gscript/issues/12。

int[] a={1,2,3};
println(a);
println();
a = append(a,4);
println(a);
int[] a={1,2,3};
println(a);
println();
append(a,4);
int b = a[3];
assertEqual(4, b);
println(a);

現(xiàn)在 append 之后不需要再重新賦值，也會追加數(shù)據(jù)，優(yōu)化后這里看起來是一個值/引用傳遞的問題，但其實底層也是值傳遞，只是在語法上增加了這樣的語法糖，幫使用者重新做了一次賦值。

之后是新增了編譯錯誤信息提示，比如下面這段代碼：

a+2;
b+c;

使用沒有聲明的變量，現(xiàn)在會直接編譯失敗：

1:0: undefined: a
2:0: undefined: b
2:2: undefined: c

class T{}
class T{}
2:0: class T redeclared in this block

重復(fù)聲明之類的語法錯誤也有相關(guān)提示。

最后一個才是本次討論的重點，也就是遞歸函數(shù)的支持。

int num(int x,int y){
 if (y==1 || y ==x) {
  return 1;
 }
 int v1 = num(x - 1, y - 1);
 return c;
}

再上一個版本中 int v1 = num(x - 1, y - 1); 這行代碼是不會執(zhí)行的，具體原因后文會分析。

現(xiàn)在利用遞歸便可以實現(xiàn)類似于打印楊輝三角之類的程序了：

int num(int x,int y){
 if (y==1 || y ==x) {
  return 1;
 }
    int v1 = num(x - 1, y - 1);
    int v2 = num(x - 1, y);
 int c = v1+v2;   
 return c;
}
printTriangle(int row){
 for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= row - i; j++) {
           print(" ");
        }
        for (int j = 1; j <= i; j++) {
            print(num(i, j) + " ");
        }
        println("");
    }
}
printTriangle(7);
      1 
     1 1 
    1 2 1 
   1 3 3 1 
  1 4 6 4 1 
 1 5 10 10 5 1 
1 6 15 20 15 6 1

函數(shù)中的 return

int num(int x,int y){
 if (y==1 || y ==x) {
  return 1;
 }
 int v1 = num(x - 1, y - 1);
 return c;
}

現(xiàn)在我們來看看這樣的代碼為什么執(zhí)行完 return 1 之后就不會執(zhí)行后邊的語句了。

其實在此之前我首先解決的時候函數(shù) return 后不能執(zhí)行后續(xù) statement 的需求，其實正好就是上文提到的邏輯，只是這里是遞歸而已。

先把代碼簡化一下方便分析：

int f1(int a){
 if (a==10){
  return 10;
 }
 println("abc");
}

當(dāng)參數(shù) a 等于 10 的時候確實不能執(zhí)行后續(xù)的打印語句了，那么如何實現(xiàn)該需求呢？

以正常人類的思考方式：當(dāng)我們執(zhí)行完 return 語句的時候，就應(yīng)該標(biāo)記該語句所屬的函數(shù)直接返回，不能在執(zhí)行后續(xù)的 statement。

可是這應(yīng)該如何實操呢？

其實看看 AST 就能明白了：

當(dāng)碰到 return 語句的時，會遞歸向上遍歷語法樹，標(biāo)記上所有 block 節(jié)點表明這個 block 后續(xù)的語句不再執(zhí)行了，同時還得把返回值記錄下來。

這樣當(dāng)執(zhí)行到下一個 statement 時，也就是 println("abc"); 則會判斷他所屬的 block 是否有被標(biāo)記，如果有則直接返回，這樣便實現(xiàn)了 return 語句不執(zhí)行后續(xù)代碼。

部分實現(xiàn)代碼如下：

func (v *Visitor) scanBlockStatementCtx(tree antlr.ParseTree, value interface{}) {
 context, ok := tree.(*parser.BlockContext)
 if ok {
  if v.blockCtx2Mark == nil {
   v.blockCtx2Mark = make(map[*parser.BlockContext]interface{})
  }
  v.blockCtx2Mark[context] = value
 }
 if tree.GetParent() != nil {
  v.scanBlockStatementCtx(tree.GetParent().(antlr.ParseTree), value)
 }
}

源碼地址：https://github.com/crossoverJie/gscript/blob/793d196244416574bd6be641534742e57c54db7a/visitor.go#L182。

遞歸的問題

但同時問題也來了，就是遞歸的時候也不會執(zhí)行后續(xù)的遞歸代碼了。

其實解決問題的方法也很簡單，就是在判斷是否需要直接返回那里新增一個條件，這個 block 中不存在遞歸調(diào)用。

所以我們就得先知道這個 block 中是否存在遞歸調(diào)用。

整個過程有以下幾步：

• 編譯期：在函數(shù)聲明處記錄下函數(shù)與當(dāng)前context 的映射關(guān)系。
• 編譯期：掃描statement 時，取出該 statement 的 context 所對應(yīng)的函數(shù)。
• 編譯期：掃描到的statement 如果是一個函數(shù)調(diào)用，則判斷該函數(shù)是否為該 block 中的函數(shù)，也就是第二步取出的函數(shù)。
• 編譯期：如果兩個函數(shù)相等，則將當(dāng)前block 標(biāo)記為遞歸調(diào)用。
• 運行期：在剛才判斷return 語句處，額外多出判斷當(dāng)前 block 是否為遞歸調(diào)用，如果是則不能返回。

部分代碼如下：

https://github.com/crossoverJie/gscript/blob/3e179f27cb30ca5c3af57b3fbf2e46075baa266b/resolver/ref_resolver.go#L70。

總結(jié)

這里的遞歸調(diào)用其實卡了我挺長時間的，思路是有的，但是寫出來的代碼總是和預(yù)期不符，當(dāng)天晚上坐在電腦面前到凌晨兩三點，百思不得其解。

最后受不了上床休息的時候，突然一個靈光乍現(xiàn)讓我想到了解決方案，于是第二天起了個早床趕忙實踐，還真給解決了。

所以有些時候碰到棘手問題時給自己放松一下，往往會有出其不意的效果。

最后是目前的遞歸在某些情況下性能還有些問題，后續(xù)會盡量將這些標(biāo)記過程都放在編譯期，編譯慢點沒事，但運行時慢那就有問題了。

之后還會繼續(xù)優(yōu)化運行時的異常，目前是直接 ??panic??，堆棧也沒有，體感非常不好；歡迎感興趣的朋友試用反饋bug。