手寫程式語言-遞迴函式是如何實現的?
前言
本篇文章主要是記錄一下在 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
時,取出該statement
的context
所對應的函式。 - 編譯期:掃描到的
statement
如果是一個函式呼叫,則判斷該函式是否為該block
中的函式,也就是第二步取出的函式。 - 編譯期:如果兩個函式相等,則將當前
block
標記為遞迴呼叫。 - 執行期:在剛才判斷
return
語句處,額外多出判斷當前block
是否為遞迴呼叫,如果是則不能返回。
部分程式碼如下:
總結
這裡的遞迴呼叫其實卡了我挺長時間的,思路是有的,但是寫出來的程式碼總是和預期不符,當天晚上坐在電腦面前到凌晨兩三點,百思不得其解。
最後受不了上床休息的時候,突然一個靈光乍現讓我想到了解決方案,於是第二天起了個早床趕忙實踐,還真給解決了。
所以有些時候碰到棘手問題時給自己放鬆一下,往往會有出其不意的效果。
最後是目前的遞迴在某些情況下效能還有些問題,後續會盡量將這些標記過程都放在編譯期,編譯慢點沒事,但執行時慢那就有問題了。
之後還會繼續優化執行時的異常,目前是直接 panic
,堆疊也沒有,體感非常不好;歡迎感興趣的朋友試用反饋bug。
原始碼地址:
http://github.com/crossoverJie/gscript
本文來源:手寫程式語言-遞迴函式是如何實現的?
- OceanBase榮獲OSCAR兩項大獎,開源已成主流開發模式
- linux根據inode編號刪除檔案
- 特約專訪 | 思否 CEO 高陽帶你瞭解 Code For Better _ Hackathon 冠軍團隊背後的故事
- Nest.js快速啟動API專案
- TiDB Hackathon 2022丨總獎金池超 35 萬!邀你喚醒程式碼世界的更多可能性!
- Go 為什麼能火?歸功於這 5 個方面
- JS 逆向百例】猿人學系列 web 比賽第五題:js 混淆 - 亂碼增強,詳細剖析
- 汪源:資料分析熱詞迭出,“三個統一”值得關注
- Go 為什麼能火?歸功於這 5 個方面
- Go 為什麼能火?歸功於這 5 個方面
- Go 為什麼能火?歸功於這 5 個方面
- Go 為什麼能火?歸功於這 5 個方面
- SpringBoot Vue Flowable,模擬一個請假審批流程!
- Go 為什麼能火?歸功於這 5 個方面
- 聊聊如何利用管道模式來進行業務編排(下篇)
- Golang 單例模式與sync.Once
- Golang 單例模式與sync.Once
- 如何通俗地理解「分散式系統」;Vue是否可以在一個專案中使用多個UI框架;大廠上線流程:先上前端還是後端|極客觀點
- 第二屆 1024 中國工程師文化日議程全覽,你不能錯過的 N 個理由
- 手寫程式語言-遞迴函式是如何實現的?