SICP Exercise 4.21

November 25, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.21

; The evaluation proceeds as follows
((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)

;-->

((lambda (fact)
   (fact fact 10))
 (lambda (ft k)
   (if (= k 1)
       1
       (* k (ft ft (- k 1))))))

;-->

((lambda (ft k)
   (if (= k 1)
       1
       (* k (ft ft (- k 1)))))
 (lambda (ft k)
   (if (= k 1)
       1
       (* k (ft ft (- k 1)))))
 10)

;-->

(if (= 10 1)
    1
    (* 10 ((lambda (ft k)
             (if (= k 1)
                 1
                 (* k (ft ft (- k 1)))))
           (lambda (ft k)
             (if (= k 1)
                 1
                 (* k (ft ft (- k 1)))))
           9)))

;-->
(* 10 ((lambda (ft k)
         (if (= k 1)
             1
             (* k (ft ft (- k 1)))))
       (lambda (ft k)
         (if (= k 1)
             1
             (* k (ft ft (- k 1)))))
       9))

;......

The following expression computes the 10th Fibonacci number.

((lambda (n)
   ((lambda (fibo)
      (fibo fibo n))
    (lambda (fb k)
      (cond ((= k 0) 0)
            ((= k 1) 1)
            (else (+ (fb fb (- k 1))
                     (fb fb (- k 2))))))))
 10)

An alternative definition of f:

(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))))))

SICP Exercise 4.20

November 25, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.20

(define (eval exp env)
; ......
        ((letrec? exp) (eval (letrec->let exp) env))
; ......
)

