Function in Go

函数声明包含函数名，参数（形参，parameter），返回值，函数体。

func name(parameter-list) (result-list) {
    body
}

func add(x int, y int) int { return x + y }
func sub(x, y int) (z int) { z = x - y; return }
func first(x int, _ int) int { return x }
func zero(int, int) int { return 0 } // what

参数（形参）列表指定参数的名称和类型。
若函数没有返回值，或者返回值是只有一个且未指定变量名，返回值的括号通常会省略不写。
返回值也可以指定变量名，此变量是函数内的局部变量并被初始化为该类型的零值。
函数若有返回值，必须以 return 语句结尾，除非函数的执行明显无法执行到函数的结尾（例如函数以调用 panic 或是无限循环结束）。
存在多个相同类型的形参或返回值，类型可以只写一次（factored）。
空白标识符 _ 用于强调参数未被使用。

函数的类型也称为函数的签名（signature）。两个函数的形参列表类型、返回值列表类型都相同（个数，类型，顺序），就认为这两个函数的类型（签名）相同。形参和返回值的变量名称对函数类型没有影响，类型 factored 的写法也没有影响。

调用函数时必须按照形参列表中指定的顺序传入参数。Go 没有参数默认值的概念，也不能指定实参的名称，所以形参和返回值的名称对函数的调用者没有影响。

形参是函数调用者提供的实参（argument）在函数内部的局部变量。函数形参和指定名称的返回值与函数体内最外层的局部变量处于相同的词法作用域（lexical block）。

实参是按值传递的，形参实际上是实参的一个副本，所以对值类型的形参的修改不会影响到实参。但若实参是引用类型，如指针、切片、map、函数、通道，函数内部对形参间接指向的变量的修改也会反映到函数的外部。

函数的声明若不包含函数体，表示该函数是由 Go 以外的语言实现的，这样的声明只定义函数的签名。

package math
func Sin(x float64) float64 // implemented in assembly language

函数可以返回多个返回值。
多个返回值的函数调用结果可以直接作为接收多个参数的函数的实参（生产代码中很少用到；调试时可以用一条语句就打印出函数调用返回的所有结果）。

links, err := findLinks(url)
links, _ := findLinks(url) // errors ignored

log.Println(findLinks(url))
links, err := findLinks(url)
log.Println(links, err)

若函数的返回值指定了名称，则 return 语句的操作数（operand）可以省略。这样的写法称为 bare return，它是一种简写，可以减少代码量，但不易读，要谨慎使用。

递归

递归指函数直接或间接地调用自己。

func main() { // 将输入的 html node 中包含的 url 提取出来
    doc, err := html.Parse(os.Stdin)
    if err != nil {
        fmt.Fprintf(os.Stderr, "findlinks1: %v\n", err)
        os.Exit(1)
    }
    for _, link := range visit(nil, doc) {
        fmt.Println(link)
    }
}
func visit(links []string, n *html.Node) []string {
    if n.Type == html.ElementNode && n.Data == "a" {
        for _, a := range n.Attr {
            if a.Key == "href" {
                links = append(links, a.Val) // 相对路径
            }
        }
    }
    for c := n.FirstChild; c != nil; c = c.NextSibling { // 遍历子节点
        links = visit(links, c)
    }
    return links
}
// curl https://hofungkoeng.com | go run main.go

// /
// /
// /post/
// /categories/
// /tags/
// /about/
// ...

func main() { // 打印输入的 html node 树的轮廓（outline）
    doc, err := html.Parse(os.Stdin)
    if err != nil {
        fmt.Fprintf(os.Stderr, "outline: %v\n", err)
        os.Exit(1)
    }
    outline(nil, doc)
}
func outline(stack []string, n *html.Node) {
    if n.Type == html.ElementNode {
        stack = append(stack, n.Data) // push tag
        fmt.Println(stack)
    }
    // outline 的递归过程中，被调用者接收到 stack 的副本作为参数，它可以追加元素（可能会触发分配一个新的底层数组），但追加操作不会改变它的调用者“看到的”初始的那些元素。
    // 假如分配了一个新的数组，形参和实参指向的就不再是同一个底层数组了，所以实参不会受到影响。所以被调用者返回后，调用者看到的 stack 还是和调用之前一样的。
    for c := n.FirstChild; c != nil; c = c.NextSibling {
        outline(stack, c)
    }
}
// curl https://hofungkoeng.com | go run main.go

