Scheme - 標準部品化力、オブジェクトおよび状態(可変データのモデル化(表の表現(局所表の作り方(レコード、二進木))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X El Capitan - Apple (OS)
• Emacs(Text Editor)
• Scheme (プログラミング言語)
• kscheme (github) (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の第3章(標準部品化力、オブジェクトおよび状態)、3.3(可変データのモデル化)、3.3.3(表の表現)、局所表の作り方、問題3.26.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
• Scheme手習い

問題3.26.

コード(Emacs)

(begin
  (define (print obj)
    (display obj)
    (newline))
  (define (for-each proc . lists)
    (define (exist-null? list-of-list)
      (if (null? list-of-list)
          #f
          (let ((lst (car list-of-list)))
            (if (null? lst)
                #t
                (exist-null? (cdr list-of-list))))))
    (define (heads list-of-list)
      (define (iter list-of-list)
        (if (null? list-of-list)
            '()
            (let ((lst (car list-of-list)))
              (if (not (pair? lst))
                  (display "error")
                  (cons (car lst)
                        (iter (cdr list-of-list)))))))
      (if (or (null? list-of-list)
              (exist-null? list-of-list))
          '()
          (iter list-of-list)))
    (define (rests list-of-list)
      (define (iter list-of-list)
        (if (null? list-of-list)
            '()
            (let ((lst (car list-of-list)))
              (if (not (pair? lst))
                  (display "error")
                  (cons (cdr lst)
                        (iter (cdr list-of-list)))))))
      (if (or (null? list-of-list)
              (exist-null? list-of-list))
          '()
          (iter list-of-list)))
    (define (iter list-of-list)
      (let ((args (heads list-of-list)))
        (if (null? args)
            '()
            (begin (apply proc args)
                   (iter (rests list-of-list))))))
    (if (null? lists)
        (display "error")
        (iter lists))
    ;; undefined
    (if #f #f))

  ;; ((key . value) left right)
  (define (make-table)
    (let ((local-table '()))
      (define (make-tree record left right) (list record left right))
      (define (key tree) (caar tree))
      (define (value tree) (cdar tree))
      (define (left-branch tree) (cadr tree))
      (define (right-branch tree) (caddr tree))
      (define (lookup-iter k tree)
        (cond ((null? tree) #f)
              ((= k (key tree)) (value tree))
              ((< k (key tree)) (lookup-iter k (left-branch tree)))
              (else (lookup-iter k (right-branch tree)))))
      (define (lookup k) (lookup-iter k local-table))
      (define (insert-iter! k v tree)
        (cond ((eq? tree '())
               (set! local-table (make-tree (cons k v) '() '()))
               'done)
              ((= k (key tree)) (set-cdr! (car tree) v)
               'done)
              ((< k (key tree))
               (if (null? (left-branch tree))
                   (set-car! (cdr tree) (make-tree (cons k v) '() '()))
                   (insert-iter! k v (left-branch tree)))
               'done)
              (else
               (if (null? (right-branch tree))
                   (set-car! (cddr tree) (make-tree (cons k v) '() '()))
                   (insert-iter! k v (right-branch tree)))
               'done)))
      (define (insert! k value) (insert-iter! k value local-table))
      (define (dispatch m)
        (cond ((eq? m 'lookup-proc) lookup)
              ((eq? m 'insert-proc!) insert!)
              (else (display "Unknown operation -- TABLE ")
                    (print m))))
      dispatch))
  
  (define operation-table (make-table))
  (define get (operation-table 'lookup-proc))
  (define put (operation-table 'insert-proc!))

  (for-each
   (lambda (pair)
     (print (put (car pair) (cdr pair))))
   (list (cons 5 'a) (cons 1 'b) (cons 4 'c) (cons 2 'd) (cons 3 'e)))

  ;; b d e c a #f
  (for-each (lambda (n)
              (print (get n)))
            '(1 2 3 4 5 10))
  
  (for-each
   (lambda (pair)
     (print (put (car pair) (cdr pair))))
   (list (cons 5 'A) (cons 1 'B) (cons 4 'C) (cons 2 'D) (cons 3 'E)))

  ;; B D E C A #f
  (for-each (lambda (n)
              (print (get n)))
            '(1 2 3 4 5 10))  
  )

入出力結果(Terminal(kscheme), REPL(Read, Eval, Print, Loop))

$ ./kscheme sample26.scm
done
done
done
done
done
b
d
e
c
a
#f
done
done
done
done
done
B
D
E
C
A
#f
$