[Back]

4.1 元循环求值器

4.1

(define (list-of-values-left exps env)
    (if (no-oprands? exps)
        `()
        (let ((first-value (eval (first-oprand exps) env)))
            (cons first-value
                (list-of-values (rest-oprands exps) env)))))
(define (list-of-values-right exps env)
    (if (no-oprands? exps)
        `()
        (let ((rest-value (list-of-values (rest-oprand exps) env)))
            (cons (eval (first-oprand exps) env)
                rest-value))))

4.2

a) Louis的计划将会使得所有赋值和定义被看作过程应用,这将使整个eval无法奏效。实际上,特殊形式基本上会拥有更高的优先级,如果我们一定要用条件判定的写法来写求值器,那特殊形式一定要放在开头。

b) 只需要修改抽象过程

(define (application? exp) (tagged-list? exp `call))
(define (operator exp) (car (cdr exp)))
(define (operands exp) (cdr (cdr exp)))

4.3

(define (eval exp env)
    (if (self-evaluating? exp)
        exp
        (let ((proc (get 'eval (expr-type exp))))
            (proc (expr-body exp) env))))

4.4

(define (or? exp) (tagged-list? exp `or))
(define (and? exp) (tagged-list? exp `and))
(define (or-body exp) (cdr exp))
(define (and-body exp) (cdr exp))
(define (first-predicate exp) (car exp))
(define (rest-predicate exp) (car exp))
(define (eval-or clauses env)
    (if (null? clauses)
        #f
        (if (true? (eval (first-predicate clauses) env))
            #t
            (eval-or (rest-predicate clauses) env))))
(define (eval-and clauses env)
    (if (null? clauses)
        #t
        (if (false? (eval (first-predicate clauses) env))
            #f
            (eval-and (rest-predicate clauses) env))))

4.5

(define (cond-form-predicate clause) (car clause))
(define (cond-form-process clause) (car (cdr (cdr clause))))
(define (cond-form stream env)
    (if (null? (cdr stream))
        (if (eq? `else (cond-form-predicate (car stream)))
            (car (cdr (car stream)))
            #f)
        (let ((first (car stream))
             (second (cdr stream))
            (eval-value (eval (cond-form-predicate first) env)))
            (cond ((eq? eval-value `else) (display "ERROR ELSE isn't an end. --COND-FORM" first))
                  ((true? eval-value) ((cond-form-process first) eval-value))
                  (else (cond-form second env))))))

4.6

(define (let-variable-list exp) (car (cdr exp)))
(define (get-variable-list exp)
    (if (null? exp)
        `()
        (cons (car (car exp))
            (get-variable-list (cdr exp)))))
(define (get-arguments-list exp)
    (if (null? exp)
        `()
        (cons (cdr (car exp))
            (get-arguments-list (cdr exp)))))
(define (let->combination exp)
    (append (make-lambda (get-variable-list (let-variable-list exp))
        (car (cdr (cdr exp))))
        (get-arguments-list (let-variable-list exp))))

4.7

我们的求值环境模型告诉了我们,let是创建一个新的lambda环境来求值,要实现let*的效果,我们也就一定要创建相应的嵌套的环境结构。

(define (make-let variable-list)
    (list `let variable-list))
(define (let*->nested-lets exp)
    (let ((variable-list) (get-variable-list exp))
        (define (iter result exp)
            (cond ((null? (cdr exp)) (cons result (make-let (car exp))))
                  (else (iter (cons result (make-let (car exp)))
                            (cdr exp)))))
        (iter `() variable-list)))

4.8

实际上是再套了一层的let

4.9

(define (for? exp) (tagged-list? exp `for))
(define (for-to-lambda exp)
    (let ((predicate (cadr exp))
          (iter-function (caddr exp))
          (function (cadddr exp))
          (init-value (caddddr exp)))
    `((define (lamdba-func it)
        (cond (((not (predicate it)) `())
              (else (begin function (lambda-func (iter-function it)))))))
        (lambda-func init-value))))

Lisp with imperative(逃

4.10

与4.3重复

4.11

(define (make-frame variables values)
    (if (null? variables)
        `()
        (cons (cons (car variables) (car values))
            (make-frame (cdr variables) (cdr values)))))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
    (set! frame (cons (cons var val) frame)))

4.12

抽象模式就是对环境的遍历,因此我们可以将scan独立为一个过程

4.13

(define (make-unbound var env)
    (let ((frame (first-frame env)))
        (define (scan vars vals)
            (cond ((null? vars 
                    (display "No such variables in scope" var)))
                  ((eq? var (car vars)) (set-cdr! vals (cdr vals)) (set-cdr! vars (cdr vars)))
                  (else scan (cdr vars) (cdr vals))))
        (scan (frame-variables frame)
              (frame-values frame))))

根据作用域的原则,建议只删除当前框架里的变量绑定

4.14

在这里使用map的系统定义可能会造成以下的错误:

由于系统的map参数是任意的,一旦我们把它作为普通的过程来处理,就会发生不能正确接收参数的问题。

4.15

这个问题的表述就是图灵的停机问题。

对于try,我们求值它本身,如果它确实是可停止的,那么try又会执行下去,而如果try是不可停止的,那么我们的halted会使它停止。

形式化的表述为:

K = {(i, x) | program i halts when run on input x}

Prove K is undecidable.

4.16

((eq? var (car vars))  
    (if (eq? (car vals) '*unassigned*) 
        (error "variable is unassigned" var) 
        (car vals)))

安裝在make-procedure更好一些,這樣效率更高

4.17

这个额外的框架是let构建出来的。解决方法是文法替换将定义放在开头进行上下顺序解析

4.18

不可以,因为let语句是会求值的,一旦我们不延迟定义函数体,就会因找不到过程而错误。

4.19

在一个急切求值的MIT Scheme中,实现Eva的想法是非常困难的。

4.20

 (define (letrec? expr) (tagged-list? expr 'letrec)) 
 (define (letrec-inits expr) (cadr expr)) 
 (define (letrec-body expr) (cddr expr)) 
 (define (declare-variables expr) 
         (map (lambda (x) (list (car x) '*unassigned*)) (letrec-inits expr))) 
 (define (set-variables expr) 
         (map (lambda (x) (list 'set! (car x) (cadr x))) (letrec-inits expr))) 
 (define (letrec->let expr) 
         (list 'let (declare-variables expr)  
                (make-begin (append (set-variables expr) (letrec-body expr))))) 

本质是一个不能被求值的let 参考4.16

4.21

Magic Y combinator

((lambda (n)
    ((lambda (fib)
        (fib fib n))
        (lambda (body k)
            (cond ((= k 0) 0)
                  ((= k 1) 1)
                  (else (+ (body body (- k 1))
                            (body body (- k 2)))))))) 5)

(define (f x)
    ((lambda (even? odd?)
        (even? even? odd? x))
        (lambda (ev? od? n)
            (if (= n 0) true (od? ev? od? (- n 1))))
            (lambda (ev? od? n)
                (if (= n 0) false (ev? ev? od? (- n 1))))))

 (define Y-combinator 
   (lambda (f) 
     ((lambda (x) (x x)) 
      (lambda (x) (f (lambda (y) ((x x) y)))))))

4.22

((let? expr) (analyze (let->combination expr)))

4.23

这个程序在一个表达式的时候依然是有优势的,但是在两个及以上的时候,它会重复的执行递归和返回执行,这本质上是把执行的步骤放在了语法分析里做了,这样做会减慢速度。

4.24

由于我的MIT Scheme实现问题,暂时无法完成这道题目。