开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Python知识库 -> sicp_python chap.3 review -> 正文阅读

[Python知识库]sicp_python chap.3 review

内容梳理

3.1 导论

我们可以通过这些编程基本元素的技巧来构建模块化、可维护、可扩展的程序：

函数（第一章）
- 函数抽象
- 泛用函数
数据（第二章）
- 数据抽象
- 类的继承

本章专注于编程的第三个基本元素：

程序自身
- 解释器只是另一个程序，它确定编程语言中表达式的意义。
- 编程语言在语法结构、特性和应用领域上差别很大。
- 通用编程语言中，函数定义和函数调用无处不在。
- 但也存在不包含对象系统、高阶函数或虚幻控制结构的编程语言。
- 典型的解释器拥有简洁的通用结构（两个递归函数）：
  - 求解环境中的表达式。
  - 在参数上调用函数。

3.2 函数和所生成的过程

虽然我们可以使用计算模型展开递归，但通常把递归调用看作函数抽象更清晰一些，也就是说我们不该关心fn‘() 在fn()中如何实现，我们只要相信他完成了他的功能即可。这样，递归函数的正确性验证就成了一种归纳证明。

递归函数：函数体直接或间接的调用自己。
通用模式：

基本条件：一个条件语句，处理最简单的输入定义函数行为（递归跳出）。
递归调用：一个或者多个，该调用必须简化原始问题。

递归 vs. 迭代：

概念上不同。
维护局部状态的方式不同：
- 迭代要引入局部变量，并随着迭代的进行来修改。
- 递归则是通过调用与返回，状态包含在表达式树的结果中。
时空复杂度不同

树形递归：多次递归调用，整个计算过程看起来像一棵树。
记忆：可以通过空间复杂度的上升来换取时间复杂度的下降。

3.3 递归数据结构

本节介绍了几种(可以)使用递归来实现/处理的数据结构。

3.3.1 递归列表(Rlist)

列表实现为(first, rest)的递归嵌套，其上的方法：

__len__
__getitem__
extend_item
map_rlist
filter_rlist

都可以通过递归，简单而清晰的实现。

3.3.2 层次结构(Tree)

其实就是树了，递归是处理树形结构的自然工具。因为我们通常可以将树的操作降至他的子节点的操作，直至到达了叶节点。

映射与递归为树的操作建立了强大而通用的计算形式。

3.3.3 集合

类似于数学中的集合，无序的唯一容器，可以有多种实现方式：

不重复的元素序列
- 成员测试会递归遍历整个列表， $\theta(n)$ 。
- 增加元素会递归遍历整个列表(排除重复)， $\theta(n)$ 。
- 交集，需要比较每个元素是否重复， $\theta(n^2)$ 。
- 并集，需要比较每个元素是否重复， $\theta(n^2)$ 。
- 通过将集合实现为有序列表，可以有效的减低操作的时间复杂度。
二叉树的集合(BST/AVL)
- 成员测试、添加元素为 $\theta(log n)$ 。
- 交集与并集为 $\theta(n)$ 。
- 维护AVL需要额外的开销。
哈希表
- 成员测试、添加元素为 $\theta(1)$ 。
- 交集与并集为 $\theta(n)$ 。
- 不能包含可变元素。

3.4 异常

异常是一个对象实例，直接或间接继承自BaseException类。
通常由try except语句块来处理。
自定义的异常类可以携带额外的属性。

3.5 组合语言的解释器

这里实现一个计算器的解释器，规定使用python调用表达式的语法，但对接受的参数数量更加灵活。
分模块如下：

Exp类作为操作对象的抽象
REPL 处理输入&输出接口
tokenize词法分析
analyze语法分析
- 递归处理操作数(子表达式)
- 错误处理
calc_eval接受表达式作为参数，并返回它的值
- 递归处理每个子表达式
- 调用calc_apply处理实际运算
calc_apply实际在参数列表上计算

3.6 抽象语言的解释器

实现求值过程的函数与实现函数应用过程(调用)的函数是相互递归的，求值的基本条件是：求解基本表达式、变量、引用表达式或定义；调用的基本条件是调用基本过程。这个互相递归的结构在解释器中非常常见，在处理表达式形式的求值函数，和处理函数及其参数的应用之间，构成了求值过程的本质。

3.6.1 Scheme简介

pass 这部分看这本书大概是看不懂的。而且虽然我很感谢译者的工作，但看起这部分的译文确实让人感到折磨…

3.6.2 Logo简介

Logo过程以前缀形式调用，但是通用的算术运算符以普遍的中缀形式调用。但同时Logo语言使用了非标准的调用表达式语法，完全不带括号分隔符，而是通过固定参数数量来进行语法识别。

