SICP勉強会(2)

SICP勉強会2日目。図もいくつか描いたけど、アップするのが面倒くさい。

コードは次のような感じ。けっこう演習問題をはしょってる。

; 3.3.1 ---------------------------------------------------

(define (mystery x)
  (define (loop x y)
    (if (null? x)
      y
      (let ((temp (cdr x)))
        (set-cdr! x y)
        (loop temp x))))
  (loop x '()))

; ex 3.17
(define (exist? x ls)
  (cond ((null? ls) #f)
        ((eq? x (car ls)) #t)
        (else (exist? x (cdr ls)))))

(define (count-pairs ls)
  (define (inner ls visited)
    (cond ((not (pair? ls)) 1)
          ((exist? (car ls) visited) 0)
          (else (+ 1 (inner (car ls) (cons (car ls) visited))
                   (inner (cdr ls) (cons (car ls) visited))))))
  (inner ls ()))

; ex 3.18
(define (loop? ls)
  (define (iter ls visited)
    (cond ((null? ls) #f)
          ((exist? (car ls) visited) #t)
          (else (iter (cdr ls) (cons (car ls) visited)))))
  (iter ls ()))

; ex 3.19
(define (loop? ls)
  (define (iter xs ys)
    (cond ((null? ys) #f)
          ((null? (cdr ys)) #f)
          ((eq? xs ys) #t)
          (else (iter (cdr xs) (cddr ys)))))
  (if (null? ls)
    #f
    (iter ls (cdr ls))))

; 3.2.2 ---------------------------------------------------

(define (front-ptr queue) (car queue))

(define (rear-ptr queue) (cdr queue))

(define (set-front-ptr! queue item) (set-car! queue item))

(define (set-rear-ptr! queue item) (set-cdr! queue item))

(define (empty-queue? queue) (null? (front-ptr queue)))

(define (make-queue) (cons '() '()))

(define (front-queue queue)
  (if (empty-queue? queue)
    (error "FRONT called with an empty queue" queue)
    (car (front-ptr queue))))

(define (insert-queue! queue item)
  (let ((new-pair (cons item ())))
    (cond ((empty-queue? queue) (set-front-ptr! queue new-pair)
                                (set-rear-ptr! queue new-pair)
                                queue)
          (else (set-cdr! (rear-ptr queue) new-pair)
                (set-rear-ptr! queue new-pair)
                queue))))

(define (deloete-queue! queue)
  (cond ((empty-queue? queue) (error "DELETE! called with an empty queue" queue))
        (else (set-front-ptr! queue (cdr (front-ptr queue)))
              queue)))

; ex 3.20
;(define (print-queue queue)
; (car queue))

(define (print-queue queue)
  (define (iter ls)
    (cond ((null? ls) ())
          (else (display (car ls))
                (if (not (null? (cdr ls)))
                  (display ","))
                (iter (cdr ls)))))
  (display "<")
  (iter (front-ptr queue))
  (display ">\n"))

enclosing environmentについて大きな勘違いをしていたことがわかってよかった。

「enclosing environmentはcall stackにおいてひとつ下にあるenvironmentことではない」

C言語やC++のようにlexical closureのない言語だと、普通、environmentと戻り先をセットにしてスタックに積んでいく実装になっていて、スタックのひとつ下のenvironmentが必ずenclosing environmentになってるんだけど、Schemeや他のlexical closureのある言語ではそうなっているとは限らないらしい。