SICP_interpreter_笔记

2026年1月3日 · 572 字 · 3 分钟

摘要

本文为《计算机程序的构造和解释》（SICP，CS61A 南大引进版）用python实现scheme解释器部分课程核心笔记，聚焦程序设计的底层逻辑与核心思想，旨在帮助学习者搭建“知其然更知其所以然”的编程认知框架。适合正在学习 CS61A 课程的学习者梳理知识体系，也可作为编程入门者夯实基础、理解程序设计本质的参考资料。

使用python实现scheme解释器 (Interpreters)

Hangout

翻译与解释器基础 (Translation and Interpreter Basics)

主题概述

计算机只能理解二进制 (Binary) ，而高级编程语言需要被翻译成二进制才能运行。解释器 (Interpreter) 实现了即时 (on-the-fly) 翻译和执行。

核心概念 (Core Concepts)

1. 翻译类型 (Types of Translation)

编译 (Compiled): 一次性全部翻译，稍后运行。

解释 (Interpreted): 边运行边翻译。

2. 解释器语言 (Interpreter Languages)

实现语言 (Implementation Language): 用来编写解释器本身的语言（如 Scheme 解释器可能是用 Python 实现的）。

被实现语言 (Implemented Language): 用户输入的语言（即 Scheme）。

被实现语言被翻译成实现语言。

3. 读-求值-打印循环 (Read-Eval-Print Loop, REPL)

解释器核心的三个步骤:

读 (Read): 读取用户输入（字符串）。
求值 (Eval): 将输入翻译成计算机可读的形式并求值。
打印 (Print): 打印结果给用户。

读取阶段 (The Read Phase)

主题概述

读取阶段将原始输入字符串转换为一种在实现语言（Python）中可操作的表达式表示 (Expression Representation) 。

核心概念

1. 词法分析/提词器(Lexical Analysis / Lexer)

将输入字符串转化为标记 (Tokens) 集合。
分割+提取+初步处理(按照规则转化为放在python列表里的python语法的东西)

标记 (Token): 输入字符串的单个有意义单元，如字面量(literals)、名称(names)、关键字(keywords)、分隔符(delimiters)等。
注：

