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

Question

[注意:我在Go中阅读了Python风格的生成器,这不是它的重复.]

在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的下一个迭代,循环将终止.

问题

如果调用者不需要所有排列,则它需要close()显式地通道,或者在程序终止之前不会关闭通道(发生资源泄漏).另一方面,如果调用者需要所有排列(即range循环直到结束),则调用者不得使用close()该通道.这是因为 - close()已经关闭的通道会导致运行时混乱(请参阅规范中的此处).但是,如果确定是否应该停止的逻辑并不像上面所示那么简单,我认为最好使用它defer close(channel).

问题

1. 实现这样的生成器的惯用方法是什么？
2. 通俗地说,谁应该close()对频道负责- 图书馆功能还是来电者？
3. 如下所示修改我的代码是一个好主意,这样defer close()无论如何调用者都对通道负责？

在库中,修改:

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

4. 尽管通过执行上面的代码无法观察到,并且算法的正确性不受影响,但在调用者close()的通道之后,运行库代码的goroutine应该panic在下一次迭代中尝试发送到关闭的通道时,如记录在这里的规范,导致其终止.这会导致任何负面副作用吗？
5. 库函数的签名是func(strings []string) chan []string.理想情况下,返回类型应该是将<-chan []string其限制为仅接收.但是,如果呼叫者close()对频道负责,则不能将其标记为"仅接收",因为close()内置功能不适用于仅接收频道.解决这个问题的惯用方法是什么？

Answer 1

I.替代方案

前言:我将使用更简单的发电机,因为问题不涉及发电机的复杂性,而是发电机和消费者之间的信号,以及消费者本身的呼叫.这个简单的生成器只生成0to 的整数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

请注意,consumer(process)不需要是"本地"函数,它可以在外部声明main(),例如它可以是全局函数或来自另一个包的函数.

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

2.有渠道

如果您仍想使用频道,则可以.请注意,由于通道是由生成器创建的,并且由于消费者循环接收从通道接收的值(理想情况下是通过for ... range构造),因此关闭通道是生成器的责任.使用此功能也可以返回仅接收频道.

是的,关闭生成器中返回的通道最好作为延迟语句完成,因此即使生成器发生混乱,消费者也不会被阻止.但请注意,这个延迟关闭不在generate()函数中,而是在匿名函数中启动generate()并作为新的goroutine执行; 否则通道将在返回之前关闭generate()- 完全没用...

如果您想要从消费者发信号通知发生器(例如,中止而不生成其他值),您可以使用另一个通道,该通道将传递给生成器.由于生成器只会"监听"此通道,因此它也可以声明为生成器的仅接收通道.如果您只需要发出一个事件的信号(在我们的情况下中止),则不需要在此通道上发送任何值,只需关闭即可.如果您需要发出多个事件的信号,可以通过在此通道上实际发送一个值来完成,即要执行的事件/操作(中止可能是多个事件中的一个).

您可以使用该select语句作为惯用方法来处理返回通道上的发送值并观察传递给生成器的通道.

这是一个有abort渠道的解决方案:

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作为返回的通道发生器可以同时从多个goroutine使用 - 通道可以安全地同时接收,数据竞争不会发生,设计; 更多阅读:如果我正确使用频道,我是否需要使用互斥锁？

II.未解决问题的答案

对goroutine的"未捕获"恐慌将结束goroutine的执行,但不会导致资源泄漏问题.但是如果作为单独的goroutine执行的函数在非恐慌的情况下释放由它分配的资源(在非延迟语句中),那么该代码显然不会运行并且例如会导致资源泄漏.

您没有观察到这一点,因为程序在主goroutine终止时终止(并且它不等待其他非主要goroutine完成 - 因此您的其他goroutines没有机会恐慌).请参阅规范:程序执行.

但是要知道panic()并且recover()出于例外情况,它们不适用于诸如try-catchJava中的异常和块之类的一般用例.应该避免恐慌,例如,通过返回错误(并处理它们!),恐慌绝对不应该离开包的"边界"(例如panic(),recover()可能有理由在包实现中使用,但恐慌状态应该被"抓住" "在包装内部,不要让它出来).

Answer 2

在我看来，生成器通常只是内部封闭的包装器。像这样

package main

import "fmt"

// This function `generator` returns another function, which
// we define anonymously in the body of `generator`. The
// returned function _closes over_ the variable `data` to
// form a closure.
func generator(data int, permutation func(int) int, bound int) func() (int, bool) {
    return func() (int, bool) {
        data = permutation(data)
        return data, data < bound
    }
}

// permutation function
func increment(j int) int {
    j += 1
    return j
}

func main() {
    // We call `generator`, assigning the result (a function)
    // to `next`. This function value captures its
    // own `data` value, which will be updated each time
    // we call `next`.
    next := generator(1, increment, 7)
    // See the effect of the closure by calling `next`
    // a few times.
    fmt.Println(next())
    fmt.Println(next())
    fmt.Println(next())
    // To confirm that the state is unique to that
    // particular function, create and test a new one.
    for next, generation, ok := generator(11, increment, 17), 0, true; ok; {
        generation, ok = next()
        fmt.Println(generation)
    }
}

它看起来不像“ for range”那么优雅，但对我而言在语义和语法上都非常清楚。它适用于http://play.golang.org/p/fz8xs0RYz9