// [html]
// [html head]
// [html head meta]
// [html head title]
// [html head link]
// [html body]
// [html body div]

许多编程语言的实现使用固定大小的函数调用栈，通常在 64KB 到 2MB 之间。固定大小的栈限制了递归的深度，递归遍历巨大的数据结构时可能会栈溢出。固定大小的栈还可能存在安全风险。

通常 Go 的实现使用的是可变大小的栈，可以按需增长到 GB 的量级，使得我们可以安全地使用递归，也不需要担心栈溢出。

错误

Go 认为返回错误是预料之中的行为，不像很多其它语言将错误当作异常（exceptions）处理。Go 虽然也有类似的异常处理机制，但它仅被用来报告预料之外的错误，也就是程序的 bug，而不是健壮的程序也会出现的日常错误。

这样设计的原因是异常机制常常会使对错误的描述与处理该错误的控制流纠缠在一起，导致的结果是日常的错误以一堆不可理解的、反映程序结构的堆栈踪迹（stack trace）的形式汇报给终端用户，却缺少可以反映程序究竟哪里出错的明了的上下文。

Go 使用普通的控制流，如 if，return，来响应错误。这种风格需要将更多的精力放在错误处理逻辑上，这也正是目的之所在。

按照惯例，错误通常作为最后一个返回值返回。只可能有一个原因的错误的类型是 boolean，通常命名为 ok。其它情况通常返回 error 类型（接口类型）的错误，nil 表示操作成功，非 nil 表示操作失败。

当函数返回的是非 nil 的错误，其它返回的结果通常应该忽略，但也存在一些例外情况，如 Read 读文件操作。

错误处理策略：

传递（propagate）错误，子任务中的错误成为调用者的错误。
- 可以用 fmt.Errorf 格式化错误添加必要的描述信息。
- 当错误最终被 main 函数处理时，应该提供一条串联问题的根源和最终的整体错误信息的清晰的因果关系链条。
- 错误信息通常会链式串联起来，因此错误信息的字符串不要大写、不要使用换行。
  - genesis: crashed: no parachute: G-switch failed: bad relay orientation
- 错误信息应该审慎地设计，要包含足够的描述问题的有意义的信息。错误信息要保持一致，以便用相同的方式统一处理。
- 总体来说，f(x) 负责报告 f 操作和参数 x 部分的错误信息，f(x) 的调用者负责添加 f(x) 没有的信息。
对于瞬时的或者出乎预料的错误，可以对失败的操作进行重试。

func WaitForServer(url string) error {
    const timeout = 1 * time.Minute
    deadline := time.Now().Add(timeout)
    for tries := 0; time.Now().Before(deadline); tries++ {
        _, err := http.Head(url)
        if err == nil {
            return nil // success
        }
        log.Printf("server not responding (%s); retrying...", err)
        time.Sleep(time.Second << uint(tries)) // exponential back-off
    }
    return fmt.Errorf("server %s failed to respond after %s", url, timeout)
}

终止程序。

若程序无法继续运行，调用者可以选择打印错误信息并优雅地结束程序。
通常这种操作只应该由程序的 main 包来执行，通常库函数应该将错误传递给它的调用者，除非发生的错误是 bug。

// (In function main.)
if err := WaitForServer(url); err != nil {
    fmt.Fprintf(os.Stderr, "Site is down: %v\n", err)
    os.Exit(1)
}
if err := WaitForServer(url); err != nil {
    log.Fatalf("Site is down: %v\n", err)
}

打印日志并继续执行。
直接无视错误。
- 记录下有意无视错误的意图。

