• KusonStack一站式可编程配置技术栈(Go): https://github.com/KusionStack/kusion
• KCL 配置编程语言(Rust): https://github.com/KusionStack/KCLVM
• 凹语言™: https://github.com/wa-lang/wa

6.2 递归调用µGo函数

本节将实现递归调用µGo函数，需要解决函数类型的解析、函数参数的Scope和代码生成等问题。

6.2.1 完善函数的类型

完善ast包的函数节点，添加类型信息：

// 函数信息
type Func struct {
	...
	Type    *FuncType
	...
}

函数的类型主要由函数参数和返回值类型组成：

// 函数类型
type FuncType struct {
	Func   token.Pos
	Params *FieldList
	Result *Ident
}

参数数一个参数名和类型对组成的列表，返回值只有一个表示类型的名字。

参数列表定义如下：

// 参数/属性 列表
type FieldList struct {
	Opening token.Pos
	List    []*Field
	Closing token.Pos
}

// 参数/属性
type Field struct {
	Name *Ident // 名称
	Type *Ident // 类型
}

uGo不支持Go语言中多个参数共用一个类型的写法，名字和类型时一一对应的，用Field表示。

6.2.2 完善函数类型的解析包

在前面章节中，uGo实现的main函数没有参数和返回值，现在增加函数类型解析。改造parser包的Parser.parseFunc解析方法：

func (p *Parser) parseFunc() *ast.Func {
	tokFunc := p.MustAcceptToken(token.FUNC)
	tokFuncIdent := p.MustAcceptToken(token.IDENT)

	fn := &ast.Func{
		FuncPos: tokFunc.Pos,
		NamePos: tokFuncIdent.Pos,
		Name:    tokFuncIdent.Literal,
		Type: &ast.FuncType{
			Params: &ast.FieldList{},
		},
	}
	...
}

先构造函数节点对象，然后解析函数参数：

func (p *Parser) parseFunc() *ast.Func {
	...
	// parsr params
	p.MustAcceptToken(token.LPAREN) // (
	for {
		// )
		if _, ok := p.AcceptToken(token.RPAREN); ok {
			break
		}

		// arg type, ...
		tokArg := p.MustAcceptToken(token.IDENT)
		tokTyp := p.MustAcceptToken(token.IDENT)

		fn.Type.Params.List = append(fn.Type.Params.List, &ast.Field{
			Name: &ast.Ident{
				NamePos: tokArg.Pos,
				Name:    tokArg.Literal,
			},
			Type: &ast.Ident{
				NamePos: tokTyp.Pos,
				Name:    tokTyp.Literal,
			},
		})
	}
	...
}

然后解析可选的返回值类型：

func (p *Parser) parseFunc() *ast.Func {
	...
	// result type
	if _, ok := p.AcceptToken(token.LBRACE, token.SEMICOLON); ok {
		p.UnreadToken()
	} else {
		tok := p.MustAcceptToken(token.IDENT)
		fn.Type.Result = &ast.Ident{
			NamePos: tok.Pos,
			Name:    tok.Literal,
		}
	}
	...
}

最后是函数Body部分：

func (p *Parser) parseFunc() *ast.Func {
	...

	// body: {}
	if _, ok := p.AcceptToken(token.LBRACE); ok {
		p.UnreadToken()
		fn.Body = p.parseStmt_block()
	}

	return fn
}

这样就完成了函数类型的解析，读者可以自行通过ugo ast a.ugo命令测试。

6.2.3 完善函数后端代码

要实现递归函数调用，需要提前将函数的名字添加到Scope中。改造compiler包的Compiler.compileFile方法，将函数注册到当前文件对应的scope：

func (p *Compiler) compileFile(w io.Writer, file *ast.File) {
	...
	// global vars
	for _, g := range file.Globals {
		...
	}

	// global funcs
	for _, fn := range file.Funcs {
		var mangledName = fmt.Sprintf("@ugo_%s_%s", file.Pkg.Name, fn.Name)
		p.scope.Insert(&Object{
			Name:        fn.Name,
			MangledName: mangledName,
			Node:        fn,
		})
	}
	...
}

函数的注册过程和全局变量类似。

然后是改造Compiler.compileFunc函数，增加对函数参数的支持：

func (p *Compiler) compileFunc(w io.Writer, file *ast.File, fn *ast.Func) {
	...

	// args
	var argNameList []string
	for _, arg := range fn.Type.Params.List {
		var mangledName = fmt.Sprintf("%%local_%s.pos.%d", arg.Name.Name, arg.Name.NamePos)
		argNameList = append(argNameList, mangledName)
	}
	...

	// fn body
	func() {
		// args+body scope
		defer p.restoreScope(p.scope)
		p.enterScope()

		// args
		for i, arg := range fn.Type.Params.List {
			var argRegName = fmt.Sprintf("%s.arg%d", argNameList[i], i)
			var mangledName = argNameList[i]
			p.scope.Insert(&Object{
				Name:        arg.Name.Name,
				MangledName: mangledName,
				Node:        fn,
			})

			fmt.Fprintf(w, "\t%s = alloca i32, align 4\n", mangledName)
			fmt.Fprintf(
				w, "\tstore i32 %s, i32* %s\n",
				argRegName, mangledName,
			)
		}

		// body
		for _, x := range fn.Body.List {
			p.compileStmt(w, x)
		}
	}()
	...
}

新代码将函数的翻译封装到一个闭包函数中，这样做的原因是函数参数的名字空间和函数Body共享，因此需要特别处理。另外需要注意的是LLVM-IR的函数参数类似一个只读的虚拟寄存器，并不是alloc指令分配的可取地址的内存空间。我们需要将函数参数映射为alloc指令分配的空间，这样才可以统一函数参数和局部变量的操作。

6.2.4 构造测试

现在构造一个递归版本的斐波那契：

package main

func main() {
	for i := 0; i < 20; i = i + 1 {
		if n := fib(i); n <= 100 {
			println(n)
		}
	}
}

func fib(n int) int {
	if n >= 2 {
		return fib(n-1) + fib(n-2)
	}
	return 1
}

执行以下命令测试：

$ go run main.go -debug run ./_examples/fib2.ugo
1
1
2
3
5
8
13
21
34
55
89

结果正常。