前言

本篇文章主要是记载一下在 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){}

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

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 的建议:
github.com/crossoverJi…

// 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]

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

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

// 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)
}
}

源码地址:
github.com/crossoverJi…

递归的问题

但一起问题也来了,便是递归的时分也不会履行后续的递归代码了。

其实处理问题的办法也很简略,便是在判别是否需求直接回来那里新增一个条件,这个 block 中不存在递归调用。

所以我们就得先知道这个 block 中是否存在递归调用。

整个进程有以下几步:

  • 编译期:在函数声明处记载下函数与当时 context 的映射联系。
  • 编译期:扫描 statement 时,取出该 statementcontext 所对应的函数。
  • 编译期:扫描到的 statement 如果是一个函数调用,则判别该函数是否为该 block 中的函数,也便是第二步取出的函数。
  • 编译期:如果两个函数相等,则将当时 block 符号为递归调用。
  • 运行期:在方才判别 return 句子处,额定多出判别当时 block 是否为递归调用,如果是则不能回来。

部分代码如下:

github.com/crossoverJi…

总结

这儿的递归调用其实卡了我挺长时间的,思路是有的,但是写出来的代码总是和预期不符,当天晚上坐在电脑面前到清晨两三点,百思不得其解。

最终受不了上床歇息的时分,突然一个灵光乍现让我想到了处理方案,所以第二天起了个早床赶忙实践,还真给处理了。

所以有些时分碰到棘手问题时给自己放松一下,往往会有出其不意的效果。

最终是现在的递归在某些情况下功能还有些问题,后续会尽量将这些符号进程都放在编译期,编译慢点没事,但运行时慢那就有问题了。

之后还会继续优化运行时的反常,现在是直接 panic,仓库也没有,体感十分不好;欢迎感兴趣的朋友试用反馈bug。

源码地址:

github.com/crossoverJi…

本文来源:手写编程语言-递归函数是如何完成的?