分隔符：用于分割不同语法单元，如括号，分号，引号关键字：即special form和standard procedures,如define,lambda,if,begin,quote 名称：即标识符，如函数名，变量名字面量：表示直接值的语法元素，如数字，字符串，字符(#\a)，符号('symbol)，布尔值，列表、向量字面量('(1 2 3)、#(a b c))

2. 语法分析 (Syntactic Analysis / Parser)

将标记转化为实现语言中表达式的表示形式(Representation)。

基本表达式的表示:
- 自求值表达式 (Self-Evaluating Expressions) (#t, 5.2): 使用 Python 对应的布尔值或数字。
- 符号 (Symbols) (cons): 使用 Python 字符串。
注： scheme 表达式种类：
- 自求值表达式(self-evaluatingexpressions)
- 符号(symbols)
- 调用表达式(call expressions)
- 特殊表达式(special form expressions)

3. 表示组合 (Representing Combinations)

Scheme 的组合表达式 (<operator> <operand1> ...) 在内部被表示为包含操作符和操作数的Scheme 链表 (Linked Lists) 。

scm> (define expr '(+ 2 3)) ; Create the expression (+ 2 3)
expr
scm> (eval expr) ; Evaluate the expression
5
scm> (car expr) ; Get the operator
+
scm> (cdr expr) ; Get the operands
(2 3)

在 Python 中，Scheme 列表通过自定义的 Pair 类和全局 nil 实例来精确表示:

Python Pair 和 nil 类:

class Pair:
    def __init__(self, first, second):
        self.first = first # 相当于 Scheme 的 car
        self.second = second # 相当于 Scheme 的 cdr
    def __repr__(self):
        return 'Pair({0}, {1})'.format(self.first, self.second)

class nil:
    def __repr__(self):
        return 'nil'

nil = nil()
# 让所有的nil都是同一个nil,防止每次都创建一个instance,出现不同的instance不能进行相等的运算

4. 特殊情况：引用 (`quote`)

特殊语法 ‘<expr> 在读取时会被转换成一个完整的 quote 表达式。

例题

(+ 2 3) 被表示为: Pair('+', Pair(2, Pair(3, nil)))
(define (f) 3)表示为 Pair('define', (Pair(Pair('f', nil), Pair(3, nil))))
4.67 -> 4.67
#t -> True
list -> 'list'
(cons 2 3) -> Pair('cons', Pair(2, Pair(3, nil)))
(if (< x 0) 1 (+ x 1)) -> Pair('if', Pair(Pair('<', Pair('x', Pair(0, nil))), Pair(1, Pair(Pair('+', Pair('x', Pair(1, nil))), nil))))

遇到括号套一层pair

'hello -> Pair('quote', Pair('hello', nil))

求值阶段 (The Eval Phase)

复习：怎么画环境图来着？

(define (make-adder x)
    (lambda (y) (+ x y)))
(define add-three (make-adder 3))
(add-three 5)
(add-three 10)

alt text

主题概述

求值阶段 (Eval) 是解释器的核心，它接收表达式的表示形式和一个环境 (Environment) ，并返回求值结果（值）。Eval 和 Apply 是相互递归 (mutually-recursive) 的。

核心概念

1. 环境与框架 (Environments and Frames)

环境 (Environment): 由当前框架、其父框架及其所有祖先框架直到全局框架组成。
框架 (Frame): 在解释器中由 Frame 类实例表示。 Frame有两个实例属性： bindings: 字典，将 Scheme 符号 (Python 字符串) 绑定到 Scheme 值。 parent: 指向父框架（另一个frame实例）

2. 求值基本表达式 (Evaluating Primitive Expressions)

自求值表达式: 它们求值结果就是自身。
符号 (Symbols):

从当前框架开始查找符号的绑定值。
如果未找到，递归地向父框架查找，直到全局框架 。
如果全局框架仍未找到，抛出错误 (SchemeError) 。

3. 求值组合 (Evaluating Combinations)

组合表达式分为特殊形式和调用表达式，取决于其运算符。

特殊形式 (Special Forms): 运算符是特殊的符号（如 define, if, lambda），有其自身的求值规则。
调用表达式 (Call Expressions):
1. 求值运算符，得到一个过程 (Procedure) 。
2. 从左到右求值所有操作数，得到参数值。
3. 应用 (Apply) 过程到参数值。

前两步递归的调用eval喵

应用阶段 (The Apply Phase)

主题概述

应用阶段 (Apply) 将一个过程 (Procedure) 应用于一组参数 (Arguments)。过程有两种类型：内置过程和用户定义过程。

核心概念

1. 内置过程 (Built-In Procedures)

例如 +, list, modulo 。
在解释器中，它们是 BuiltinProcedure 类的实例。

应用规则: 直接调用对应的实现语言（Python）函数，并将参数值传入。

2. 用户定义过程 (User-Defined Procedures)

通过 lambda 或 define 定义。
在解释器中，它们是 LambdaProcedure 类的实例，包含形式参数列表、函数体和父框架 (Parent Frame) 。

应用规则 (Application Rules):

打开一个新框架 (New Frame)，其父框架是该过程的父框架（即创建该过程时的环境）。
将形式参数 (Formal Parameters) 绑定到参数值 (Arguments) 上，存储在新框架中。
在新框架中求值过程的函数体。

3. Eval/Apply 计数 (Counting Eval/Apply Calls)

Eval 和 Apply 是相互调用的： alt text

1. Eval（求值）

Eval 的任务是接收一个表达式（代码）和当前环境，并返回它的值。

基础情况 (Base Cases): 这是递归的终点。
- 自求值表达式 (Self-evaluating expressions): 比如数字（5）或字符串（"hello"），它们的值就是它们本身。
- 符号查找 (Look up values): 比如变量名 x。求值器会去内存（环境）中查找 x 对应的值。
递归情况 (Recursive Cases):
- Eval(operator) 和 Eval(o): 当遇到一个函数调用时，它先分别求出“函数名”和“所有参数”的具体数值。
- Apply(proc, args): 一旦参数准备好了，它就会把这些参数交给 Apply 去实际执行。
- 特殊形式 (Special Form): 比如 if 语句或 define。这些不是普通函数，需要特殊的处理逻辑

2. Apply（应用）

Apply 的任务是接收一个“函数”和一组“参数”，并执行这个函数。

基础情况 (Base Cases):
内置过程 (Built-in procedures): 比如加法 + 或减法 -。这些是由底层硬件或底层语言（如 C 或 Python）直接实现的，不需要再拆解。
递归情况 (Recursive Cases):
- Eval(body) of user defined procedures: 对于用户自己定义的函数，Apply 会打开函数体（Body），然后在这一组新参数的环境下，**重新调用 Eval** 来处理函数体里的代码。

这种相互递归 (Mutual Recursion) 形成了一个闭环。通过这个循环，解释器可以处理极其复杂的嵌套代码：

Eval 负责“拆解”结构。
Apply 负责“执行”动作。

例题

使用python实现scheme解释器 (Interpreters)

翻译与解释器基础 (Translation and Interpreter Basics)

主题概述

核心概念 (Core Concepts)

1. 翻译类型 (Types of Translation)

2. 解释器语言 (Interpreter Languages)

3. 读-求值-打印循环 (Read-Eval-Print Loop, REPL)

读取阶段 (The Read Phase)

主题概述

核心概念

1. 词法分析/提词器(Lexical Analysis / Lexer)

2. 语法分析 (Syntactic Analysis / Parser)

3. 表示组合 (Representing Combinations)

4. 特殊情况：引用 (quote)

例题

求值阶段 (The Eval Phase)

复习：怎么画环境图来着？

主题概述

核心概念

1. 环境与框架 (Environments and Frames)

2. 求值基本表达式 (Evaluating Primitive Expressions)

3. 求值组合 (Evaluating Combinations)

应用阶段 (The Apply Phase)

主题概述

核心概念

1. 内置过程 (Built-In Procedures)

2. 用户定义过程 (User-Defined Procedures)

3. Eval/Apply 计数 (Counting Eval/Apply Calls)

4. 特殊情况：引用 (`quote`)