recursion - 在Golang中为递归函数实现生成器( yield )的惯用方式

Question

[注意:我读了Python-style generators in Go，这不是它的重复。 ]

在Python/Ruby/JavaScript/ECMAScript 6中，可以使用该语言提供的yield关键字来编写生成器函数。在Go中，可以使用goroutine和 channel 对其进行仿真。

代码

以下代码显示了如何实现排列函数(abcd，abdc，acbd，acdb，...，dcba):

// $src/lib/lib.go

package lib

// private, starts with lowercase "p"
func permutateWithChannel(channel chan<- []string, strings, prefix []string) {
    length := len(strings)
    if length == 0 {
        // Base case
        channel <- prefix
        return
    }
    // Recursive case
    newStrings := make([]string, 0, length-1)
    for i, s := range strings {
        // Remove strings[i] and assign the result to newStringI
        // Append strings[i] to newPrefixI
        // Call the recursive case
        newStringsI := append(newStrings, strings[:i]...)
        newStringsI = append(newStringsI, strings[i+1:]...)
        newPrefixI := append(prefix, s)
        permutateWithChannel(channel, newStringsI, newPrefixI)
    }
}

// public, starts with uppercase "P"
func PermutateWithChannel(strings []string) chan []string {
    channel := make(chan []string)
    prefix := make([]string, 0, len(strings))
    go func() {
        permutateWithChannel(channel, strings, prefix)
        close(channel)
    }()
    return channel
}

使用方法如下:

// $src/main.go

package main

import (
    "./lib"
    "fmt"
)

var (
    fruits  = []string{"apple", "banana", "cherry", "durian"}
    banned = "durian"
)

func main() {
    channel := lib.PermutateWithChannel(fruits)
    for myFruits := range channel {
        fmt.Println(myFruits)
        if myFruits[0] == banned {
            close(channel)
            //break
        }
    }
}

笔记:

不需要 break语句(上面有注释)，因为 close(channel)会使 range在下一次迭代中返回 false，因此循环将终止。

问题

如果调用方不需要所有排列，则需要显式地对该 channel 进行 close()编码，否则直到程序终止(发生资源泄漏)后， channel 才会关闭。另一方面，如果调用者需要所有排列(即 range循环直到结束)，则调用者务必不 close()该 channel 。这是因为对已经关闭的 channel 进行 close()调用会导致运行时出现紧急情况(请参阅 here in the spec)。但是，如果确定是否应该停止的逻辑并非如上所示那么简单，我认为最好使用 defer close(channel)。

问题

实现这种生成器的惯用方式是什么？

通常，谁应该负责close() channel -库函数还是调用者？

像下面这样修改我的代码是个好主意，以便无论如何调用者都负责defer close() channel ？

在库中，修改以下内容:

    go func() {
        permutateWithChannel(channel, strings, prefix)
        close(channel)
    }()

对此:

    go permutateWithChannel(channel, strings, prefix)

在调用方中，对此进行修改:

func main() {
    channel := lib.PermutateWithChannel(fruits)
    for myFruits := range channel {
        fmt.Println(myFruits)
        if myFruits[0] == banned {
            close(channel)
        }
    }
}

对此:

func main() {
    channel := lib.PermutateWithChannel(fruits)
    defer close(channel)    // <- Added
    for myFruits := range channel {
        fmt.Println(myFruits)
        if myFruits[0] == banned {
            break           // <- Changed
        }
    }
}

尽管通过执行上面的代码无法观察到，并且算法的正确性也没有受到影响，但在调用方close()成为 channel 之后，运行库代码的goroutine在尝试将其发送到下一个封闭 channel 时应为panic如here in the spec所述，导致其终止。这会产生负面影响吗？

库函数的签名为func(strings []string) chan []string。理想情况下，返回类型应为<-chan []string以将其限制为仅接收。但是，如果调用方负责close() channel ，则无法将其标记为“仅接收”，因为close()内置函数不适用于仅接收 channel 。处理这个的惯用方式是什么？

Answer 1

I.替代

前言:我将使用一个更简单的生成器，因为问题不涉及生成器的复杂性，而是生成器与使用者之间的信号以及使用者本身的调用。这个简单的生成器只生成从0到9的整数。

1.具有功能值

通过使用简单的消费者函数，生成消费者模式更加简洁，这还具有以下优点:如果需要中止或任何其他操作，它可以返回一个值信号。