表达式：
- 调用表达式
- 基本表达式
- 引用表达式
- 定义表达式
单词：基本的数据类型，不带空格的字符串。可以表示数值、名称和布尔值。
引用：不被求值的表达式，可以解释为单词字面值。
句子：列表数据类型，可以储存Logo源码，通过run来求值。
- sentence 将参数(2个)组装为句子：
  - 如果参数是单词，会把参数放进局子。
  - 如果参数是句子，则会拼接参数。
- list 从两个元素创建句子，可以创建层次数据结构。
- fput 从第一个元素和剩余元素创建列表。
- 可以通过first、butfirst、last来访问句子元素。
print/show：输出，show可以展示句子的方括号([ ])。
Lisp允许将代码表示为数据，待稍后将其解释为程序的一部分，这是Lisp风格语言的特性。

? run sentence "print [sum 1 2]
3
? print run sentence "sum sentence 10 run [difference 7 3]
14

如这一段代码所示，虽然Logo中的过程(sum, difference)不全是一等公民(不能直接放在句子中)，但他们的名字是一等的。可以放在句子中储存，然后通过run过程来解析。

赋值：绑定名称和值。
- 使用make来绑定。
- 以：开始的单词为变量。
- 如果名称已绑定，会在找到它的第一帧(最近的调用处)重新绑定该帧。
- 如果没有绑定，在全局帧中绑定名称。
过程：使用to关键字开始定义过程。
- 新过程的名字
- 变量作为形参
- 几行过程的主体
- end记号标记结束
output 中断过程体的执行，并返回一个值。
动态作用域，环境扩展于过程调用处。

3.6.3 结构

解析器：产生表达式数据结构。
- 不返回表达式树，而是按行解析表达式。
- 动态特性需要求值器分析嵌套表达式
求值器：每次求值一行。
- eval_line: 求值一行，返回最后一个表达式的值。
- logo_eval: 求值一个表达式，并返回它的值。每种表达式都有自己的求值规则：
  - 基本表达式：求值为自身。
  - 变量：在环境中查找。
  - 定义：特殊情况，调用储存相应的过程到全局环境。
  - 引用表达式：求值为引用的文本。
  - 调用表达式：在环境中查找运算符的名称，并调用该过程。
    - apply_procedure: 检查调用过程，调用参数分析&实际应用函数。
    - collect_args: 分析参数。
    - logo_apply: 在参数上应用函数。
      - 基本过程直接调用。
      - 自定过程求出主体的代码行，递归调用eval_line。

3.6.4 环境

环境：

帧集合
- 帧以字典实现
过程列表
变量集合

总结与感悟

模块化设计

编译器中的模块化很有趣，输入输出处理、分析器、求值器……合理的模块化设计有效的隔离了思考的边界。
但是感觉这方面非常需要经验… 就比如这章中出现的两个编译器，动态语言的部分就把表达式分析放到了求值器中，这就是针对了具体的需求做了模块设计的更改，还是需要多体会体会。

动态作用域

动态作用域环境扩展于调用处，有效的避免了在函数调用时传递一些冗余的参数。感觉对递归调用十分友好。
而且这种作用域函数内没有独立的符号表，十分契合函数式编程的纯函数要求，可能这也是函数式语言喜欢采用它的原因吧。

项目——实现一个简易的Scheme解释器

项目目标

使用python语言，为scheme语言的一个子集开发一个解释器，包含了：

一部分Scheme Primitives (已实现)
- + - * / …
- car cdr
- boolean? null? eq?
- display
- …
special forms
- lambda mu …
logical special forms
- if cond …
- and or …
部分尾递归优化
尝试写一些scheme程序

项目框架

scheme解释器的模块结构

Read-Eval-Print-Loop：负责和使用者交互，显示提示符scm>。将读入的代码交由Scheme Reader分析，由Scheme Eval求值并打印结果/错误信息。
Scheme-Reader：实现了Pair类，并将读入的代码整理为表达式List（Pair的嵌套）。
Scheme-Eval：在环境中对表达式求值，不同的表达式可能会使用不同的辅助函数，或者使用Scheme-Apply应用一个过程。
Scheme-Apply：在环境中创建新的帧，并在该帧中调用过程。通常scheme-eval和scheme-apply会相互调用。
Auxiiary Functions：一些特殊表达式的处理函数，类似if、lambda之类的。

关键代码

scheme-eval