在 Go 中，检查错误后，通常先写处理错误的逻辑，再写没有错误的逻辑。如果错误导致函数返回，处理成功情况的逻辑不写在 else 中，而是直接写在 if-else 控制流的外层，减少函数实质性功能代码的缩进。

io 包保证由 end-of-file 引起的读错误返回的报错是 io.EOF，可以通过 err == io.EOF 探测此错误。

package io
import "errors"
// EOF is the error returned by Read when no more input is available.
var EOF = errors.New("EOF")

由于错误的原因无需多言，end-of-file 的错误信息是固定的 “EOF”。

函数变量（function values）

Go 中的函数是第一类值（first-class values）。和其它类型一样，函数变量有类型，可以被赋值给变量、作为参数传递给函数、作为函数的返回值。

函数类型可以像其它函数一样被调用。

func square(n int) int { return n * n }
func product(m, n int) int { return m * n }
f := square
fmt.Println(f(3)) // "9"
fmt.Printf("%T\n", f) // "func(int) int"
f = product // compile error: can't assign f(int, int) int to f(int) int

函数类型的零值是 nil，调用 nil 函数会 panic。

var f func(int) int
f(3) // panic: call of nil function

函数变量可以和 nil 比较，但函数变量之间不能比较，因此不能用作 map 的键。

var f func(int) int
if f != nil {
    f(3)
}

我们可以将数据作为参数传递进函数，有了函数变量，我们也可以将函数的行为参数化传入。

func add1(r rune) rune { return r + 1 } // 右移 1 个 rune
fmt.Println(strings.Map(add1, "HAL-9000")) // "IBM.:111"

var depth int // 打印的缩进层级
func main() {
	doc, err := html.Parse(os.Stdin)
	if err != nil {
		fmt.Fprintf(os.Stderr, "outline: %v\n", err)
	}
	forEachNode(doc, startElement, endElement)
}
func forEachNode(n *html.Node, pre, post func(n *html.Node)) {
    if pre != nil {
        pre(n) // 在节点的子元素被访问之前被调用
    }
    for c := n.FirstChild; c != nil; c = c.NextSibling {
        forEachNode(c, pre, post)
    }
    if post != nil {
        post(n) // 在节点的子元素被访问之后被调用
    }
}
func startElement(n *html.Node) {
    if n.Type == html.ElementNode {
        fmt.Printf("%*s<%s>\n", depth*2, "", n.Data)
        depth++
    }
}
func endElement(n *html.Node) {
    if n.Type == html.ElementNode {
        depth--
        fmt.Printf("%*s</%s>\n", depth*2, "", n.Data)
    }
}
// <html>
//   <head>
//     <meta>
//     </meta>
//     <title>
//     </title>
//     <style>
//     </style>
//   </head>
//   <body>
// ...

匿名函数

具名函数只能定义在包级别的范围。

在任意表达式中，可以用函数字面量来表示一个函数变量。

函数字面量和函数声明的区别是前者没有跟在 func 后面的函数名。

函数字面量是一个表达式，表达式的值称为匿名函数。

函数字面量使我们可以在要用到函数的当时即刻去定义。

strings.Map(func(r rune) rune { return r + 1 }, "HAL-9000")

更为重要的是，通过函数字面量定义的函数可以访问到它所处的整个词法环境，即内部函数可以引用到将它封闭的外部函数的变量（闭包），函数不再仅仅是代码，也可以包含状态。
Go 程序员通常将闭包作为函数变量的代称。

func squares() func() int {
    var x int
    return func() int { // return 后面的部分就是函数字面量
        x++
        return x * x
    }
}
func main() {
    f := squares()
    fmt.Println(f()) // "1"
    fmt.Println(f()) // "4"
}

局部变量 x 的存活期不由它所处的作用域决定，squares 返回后 x 仍然以隐藏在 f 中的形式存在。

闭包中暗藏的引用关系是将函数归类为引用类型的原因，也是函数变量不能比较的原因。

Depth-first Traversal

拓扑排序（有向图，非循环图，深度优先搜索，栈）：

