前言

本篇文章次要是记录一下在 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 的倡议：
https://github.com/crossoverJie/gscript/issues/12

// Beforeint[] a={1,2,3};println(a);println();a = append(a,4);println(a);// Output: [1 2 3 4]// Nowint[] 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: a2:0: undefined: b2: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)    }}

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

递归的问题

但同时问题也来了，就是递归的时候也不会执行后续的递归代码了。

其实解决问题的办法也很简略，就是在判断是否须要间接返回那里新增一个条件，这个 block 中不存在递归调用。

所以咱们就得先晓得这个 block 中是否存在递归调用。

整个过程有以下几步：

  • 编译期：在函数申明处记录下函数与以后 context 的映射关系。
  • 编译期：扫描 statement 时，取出该 statement 的 context 所对应的函数。
  • 编译期：扫描到的 statement 如果是一个函数调用，则判断该函数是否为该 block 中的函数，也就是第二步取出的函数。
  • 编译期：如果两个函数相等，则将以后 block 标记为递归调用。
  • 运行期：在方才判断 return 语句处，额定多出判断以后 block 是否为递归调用，如果是则不能返回。

局部代码如下：

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

总结

这里的递归调用其实卡了我挺长时间的，思路是有的，然而写进去的代码总是和预期不符，当天早晨坐在电脑背后到凌晨两三点，百思不得其解。

最初受不了上床劳动的时候，忽然一个灵光乍现让我想到了解决方案，于是第二天起了个早床赶紧实际，还真给解决了。

所以有些时候碰到辣手问题时给本人放松一下，往往会有出人意料的成果。

最初是目前的递归在某些状况下性能还有些问题，后续会尽量将这些标记过程都放在编译期，编译慢点没事，但运行时慢那就有问题了。

之后还会持续优化运行时的异样，目前是间接 panic，堆栈也没有，体感十分不好；欢送感兴趣的敌人试用反馈bug。

源码地址：

https://github.com/crossoverJie/gscript