并且由于在该示例中仅信号通知了一个事件(“中止”)，所以使用者函数将具有bool返回类型，用于指示是否需要中止。

因此，请参见将消费者函数值传递到生成器的简单示例:

func generate(process func(x int) bool) {
    for i := 0; i < 10; i++ {
        if process(i) {
            break
        }
    }
}

func main() {
    process := func(x int) bool {
        fmt.Println("Processing", x)
        return x == 3 // Terminate if x == 3
    }
    generate(process)
}

输出(在 Go Playground上尝试):

Processing 0
Processing 1
Processing 2
Processing 3

请注意，使用者( process)不必是“本地”函数，可以在 main()之外声明它，例如它可以是全局函数，也可以是其他包中的函数。

该解决方案的潜在缺点是，它仅使用1个goroutine来生成和使用值。

2.有 channel

如果您仍想使用 channel 来做，可以。请注意，由于 channel 是由生成器创建的，并且由于使用者遍历从 channel 接收的值(理想情况下是使用 for ... range构造)，因此关闭 channel 是生成器的责任。对此进行解决还可以使您返回仅接收 channel 。

是的，最好以延迟语句的方式关闭生成器中返回的 channel ，因此，即使生成器出现紧急情况，也不会阻止使用者。但是请注意，此延迟关闭不是在 generate()函数中，而是在从 generate()开始并作为新的goroutine执行的匿名函数中；否则，该 channel 在从 generate()返回之前将被关闭-完全没有用...

而且，如果您要向使用者发出信号给生成器(例如中止而不生成进一步的值)，则可以使用例如另一个 channel ，该 channel 传递到生成器。由于生成器只会“监听”该 channel ，因此也可以将其声明为生成器的仅接收 channel 。如果您只需要发信号通知一个事件(在本例中为中止)，而无需在该 channel 上发送任何值，则只需执行简单的关闭操作即可。如果您需要发信号通知多个事件，则可以通过在该 channel 上实际发送一个要执行的事件/操作的值来完成(其中中止可能是多个事件之一)。

您可以使用 select statement作为惯用方式来处理在返回的 channel 上发送值并查看传递给生成器的 channel 。

这是一个带有 abort channel 的解决方案:

func generate(abort <-chan struct{}) <-chan int {
    ch := make(chan int)
    go func() {
        defer close(ch)
        for i := 0; i < 10; i++ {
            select {
            case ch <- i:
                fmt.Println("Sent", i)
            case <-abort: // receive on closed channel can proceed immediately
                fmt.Println("Aborting")
                return
            }
        }
    }()
    return ch
}

func main() {
    abort := make(chan struct{})
    ch := generate(abort)
    for v := range ch {
        fmt.Println("Processing", v)
        if v == 3 { // Terminate if v == 3
            close(abort)
            break
        }
    }
    // Sleep to prevent termination so we see if other goroutine panics
    time.Sleep(time.Second)
}

输出(在 Go Playground上尝试):

Sent 0
Processing 0
Processing 1
Sent 1
Sent 2
Processing 2
Processing 3
Sent 3
Aborting

该解决方案的明显优势在于，它已经使用了2个goroutine(1个生成值，1个使用/处理它们)，并且很容易扩展它以使用任意数量的goroutines作为返回的 channel 来处理生成的值。生成器可以同时从多个goroutine中使用-通过设计可以安全地并发接收 channel ，设计不会发生数据争用；更多信息: If I am using channels properly should I need to use mutexes?

二。未解决问题的答案

对goroutine的“未捕获” panic 将终止goroutine的执行，但不会引起资源泄漏方面的问题。但是，如果在非紧急情况下作为单独的goroutine执行的函数将释放由其分配的资源(在非延迟语句中)，则该代码显然将无法运行，并且会导致资源泄漏。

您尚未观察到此情况，因为该程序在主goroutine终止时终止(并且它不等待其他非主goroutine完成-因此您的其他goroutine没有机会惊慌)。参见 Spec: Program execution。

但是请知道 panic()和 recover()是用于特殊情况的，它们不适用于Java中的Exceptions和 try-catch块等一般用例。例如，应通过返回错误(并处理错误!)来避免 panic ，并且 panic 绝对不应离开软件包的“边界”(例如 panic()和 recover()可能被证明在软件包实现中使用是合理的，但 panic 状态应为“捕获”在包装内，而不是从包装中放出)。