手寫編程語(yǔ)言-遞歸函數(shù)是如何實(shí)現(xiàn)的?
前言
本篇文章主要是記錄一下在 GScript 中實(shí)現(xiàn)遞歸調(diào)用時(shí)所遇到的坑,類似的問(wèn)題在中文互聯(lián)網(wǎng)上我?guī)缀鯖](méi)有找到相關(guān)的內(nèi)容,所以還是很有必要記錄一下。
在開(kāi)始之前還是簡(jiǎn)單介紹下本次更新的 GScript v0.0.9 所包含的內(nèi)容:
- 支持可變參數(shù)
- 優(yōu)化append 函數(shù)語(yǔ)義
- 優(yōu)化編譯錯(cuò)誤信息
- 最后一個(gè)就是支持遞歸調(diào)用
先看第一個(gè)可變參數(shù):
printf(string format, any ...a){}
string sprintf(string format, any ...a){}
以上是隨著本次更新新增的兩個(gè)標(biāo)準(zhǔn)函數(shù),均支持可變參數(shù),其中使用 ... 表示可變參數(shù),調(diào)用時(shí)如下:
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");
與大部分語(yǔ)言類似,可變參數(shù)本質(zhì)上就是一個(gè)數(shù)組,所以可以拿來(lái)循環(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ǔ)義,本次優(yōu)化來(lái)自于 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 之后不需要再重新賦值,也會(huì)追加數(shù)據(jù),優(yōu)化后這里看起來(lái)是一個(gè)值/引用傳遞的問(wèn)題,但其實(shí)底層也是值傳遞,只是在語(yǔ)法上增加了這樣的語(yǔ)法糖,幫使用者重新做了一次賦值。
之后是新增了編譯錯(cuò)誤信息提示,比如下面這段代碼:
a+2;
b+c;
使用沒(méi)有聲明的變量,現(xiàn)在會(huì)直接編譯失?。?/p>
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ù)聲明之類的語(yǔ)法錯(cuò)誤也有相關(guān)提示。
最后一個(gè)才是本次討論的重點(diǎn),也就是遞歸函數(shù)的支持。
int num(int x,int y){
if (y==1 || y ==x) {
return 1;
}
int v1 = num(x - 1, y - 1);
return c;
}
再上一個(gè)版本中 int v1 = num(x - 1, y - 1); 這行代碼是不會(huì)執(zhí)行的,具體原因后文會(huì)分析。
現(xiàn)在利用遞歸便可以實(shí)現(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)在我們來(lái)看看這樣的代碼為什么執(zhí)行完 return 1 之后就不會(huì)執(zhí)行后邊的語(yǔ)句了。
其實(shí)在此之前我首先解決的時(shí)候函數(shù) return 后不能執(zhí)行后續(xù) statement 的需求,其實(shí)正好就是上文提到的邏輯,只是這里是遞歸而已。
先把代碼簡(jiǎn)化一下方便分析:
int f1(int a){
if (a==10){
return 10;
}
println("abc");
}
當(dāng)參數(shù) a 等于 10 的時(shí)候確實(shí)不能執(zhí)行后續(xù)的打印語(yǔ)句了,那么如何實(shí)現(xiàn)該需求呢?
以正常人類的思考方式:當(dāng)我們執(zhí)行完 return 語(yǔ)句的時(shí)候,就應(yīng)該標(biāo)記該語(yǔ)句所屬的函數(shù)直接返回,不能在執(zhí)行后續(xù)的 statement。
可是這應(yīng)該如何實(shí)操呢?
其實(shí)看看 AST 就能明白了:
當(dāng)碰到 return 語(yǔ)句的時(shí),會(huì)遞歸向上遍歷語(yǔ)法樹(shù),標(biāo)記上所有 block 節(jié)點(diǎn)表明這個(gè) block 后續(xù)的語(yǔ)句不再執(zhí)行了,同時(shí)還得把返回值記錄下來(lái)。
這樣當(dāng)執(zhí)行到下一個(gè) statement 時(shí),也就是 println("abc"); 則會(huì)判斷他所屬的 block 是否有被標(biāo)記,如果有則直接返回,這樣便實(shí)現(xiàn)了 return 語(yǔ)句不執(zhí)行后續(xù)代碼。
部分實(shí)現(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。
遞歸的問(wèn)題
但同時(shí)問(wèn)題也來(lái)了,就是遞歸的時(shí)候也不會(huì)執(zhí)行后續(xù)的遞歸代碼了。
其實(shí)解決問(wèn)題的方法也很簡(jiǎn)單,就是在判斷是否需要直接返回那里新增一個(gè)條件,這個(gè) block 中不存在遞歸調(diào)用。
所以我們就得先知道這個(gè) block 中是否存在遞歸調(diào)用。
整個(gè)過(guò)程有以下幾步:
- 編譯期:在函數(shù)聲明處記錄下函數(shù)與當(dāng)前context 的映射關(guān)系。
- 編譯期:掃描statement 時(shí),取出該 statement 的 context 所對(duì)應(yīng)的函數(shù)。
- 編譯期:掃描到的statement 如果是一個(gè)函數(shù)調(diào)用,則判斷該函數(shù)是否為該 block 中的函數(shù),也就是第二步取出的函數(shù)。
- 編譯期:如果兩個(gè)函數(shù)相等,則將當(dāng)前block 標(biāo)記為遞歸調(diào)用。
- 運(yùn)行期:在剛才判斷return 語(yǔ)句處,額外多出判斷當(dāng)前 block 是否為遞歸調(diào)用,如果是則不能返回。
部分代碼如下:
https://github.com/crossoverJie/gscript/blob/3e179f27cb30ca5c3af57b3fbf2e46075baa266b/resolver/ref_resolver.go#L70。
總結(jié)
這里的遞歸調(diào)用其實(shí)卡了我挺長(zhǎng)時(shí)間的,思路是有的,但是寫出來(lái)的代碼總是和預(yù)期不符,當(dāng)天晚上坐在電腦面前到凌晨?jī)扇c(diǎn),百思不得其解。
最后受不了上床休息的時(shí)候,突然一個(gè)靈光乍現(xiàn)讓我想到了解決方案,于是第二天起了個(gè)早床趕忙實(shí)踐,還真給解決了。
所以有些時(shí)候碰到棘手問(wèn)題時(shí)給自己放松一下,往往會(huì)有出其不意的效果。
最后是目前的遞歸在某些情況下性能還有些問(wèn)題,后續(xù)會(huì)盡量將這些標(biāo)記過(guò)程都放在編譯期,編譯慢點(diǎn)沒(méi)事,但運(yùn)行時(shí)慢那就有問(wèn)題了。
之后還會(huì)繼續(xù)優(yōu)化運(yùn)行時(shí)的異常,目前是直接 ??panic?
?,堆棧也沒(méi)有,體感非常不好;歡迎感興趣的朋友試用反饋bug。