def scheme_eval(expr, env):
    """Evaluate Scheme expression EXPR in environment ENV.

    >>> expr = read_line("(+ 2 2)")
    >>> expr
    Pair('+', Pair(2, Pair(2, nil)))
    >>> scheme_eval(expr, create_global_frame())
    4
    """
    if expr is None:
        raise SchemeError("Cannot evaluate an undefined expression.")

    # Evaluate Atoms
   	# 求值标识符，在环境中查找‘变量’的值
    if scheme_symbolp(expr):
        return env.lookup(expr)
    elif scheme_atomp(expr) or scheme_stringp(expr) or expr is okay:
        return expr

    # All non-atomic expressions are lists.
    if not scheme_listp(expr):
        raise SchemeError("malformed list: {0}".format(str(expr)))
    first, rest = expr.first, expr.second

    # Evaluate Combinations
    # 求值不同的表达式
    if (scheme_symbolp(first) # first might be unhashable
        and first in LOGIC_FORMS):
        return scheme_eval(LOGIC_FORMS[first](rest, env), env)
    elif first == "lambda":
        return do_lambda_form(rest, env)
    elif first == "mu":
        return do_mu_form(rest)
    elif first == "define":
        return do_define_form(rest, env)
    elif first == "quote":
        return do_quote_form(rest)
    elif first == "let":
        expr, env = do_let_form(rest, env)
        return scheme_eval(expr, env)
    else:
    	# 调用过程
        procedure = scheme_eval(first, env)
        args = rest.map(lambda operand: scheme_eval(operand, env))
        return scheme_apply(procedure, args, env)

scheme-apply

def scheme_apply(procedure, args, env):
    """Apply Scheme PROCEDURE to argument values ARGS in environment ENV."""
    # 调用已实现的Primitives
    if isinstance(procedure, PrimitiveProcedure):
        return apply_primitive(procedure, args, env)
    # 在定义过程的环境处扩展新环境，并求值
    elif isinstance(procedure, LambdaProcedure):
        "*** YOUR CODE HERE ***"
        frame = procedure.env.make_call_frame(procedure.formals, args)
        return scheme_eval(procedure.body, frame)
    # 在调用处扩展新环境，并求值
    elif isinstance(procedure, MuProcedure):
        "*** YOUR CODE HERE ***"
        frame = env.make_call_frame(procedure.formals, args)
        return scheme_eval(procedure.body, frame)
    else:
        raise SchemeError("Cannot call {0}".format(str(procedure)))

项目结果

实现了项目的目标，通过了所有的测试用例。
可以承担起scheme的子集的解释功能。
但scheme程序完成的不多，毕竟没有系统的学习过，用起来还是有些陌生。

遇到的问题与感想

模块化设计

不得不再次感慨，这种模块化设计好的项目写起来真的好舒畅。每当完成了一个问题，测试发现一遍通过的时候，那种成就感正是喜欢编程的一大因素。但同时也感到，正式这种工程向的模块化设计，拟定好的测试用例才带来了这份体验。
这种设计应该没什么取巧的方式，多写多想多重构，争取有朝一日也能有这种工程能力吧。

Pair类

在这个项目实现里，所有的表达式经过reader的处理都会转换为嵌套的Pair。本来还好，但是考虑到quote表达式，是否要在最外层添加一个Pair(*,nil)包裹，让我有点难以确定。
包括在其他辅助函数的实现中，什么地方要返回Pair表达式，什么地方要求值后在返回（赋值），我没有清晰的认识。更多的时候是在测试失败后，对应错误信息来修改的。
这大概也是对项目整体的设计，不同的数据类型代表的含义，模块化的分割不是很清楚的结果吧。

递归

解释器的实现中充满了递归，嵌套的Pair表达式也很适合拿来做递归处理。毕竟递归终止条件可以很简单的写成 expr.second == nil。但是在自己真正去做的时候，还是忍不住习惯性的使用循环迭代。循环是一种很直接的思维方式，但是递归却需要一点抽象、分隔的能力。还是要多熟悉这种思维方式。

scheme程序

这个括号匹配快给我写吐了，尤其是括号在scheme中确切的代表着调用的含义。尾括号换行吧，看起来不太像是调用，不换行吧，这个逻辑关系一个不小心就整乱了，唉……
函数式语言摒弃了局部变量的存在，这种风格在刚开始写代码的时候让我有很大的不适应。无法改变变量的值（项目的实现中没有set!)，很多算法我感觉自己都有点不会写了。尤其是在那个深度优先遍历一棵树的时候，怎么在遍历过程中向结果list中添加元素快给我整不会了。尤其是本身就不太熟悉这种树的实现的时候……
有机会的再接触scheme的话，感觉应该先多看一看，学一学scheme风格的代码应该怎么去写捏