Python 中的 SICP "streams as signals"

Question

我找到了一些在Python中实现类似sicp的流的很好的例子(这里，这里)。但我仍然不确定如何处理像SICP 3.5.3"流作为信号"中发现的integral这样的例子。

找到的Scheme代码是

(define (integral integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (add-streams (scale-stream integrand dt)
                              int)))
  int)

这个问题的棘手之处在于，返回的流int是根据自身定义的(即，流int在流int的定义中使用)。

我相信Python可以有类似的表达和简洁…但不知道怎么做。我的问题是，Python中类似的stream-y结构是什么?(我所说的流是SICP中3.5节的主题，但简单地说，是一种结构(类似于Python生成器)，它返回不确定长度序列的连续元素，并且可以与add-streams和scale-stream等操作组合和处理，这些操作尊重流的惰性特征。)

Answer 1

你的问题有两种解读方式。第一个问题很简单:如何使用流结构(可能是第二个链接中的结构)，但使用递归定义?这是可以做到的，尽管在Python中有点笨拙。

在Python中，你可以表示循环数据结构，但不能直接表示。你不能写:

l = [l]

但是你可以写:

l = [None]
l[0] = l

同样，你不能写:

def integral(integrand,initial_value,dt):
    int_rec = cons_stream(initial_value,
                          add_streams(scale_stream(integrand,dt),
                                      int_rec))
    return int_rec

但是你可以写:

def integral(integrand,initial_value,dt):
    placeholder = Stream(initial_value,lambda : None)
    int_rec = cons_stream(initial_value,
                          add_streams(scale_stream(integrand,dt),
                                      placeholder))
    placeholder._compute_rest = lambda:int_rec
    return int_rec

注意，我们需要笨拙地预先计算placeholder的第一个元素，然后只修复流其余部分的递归。但这一切都工作(与所有其他代码的适当定义一起-我将把它们都放在这个答案的底部)。

然而，你问题的第二部分似乎是在问如何在Python中自然地做到这一点。您要求"在Python中使用类似的流-y结构"。很明显，答案就是发电机。生成器自然地提供了流概念的延迟求值。它的不同之处在于没有自然地递归表达，但Python不像Scheme那样支持它，我们将看到。

换句话说，严格的流概念可以在Python中表示(如上面的链接)，但是惯用的方式是使用生成器。

通过将流直接机械地转换为生成器(但避免了内置的int)，或多或少可以复制Scheme示例:

def integral_rec(integrand,initial_value,dt):
    def int_rec():
        for x in cons_stream(initial_value,
                    add_streams(scale_stream(integrand,dt),int_rec())):
            yield x
    for x in int_rec():
        yield x
def cons_stream(a,b):
    yield a
    for x in b:
        yield x
def add_streams(a,b):
    while True:
        yield next(a) + next(b)
def scale_stream(a,b):
    for x in a:
        yield x * b

这里唯一棘手的事情是要意识到您需要急切地调用递归使用int_rec作为add_streams的参数。调用它并不会开始生成值——它只是创建了一个生成器，准备好在需要的时候惰性地生成这些值。

对于小的积分来说，这很好地工作，尽管它不是很python。Scheme版本通过优化尾部递归来工作——如果你的被积项太长，Python版本将超过最大堆栈深度。所以这在Python中并不合适。

一个直接和自然的python版本应该是这样的，我想:

def integral(integrand,initial_value,dt):
    value = initial_value
    yield value
    for x in integrand:
        value += dt * x
        yield value

这有效地工作并正确地将integrand惰性地视为"流"。然而，它使用迭代而不是递归来解包可集成可迭代对象，这更符合Python的方式。

在转向自然Python时，我也删除了流组合函数——例如，用+=代替add_streams。但是，如果我们想要一个折衷的版本，我们仍然可以使用它们:

def accum(initial_value,a):
    value = initial_value
    yield value
    for x in a:
        value += x
        yield value
def integral_hybrid(integrand,initial_value,dt):
    for x in accum(initial_value,scale_stream(integrand,dt)):
        yield x

这个混合版本使用Scheme中的流组合，只避免了尾部递归。这仍然是python的，python在itertools模块中包含了各种其他很好的方法来处理可迭代对象。它们都"尊重流的懒惰特征"。

最后，这里是第一个递归流示例的所有代码，其中大部分来自Berkeley参考:

class Stream(object):
        """A lazily computed recursive list."""
        def __init__(self, first, compute_rest, empty=False):
            self.first = first
            self._compute_rest = compute_rest
            self.empty = empty
            self._rest = None
            self._computed = False
        @property
        def rest(self):
            """Return the rest of the stream, computing it if necessary."""
            assert not self.empty, 'Empty streams have no rest.'
            if not self._computed:
                self._rest = self._compute_rest()
                self._computed = True
            return self._rest
        def __repr__(self):
            if self.empty:
                return '<empty stream>'
            return 'Stream({0}, <compute_rest>)'.format(repr(self.first))
Stream.empty = Stream(None, None, True)

def cons_stream(a,b):
    return Stream(a,lambda : b)
def add_streams(a,b):
    if a.empty or b.empty:
            return Stream.empty
    def compute_rest():
        return add_streams(a.rest,b.rest)
    return Stream(a.first+b.first,compute_rest)
def scale_stream(a,scale):
    if a.empty:
            return Stream.empty
    def compute_rest():
        return scale_stream(a.rest,scale)
    return Stream(a.first*scale,compute_rest)
def make_integer_stream(first=1):
      def compute_rest():
        return make_integer_stream(first+1)
      return Stream(first, compute_rest)
def truncate_stream(s, k):
        if s.empty or k == 0:
            return Stream.empty
        def compute_rest():
            return truncate_stream(s.rest, k-1)
        return Stream(s.first, compute_rest)
def stream_to_list(s):
        r = []
        while not s.empty:
            r.append(s.first)
            s = s.rest
        return r
def integral(integrand,initial_value,dt):
    placeholder = Stream(initial_value,lambda : None)
    int_rec = cons_stream(initial_value,
                          add_streams(scale_stream(integrand,dt),
                                      placeholder))
    placeholder._compute_rest = lambda:int_rec
    return int_rec
a = truncate_stream(make_integer_stream(),5)
print(stream_to_list(integral(a,8,.5)))