var prereqs = map[string][]string{ // 键本身是节点，值是键指向的节点
    "Algorithms": {"data structures"},
    "calculus": {"linear algebra"},
    "compilers": {
        "data structures",
        "formal languages",
        "computer organization",
    },
    "data structures": {"discrete math"},
    "databases": {"data structures"},
    "discrete math": {"intro to programming"},
    "formal languages": {"discrete math"},
    "networks": {"operating systems"},
    "operating systems": {"data structures", "computer organization"},
    "Programming Languages": {"data structures", "computer organization"},
}
func main() {
    for i, course := range topoSort(prereqs) {
        fmt.Printf("%d:\t%s\n", i+1, course)
    }
}
func topoSort(m map[string][]string) []string { // depth-first search
    var order []string
    seen := make(map[string]bool)
    var visitAll func(items []string)
    visitAll = func(items []string) {
        for _, item := range items {
            if !seen[item] {
                seen[item] = true
                visitAll(m[item])
                order = append(order, item) // 图能延伸的最远（深）节点先被追加到切片，接着次远的被追加，如此往复，此所谓深度优先
            }
        }
    }
    var keys []string
    for key := range m {
        keys = append(keys, key)
    }
    sort.Strings(keys)
    visitAll(keys)
    return order
}

当匿名函数需要使用递归时，必须先声明变量，再将匿名函数赋值给该变量。
如果两步并做一步写，函数字面量就不在变量 visitAll 的作用域中了，两者处于平行、平级的作用域，函数字面量内部访问不到 visitAll，所以无法递归调用。

visitAll := func(items []string) {
    // ...
    visitAll(m[item]) // compile error: undefined: visitAll
    // ...
}

Breadth-first Traversal

func main() { // 程序在所有可及的网页都爬过或者计算机内存耗尽后才结束
	breadthFirst(crawl, os.Args[1:])
}
func crawl(url string) []string { // 返回当前网页包含的所有 url
    fmt.Println(url)
	list, err := Extract(url)
	if err != nil {
		log.Print(err)
	}
	return list
}
func breadthFirst(f func(item string) []string, worklist []string) {
	seen := make(map[string]bool)
	for len(worklist) > 0 { // 广度优先，以层为单位从外层往内层遍历
		urls := worklist
		worklist = nil
		for _, url := range urls {
			if !seen[url] {
				seen[url] = true
				worklist = append(worklist, f(url)...) // f(url) 即 crawl(url)，将新爬到的页面的包含的 url 追加到 worklist，供外层 for 循环的下一轮调用
			}
		}
	}
}
func Extract(url string) ([]string, error) { // 返回当前 url 的网页包含的所有 url
	resp, err := http.Get(url)
	if err != nil {
		return nil, err
	}
	if resp.StatusCode != http.StatusOK {
		resp.Body.Close()
		return nil, fmt.Errorf("getting %s: %s", url, resp.Status)
	}
	doc, err := html.Parse(resp.Body)
	resp.Body.Close()
	if err != nil {
		return nil, fmt.Errorf("parsing %s as HTML: %v", url, err)
	}
	var links []string
	visitNode := func(n *html.Node) { // 解析当前 html 元素（tag），若是 <a> 则记录 href 的值（即 url）
		if n.Type == html.ElementNode && n.Data == "a" {
			for _, a := range n.Attr {
				if a.Key != "href" {
					continue
				}
				link, err := resp.Request.URL.Parse(a.Val) // 获取绝对 url
				if err != nil {
					continue // ignore bad URLs
				}
				links = append(links, link.String()) // closure
			}
		}
	}
	forEachNode(doc, visitNode)
	return links, nil
}
func forEachNode(n *html.Node, visitNode func(n *html.Node)) { // 深度优先
	visitNode(n)
	for c := n.FirstChild; c != nil; c = c.NextSibling {
		forEachNode(c, visitNode)
	}
}

References

https://www.youtube.com/watch?v=bIA8HEEUxZI

Contents

递归

错误

函数变量（function values）

匿名函数

Depth-first Traversal

Breadth-first Traversal