庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理
    当将用scheme写的scheme求值器跑起来的时候,你不觉的兴奋是不可能的,真的太酷了,太magic了。
习题4.2,如果将application?判断放在define?判断之前,那么求值(define x 3)将把define当作一般的procedure应用于参数x和3,可是define是特殊的语法形式,而非一般过程,导致出错。
习题4.4,我的解答,eval增加两个判断:
 ((and? exp)
   (eval
-and (and-exps exp) env))
 ((or
? exp)
   (eval
-or (or-exps exp) env))
实现谓词和各自的过程:
(define (and? exp) 
  (tagged
-list? exp 'and))
(define (and-exps exp)
  (cdr exp))
(define (eval
-and exps env)
  (cond ((
null? exps)
          
'true)
        (else
          (let ((result (eval (car exps) env)))
            (
if (not result)
                result
                (eval
-and (cdr exps) env))))))
(define (or
? exp)
  (tagged
-list? exp 'or))
(define (or-exps exp) (cdr exp))
(define (eval
-or exps env)
  (cond ((
null? exps)
         
'false)
        (else
         (let ((result (eval (car exps) env)))
           (
if result
               result
               (eval
-or (cdr exps) env))))))

如果用宏实现就简单了:
(define-syntax and
  (syntax
-rules ()
      ((_) #t)
      ((_ e) e)
      ((_ e1 e2 e3 )
        (
if e1 (and e2 e3 ) #f))))
(define
-syntax or
   (syntax
-rules ()
             ((_) #f)
             ((_ e) e)
             ((_ e1 e2 e3 )
              (let ((t e1))
                  (
if t t (or e2 e3 ))))))

习题4.5,cond的扩展形式,也不难,在else子句之外增加个判断,是否带有=>符号,修改expand-clauses过程:
(define (cond-extended-clauses? clause)
  (and (> (length clause) 2) (eq? (cadr clause) '=>)))
(define (extended-cond-test clause)
  (car clause))
(define (extended-cond-recipient clause)
  (caddr clause)
(define (expand
-clauses clauses)
  (
if (null? clauses)
      
'false
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (cond ((cond
-else-clauses? first)
                (
if (null? rest)
                    (sequence
->exp (cond-actions first))
                    (error 
"else clause is not LAST" clauses)))
              ((cond
-extended-clauses? first)  ;判断是否扩展形式
               (make
-if
                   (extended
-cond-test first)
                    (list
                      (extended
-cond-recipient first)
                      (extended
-cond-test first))
                      (expand
-clauses rest)))
              (
else
               (make
-if (cond-predicate first)
                        (sequence
->exp (cond-actions first))
                        (expand
-clauses rest)))))))

习题4.6,let如果用宏定义,类似这样:
(define-syntax let
  (syntax
-rules ()
    ((_ ((x v) ) e1 e2 )
     ((
lambda (x ) e1 e2 ) v ))))
求值器扩展,实现let->combination过程:
(define (let? exp)
  (tagged
-list? exp 'let))
(define (let->combination exp)
  (let ((vars (map car (cadr exp)))
        (vals (map cadr (cadr exp)))
        (body (caddr exp)))
  (cons (make
-lambda vars (list body)) vals)))
我们做的仅仅是syntax transform,将let转成对应的lambda形式。

习题4.7,这里的关键在于let*->netsted-lets要递归调用,从let*的宏定义可以看出:
(define-syntax let*
     (syntax
-rules()
       ((_ ((var1 val1)) e1 )
        (let ((var1 val1)) e1 ))
       ((_ ((var1 val1) (var2 val2) ) e1 )
        (let ((var1 val1))
          (let
* ((var2 val2) )
            e1 )))))
那么,let*->nested-lets可以定义为:
(define (let*? exp)
  (tagged
-list? exp 'let*))
(define (let*->nested-lets exp)
     (let ((pairs (cadr exp))
           (body (caddr exp)))
       (
if (null? (cdr pairs))
           (list 
'let pairs body)
           (list 'let (list (car pairs)) (let*->nested-lets (list 'let* (cdr pairs) body))))))
测试一下:
(let* ((x 1) (y (+ x 3))) (+ x y)) =》5

习题4.8,命名let,修改let->combination过程,判断cadr是pair还是symbol,如果是前者,那就是一般的let,如果是symbol就是命名let语句,那么需要定义一个名为(cadr exp)的过程放在body里,注意,我们是在做语法转换,因此,这个定义也应该描述成符号,定义一个make-define过程来生成define语句:
(define (make-define var parameters body)
  (list 
'define (cons var parameters) body))
然后修改let->combination过程,如上所述:
(define (let->combination exp)
  (
if (symbol? (cadr exp))
      (let ((var (cadr exp))
            (vars (map car (caddr exp)))
            (vals (map cadr (caddr exp)))
            (pairs (caddr exp))
            (body (cadddr exp)))
        (cons (make
-lambda vars (list (make-define var vars body) body)) vals))
      (let ((vars (map car (cadr exp)))
            (vals (map cadr (cadr exp)))
            (body (caddr exp)))
              (cons (make
-lambda vars (list body)) vals))))


习题4.1.4,原生的map过程接受的procedure,是以scheme内在数据结构表示的procedure,而在我们的求值器中,procedure的内在数据结构取决于我们,与原生的结构不同,导致原生的map无法接受自制求值器的procedure,如果map也以求值器中的结构定义,那么就没有这个问题。因此,本质上的困难就在于两个求值器对procedure的数据结构表示的不同。

习题4.1.5,著名的图灵停机问题,先是假设存在halts?过程可以正确地判断任何过程p和对象a是否p对a终止,定义了try过程:
(define (try p)
   (if (halts? p p)
       (run-forever)
        'halted))
当执行(try try),如果这个过程可终止,那么(halts? try try)应该返回false,也就是try过程对try不会终止,这与一开始的假设矛盾;如果这个过程将无穷运行下去,那么(halts? try try)应该返回true,也就是try对try终止,这也与(try try)将无穷运行的假设矛盾。因此,可以推论出,我们不可能写出一个过程halts?,使它能正确地判断任何过程p和对象a是否p对a终止。


只有注册用户登录后才能发表评论。


网站导航: