SICP:惰性求值、流和尾递归(Python实现)

求值器完整实现代码我已经上传到了GitHub仓库:TinySCM,感兴趣的童鞋可以前往查看。这里顺便强烈推荐UC Berkeley的同名课程CS 61A。

即使在变化中,它也丝毫未变。

——赫拉克利特

吾犹昔人,非昔人也。

——僧肇

绪论

在上一篇博客《SICP:元循环求值器(Python实现)》中,我们介绍了用Python对来实现一个Scheme求值器。然而,我们跳过了部分特殊形式(special forms)和基本过程(primitive procedures)实现的介绍,如特殊形式中的delaycons-stream,基本过程中的forcestreawn-carstream-map等。事实上,以上特殊形式和基本过程都和惰性求值与流相关。这篇博客我们将介绍如何用Python来实现Scheme中的惰性求值和流,并使用惰性求值的原理来为我们的Scheme解释器增添尾递归的支持。

1 Scheme中的流简介

所谓,一言以蔽之,就是使用了惰性求值技术的表。它初始化时并没有完全生成,而是能够动态地按需构造,从而同时提升程序的计算和存储效率。

我们先来比较两个程序,它们都计算出一个区间里的素数之和。其中第一个程序用标准的迭代(尾递归)风格写出:

(define (sum-primes a b)
  (define (iter count accum)
    (cond ((> count b) accum)
          ((prime? count) (iter (+ count 1) (+ count accum)))
          (else (iter (+ count 1) accum))))
  (iter a 0))

第二个程序完成同样的计算,其中使用了我们在博客《SICP: 层次性数据和闭包性质(Python实现)》中所介绍过的序列操作:

(define (sum-primes a b)
  (reduce +
          (filter prime? (enumerate-interval a b))))

在执行计算时,第一个程序只需要维持正在累加的和;而对于第二个程序而言,只有等enumerate-interval构造完这一区间所有整数的表后,filter才能开始工作,而且等过滤区工作完后还得将结果表传给reduce得到求和。显然,第一个程序完全不需要像第二个程序这么大的中间存储。

以上情况还不是最极端的,最极端的情况是下面这种,我们枚举并过滤出了10000到1000000内的所有素数,但实际上只取第二个:

(car (cdr (filter prime?
                    (enumerate-interval 10000 1000000))))

这程序槽点很多,首先要构造与一个大约包含了一百万个整数的表,然后再通过过滤整个表的方式去检查每个元素是否是素数,而后只取第二个,几乎抛弃了全部结果,这在时间和空间上都是极大的浪费。在更传统的程序设计风格中,我们完全可以交错进行枚举和过滤,并在找到第二个素数时立即停下来。

流是一种非常巧妙的想法,使我们在保留各种序列操作的同时,不会带来将序列作为表去操作引起的代价(时间上和空间上的)。从表面上看,流也是就是表,但对它们进行操作的过程名字不同。对于流而言有构造函数cons-stream,还有两个选择函数stream-cdrstream-cdr,它们对任意的变量xy都满足如下的约束条件:

scm> (equal? (stream-car (cons-stream x y)) x)
#t
scm> (equal? (stream-cdr (cons-stream x y)) y)
#t

为了使流的实现能自动透明地完成一个流的构造与使用的交错进行,我们需要做出一种安排,使得对于流的cdr的求值要等到真正通过过程stream-cdr去访问它的时候再做,而非在用cons-stream构造流的时候就做。事实上,这一思想在原书2.1.2节中介绍实现有理数的时候也有体现。再那里简化分子与分母的工作可以在构造的时候完成,也可以在选取的时候完成,这两种方式将产生同一个数据抽象,但不同的选择可能产生效率的影响。流和常规表也存在着类似的关系、对于常规的表,其carcdr都是在构造时求值;而流的cdr则是在读取时才求值。

我们可以使用流来完成上面所说的素数筛选功能:

scm> (define (stream-enumerate-interval low high)
        (if (> low high)
            nil
            (cons-stream
            low
            (stream-enumerate-interval (+ low 1) high))))
stream-enumerate-interval
scm> (car (cdr (stream-filter prime?
                    (stream-enumerate-interval 10000 1000000))))
10009

2 惰性求值

接下来我们来看如何在求值器中实现流。流的实现将基于一种称为delay的特殊形式,对于(delay <expr>)的求值将不对表达式<expr>求值,而是返回一个称为延时对象(delayed object) 的对象,它可以看做是对在未来(future)求值<expr>允诺(promise)。这种直到需要时才求值的求值策略我们称之为惰性求值(lazy evaluation)按需调用(call-by-need)[2][3][4]。与之相反的是所谓的急切求值(eager evaluation),也即表达式立即进行求值(除非被包裹在特殊形式中)。

:事实上,futurepromisedelaydeferred等来自函数式编程的特性已经被许多语言的并发模块所吸纳[5]。在并发编程中,我们常常会对程序的执行进行同步,而由于某些计算(或者网络请求)尚未结束,我们需要一个对象(也即futurepromise)来代理这个未知的结果。

我们求值器中的延时对象定义为:

class Promise:
    def __init__(self, expr, env):
        self.expr = expr
        self.env = env

    def __str__(self):
        return "#[promise ({0}forced)]".format(
            "not " if self.expr is not None else "")

可以看到,该对象保持了表达式expr及其对应的环境env,但未对其进行求值。

特殊形式delay对应的的求值过程如下,可以看到它返回了一个Promise延时对象:

def eval_delay(expr, env):
    validate_form(expr, 1, 1)
    return Promise(expr.first, env)

delay一起使用的还有一个称为force的基本过程,它以一个延时对象为参数,执行相应的求值工作,也即迫使delay完成它所允诺的求值。

@ primitive("force")
def scheme_force(obj):
    from eval_apply import scheme_eval

    validate_type(obj, lambda x: is_scheme_promise(x), 0, "stream-force")
    return scheme_eval(obj.expr, obj.env)

我们接下来测试下delayforce

