Table of Contents

  1. 一、语法
  2. 二、流编程

SICP第三章总结(下)——流编程

Posted on 14 Mar 2012, tagged sicpprogramming

第三章的后半部分是讲的有关流编程。现在很多地方都会提到“流”这个概念,在SICP中,流可以被看作是一个列表,但是它所占用的空间是常数级的,并且它可以表示一个无穷的列表。因此从某种程度上说,它更像是一种规则,一种函数。

我们在第三章的前半部分看到了,使用赋值会使代码容易出问题,但是不使用的话又有很多问题没办法方便的解决,比如面向对象的编程。但是流编程正是提供了除赋值之外的另一种方法,这是第一次听说可以不用赋值实现面向对象编程,我们后面就会分析这个巧妙的方法。首先按照惯例,我们还是分析一下这一部分所涉及到的语法吧。

一、语法

1.delay和force

在解释器中,当遇到一个函数或者表达式的时候,会先解释它,返回结果。比如下面的代码

(+ 2 (sqrt 4))

就会先计算(sqrt 4),得出结果然后再加2。

而delay的作用就是延迟这种计算,比如在解释器中输入以下代码:

(+ 2 (delay (sqrt 4)))

就会发现因为延迟了计算(sqrt 4),解释器一直在等待。

这样一直等待下去肯定是不行的,force和delay相对,就是结束这种延迟。也许现在看不出它们有什么太大的用,但是在后面我们会看到,这是实现流编程必不可少的两个操作。

Scheme中大部分函数都可以由基本的函数所实现。那么delay和force又是怎么实现的呢?简单来说,

(delay <exp>)

可以看作是

(lambda () <exp>)

force可以看作:

(define (force delayed-object)
    (delayed-object))

但是注意,delay直接用define是不可以实现的,需要用到宏的方式来定义。而在实际的应用中也没有这么简单,在一些递归应用中,一个被delay的表达式有可能被force多次,因此实际的实现要复杂一些。

2.stream的相关操作及实现

看起来很神秘的stream是怎样实现的呢?其实它就是一个尾部被delay的一个列表。即在生成列表的时候,把尾部delay,在cdr函数中,再force这个被delay的尾部。这样不管一个多长的列表,都只包含一个头部,和一个被delay的尾部,它们所占的空间是常数级的。被delay的部分是用于生成列表后面部分的规则,因此只要有这个规则,可以生成一个无限长的列表,当用到列表中的某一个时,再对这部分force,就得到了真实的值。这就像一卷卫生纸,当不用的时候它是“蜷缩”在那里的,当用的时候才把它展开,取出要用到的部分。

后面会和所关于stream巧妙的应用。这里先将stream的实现贴出来。书中给出的生成stream的函数是不行的,因为同样需要用到宏。所以我将自己的代码写到这里,也方便自己和别人查询:

(use-syntax (ice-9 syncase))

(define-syntax cons-stream
    (syntax-rules ()
        ((cons-stream head tail)
            (cons head (delay tail)))))

(define (stream-car stream)
    (car stream))

(define (stream-cdr stream)
    (force (cdr stream)))

(define (list-stream . args)
    (if (null? (cdr args))
        (cons-stream (car args) the-empty-stream)
        (cons-stream
            (car args)
            (apply 
                list-stream
                (cdr args)))))

(define (stream-null? stream)
    (eq? stream the-empty-stream))
(define the-empty-stream 'null)

(define (stream-for-each proc s)
    (if (stream-null? s)
        'done
        (begin (proc (stream-car s))
            (stream-for-each proc (stream-cdr s)))))

(define (stream-ref s n)
    (if (= n 0)
        (stream-car s)
        (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc . args)
    (if (stream-null? (car args))
        the-empty-stream
        (cons-stream
            (apply proc (map stream-car args))
            (apply stream-map
                (cons proc (map stream-cdr args))))))

(define (stream-enumerate-interval low high)
    (if (> low high)
        the-empty-stream
        (cons-stream
            low
            (stream-enumerate-interval
                (+ low 1)
                high))))

(define (stream-filter pred stream)
    (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
            (cons-stream (stream-car stream)
                (stream-filter pred
                    (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))
    

(define (display-stream s)
    (stream-for-each display-line s))

(define (display-line x)
    (display x)
    (newline))

(define (interge-starting-from n)
    (cons-stream n (interge-starting-from (+ n 1))))

二、流编程

有了上面的实现,再来看看流的巧妙应用。我们不会将所有有关流的应用都列举出来,只是分析一下其中两个很有趣的应用:无穷长的列表和面向对象编程。

1.无穷长的列表

我们看一个最简单的无穷长的列表,所有大于等于n的整数做组成的列表:

(define (integers-start-from n)
    (cons-stream n
        (integers-start-from (+ n 1))))

由此可以定义包含所有正整数的列表:

(define integers (integers-start-from 1))

当要获取这个列表第5个元素的时候,可以使用下面的代码:

(stream-ref integers 5)

由于(integers-start-from (+ n 1))没有立刻被实现,所以它现在只是作为一个函数被存储着。当执行stream-ref的时候,一步步计算尾部的数据,当计算到第5个的时候停止。所以计算的过程中所用的空间也是常数级别的。而所用的时间,是线性的。

书中还有很多巧妙的无穷列表,但是基本的原理就是这样了,就不一一列举了。

2.面向对象编程

在面向对象编程中,比较重要的一个概念就是,一个类中有很多状态,而它们是随时间而改变的。这些状态的改变,可以看作是由时间所构成的函数。由此我们可以想到,为什么不把每个改变放到一个流中呢?然后对这个流进行处理。

还是上篇文章所说的银行账户的例子。我们可以把每次用户取钱的情况看称是一个流,这个流是由输入所决定的。它可以并且应该是无限的,因为时间是无限的。这个流由用户的输入组成。在思考的过程中,把流作为一个整体来思考,而不用考虑这个流的实现细节。假设这个输入的流是amount-stream,那么我们可以用下面的代码获得存款或者取款之后余额的流:

(define (stream-withraw balance amount-stream)
    (cons-stream
        balance
        (stream-withraw
            (- balance (stream-car amount-stream))
            (stream-cdr amount-stream))))

所得到的流stream-withraw就是相应的每次存取款之后的余额。驱动这个流前进的,可以是用户的输入。

用流来思考面向对象编程确实比较别扭。严格的说,书中所讲的并非面向对象编程,也没有出现过面向对象编程这些字眼。但是基本的思想都是差不多的。现代的面向对象编程已经支持继承等操作,所以相对于这种方法,也许更加方便一些。而一些纯粹的函数式编程语言,却是是没有赋值操作的,当想用这些语言进行一些面向对象的操作的时候,也许就要用到这里的一些思想了。

3.一些思考

相对于面向对象的“一切皆是对象”,想象一切皆是流也非常不错。数据是流,从这个函数到那个函数,从这个模块到那个模块,得到的数据流则是我们想要的结果。这很像Linux中的管道的思想。只不过Linux中的管道是操作系统中的每个程序通过数据流来交互,而在Scheme中是一个程序的不同模块通过数据流来交互。读完这一部分,我对模块化的编程有了很深的感触。

另外,有一些语言自动将列表转换成流。

comments powered by Disqus