手寫程式語言-遞迴函式是如何實現的?

語言: CN / TW / HK

前言

本篇文章主要是記錄一下在 GScript 中實現遞迴呼叫時所遇到的坑,類似的問題在中文網際網路上我幾乎沒有找到相關的內容,所以還是很有必要記錄一下。

在開始之前還是簡單介紹下本次更新的 GScript v0.0.9 所包含的內容:

  • 支援可變引數
  • 優化 append 函式語義
  • 優化編譯錯誤資訊
  • 最後一個就是支援遞迴呼叫

先看第一個可變引數:

//formats according to a format specifier and writes to standard output.
printf(string format, any ...a){}

//formats according to a format specifier and returns the resulting string.
string sprintf(string format, any ...a){}

以上是隨著本次更新新增的兩個標準函式,均支援可變引數,其中使用 ... 表示可變引數,呼叫時如下:

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

與大部分語言類似,可變引數本質上就是一個數組,所以可以拿來迴圈遍歷:

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

// appends "v" to the end of a array "a"
append(any[] a, any v){}

之後是優化了內建函式 append() 的語義,本次優化來自於 issue12 的建議:
http://github.com/crossoverJie/gscript/issues/12

// Before
int[] a={1,2,3};
println(a);
println();
a = append(a,4);
println(a);
// Output: [1 2 3 4]

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

現在 append 之後不需要再重新賦值,也會追加資料,優化後這裡看起來是一個值/引用傳遞的問題,但其實底層也是值傳遞,只是在語法上增加了這樣的語法糖,幫使用者重新做了一次賦值。


之後是新增了編譯錯誤資訊提示,比如下面這段程式碼:

a+2;
b+c;

使用沒有宣告的變數,現在會直接編譯失敗:

1:0: undefined: a
2:0: undefined: b
2:2: undefined: c
class T{}
class T{}

// output:
2:0: class T redeclared in this block

重複宣告之類的語法錯誤也有相關提示。


最後一個才是本次討論的重點,也就是遞迴函式的支援。

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); 這行程式碼是不會執行的,具體原因後文會分析。

現在利用遞迴便可以實現類似於列印楊輝三角之類的程式了:

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;
    // int c = num(x - 1, y - 1)+num(x - 1, y);
    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);

// output:
      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 

函式中的 return

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

現在我們來看看這樣的程式碼為什麼執行完 return 1 之後就不會執行後邊的語句了。

其實在此之前我首先解決的時候函式 return 後不能執行後續 statement 的需求,其實正好就是上文提到的邏輯,只是這裡是遞迴而已。

先把程式碼簡化一下方便分析:

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

當引數 a 等於 10 的時候確實不能執行後續的列印語句了,那麼如何實現該需求呢?

以正常人類的思考方式:當我們執行完 return 語句的時候,就應該標記該語句所屬的函式直接返回,不能在執行後續的 statement

可是這應該如何實操呢?

其實看看 AST 就能明白了:

當碰到 return 語句的時,會遞歸向上遍歷語法樹,標記上所有 block 節點表明這個 block 後續的語句不再執行了,同時還得把返回值記錄下來。

這樣當執行到下一個 statement 時,也就是 println("abc"); 則會判斷他所屬的 block 是否有被標記,如果有則直接返回,這樣便實現了 return 語句不執行後續程式碼。

部分實現程式碼如下:

// 在 return 的時候遞歸向上掃描所有的 Block,並打上標記,用於後面執行 return 的時候直接返回。
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)
    }
}

原始碼地址:
http://github.com/crossoverJie/gscript/blob/793d196244416574bd6be641534742e57c54db7a/visitor.go#L182

遞迴的問題

但同時問題也來了,就是遞迴的時候也不會執行後續的遞迴程式碼了。

其實解決問題的方法也很簡單,就是在判斷是否需要直接返回那裡新增一個條件,這個 block 中不存在遞迴呼叫。

所以我們就得先知道這個 block 中是否存在遞迴呼叫。

整個過程有以下幾步:

  • 編譯期:在函式宣告處記錄下函式與當前 context 的對映關係。
  • 編譯期:掃描 statement 時,取出該 statementcontext 所對應的函式。
  • 編譯期:掃描到的 statement 如果是一個函式呼叫,則判斷該函式是否為該 block 中的函式,也就是第二步取出的函式。
  • 編譯期:如果兩個函式相等,則將當前 block 標記為遞迴呼叫。
  • 執行期:在剛才判斷 return 語句處,額外多出判斷當前 block 是否為遞迴呼叫,如果是則不能返回。

部分程式碼如下:

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

總結

這裡的遞迴呼叫其實卡了我挺長時間的,思路是有的,但是寫出來的程式碼總是和預期不符,當天晚上坐在電腦面前到凌晨兩三點,百思不得其解。

最後受不了上床休息的時候,突然一個靈光乍現讓我想到了解決方案,於是第二天起了個早床趕忙實踐,還真給解決了。

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

最後是目前的遞迴在某些情況下效能還有些問題,後續會盡量將這些標記過程都放在編譯期,編譯慢點沒事,但執行時慢那就有問題了。

之後還會繼續優化執行時的異常,目前是直接 panic,堆疊也沒有,體感非常不好;歡迎感興趣的朋友試用反饋bug。

原始碼地址:

http://github.com/crossoverJie/gscript

本文來源:手寫程式語言-遞迴函式是如何實現的?