SICP 笔记 - 0x07

archive time: 2025-03-21

LISP 的表现力确实强大

• Lecture 7A
  • LISP 求值器
  • 求值过程
  • 不动点
  • Y 组合子
• Lecture 7B
  • 变长参数列表
  • 动态绑定
  • 符号参数

Lecture 7A

对于代码流程，我们可以抽象为一个机器，机器内部可以用线路图表示， 即每个过程都是一个元件，数据通过连线传递， 对于递归过程，那么对应的就是一个无限机器，即机器中包含自身这个元件

但是还有一种 “通用” 的机器，可以接受其他机器作为输入， 那么这个机器就可与模拟这个输入的机器来处理数据，一个典型的例子就是 eval

(fact 6) ;; => 720
(eval "<fact>" 6) ;; => 720

<fact> 指实现 fact 的代码

LISP 求值器

这个 eval 的定义大概如下：

(define eval
  (lambda
    (exp env)
    (cond
      ((number? exp) exp)
      ((symbol? exp) (lookup exp env))
      ((eq? (car exp) 'quote) (cadr exp))
      ((eq? (car exp) 'lambda) (list 'closure (cdr exp) env))
      ((eq? (car exp) 'cond) (eval-cond (cdr exp) env))
      (else (apply (eval (car exp) env) (eval-list (cdr exp) env))))))

可以看到，LISP 自身的简洁性和强表达力足以这些简单的方式来解释自身

对应 Rust 对应伪代码如下：

type Environment = std::rc::Rc<std::collections::HashMap<String, Expression>>;

#[derive(Clone, Debug)]
enum Expression {
    Number(f64),
    Symbol(String),
    Quote(&'static str),
    Lambda(Vec<Expression>, Box<Expression>),
    Closure(Vec<Expression>, Box<Expression>, Environment),
    Cond(Vec<(Expression, Expression)>),
    Apply(Box<Expression>, Vec<Expression>),
}

// all primitive operators
const NUMBER_PRIMITIVES: [&'static str; 6] = ["add", "sub", "mul", "div", "gt", "lt"];
const LOGIC_PRIMITIVES: [&'static str; 3] = ["and", "or", "eq"];
const UNARY_PRIMITIVES: [&'static str; 2] = ["neg", "not"];

fn eval(exp: Expression, env: Environment) -> Expression {
    match exp {
        n @ Expression::Number(_) => n,
        Expression::Symbol(sym) => lookup(&sym, env),
        q @ Expression::Quote(_) => q,
        Expression::Lambda(params, body) => closure(params, body, env),
        c @ Expression::Closure(_, _, _) => c,
        Expression::Cond(conds) => eval_cond(&conds, env),
        Expression::Apply(sym, exps) => {
            apply(eval(*sym, env.clone()), eval_list(exps, env.clone()), env)
        }
    }
}

大概框架有了，我们只需要往里面填充细节就好，例如对于 apply 可以定义如下：

fn apply(f: Expression, exps: Vec<Expression>, env: Environment) -> Expression {
    if is_primitive(&f) {
        apply_primitive(f, exps, env)
    } else if let Expression::Closure(params, body, c_env) = f {
        let mut new_env = (*env).clone();
        new_env.extend(c_env.iter().map(|(key, val)| (key.clone(), val.clone())));
        eval(*body, bind(params, exps, std::rc::Rc::new(new_env)))
    } else {
        panic!("not a procedure")
    }
}

但是未定义的东西更多了，什么是 bind？什么是 is_primitive？ 这些都需要我们进一步定义，但是这些具体的步骤是比较轻松的，只是一些判断和匹配

这里还展示了 eval_list 和 eval_cond 的实现：

fn eval_list(exps: Vec<Expression>, env: std::rc::Rc<Environment>) -> Vec<Expression> {
    exps.iter()
        .map(|exp| eval(exp.clone(), env.clone()))
        .collect::<Vec<Expression>>()
}

fn eval_cond(conds: &[(Expression, Expression)], env: std::rc::Rc<Environment>) -> Expression {
    if conds.is_empty() {
        panic!("no conditions")
    } else {
        let (pred, val) = &conds[0];
        if let Expression::Quote("else") = pred {
            eval(val.clone(), env.clone())
        } else if let Expression::Quote(sym) = eval(pred.clone(), env.clone()) {
            if sym.to_lowercase() == "true" {
                eval(val.clone(), env)
            } else if sym.to_lowercase() == "false" {
                eval_cond(&conds[1..], env)
            } else {
                panic!("wrong condition {}", sym)
            }
        } else {
            panic!("wrong predicate {:?}", pred)
        }
    }
}

type Environment = std::rc::Rc<std::collections::HashMap<String, Expression>>;

#[derive(Clone, Debug)]
enum Expression {
    Number(f64),
    Symbol(String),
    Quote(&'static str),
    Lambda(Vec<Expression>, Box<Expression>),
    Closure(Vec<Expression>, Box<Expression>, Environment),
    Cond(Vec<(Expression, Expression)>),
    Apply(Box<Expression>, Vec<Expression>),
}

// all primitive operators
const NUMBER_PRIMITIVES: [&'static str; 6] = ["add", "sub", "mul", "div", "gt", "lt"];
const LOGIC_PRIMITIVES: [&'static str; 3] = ["and", "or", "eq"];
const UNARY_PRIMITIVES: [&'static str; 2] = ["neg", "not"];

fn eval(exp: Expression, env: Environment) -> Expression {
    match exp {
        n @ Expression::Number(_) => n,
        Expression::Symbol(sym) => lookup(&sym, env),
        q @ Expression::Quote(_) => q,
        Expression::Lambda(params, body) => closure(params, body, env),
        c @ Expression::Closure(_, _, _) => c,
        Expression::Cond(conds) => eval_cond(&conds, env),
        Expression::Apply(sym, exps) => {
            apply(eval(*sym, env.clone()), eval_list(exps, env.clone()), env)
        }
    }
}

fn closure(params: Vec<Expression>, body: Box<Expression>, env: Environment) -> Expression {
    Expression::Closure(params, body, env)
}

fn lookup(symbol: &str, env: Environment) -> Expression {
    let sym = Expression::Symbol(String::from(symbol));
    if is_primitive(&Expression::Symbol(String::from(symbol))) {
        sym
    } else {
        env.get(symbol)
            .expect(&format!("unknown symbol {}", symbol))
            .clone()
    }
}

fn eval_cond(conds: &[(Expression, Expression)], env: Environment) -> Expression {
    if conds.is_empty() {
        panic!("no conditions")
    } else {
        let (pred, val) = &conds[0];
        if let Expression::Quote("else") = pred {
            eval(val.clone(), env.clone())
        } else if let Expression::Quote(sym) = eval(pred.clone(), env.clone()) {
            if sym.to_lowercase() == "true" {
                eval(val.clone(), env)
            } else if sym.to_lowercase() == "false" {
                eval_cond(&conds[1..], env)
            } else {
                panic!("wrong condition {}", sym)
            }
        } else {
            panic!("wrong predicate {:?}", pred)
        }
    }
}

fn apply(f: Expression, exps: Vec<Expression>, env: Environment) -> Expression {
    if is_primitive(&f) {
        apply_primitive(f, exps, env)
    } else if let Expression::Closure(params, body, c_env) = f {
        let mut new_env = (*env).clone();
        new_env.extend(c_env.iter().map(|(key, val)| (key.clone(), val.clone())));
        eval(*body, bind(params, exps, std::rc::Rc::new(new_env)))
    } else {
        panic!("not a procedure")
    }
}

fn eval_list(exps: Vec<Expression>, env: Environment) -> Vec<Expression> {
    exps.iter()
        .map(|exp| eval(exp.clone(), env.clone()))
        .collect::<Vec<Expression>>()
}

fn is_primitive(f: &Expression) -> bool {
    if let Expression::Symbol(sym) = f {
        NUMBER_PRIMITIVES.contains(&sym.as_str())
            || LOGIC_PRIMITIVES.contains(&sym.as_str())
            || UNARY_PRIMITIVES.contains(&sym.as_str())
    } else {
        false
    }
}

fn apply_primitive(f: Expression, exps: Vec<Expression>, env: Environment) -> Expression {
    let Expression::Symbol(sym) = f else {
        panic!("need a symbol, but find {:?}", f)
    };
    if exps.len() == 1 && UNARY_PRIMITIVES.contains(&sym.as_str()) {
        let op = eval(exps[0].clone(), env);
        if sym.as_str() == "neg" {
            let Expression::Number(n) = op else {
                panic!("neg can only apply to numbers, but find {:?}", op)
            };
            Expression::Number(-n)
        } else if sym.as_str() == "not" {
            let Expression::Quote(sym) = op else {
                panic!("not can only apply to booleans, but find {:?}", op)
            };
            match sym {
                "true" => Expression::Quote("false"),
                "false" => Expression::Quote("true"),
                _ => panic!("not a boolean"),
            }
        } else {
            panic!("unkown unary primitive {}", sym)
        }
    } else {
        if exps.len() != 2 {
            panic!("need two arguments, but has {}", exps.len())
        } else {
            let op1 = eval(exps[0].clone(), env.clone());
            let op2 = eval(exps[1].clone(), env);

            if NUMBER_PRIMITIVES.contains(&sym.as_str()) {
                let Expression::Number(n1) = op1 else {
                    panic!("need a number, but find {:?}", op1)
                };
                let Expression::Number(n2) = op2 else {
                    panic!("need a number, but find {:?}", op2)
                };
                match sym.as_str() {
                    "add" => Expression::Number(n1 + n2),
                    "sub" => Expression::Number(n1 - n2),
                    "mul" => Expression::Number(n1 * n2),
                    "div" => Expression::Number(n1 / n2),
                    "gt" => {
                        if n1 > n2 {
                            Expression::Quote("true")
                        } else {
                            Expression::Quote("false")
                        }
                    }
                    "lt" => {
                        if n1 < n2 {
                            Expression::Quote("true")
                        } else {
                            Expression::Quote("false")
                        }
                    }
                    _ => unreachable!(),
                }
            } else if &sym == "eq" {
                Expression::Quote(match (op1, op2) {
                    (Expression::Number(n1), Expression::Number(n2)) => {
                        if n1 == n2 {
                            "true"
                        } else {
                            "false"
                        }
                    }
                    (Expression::Quote(q1), Expression::Quote(q2)) => {
                        if q1 == q2 {
                            "true"
                        } else {
                            "false"
                        }
                    }
                    _ => "false",
                })
            } else if LOGIC_PRIMITIVES.contains(&sym.as_str()) {
                let Expression::Quote(sym1) = op1 else {
                    panic!("need a number, but find {:?}", op1)
                };
                let Expression::Quote(sym2) = op2 else {
                    panic!("need a number, but find {:?}", op2)
                };
                if sym1 != "true" || sym1 != "false" || sym2 != "true" || sym2 != "false" {
                    panic!("not a boolean")
                } else {
                    Expression::Quote(match sym.as_str() {
                        "and" => {
                            if sym1 == "true" && sym2 == "true" {
                                "true"
                            } else {
                                "false"
                            }
                        }
                        "or" => {
                            if sym1 == "true" || sym2 == "true" {
                                "true"
                            } else {
                                "false"
                            }
                        }
                        _ => unreachable!(),
                    })
                }
            } else {
                panic!("unkown primitive {}", sym)
            }
        }
    }
}

fn bind(params: Vec<Expression>, exps: Vec<Expression>, env: Environment) -> Environment {
    if params.len() != exps.len() {
        panic!("require {} argument, has {}", params.len(), exps.len())
    } else {
        if params.is_empty() {
            env
        } else {
            let mut new_env = (*env).clone();
            new_env.extend(
                params
                    .iter()
                    .map(|e| {
                        let Expression::Symbol(sym) = e else {
                            panic!("need a symbol, but find {:?}", e)
                        };
                        String::from(sym)
                    })
                    .zip(exps.iter().cloned()),
            );
            std::rc::Rc::new(new_env)
        }
    }
}

我们可以使用一下：

fn main() {
    // lambda = |x, y| (x + y) * (x - y)
    let lambda = Expression::Lambda(
        vec![
            Expression::Symbol(String::from("x")),
            Expression::Symbol(String::from("y")),
        ],
        Box::new(Expression::Apply(
            Box::new(Expression::Symbol(String::from("mul"))),
            vec![
                Expression::Apply(
                    Box::new(Expression::Symbol(String::from("add"))),
                    vec![
                        Expression::Symbol(String::from("x")),
                        Expression::Symbol(String::from("y")),
                    ],
                ),
                Expression::Apply(
                    Box::new(Expression::Symbol(String::from("sub"))),
                    vec![
                        Expression::Symbol(String::from("x")),
                        Expression::Symbol(String::from("y")),
                    ],
                ),
            ],
        )),
    );
    // (x = 3.0, y = 2.0)
    let env = std::rc::Rc::new(std::collections::HashMap::from([
        (String::from("x"), Expression::Number(3.0)),
        (String::from("y"), Expression::Number(2.0)),
    ]));

    // lambda(4.0, 2.0)
    let res1 = eval(
        Expression::Apply(
            Box::new(eval(lambda.clone(), env.clone())),
            vec![Expression::Number(4.0), Expression::Number(2.0)],
        ),
        env.clone(),
    );
    println!("res = {:?}", res1);
    // => res = Number(12.0)

    // lambda(y, x)
    let res2 = eval(
        Expression::Apply(
            Box::new(eval(lambda, env.clone())),
            vec![
                Expression::Symbol(String::from("y")),
                Expression::Symbol(String::from("x")),
            ],
        ),
        env.clone(),
    );
    println!("res = {:?}", res2);
    // => res = Number(-5.0)

    let check = eval(
        Expression::Cond(vec![
            (
                Expression::Apply(
                    Box::new(Expression::Symbol(String::from("eq"))),
                    vec![res2, Expression::Number(-5.0)],
                ),
                Expression::Quote("matched"),
            ),
            (Expression::Quote("else"), Expression::Quote("failed")),
        ]),
        env,
    );
    println!("check = {:?}", check);
    // => check = Quote("matched")
}

发现是能够正常使用的

这里其实还可以使用数据驱动编程， 即使用 Expression 接口，这个接口实现了 eval() 函数， 那么就可以更加方便地增添类型和增加特性了

求值过程

那么这个过程是什么样的呢？例如 res2，我们有：

apply(lambda, [y, x], env)

对于 apply，我们会先使用 eval_list 对其实参列表求值：

apply(lambda, eval_list([y, x], env), env)
--eval-->
apply(lambda,[eval(y, env), eval(x, env)],env)

对于符号求值则会去环境中寻找符号：

apply(lambda, [
  lookup(y, {x = 3.0, y = 2.0}),
  lookup(x, {x = 3.0, y = 2.0})], env)
--eval-->
apply(lambda, [2.0, 3.0], env)

然后 apply 将展开 lambda 对应的 closure：

apply(closure(|x, y| (x + y) * (x - y), env), [2.0, 3.0], env)

最后会根据传参生成新的环境，然后会 closure 求值：

closure((x + y) * (x - y), {x = 2.0, y = 3.0})
--eval-->
closure(5.0 * (-1.0), {x = 2.0, y = 3.0})
--eval-->
-5.0

不动点

对于一个方程组，如果我们能将其写成 <var> = <expr> 的形式， 那么就可以将 <expr> 看成是一个函数，或者说一个变换， 而这组方程的解就是这个变换的 不动点，例如：

$$\begin{array}{rl}x& =3-y\\ y& =x-1\end{array}$$

左边就可以看成是向量 $⟨x,y⟩$， 右边就可以看成是 $\mathcal{T}⟨x,y⟩$， 这个方程组的解就是 $\mathcal{T}$ 的不动点

对于递归函数，我们完全可以将其视为求不动点的过程，例如幂函数：

fn expt(x: u64, n: u8) -> u64 {
    if n == 0 { 1 } else { x * expt(x, n - 1) }
}

其运算结果可以看成是某个函数的不动点，即：

fn fix(g: Box<dyn Fn(u64, u8) -> u64>) -> impl Fn(u64, u8) -> u64 {
    move |x: u64, n: u8| -> u64 { if n == 0 { 1 } else { x * g(x, n - 1) } }
}

如果 g 是一个好的幂函数，那么 g(x, n - 1) 将返回 $x^{n-1}$ 的结果， 然后乘上 x，返回 $x^n$，即 f 的返回结果将是一个好的幂函数

可以发现 fix(Box::new(expt)) 与 expt 是等价的， expt 是 fix 的一个不动点

Y 组合子

但是要构造不动点，我们需要有能力构造无限调用， 在不直接使用递归的情况下，我们该怎么实现呢？

这里有一个最简单的无限循环的例子：

((lambda x x) (lambda x x))

这在 Rust 中无法构造，因为不允许递归类型

即接受一个函数，然后将这个函数自身作为参数传给函数，最后再应用上这个函数

基于这种思想，我们可以拓展一下 x 的功能，即：

(define Y
  (lambda (f)
    ((lambda (x) (f (x x)))
      (lambda (x) (f (x x))))))

其中内层就是上面的无限循环，但是加入了 f 作为循环的一部分，例如 (Y G)

(Y G)
;; =sub=>
((lambda (f)
    ((lambda (x) (f (x x)))
      (lambda (x) (f (x x)))))
  G)
;; =sub=>
((lambda (x) (G (x x)))
  (lambda(x) (G (x x))))
;; =sub=>
(G
  ((lambda (x) (G (x x)))
    (lambda (x) (G (x x)))))
;; =sub=>
(G
  (G
    ((lambda (x) (G (x x)))
      (lambda (x) (G (x x))))))
;; ...
;; (Y G) = (G (Y G))

这样，我们就可以无限调用我们的函数了

但并非所有函数都有其不动点，也就是并非所有函数都是有解的， 所以我们不能随意地对任意无限过程命名，找到其不动点， 因为这个不动点可能压根就不存在，例如：

$$\begin{array}{rl}v& =1+2+4+\cdots +2^n+\cdots \\ v-1& =2+4+8+\cdots +2^n+2^{n+1}+\cdots \\ \frac{v-1}{2}& =1+2+4+\cdots +2^n+\cdots \\ \therefore & \frac{v-1}{2}=v\\ \therefore & v=-1\end{array}$$

很明显这个结论是错误的

Lecture 7B

实现了求值器后，我们还需要想想该如何使用

随着用户的增加，基本功能必然是不太够用的， 这时候就需要给我们的求值器添加一些 功能（Features）， 这一部分的内容将围绕 “如何完善求值器？” 展开

变长参数列表

如果有使用过 LISP 就会发现，LISP 的某些函数的参数个数是不固定的， 例如 +，可以传入任意多参数来实现连加，那么这种任意参数的传递是如何实现的呢？

在 LISP 中，这十分自然，我们可以使用 cons 来实现，即传入一个列表，而非固定的参数

例如加法函数 +，最少需要两个参数， 那么可以记这两个参数为 x 和 y，其余的参数记为 z， 对于这个函数，就可以使用如下方法实现：

(define '+
  (lambda (x y . z)
    (cond ((is-empty? z) (add x y))
          (else (+ x (add y (car z)) (cdr z))))))

这里使用 add 表示最基本的，只接受两个参数的加法，以和我们这里的 + 区分

更进一步的，其实 list 函数可以使用类似方法定义：

(define list
  (lambda x x))

这里 x 就是参数列表的打包，利用了语言本身的性质， 这点 Python 就做得不错，使用了列表和字典的解包来支持变长参数列表， 而 Rust 为了确定函数类型，就没有对应支持，需要手动传入 HashMap 或者 Vec 这种容器作为替代， 但是 Rust 可以使用宏来做到类似的功能，例如：

macro_rules! addup {
    ($x:expr, $y:expr) => {
        $x + $y
    };
    ($x:expr, $y:expr, $($z:expr),*) => {{
        let mut sum = $x + $y;
        $(sum += $z;)*
        sum
    }};
}

fn main() {
    // let sum = addup!(1); // at least two argument
    let two_sum = addup!(1, 2);
    println!("1 + 2 = {}", two_sum);
    // 1 + 2 = 3
    let four_sum = addup!(1, 2, 3, 4);
    println!("1 + 2 + 3 + 4 = {}", four_sum);
    // 1 + 2 + 3 + 4 = 10
}

而在求值器层面支持这点，只需要修改 bind 中实参列表与参数列表的配对过程就可以了， 如果参数是一个符号，那么就匹配所有剩下的实参，即作为一个列表，

这将引入 Cons 类型，由于处理起来还算简单，这里就不做演示了

动态绑定

有时候我们需要在定义 $\lambda$-表达式的时候引入自由变量， 以支持不同环境下的函数支持，要实现这点非常简单，那就是使用动态绑定， 自由变量的值不再由定义的时候自动捕获，而是在执行时动态从环境中查找， 这个特性非常方便，但这样也会引入一个非常著名的 Bug

这个问题就是模块化问题，每个模块内部使用的名字不应该影响模块外部的调用， 但是使用动态绑定，如果我在模块内没有使用对应的名称， 而使用了其他名称来等价替代需要的自由变量，例如需要 n，但是我使用了 n 作为其他含义的变量， 那么这个时候运行结果就有可能会出错，因为找到这个变量并非真正需要的变量，对于一个封装好的模块而言这是不应该发生的问题

;; current module
(define n 5)
(define add-five
  (lambda (x) (+ x n)))
;; add-five ::= x + 5
(add-five 3) ;; => 8

;; other module
(define n 10)
(add-five 3) ;; => 13

对应到我们的实现中可以用如下方法测试：

fn main() {
    // (n = 5.0)
    let env = std::rc::Rc::new(std::collections::HashMap::from([(
        String::from("n"),
        Expression::Number(5.0),
    )]));
    // add_five = |x| x + n where n = 5
    let add_five = eval(
        Expression::Lambda(
            vec![Expression::Symbol(String::from("x"))],
            Box::new(Expression::Apply(
                Box::new(Expression::Symbol(String::from("add"))),
                vec![
                    Expression::Symbol(String::from("x")),
                    Expression::Symbol(String::from("n")),
                ],
            )),
        ),
        env.clone(),
    );
    // check current
    let test1 = eval(
        Expression::Apply(Box::new(add_five.clone()), vec![Expression::Number(3.0)]),
        env.clone(),
    );
    // (n = 10.0)
    let new_env = std::rc::Rc::new(std::collections::HashMap::from([(
        String::from("n"),
        Expression::Number(10.0),
    )]));
    // check new
    let test2 = eval(
        Expression::Apply(Box::new(add_five.clone()), vec![Expression::Number(3.0)]),
        new_env.clone(),
    );
    // test
    let is_equal = eval(
        Expression::Apply(
            Box::new(Expression::Symbol(String::from("eq"))),
            vec![test1, test2],
        ),
        env,
    );
    println!("should equal = {:?}", is_equal);
    // => should equal = Quote("true")
}

如果是动态绑定，那么就将返回 false

不过解决方法也很简单，那就是不再从环境中捕获 n，而是作为参数，即：

(define add-to
  (lambda (n)
          (lambda (x)
            (+ x n))))
(define add-five (add-to 5))
(define n 10)
(add-five 3) ;; => 8

因为参数的解析优先级要高于自由变量， 即如果环境中还有一个 n，但是由于我们显示传入了 5 作为 n 的绑定， 那么返回的过程中 n 就是我们传入的 5 而非环境中的那个 n

符号参数

有时候我们可能想要显式地延迟参数求值， 这时候就可以借鉴 ALGOL60¹ 的做法， 即对于函数参数，默认情况下将传递求值后的结果， 如果是一个符号参数，那么就传递对应实参的延迟求值

这个非常有意义，因为有时候我们可能无意中会写出如下代码：

(define unless
  (lambda (p f t)
          (cond ((not p) f)
                (else t))))
(unless (eq? 0 2) 2 (/ 2 0)) ;; error

在这里，由于参数会立即求值，(/ 2 0) 就会出现错误， 但是如果参数没有提前求值，而仅仅是替换，那么就不会有这个问题， 因为我们不会走到 else 分支，也就不会对 (/ 2 0) 求值

那么有一种方案是在定义时，对于需要延迟的部分加上 name 标签，即：

(define unless
  (lambda (p (name f) (name t))
          (cond ((not p) f)
                (else t))))

在求值器部分，我们只需要修改 apply 和 eval-list 以及 eval-cond， 在传递参数时判断是否是符号参数，如果是，那么到具体求值时再 force 求值即可

这部分不做演示，只需要添加一个 Named 类型即可

这一节实现了一个简单的 LISP 求值器， 我们完全可以把这个 DSL 作为某种 IR， 这样我们只需要设计对应的前端解析就可以实现一门语言

这一节最重要的并非具体的实现，而是体会在设计过程中的各种考量以及需求分析

下一节将会介绍有关逻辑式程序设计的相关内容