(define (letrec? exp) (tagged-list? exp 'letrec))
(define (make-unassigned-letrec vars)
  (if (null? vars)
      '()
      (cons (list (car vars) ''*unassigned*)
            (make-unassigned-letrec (cdr vars)))))
(define (make-set-letrec vars exps)
  (if (null? vars)
      '()
      (cons (list 'set! (car vars) (car exps))
            (make-set-letrec (cdr vars) (cdr exps)))))
(define (letrec->let exp)
  (let* ((assi (let-assignment exp))
         (lvars (let-var assi))
         (lexps (let-exp assi)))
    (cons 'let (cons (make-unassigned-letrec lvars)
                     (append (make-set-letrec lvars lexps)
                             (let-body exp))))))

See SICP Exercise 4.6 for the definitions of let-assignment, let-body, let-var and let-exp.

I am going to skip the environment diagram. But I will explain why Louis Reasoner is wrong. Note that

  (let ((even?
         (lambda (n)
           <body of even? including call to odd?>)
        (odd?
         (lambda (n)
           <body of odd? including call to even?>)))
        <rest of body of f>))

is equivalent to

  ((lambda (even? odd?)
     <rest of body of f>)
   (lambda (n) <body of even? including call to odd?>)
   (lambda (n) <body of odd? including call to even?>))

There are three lambda functions in the above piece of code. The arguments even? and odd? of the first lambda function have no relationship whatsoever with odd? in the body of the second lambda function and even? in the body of the third lambda function. The way I see it, the arguments even? and odd? of the first lambda function are just names. We can rename them to foo and bar if we like. Therefore the above code will not work. Louis Reasoner is wrong.

SICP Exercise 4.19

November 13, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.19

I read the footnote of this exercise before I thought about this carefully. So I already knew the opinion of the authors of SICP. I guess they were right that it would be very hard to implement Eva’s view. The order of internal definitions has to been carefully rearranged. In the example, the definition of a should appear before that of b because b depends on a.

As for Ben’s view, his approach would make the language much less powerful.

SICP Exercise 4.18

November 13, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.18

Using the alternative strategy in this exercise for scanning out definitions, the solve procedure becomes

(define (solve f y0 dt)
  (let ((y '*unassigned*)
        (dy '*unassigned*))
    (let ((a (integral (delay dy) y0 dt))
          (b (stream-map f y)))
      (set! y a)
      (set! dy b))
    y))

Then converting the inner let to a lambda function gives

(define (solve f y0 dt)
  (let ((y '*unassigned*)
        (dy '*unassigned*))
    ((lambda (a b)
       (set! y a)
       (set dy b))
     (integral (delay dy) y0 dt)
     (stream-map f y))
    y))

We can see that this approach does not work because the evaluation of the second argument to the lambda function (stream-map f y) uses y, which is still *unassigned* at that time.

SICP Exercise 4.17

November 13, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.17

There is an extra frame in the transformed program because let will be converted to a call to a lambda function. Since that is the only difference, it is obvious that this difference should not make any difference in the behavior of a correct program.

To make the interpreter implement the “simultaneous” scope rule for internal definitions without constructing the extra frame, we can rearrange the order of the procedure body making sure internal definitions always appear before being called.

(define (rearrange-defines body)
  (let ((defs '())
        (others '()))
    (let scan-iter ((b body))
      (cond ((null? b)
             '())
            ((definition? (car b))
             (set! defs (append defs (list (car b)))))
            (else
             (set! others (append others (list (car b))))))
      (if (not (null? b))
          (scan-iter (cdr b))))
    (if (null? defs)
        body
        (append defs others))))

(define (make-procedure parameters body env)
  (list 'procedure parameters (rearrange-defines body) env))

SICP Exercise 4.16

November 11, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.16

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (if (equal? (car vals) "*unassigned*")
                 (error "Unassigned variable" var)
                 (car vals)))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

(define (scan-out-defines body)
  (let ((let-body '())
        (set-body '())
        (others '()))
    (let scan-iter ((b body))
      (cond ((null? b)
             '())
            ((definition? (car b))
             (let ((def-var (definition-variable (car b)))
                   (def-val (definition-value (car b))))
               (set! let-body (cons (list def-var ''*unassigned*)
                                    let-body))
               (set! set-body (cons (cons 'set! (list def-var def-val))
                                    set-body))))
            (else (set! others (append others (list (car b))))))
      (if (not (null? b))
          (scan-iter (cdr b))))
    (if (null? let-body)
        body
        (list (append (list 'let let-body) (append set-body others))))))

(define (make-procedure parameters body env)
  (list 'procedure parameters (scan-out-defines body) env))

;(define (procedure-body p) (scan-out-defines (caddr p)))

Procedure scan-out-defines can be installed either in make-procedure or in procedure-body. It is better to install it in make-procedure because it is more efficient. Note that make-procedure is called only once for each procedure, whereas procedure-body might be called multiple times.

SICP Exercise 4.15

November 8, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.15

The outcome of (try try) depends upon the result of (halts? try try). If (halts? try try) returns true (i.e., try halts on try), then (try try) will run forever. Otherwise it will halt. Thus halts? does not behave correctly in this case.

SICP Exercise 4.14

November 8, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.14

The map procedure takes another procedure (say foo) and lists as its arguments. If it is implemented as a primitive, the evaluator will eventually call

(apply-in-underlying-scheme map args)

Here args is a list with procedure foo as its first element. Unfortunately the foo procedure is now a tagged list even if the original foo procedure is a primitive. Therefore, this approach will not work. If the map procedure is implemented as a compound procedure, there will be no such issue.

This suggests that any procedure which takes other procedures as arguments has to be implemented as a compound procedure rather than a primitive in the underlying Scheme.

SICP Exercise 4.13

November 4, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.13

I think make-unbound! should remove only the binding in the first frame. Otherwise we could break another environment which is extended from the enclosing environment.

(define (make-unbound! var env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (error "Unbound variable -- MAKE-UNBOUND!" var))
            ((eq? var (car vars))
             (set-car! vars '())
             (set-car! vals '()))
            (else (scan (cdr vars) (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

SICP Exercise 4.12

November 3, 2009 in SICP, Scheme | Tags: , , | Leave a comment

SICP Exercise 4.12

(define (env-loop var null-action eq-action env)
  (define (scan vars vals)
    (cond ((null? vars)
           (null-action env))
          ((eq? var (car vars))
           (eq-action vals))
          (else (scan (cdr vars) (cdr vals)))))
  (if (eq? env the-empty-environment)
      (error "Unbound variable" var)
      (let ((frame (first-frame env)))
        (scan (frame-variables frame)
              (frame-values frame)))))
;
(define (set-variable-value! var val env)
  (define (null-action e)
    (env-loop var null-action eq-action (enclosing-environment e)))
  (define (eq-action vs)
    (set-car! vs val))
  (env-loop var null-action eq-action env))
;
(define (lookup-variable-value var env)
  (define (null-action e)
    (env-loop var null-action eq-action (enclosing-environment e)))
  (define eq-action car)
  (env-loop var null-action eq-action env))
;
(define (define-variable! var val env)
  (define (null-action e)
    (add-binding-to-frame! var val (first-frame e)))
  (define (eq-action vs)
    (set-car! vs val))
  (env-loop var null-action eq-action env))