SICP Chapter4 读书笔记

4 Metalinguistic Abstraction 元语言抽象

前三章讨论了过程的组合与抽象,数据的组合与抽象,指引过程和数据组合与关系的顶层范式。带领我们一步步地解决抽象的问题,但如果遇到的问题更复杂,有可能发现现实可用的语言都不够满意或不够方便,因此第四章主要就是讲述如何设计和实现一门新语言。

“抽象的一大目的,就是明确地表达我们的思想”–hjz

4.1 The Metacircular Evaluator 元循环求值器

第一部分意在展示解释器的基本结构,例子是使用lisp实现的lisp解释器,称作metacircular evaluator

  • eval 在一个环境里的求值一个表达式
  • apply 将一个过程对象应用于一组实际参数

表达式的求值就是evaluate与apply的交替运行,在一个环境里求值的表达式最终会变成一次应用,一次应用又会变成在新环境里求值的表达式。 eval和apply交替下降,直到抵达变量符号/原语为止。

eval和apply不负责定义原语,那么怎么得到到原语数据的值呢?

  • apply负责打开抽象,将抽象的过程代入具体的参数,将抽象定义变回组合表达式。 eval负责化简组合,将组合的表达式递归求值,直到变成必须打开抽象的简单应用。

后面的 amb 解释器、查询语言的解释器都是在这个基本循环(交替)的基础上改造来的。

4.2 Variations on a Scheme — Lazy Evaluation sheme的变形–惰性求值

应用序与正则序

应用序与正则序是求值模型的选择,即什么时候计算表达式的值,Scheme是一个应用序求值语言。

  • 应用序:即任何过程应用前,对应的参数都会被求值
  • 正则序:推迟求值,直到被迫需要值为止

正则序求值的意义重大,它极大地增强了语言的表达能力(如可以用来实现第三章介绍的流),并且它能允许我们写出应用序所不能正确运行的程序:

(define (try a b)
  (if (= a 0)
    a
    b
  )
)
(try 0 (/ 1 0))

应用序求值会报错,但正则序不会,因为 try 函数中根本就没用b的值。

在第三章,我们使用了delay和cons-stream两个特殊形式来产生流。 但这有个坏处——特殊形式可不是一等公民,我们不能在map的参数里用cons-stream。

而且我们被迫把流作为一个单独的数据结构,所有的list操作都要修改之后才能用。

但是在正则序下,所有的问题都烟消云散,我们可以把list和流划等号—-只需要让cons的参数被延迟求值即可。

4.3 Variations on a Scheme — Nondeterministic Computing sheme的变形–非确定性计算

amb(ambiguous歧义,多义)非确定性计算

  • 允许一个表达式有多个可能的值
  • 在求值这种表达式时,求值器可以自动从可以选的值中任意选出一个。
  • 还需要维持与选择相关的轨迹(知道哪些元素已经选过,哪些没选过。在后续计算中要保证不出现重选的情况)
  • 如果已做选择不能满足后面的要求,求值器就会回到有关的表里再 次选择,直至求值成功;或者所有选择都已用完时求值失败

例子:通过利用非确定性求值的”尝试”特性,我们可以写出分析普通英语句子语法结构的程序。
输入是一个英文句子,输出是一个经过词性解析的结果:

;input
the cat eats
;output
(sentence
(noun-phrase (article the) (noun cat))
(verb eats)
)

我们还需要告诉解释器:

  1. 单词词性有哪些
  2. 匹配规则(语法)
;单词词性表
(define nouns '(noun student professor cat class))
(define verbs '(verb studies lectures eats sleeps))
(define articles '(article the a))
(parse '(the professor lectures to the student with the cat))
;基础语法--句子结构
(define (parse-noun-phrase)
(list 'noun-phrase (parse-word articles) (parse-word nouns))
)
(define (parse-sentence)
(list 'sentence (parse-noun-phrase) (parse-word verbs))
)

continuation“继续”:(类似Node.js 里面的 callback和promise、Python 里面的 generator)

“继续”是一种过程参数,它总是在过程的最后一步调用。带有“继续”参数的过程不准备返回,过程的最后一步是调用某个“继续”过程。“继续”是“尾调用”,调用过程的代码已经全部执行完毕。

Amb解释器的实现难点:

  1. 回溯及其触发条件的确定
  2. 求值的轨迹记录(避免重复、确定全部尝试)
  3. 回溯时如何状态撤销

4.4 Logic Programming 逻辑程序设计

计算机科学是研究命令式知识的学科,而数学是研究描述式知识的学科。

程序语言要求用算法的方式描述解决问题的过程,我们必须要一步步地告诉计算机如何进行计算:

  1. 程序要描述具体“怎么做”的过程
  2. 所描述的计算有明确方向,从输入到输出
  3. 描述经计算的表达式,给出从一些值算出结果的方法
  4. 定义过程描述如何从参数计算出结果

我们如何能做到告诉计算机描述性知识,就能自动求解?

  • 3.3.5的约束计算系统就是个例子,我们只需要给出一个公式的约束关系,那么接下来只需要给出已知,它就能自动求出剩下的那个未知。
  • 4.3的非确定求值就更像描述性知识了——给出已知,给出约束,自动求解。

例子:描述式append

功能很简单,(append a b)就是把list b追加到list a的末尾:

(define (append x y)
  (if (null? x)
    y
    (cons (car x) (append (cdr x) y))
  )
)

这个程序背后藏着一条描述性知识:

  1. 对任何一个表 y,空表与其拼接得到的表是 y 本身
  2. 任何表 uvyz(cons u v) 与 y 拼接得到 (cons u z) 的条件是 vy的拼接得到z
  • 如果x是空列表,那么(append x y)为y,如果(append v y)是z,那么(append (cons x v) y)等于(cons u z)
  • 所以如果x和y append出z,那么我在x前面cons个东西再append y的结果等于直接在z前面cons个东西
  • 所以我们现在不仅可以回答(append ‘(a b) ‘(c d))是什么,还能回答 (append x ‘(c d)) = ‘(a b c d)中的那个“x”是什么。

在逻辑式程序语言里,可以写出与上面两条规则直接对应的表达式。求值器可以基于它得到上面各问题的解。但各种逻辑语言都有缺陷,由于解释器本身的算法问题,它们没有办法完美地把描述性知识变成过程性知识。简单提供“做什么” 知识 有时会使求值器陷入无穷循环,或产生了不符合用户预期的行为。

抽象:规则定义与使用

为了抽象复杂查询,我们允许定义规则:(rule ⟨ conclusion ⟩ ⟨ body ⟩ )

(rule (wheel ?person)
  (and
    (supervisor ?middle-manager ?person)
    (supervisor ?x ?middle-manager)
  )
)
  • 如果要满足conclusion,必须要满足body。
  • 那么如果body不满足,那么conclusion就不能被满足。
  • 所以只有body为真,conclusion为假的时候,rule的定义才会被推翻。
  • 这出现了逻辑蕴含!这说明我们的”数据库”拥有逻辑推理的能力!

这样我们就可以形式化地描述例子里的append了:
(append-to-form x y z)即(append x y) = z

(rule (append-to-form () ?y ?y));trivially holds
(rule (append-to-form (?u . ?v) ?y (?u . ?z));grabs car & cdr via dot
  (append-to-form ?v ?y ?z) ; if append(v y) yields z
)

它可以进行推理,上个世纪70年代的时候我们管这个就叫“人工智能“2333

发表评论

电子邮件地址不会被公开。 必填项已用*标注