Python 中的 SICP "streams as signals"

Question

我找到了一些很好的例子 (here, here) of implementing SICP-like streams in Python. But I am still not sure how to handle an example like the integral found in SICP 3.5.3 "Streams as signals。"

找到的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 生成器）returns 一个不定长度序列的连续元素，并且可以组合和使用 add-streams 和 scale-stream 等尊重流惰性特征的操作进行处理。)

Answer 1

有两种方法可以阅读您的问题。第一个很简单：如何使用 Stream 构造，也许是来自第二个 link 的构造，但具有递归定义？这是可以做到的，虽然在 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 中自然地做到这一点。您要求 "analogous stream-y construct in Python"。显然，答案正是生成器。生成器自然地提供了流概念的惰性评估。它的不同之处在于不能自然地递归表达，但是 Python 不像 Scheme 那样支持它，正如我们将看到的那样。

换句话说，严格的流概念可以用 Python 来表达（如 link 及以上）但是 惯用的 方式就是用发电机。

通过一种将流直接机械转换为生成器（但避免内置 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 的参数。调用它不会启动它产生值 - 它只是创建生成器准备好在需要时懒惰地产生它们。

虽然它不是很 pythonic，但它很适合小的被积函数。 Scheme 版本通过优化尾递归来工作——如果你的被积函数太长，Python 版本将超过最大堆栈深度。所以这在 Python.

中不太合适

直接自然的 pythonic 版本看起来像这样，我认为：

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

这有效地工作并正确地将 integrand 惰性地视为 "stream"。但是，它使用迭代而不是递归来解压被积函数的可迭代对象，这更像是 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

这个混合版本使用了方案中的流组合，并且只避免了尾递归。这仍然是 pythonic 并且 python 包括各种其他在 itertools 模块中使用迭代器的好方法。他们都"respect streams' lazy character"如你所愿。

最后是第一个递归流示例的所有代码，其中大部分来自 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)))

Python 中的 SICP "streams as signals"

SICP "streams as signals" in Python

python

stream

sicp