scm> (define pms1 (delay (+ 2 3)))
pms1
scm> pms1
#[promise (not forced)]
scm> (force pms1)
5
scm> (define pms2 (delay (delay (+ 2 3))))
pms2
scm> (force pms2)
#[promise (not forced)]
scm> (force (force pms2))
5

可见对于(delay (delay (+ 2 3)))这种嵌套的延时对象,也需要像剥洋葱一样一层一层地对其进行force

3 流的实现

3.1 构造流

在实现了最基本的延时对象后,我们用它们来构造流。流由特殊形式cons-stream来构造,该特殊形式对应的求值过程如下:

def eval_cons_stream(expr, env):
    validate_form(expr, 2, 2)
    return scheme_cons(scheme_eval(expr.first, env), Promise(expr.rest.first, env))

可见,在实际使用中(cons-stream <a> <b>)等价于(cons <a> (delay <b>)),也即用序对来构造流,不过序对的cdr并非流的剩余部分的求值结果,而是把需要就可以计算的promise放在那里。

现在,我们就可以继续定义基本过程stream-carstream-cdr了:

@primitive("stream-car")
def stream_car(stream):
    validate_type(stream, lambda x: is_stream_pair(x), 0, "stream-car")
    return stream.first

@primitive("stream-cdr")
def stream_cdr(stream):
    validate_type(stream, lambda x: is_stream_pair(x), 0, "stream-cdr")
    return scheme_force(stream.rest)

stream-car选取有关序对的first部分,stream-cdr选取有关序对的cdr部分,并求值这里的延时表达式,以获得这个流的剩余部分。

3.2 流的行为方式

我们接下来看上述实现的行为方式,我们先来分析一下我们上面提到过的区间枚举函数stream-enumerate-interval的例子,不过它现在是以流的方式重新写出:

scm> (define (stream-enumerate-interval low high)
        (if (> low high)
            nil
            (cons-stream
            low
            (stream-enumerate-interval (+ low 1) high))))
stream-enumerate-interval

我们来看一下它如何工作。首先,我们使用该过程定义一个流integers,并尝试直接对其进行求值:

scm> (define integers (stream-enumerate-interval 10000 1000000))
integers
scm> integers
(10000 . #[promise (not forced)])

可见,对于这个流而言,其car100,而其cdr则是Promise延时对象,其意为如果需要,就能枚举出这个区间里更多的东西。

接下来我们尝试连续使用stream-cdr递归地访问流的cdr部分,以枚举区间里的更多数:

scm> (stream-cdr integers)
(10001 . #[promise (not forced)])
scm> (stream-cdr (stream-cdr integers))
(10002 . #[promise (not forced)])

这个过程实际上就像是剥洋葱的过程,相当于一层一层地对嵌套的Promise对象进行force。就像下图[5]所示的那样:

图中的每个红色箭头表示对Promise对象使用一次force

上面展示的是用流去表示有限长度的序列。但令人吃惊的是,我们甚至可以用流去表示无穷长的序列,比如下面我们定义了一个有关正整数的流,这个流就是无穷长的:

scm> (define (integers-starting-from n)
        (cons-stream n (integers-starting-from (+ n 1))))
integers-starting-from
scm> (define integers (integers-starting-from 1))
integers

在任何时刻,我们都只检查到它的有穷部分:

scm> integers
(1 . #[promise (not forced)])
scm> (stream-cdr integers)
(2 . #[promise (not forced)])
scm> (stream-cdr (stream-cdr integers))
(3 . #[promise (not forced)])
...

3.3 针对流的序列操作

目前我们已经完成了流的构造,但想实现第一节提到的sum-primes程序我们还需要针对流的map/filter/reduce操作。我们下面即将介绍针对流的stream-map/stream-filter/stream-reduce过程,它们除了操作对象是流之外,其表现和普通的map/filter/reduce完全相同。

stream-map是与过程map类似的针对流的过程,其定义如下:

@primitive("stream-map", use_env=True)
def stream_map(proc, stream, env):
    from eval_apply import complete_apply
    validate_type(proc, is_scheme_procedure, 0, "map")
    validate_type(stream, is_stream_pair, 1, "map")

    def stream_map_iter(proc, stream, env):
        if is_stream_null(stream):
            return nil
        return scheme_cons(complete_apply(proc, scheme_list(stream_car(stream)
                                                            ), env),
                           stream_map_iter(proc, stream_cdr(stream), env))

    return stream_map_iter(proc, stream, env)

stream_map将对流的car应用过程proc,然后需要进一步将过程proc应用于输入流的cdr,这里对stream_cdr的调用将迫使系统对延时的流进行求值。注意,这里我们为了方便延时,使stream_map函数直接返回用scheme_cons函数构造的普通表,在Scheme的实际实现中返回的仍然是流。

同理,我们可将stream-filterstream-reduce函数定义如下:

@primitive("stream-filter", use_env=True)
def stream_filter(predicate, stream, env):
    from eval_apply import complete_apply
    validate_type(predicate, is_scheme_procedure, 0, "filter")
    validate_type(stream, is_stream_pair, 1, "filter")

    def scheme_filter_iter(predicate, stream, env):
        if is_stream_null(stream):
            return nil
        elif complete_apply(predicate, scheme_list(stream_car(stream)), env):
            return scheme_cons(stream_car(stream),
                               scheme_filter_iter(predicate,
                                                  stream_cdr(stream), env))
        else:
            return scheme_filter_iter(predicate, stream_cdr(stream), env)

    return scheme_filter_iter(predicate, stream, env)


@primitive("stream-reduce", use_env=True)
def stream_reduce(op, stream, env):
    from eval_apply import complete_apply
    validate_type(op, is_scheme_procedure, 0, "reduce")
    validate_type(stream, lambda x: x is not nil, 1, "reduce")
    validate_type(stream, is_stream_pair, 1, "reduce")

    def scheme_reduce_iter(op, initial, stream, env):
        if is_stream_null(stream):
            return initial
        return complete_apply(op, scheme_list(stream_car(stream),
                                              scheme_reduce_iter(op,
                                                                 initial,
                                                                 stream_cdr(
                                                                     stream),
                                                                 env)), env)

    return scheme_reduce_iter(op, stream_car(stream), stream_cdr(stream), env)

以下是对stream-map的一个测试:

scm> (stream-map (lambda (x) (* 2 x))  (stream-enumerate-interval 1 10))
(2 4 6 8 10 12 14 16 18 20)

4 时间的函数式程序观点

流的使用可以让我们用一种新的角度去看对象和状态的问题(参见我的博客《SICP:赋值和局部状态(Python实现)》)。流为模拟具有内部状态的对象提供了另一种方式。可以用一个流去模拟一个变化的量,例如某个对象的内部状态,用流表示其顺序状态的时间史。从本质上说,这里的流将时间显示地表示出来,因此就将被模拟世界里的时间与求值过程中事件发生的顺序进行了解耦(decouple)。

为了进一步对比这两种模拟方式,让我们重新考虑一个“提款处理器”的实现,它管理者一个银行账户的余额。在往期博客中,我们实现了这一处理器的一个简化版本:

scm> (define (make-simplified-withdraw balance)
       (lambda (amount)
         (set! balance (- balance amount))
         balance))
make-simplified-withdraw
scm> (define W (make-simplified-withdraw 25))
w
scm> (W 20)
5
scm> (W 10)
-5

调用make-simplified-withdraw将产生出含有局部状态变量balance的计算对象,其值将在对这个对象的一系列调用中逐步减少。这些对象以amount为参数,返回一个新的余额值。我们可以设想,银行账户的用户送一个输入序列给这种对象,由它得到一系列返回值,显示在某个显示屏幕上。

换一种方式,我们也可以将一个提款处理器模拟为一个过程,它以余额值和一个提款流作为参数,生成账户中顺序余额的流:

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

这里stream-withdraw实现了一个具有良好定义的数学函数,其输出完全由输入确定(即不会出现同一个输入输出不一致的情况)。当然,这里假定了输入amount-stream是由用户送来的顺序提款值构成的流,作为结果的余额流将被显示出来。如下展示了根据一个用户的提款流来完成提款的过程:

scm> (define amount (cons-stream 20 (cons-stream 10 nil)))
amount
scm> (define W (stream-withdraw 25 amount))
w
scm> (stream-cdr W)
(5 . #[promise (not forced)])
scm> (stream-cdr (stream-cdr W))
(-5 . #[promise (not forced)])

可见,从送入这些值并观看结果的用户的角度看,这一流过程的行为与由make-simplified-withdraw创建的对象没有什么不同。当然,在这种流方式里没有赋值,没有局部状态变量,因此也就不会有我们在博客《SICP:赋值和局部状态(Python实现)》中所遇到的种种理论困难。但是这个系统也有状态!

这确实是惊人的,虽然stream-withdraw实现了一个定义良好的(well-defined)数学函数,其行为根本不会变化,但用户看到的却是在这里与一个改变着状态的系统交互。事实上,在物理学中也有类似的思想:当我们观察一个正在移动的粒子时,我们说该粒子的位置(状态)正在变化。然而,从粒子的世界线[6]的观点看,这里根本就不涉及任何变化。

我们知道,虽然用带有局部状态变量的对象来对现实世界进行模拟是威力强大且直观的,但对象模型也产生了对于事件的顺序,以及多进程同步的棘手问题。避免这些问题的可能性推动着函数式程序设计语言(functional programming languages) 的开发,这类语言里根本不提供赋值或者可变的(mutable) 数据。在这样的语言里,所有过程实现的都是它们的参数上的定义良好的数学函数,其行为不会变化。FP对于处理并发系统特别有吸引力。事实上Fortran之父John Backus在1978年获得图灵奖的授奖演讲[7]中就曾强烈地推崇FP,而在分布式计算中广泛应用的Map-Reduce并行编程模型[8]以及Spark中的弹性分布式数据集(Resilient Distributed Dataset, RDD)[9]也都受到了FP的影响(关于分布式计算可以参见我的博客《Hadoop:单词计数(Word Count)的MapReduce实现》和《Spark:单词计数(Word Count)的MapReduce实现(Java/Python)》)。

但是在另一方面,如果我们贴近观察,就会看到与时间有关的问题也潜入到了函数式模型之中,特别是当我们去模拟一些独立对象之间交互的时候。举个例子,我们再次考虑允许公用账户的银行系统的实现。普通系统系统里将使用赋值和状态,在模拟Peter和Paul共享一个账户时,让他们的交易请求送到同一个银行账户对象。从流的观点看,这里根本就没有什么“对象”,我们已经说明了可以用一个计算过程去模拟银行账户,该过程在一个请求交易的流上操作,生成一个系统响应的流。我们也同样能模拟Peter和Paul有着共同账户的事实,只要将Peter的交易请求流域Paul的请求流归并,并把归并后的流送给那个银行账户过程即可,如下图所示:

这种处理方式的麻烦就在于归并的概念。通过交替地从Peter和Paul的请求中取一个根本不想。假定Paul很少访问这个账户,我们很难强迫Peter去等待Paul。但无论这种归并如何实现,都必须要在某种Peter和Paul看到的“真实时间”之下交错归并这两个交流,这也就类似原书3.4.1节中引入显式同步来确保并发处理中的事件是按照“正确”顺序发生的。这样,虽然这里试图支持函数式的风格来解决问题,但在需要归并来自不同主体的输入时,又会将问题重新引入。

总结一下,如果我们要构造出一些计算模型,使其结构能够符合我们对于被模拟的真实世界的看法,那我们有两种方法:

  • 将这一世界模拟为一集相互分离的、受时间约束的、具有状态的相互交流的对象。

  • 将它模拟为单一的、无时间也无状态的统一体(unity)。

以上两种方案各有其优势,但有没有一种该方法能够令人完全满意。我们还等待着一个大一统的出现。

事实上,对象模型对世界的近似在于将其分割为独立的片段,函数式模型则不沿着对象的边界去做模块化。当“对象”之间不共享的状态远远大于它们所共享的状态时,对象模型就特别好用。这种对象观点失效的一个地方就是量子力学,再那里将物体看作独立的粒子就会导致悖论和混乱。将对象观点与函数式观点合并可能与程序设计的关系不大,而是与基本认识论有关的论题。

5 用惰性求值实现尾递归

所谓尾递归,就是当计算是用一个递归过程描述时,使其仍然能够在常量空间中执行迭代型计算的技术。

我们先来考虑下面这个经典的用递归过程描述的阶乘计算:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

我们可以利用原书1.1.5节中介绍的代换模型(substitution model),观看这一过程在计算\(6!\)时所表现出的行为:

可以看出它的代换模型揭示出一种先逐步展开而后收缩的的形状,如上图中的箭头所示。在展开阶段里,这一过程构造起一个推迟进行的操作所形成的链条(在这里是一个乘法*的链条),收缩阶段表现为这些运算的实际执行。这种类型的计算过程由一个推迟执行的运算链条刻画,称为一个递归计算过程。要执行这种计算过程,解释器就需要维护好以后将要执行的操作的轨迹。在这个例子中,推迟执行的乘法链条的长度也就是为保存其轨迹需要的信息量,这个长度和计算中所需的步骤数目一样,都会随着\(n\)线性增长。这样的计算过程称为一个线性递归过程

然而,如果递归调用是整个函数体中最后执行的语句,且它的返回值不属于表达式的一部分,这样就无需保存将要执行的操作轨迹,从而在常数空间内执行迭代型计算,比如下面这个过程:

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

我们也用代换模型来查看这一过程在计算\(6!\)时所表现出的行为:

可以看到,该计算过程虽然是用递归描述的,但并没有任何增长或者收缩。对于任何一个\(n\),在计算过程中的每一步,在我们需要保存的轨迹里,所有的东西就是变量productcountermax-count的当前值。我们称这种过程为一个迭代计算过程。一般来说,迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程;而与此同时,又存在着一套固定的规则,描述了计算过程在从一个状态到下一个状态转换时,这些变量的更新方式;还有一个(可能有的)结束检测,它描述了这一计算过程应该终止的条件。在计算\(n!\)时,所需的计算步骤随着\(n\)线性增长,而其使用的空间却是常量的,这种过程称为线性迭代过程

当然,这种当计算用递归过程描述时,仍能够在常量空间中执行迭代型计算的特性依赖于底层解释器的实现,我们将具有这一特性的实现称为尾递归的。有了一个尾递归的实现,我们就可以利用常规的过程调用机制表述迭代,这也会使各种复杂的专用迭代结构变成不过是一些语法糖(syntactic sugar) 了。

接下来我们看如何用前文提到的惰性求值技术来为我们的求值器实现尾递归特性。

乍一看,我们Scheme求值器的scheme_eval()求值函数是用Python语言来递归定义的:

@primitive("eval", use_env=True)
def scheme_eval(expr, env, _=None):
    # Evaluate self-evaluating expressions
    if is_self_evaluating(expr):
        return expr
    # Evaluate variables
    elif is_scheme_variable(expr):
        return env.lookup_variable_value(expr)

    ...
    # Evaluate special forms
    if is_scheme_symbol(first) and first in SPECIAL_FORMS:
        return SPECIAL_FORMS[first](rest, env)
    # Evaluate an application
    else:
        operator = scheme_eval(first, env)
        # Check if the operator is a macro
        if isinstance(operator, MacroProcedure):
            return scheme_eval(complete_apply(operator, rest, env), env)
        operands = rest.map(lambda x: scheme_eval(x, env))
        return scheme_apply(operator, operands, env)

而我们知道,Python是不支持尾递归的,但是求值器又必须要依靠Python以这种递归的方法来编写,那怎么在此基础上为我们的源语言——Scheme语言实现尾递归呢?答案就在于我们之前提到的Promise延时对象。为了和之前的Promise对象做区分(避免干扰到流的工作),我们将其定义为TailPromise对象,它直接继承了Promise类,其表现和Promise对象完全相同:

class TailPromise(Promise):
    """An expression and an environment in which it is to be evaluated."""

这里实现尾递归的诀窍就在于,我们需要使scheme_eval这个过程每次进行递归调用时,都不马上去进行递归,而是返回一个Promise对象,将当前需要求值的表达式expr和环境env暂存起来。之后,我们再在另一个while迭代的循环里去求值这个Promise对象中含有的表达式,此时的求值需要我们再次调用scheme_eval,如果遇到递归又返回一个Promise对象,然后回到之前的那个while迭代循环里再次求值,以此往复。这样,我们就用延时对象+迭代的循环在常量空间里去模拟了递归的求值过程。如下所示:

def optimize_tail_calls(original_scheme_eval):
    def optimized_eval(expr, env, tail=False):
        # If tail is True and the expression is not variable or self-evaluated,
        # return Promise directly, Note that for `optimized_eval`, argument
        # `tail` defaults to False, which means that it is impossible to
        # return Promise at the first call, that is, when the recursion depth
        # is 1
        if tail and not is_scheme_variable(expr) and not is_self_evaluating(
                expr):
            return TailPromise(expr, env)

        # If tail is False or the expression is variable or self-evaluated (
        # which includes the first call of `scheme_eval`), it will be
        # evaluated until the actual value is obtained (instead of Promise)
        result = TailPromise(expr, env)
        while (isinstance(result, TailPromise)):
            # A call to `original_scheme_eval` actually can simulate the
            # recursion depth plus one.
            result = original_scheme_eval(result.expr, result.env)
        return result

    return optimized_eval


# Uncomment the following line to apply tail call optimization
scheme_eval = optimize_tail_calls(scheme_eval)

这里为了不直接修改scheme_eval的内容,使用一个Python闭包的技巧,也就是使optimized_eval成为原始scheme_eval的函数装饰器,从而在其基础上添加尾递归功能并对其进行替代。上述代码实际上就等同于:

from functools import wraps
def optimize_tail_calls(original_scheme_eval):
    @wraps(original_scheme_eval)
    def optimized_eval(expr, env, tail=False):
        ...
        return result

    return optimized_eval

@optimize_tail_calls
@primitive("eval", use_env=True)
def scheme_eval(expr, env, _=None):
    ...

接下来我们测试一下我们求值器的尾递归功能:

scm> (define (sum n total)
            (if (zero? n) total
              (sum (- n 1) (+ n total))))
sum
scm> (sum 1000001 0)
500001500001

可以看到尾递归特性已经成功地实现了。

OK,我们已经实现好了尾递归功能,这依赖于底层惰性求值的实现。但是别忘了,我们有时候是不需要惰性求值,而是需要急切求值的(也即求值结果不能是TailPromise对象)。比如在对MacroProcedure过程对象(该过程对象由宏的定义产生)进行实际应用前,我们需要先将宏的内容进行进行展开,而这就需要我们另外定义一个complete_apply函数:

def complete_apply(procedure, args, env):
    val = scheme_apply(procedure, args, env)
    if isinstance(val, TailPromise):
        return scheme_eval(val.expr, val.env)
    else:
        return val

该函数可在给定环境env下将过程procedure应用到实参arguments,知道结果不是TailPromise对象为止。然后就得到了我们在scheme_eval()函数中对宏的处理方式:

if isinstance(operator, MacroProcedure):
    return scheme_eval(complete_apply(operator, rest, env), env)

注意,scheme-map/scheme-filter/scheme-reducestream-map/stream-filter/stream-reduce这几个基本过程函数要传入一个过程对象为参数,而在这几个函数中对该过程对象的应用就必须得是急切的。这是因为optimize_tail_calls函数中的while迭代循环只能保证map/filter/reduce等基本过程表达式本身得到求值,而对这些基本过程所调用的高阶过程的实际应用是得不到保障的。以map基本过程为例,如果仍使用惰性求值的scheme_apply来完成过程对象的应用:

@ primitive("map", use_env=True)
def scheme_map(proc, items, env):
    ...
    def scheme_map_iter(proc, items, env):
        if is_scheme_null(items):
            return nil
        return scheme_cons(scheme_apply(proc, scheme_list(items.first), env),
                           scheme_map_iter(proc, items.rest, env))

    return scheme_map_iter(proc, items, env)

那么我们将得到如下结果:

scm> (map (lambda (x) (* 2 x))  (list 1 2 3))
(#[promise (not forced)] #[promise (not forced)] #[promise (not forced)])

可以看到map这个基本过程表达式是得到求值了,但其所调用的高阶过程(lambda (x) (* 2 x))并未得到实际应用。

解决之道很简单,在scheme-map/scheme-filter/scheme-reduce几个函数中,对过程对象进行求值时使用complete-apply即可。比如对scheme-map而言,就需要使用complete-apply做如下修改:

@ primitive("map", use_env=True)
def scheme_map(proc, items, env):
    ...
    def scheme_map_iter(proc, items, env):
        if is_scheme_null(items):
            return nil
        return scheme_cons(complete_apply(proc, scheme_list(items.first), env),
                           scheme_map_iter(proc, items.rest, env))

    return scheme_map_iter(proc, items, env)

这样,再对map基本过程进行测试,就能够得到正确的求值结果了:

scm> (map (lambda (x) (* 2 x))  (list 1 2 3))
(2 4 6)

参考

  • [1] Abelson H, Sussman G J. Structure and interpretation of computer programs[M]. The MIT Press, 1996.
  • [2] 8.6 Lazy evaluation
  • [3] Wiki: Lazy evaluation
  • [4] Yet Another Scheme Tutorial: 17. Lazy evaluation
  • [5] Wiki: Futures and promises
  • [6] Wiki: World line
  • [7] Backus J. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs[J]. Communications of the ACM, 1978, 21(8): 613-641.
  • [8] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.
  • [9] Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]//Presented as part of the 9th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 12). 2012: 15-28.
数学是符号的艺术,音乐是上界的语言。
本文转载于网络 如有侵权请联系删除

相关文章

  • 0~6组成4个不重复的数

    0~6组成4个不重复的数privatestaticvoidsort(int[]a){ //TODOAuto-generatedmethodstub inttemp=0; for(intx=0;x<a.length;x++){ for(inti=0;i<a.length;i++){ for(intj=0;j<a.length;j++){ for(intk=0;k<a.length;k++){ if(a[x]!=a[i]&&a[x]!=a[j]&&a[x]!=a[k]&& a[i]!=a[j]&&a[i]!=a[k]&&a[j]!=a[k]){ temp+=1; System.out.print(a[x]+""+a[i]+""+a[j]+""+a[k]+"、"); if(temp%20==0){ System.o

  • 《使用MATLAB进行图像,音频和视频处理的基础知识:应用于模式识别》

    使用MATLAB®进行图像,音频和视频处理的基础知识:应用于模式识别的应用出版商Finelybook出版社:CRCPress;第一版(2021年4月16日) 语言:英语 页数:406页 ISBN-10书号:0367895242 ISBN-13书号:9780367895242 使用MATLAB®进行图像,音频和视频处理的基础知识介绍了媒体处理的概念和原理及其在模式识别中的应用作者:采用程序实现的动手方法。本书涵盖了使用数据分析和可视化工具MATLAB读取,修改和写入图像,音频和视频文件的工具和技术。 主要特点图像,音频和视频处理的基本概念演示了如何使用MATLAB解决处理媒体的问题讨论了图像处理工具箱,音响系统工具箱,以及计算机视觉工具箱的重要特征MATLAB代码作为提供答案的具体问题说明了在音频和视频处理中使用Simulink处理时空域和频域中的处理技术这是研究生和研究生学习图像处理,语音和语言处理,信号处理,视频对象检测和跟踪以及相关多媒体技术课程的理想伴侣,并且侧重于使用编程结构和技能发展的实际实现。它还将吸引模式识别,计算机视觉和基于内容的检索领域的研究人员,以及涉及媒体处理,

  • Github的这个彩蛋我居然才知道,我OUT了

    搞开发的哪个还没有GitHub账户?作为一个GitHub的资深用户,今天居然才发现GitHub还有这个彩蛋。什么彩蛋呢?比如我的GitHub是:https://github.com/NotFound403 复制我可以建立一个同名的仓库NotFound403。最终是这个效果:github主页它是怎么做到的呢?其实非常简单!只需要在同名仓库(我的为NotFound403)建立一个README.md,里面写Markdown,Github会自动将你写的Markdown文件渲染出来并放在你Github首页的顶部,就像上面展示的那样。你可以分享你的个人经历、思维导图,或者你可以自己想想能利用这个做点什么。如果你有静态资源要展示,可以分离,也可以在项目下建立个文件夹引用,比如我的:目录img目录就是放图片等静态文件的,假如你没有静态资源存储的话这种也是一种好办法。说句题外话,其实很多程序员没有把Github利用起来,你可以把自己每天学习积累的东西分门别类放进去。不管是日后工作需要、学习需要都可以很方便的去检索,编程能力的提高其实也是一个积累的过程,而Github,包括国内的Gitee给你我提供了很好

  • ArchLinux KDE安装Nvidia显卡驱动

    简介近期又继续在I7+GTX950M的笔记本上折腾起了archlinux。想起去年在manjaro安装NVIDIA显卡的时候导致无法开机,当时驱动是在NVIDIA官网下载的,可能方法不对。近期又在笔记本上折腾archlinux,不打算使用manjaro了。archlinux的安装虽然繁琐,但对与喜欢折腾的人来说这也算是一种乐趣吧。写一篇文章用来记录自己操作的过程,方便后续安装使用。电脑详细信息,桌面主题还没设置好就不截图了。笔记本信息预览安装显卡驱动安装intel核显驱动sudopacman-Sxf86-video-intel复制编辑pacman.conf文件启用32位软件源vim/etc/pacman.conf复制将以下两行的注释取消(删除前面的#)[multilib] Include=/etc/pacman.d/mirrorlist复制同步软件包数据库sudopacman-Syy复制安装Nvidia显卡闭源驱动sudopacman-Snvidianvidia-primenvidia-settingsnvidia-utilsopencl-nvidialib32-nvidia-util

  • VUE|Vue实例

    1.创建一个Vue实例之前初步学习了Vue的安装和一些简单介绍,这次就主要学习Vue实例。每个Vue应用都是通过用Vue函数创建一个新的Vue实例开始的。varvm=newVue({//选项})复制虽然没有完全遵循MVVM模型,但是Vue的设计也受到了它的启发。因此在文档中经常会使用vm(ViewModel的缩写)这个变量名表示Vue实例。当创建一个Vue实例时,你可以传入一个选项对象,我在Vue官方教程中学习的主要就是如何使用这些选项来创建你想要的行为。我们也可以在API文档中浏览完整的选项列表。一个Vue应用由一个通过newVue创建的根Vue实例,以及可选的嵌套的、可复用的组件树组成。举个例子,一个todo应用的组件树可以是这样的: 根实例 └─TodoList ├─TodoItem │├─DeleteTodoButton │└─EditTodoButton └─TodoListFooter ├─ClearTodosButton └─TodoListStatistics复制个人认为我们只需记住,所有的Vue组件都是Vue实例,并且接受相同的选项对象(一些根实例特有的

  • 如何跳过MySQL的root密码

    在安装好mysql后(如何安装请参考在linux服务器上部署自己的个人网站)新装的mysql不知道root密码?1、过滤初始密码grep'password'/var/log/mysqld.log复制红色框框里的就是初始密码 如果密码已经改过了,那么即使找到默认密码也是没有用的,此时就要看第二招了2、跳过密码认证vim/etc/my.cnf复制[mysqld] skip-grant-tables//指定位置加一行复制 改了配置文件,记得重启服务systemctlrestartmysqld复制mysql//进入到mysql复制mysql>updatemysql.usersetauthentication_string=password('ZG..2020')whereuser='root';//更新密码为ZG..2020 mysql>exit复制 消除跳过密码认证,进入正常mysqlvim/etc/my.cnf复制把刚刚添加的skip-grant-tables注释或者删除 同样,改了配置文件,要重启服务systemc

  • Vue.js高仿饿了么外卖App学习记录

    (给达达前端加星标,提升前端技能)​开发一款vue.js开发一款app,使用vue.js是一款高效的mvvm框架,它轻量,高效,组件化,数据驱动等功能便于开发。使用vue.js开发移动端app,学会使用组件化,模块化的开发方式。学习了如何根据需求分析开发,使用脚手架工具,数据mock,架构设计,自己测试,编译打包等流程。线上生产环境,如何考虑架构设计,组件抽象,模块拆分,代码风格统一,变量命名要求规范等优点。一款外卖app,商家页面,商家基本信息(顶部),商品区块,商品列表,分类列表,小球飞入购物车的动画。商品详情页,需要有顶部商品的大图,商品的详细信息,以及还有商品的评价列表。商品,评论列表,商家展示商家的详情信息。用vue-resource与后端做数据交互,vue-router前端路由,better-scroll的Js库等。使用vue-cli脚手架,搭建基本代码框架,vue-router官方插件管理路由。vue-resource是用于ajax通信的,webpack构建工具的使用。Vue是一套用于构建用户界面的渐进式JavaScript框架。与其它大型框架不同的是,Vue被设计为可以

  • 大数据-经典案例统计求和

    3.流量统计需求一:统计求和 统计每个手机号的上行流量总和,下行流量总和,上行总流量之和,下行总流量之和分析:以手机号码作为key值,上行流量,下行流量,上行总流量,下行总流量四个字段作为value值,然后以这个key,和value作为map阶段的输出,reduce阶段的输入Step1:自定义map的输出value对象FlowBeanpublicclassFlowBeanimplementsWritable{ privateIntegerupFlow; privateIntegerdownFlow; privateIntegerupCountFlow; privateIntegerdownCountFlow; @Override publicvoidwrite(DataOutputout)throwsIOException{ out.writeInt(upFlow); out.writeInt(downFlow); out.writeInt(upCountFlow); out.writeInt(downCountFlow); } @Override publicvoidreadFi

  • 如何基于TAPD实践Scrum的敏捷开发?

    Scrum是一种用于开发创新产品和服务的敏捷开发方式,我们首先来看一下敏捷开发过程和特点,并着重介绍Scrum框架的角色、活动和工件等内容,然后介绍团队利用TAPD中的需求管理、缺陷管理、迭代管理等应用功能来帮助团队有效实践Scrum敏捷开发。何为敏捷开发?敏捷开发所倡导的是通过若干个短期的迭代周期(也称为冲刺sprint,范围一般是1周-1个月),按一定的优先级不断增量开发和实现产品功能,每次迭代获得一个可运行的产品增量功能包。 敏捷开发首先需要建立一个按优先级排列的产品列表,其中由产品需求、功能优化或功能缺陷等类型清单项组成,排在前面的是优先级高的项,优先纳入迭代计划进行实现,这些项在纳入迭代计划前进行分解和细化,达到满足开发团队实现的粒度。越往后排的项优先级越低,这部分需求暂时不会提上开发实现日程,当前阶段可以粗略描述,也不必急于细化,以应对可能的变更。每次迭代开始阶段,从产品列表中选取一定数量的清单项作为本次迭代需要完成的目标任务,通常是由各方利益相关者讨论决定的,数量的多少视开发团队的情况而定,尽量匹配开发团队的开发节奏。迭代过程中开发团队每天通过站立会的形式沟通工作进展和面

  • Bug与Debug的随笔

    bug的本意是指昆虫、小虫、损坏、缺陷等意思,在互联网时代还有一种引申意义,用来形容某人/物超乎想象的厉害,那简直就是开挂的人生,系统的bug!一般地,在码农的世界了,bug是在电脑系统或程序代码中隐藏着的一些未被发现的缺陷或问题,可以简称为程序缺陷。从广义上看,还包括软件需要改进的细节、或与需求文档存在差异的功能实现等等。bug是如何与程序缺陷联系起来的呢?Bug的由来时光回溯到一台计算机可以装满整个房间的时代,大约在1945年9月9日,GraceHopper发现了HarvardMarkII计算机的第一个bug。GraceHopper是数据处理方面的专家,在1952年为UNIVAC开发了第一个编译器,能够把人读得懂的高级语言翻译成计算机能够识别的机器语言。那一天,GraceHopper对HarvardMarkII设置好的17000个继电器进行编程后,技术人员正在进行整机运行,它突然停止了工作。于是他们爬上去找原因,发现这台巨大的计算机内部一组继电器的触点之间有一只飞蛾,这显然是由于飞蛾受光和热的吸引,飞到了触点上,然后被高电压击死。死去的飞蛾被夹扁在触点中间,从而“卡”住了机器的运行

  • ai基础教程入门_绘画入门基础教程

    大家好,又见面了,我是你们的朋友全栈君。第一次写博文呢,这次写博客是因为应一位同学的要求,写一下GSAPJS的一个小教程。为什么说小呢?因为它实际上就是小,只是一个入门级的小教程。如果你想问:“那你为什么不写详细一点呢?”,我想说,说.,说..,“因为我也不懂,哈哈”,就是不懂,不骗你们,不懂就是不懂。那我那点英文水平肿么会懂呢?好吧,言归正传。首先说一下GSAP(GreenSockAnimationPlatform)的官网,点这里进入GSAP的官网,也可以点这里直接进入GSAPJS的介绍,有空详细看一下,并不需要非常好的英语水平才能看,你看博主我这个英文水平都能看懂部分,不懂的部分就多查查有道。看得懂的话就可以完全跳过我的这篇“小教程啦”,真的,我说得一定不够官方的详细、全面、好,还有可能会说错(:汗好吧,这次真的要开始啦!准备好了吗? 开始 啦!!!首先,我们先说一下工具的准备,要学习GSAP,那么我们一定要先准备一个GASP的类包啦,文章结束的时候,博主我会给出一个网盘地址,让同学本下载,当然,你也可以到GreenSock的官网(http://www.greensock.com)

  • 【PolyAI】【EMNLP 2020 Findings】ConveRT:来自 Transformer 的高效准确的会话表示

    介绍论文《ConveRT:EfficientandAccurateConversationalRepresentationsfromTransformers》地址:https://arxiv.org/abs/1911.03688作者在pretrain(Reddit数据)+fine-tune的方式的基础上提出了一个更轻量级的预训练回复选择模型ConveRT,并且模型还可以引入了更多的对话历史信息。另外,模型学习的句子编码可以transfer到其他对话任务(eg.意图识别)。这篇文章是基于目前预训练模型参数量过大,训练和运行都消耗巨大的计算资源,导致其实际应用受阻的问题提出的。在现实应用场景中,我们需要一个“更小”的模型。ConveRT是一个轻量级的双编码器预训练结构,它综合利用了多种方式来降低模型的复杂度,包括:子词表示(subwordrepresentation)、单头注意力机制(single-headedattention)、量化感知训练(quantization-awaretraining)等,该模型与其他模型相比,参数更少、训练时间更短、且具有更好的性能,如下表所示: 模型架构单

  • [BZOJ2819] Nim

    [BZOJ2819]Nim Description 著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。为了设计漂亮一点的初始局面,vfleaking用以下方式来找灵感:拿出很多石子,把它们聚成一堆一堆的,对每一堆编号1,2,3,4,...n,在堆与堆间连边,没有自环与重边,从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作:1.随机选两个堆v,u,询问若在v到u间的路径上的石子堆中玩Nim游戏,是否有必胜策略,如果有,vfleaking将会考虑将这些石子堆作为初始局面之一,用来坑玩家。2.把堆v中的石子数变为k。由于vfleaking太懒了,他懒得自己动手了。请写个程序帮帮他吧。 Input 第一行一个数n,表示有多少堆石子。接下来的一行,第i个数表示第i堆里有多少石子。接下来n-1行,每行两个数v,u,代表v,u间有一条边直接相连。接下来一个数q,代表操作的个数。接下

  • 用户无法进入SDSF,报NO GROUP ASSIGNMENT错误

    注:命令行小写部分表出需要根据自己的情况改变!!   a)激活SDSF资源类 SETROPTSCLASSACT(SDSF)复制 b)查看SDSF资源类的PROFILE RLISTSDSF*复制 c)如果不存在GROUP.ISFUSER.servername的PROFILE,则需要定义, RDEFINESDSF(GROUP.ISFUSER.servername)OWNER(useridorgroupname)UACC(READ)复制 这样,所有用户都可以有读取权限,就都可以访问SDSF了 附1:查看SDSFservername 用一个能进SDSF的帐户进入SDSF,输入命令WHO 可以看到,倒数第二行有一个"SERVERNAME=SDSF",所以我这里的servername就是SDSF了。   附2:如果你不想所有用户都可以访问SDSF,能这样定义 RDEFINESDSF(GROUP.ISFUSER.servername)OWNER(useridorgroupname)UACC(NONE)复制 然后对你自己单独授权 PERMITGROUP.ISFU

  • Cordova android框架详解

    一、Cordova核心java类说明   CordovaActivity:CordovaActivity入口,已实现PluginManager、WebView的相关初始化工作,只需继承CordovaActivity实现自己的业务需求。 PluginManager:插件管理器 ExposedJsApi :javascript调用Native,通过插件管理器PluginManager根据service找到具体实现类。 NativeToJsMessageQueue:Native调用javascript,主要包括三种方式:loadUrl、轮询、反射WebViewCore执行js   二、 Cordova框架类图   三、Cordova框架启动   当实现了DroidGap或者CordovaInterface接口的Activity的onCreate方法中调用DroidGap的loadUrl方法即启动了Cordova框架。   Cordova提供了一个Class(DroidGap extends Cordo

  • VSCode-配置python程序在独立窗口运行

    配置python程序在独立窗口运行 点击VSCode菜单栏的Run-AddConfiguration 选择python-pythonfile 这样会在当前工作目录下生成一个.vscode的文件夹,文件夹里面会包含一个.launch.json文件: 修改"console":"integratedTerminal"为"console":"externalTerminal" 回到python文件,按F5运行:

  • [libgdx游戏开发教程]使用Libgdx进行游戏开发(9)-场景过渡

    本章主要讲解场景过渡效果的使用。这里将用到RendertoTexture(RTT)技术。 Libgdx提供了一个类,实现了各种常见的插值算法,不仅适合过渡效果,也适合任意特定行为。 在本游戏里面,我们将实现3种转场效果:fade,slide和slice. 和前面提到的多场景管理一样,我们也需要这样的结构来统一管理转场特效: 首先创建接口ScreenTransition: packagecom.packtpub.libgdx.canyonbunny.screens.transitions; importcom.badlogic.gdx.graphics.Texture; importcom.badlogic.gdx.graphics.g2d.SpriteBatch; publicinterfaceScreenTransition{ publicfloatgetDuration(); publicvoidrender(SpriteBatchbatch,TexturecurrScreen, TexturenextScreen,floatalpha); }复制 OpenGL有个叫做F

  • 查找鞍点

    ------------恢复内容开始------------ 题目 对于给定的整数矩阵A[5,5],设计算法查找出所有的鞍点。 提示:鞍点的特点:列上最小,行上最大。 输入格式: 输入5行5列整数,同行数据间以空格为间隔。 输出格式: 在一行中以以下格式输出矩阵中的所有鞍点,每个鞍点的显示格式为: [<鞍点的行坐标>,<鞍点的列坐标>,<鞍点的值>] 输入样例: 113569 1247810 1056911 86478 1510112025 输出样例: [3,0,8][3,4,8] ---------------------------------------一条华丽的分割线---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  • [专题总结]二分图和网络流(理论篇)

    二分图 二分图最大匹配 二分图的一组匹配就是一个边集,其中任意两条边没有公共顶点。 求最大匹配的过程:建一个图,\(S\)向左部连\(1\),右部向\(T\)连\(1\),跑最大流,中间的边被流了就是匹配边。 点覆盖 是一个点的集合,使得所有的边至少有一个顶点在该集合内 最小点覆盖=最大匹配 证明:首先最小点覆盖的下界是最大匹配,因为所有匹配边两边至少有一个点需要选择。 构造一种选择恰好最大匹配个点的方案,给出构造方法。 先跑出最大流,然后从右侧所有非匹配点开始dfs,从右侧向左侧走,只能走非匹配边,从左侧到右侧走,只能走匹配边,最后,取出所有左边的被dfs到的点和右边的未被dfs到的点,就是最小点覆盖。 证明:一条边不被覆盖当且仅当左边未被dfs到,右边被dfs到。 右边被dfs到了,他如果是非匹配点,他必将便利左侧所有相连点。 如果他是匹配点,那么他肯定是由左侧的匹配点过来的,过来的左侧点肯定被访问了,其他的左侧点会被他访问。 所以,一个与右侧被dfs到的点相连的所有左侧点都会被dfs到,不存在上述情况。 似乎还叫什么定理,例题:https://www.luogu.com.cn

  • 力扣(LeetCode)试题3-无重复字符的最长子串 C++代码

    感想:今天学到了新知识,unordered_set与unorder_map数据类型,可以提供查找(find)、移除(erase)与插入(insert)功能。 这个程序在报错→调试→报错→调试…中完成。 1#include<iostream> 2#include<string> 3#include<unordered_set> 4 5usingnamespacestd; 6 7classSolution 8{ 9public: 10intlengthOfLongestSubstring(strings) 11{ 12if(s.size()==0)return0; 13unordered_set<char>str;//第一次学习这种容器,不能放入重复元素,提供了插入、删除、查询功能,容器名字叫lookup,容器内的元素类型为char 14intlenth=0; 15intleft=0; 16 17for(inti=0;i<s.size();i++)//遍历输入的串 18{ 19while(str.find(s[i])!=str.end

  • httpClient4请求工具类实现

    packagecom.http; importjava.net.URI; importjava.util.ArrayList; importjava.util.List; importorg.apache.commons.collections.CollectionUtils; importorg.apache.http.HttpEntity; importorg.apache.http.HttpResponse; importorg.apache.http.NameValuePair; importorg.apache.http.client.HttpClient; importorg.apache.http.client.entity.UrlEncodedFormEntity; importorg.apache.http.client.methods.HttpGet; importorg.apache.http.client.methods.HttpPost; importorg.apache.http.entity.StringEntity; importorg.apache.h

相关推荐

推荐阅读