Scheme - 標準部品化力、オブジェクト及び状態(可変データでのモデル化(可変リスト構造(共有と同一)))

計算機プログラムの構造と解釈 第2版
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• Scheme (プログラミング言語)
• kscm (ksc、ksi)(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.1(可変リスト構造)、共有と同一、問題3.15、16、17、18、19.を取り組んでみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題3.15、16、17、18、19.

コード(Emacs)

(begin
  (define port (current-output-port))
  (define (p x) (display x port) (display #\newline port))
  (define (count-pairs x)
    (if (not (pair? x))
        0
        (+ (count-pairs (car x))
           (+ (count-pairs (cdr x))
              1))))

  (define (memq x list)
    (if (null? list)
        #f
        (if (eq? x (car list))
            list
            (memq x (cdr list)))))
  (p "3.16")
  (define three (list 1 2 3))
  (define four (list 1 2 3))
  (define seven (list 1 2 3))
  (define cycle (list 1 2 3))
  
  (p (count-pairs three))
  (p (count-pairs four))
  (p (count-pairs seven))  

  (display #\newline port)
  
  (set-car! four (cdr (cdr four)))
  (set-car! seven (cdr seven))
  (set-car! (cdr seven) (cdr (cdr seven)))
  (set-cdr! cycle cycle)
  
  (p (count-pairs three))
  (p (count-pairs four))
  (p (count-pairs seven))
  (display #\newline port)
  
  (p "3.17")  
  (define (count-pairs-1 x)
    (define visited '())
    (define (iter x)
      (if (or (not (pair? x))
              (memq x visited))
          0
          (begin
            (set! visited (cons x visited))
            (+ 1
               (+ (iter (car x))
                  (iter (cdr x)))))))
    (iter x))

  (p (count-pairs-1 three))
  (p (count-pairs-1 four))
  (p (count-pairs-1 seven))

  (display #\newline port)

  (p "3.18, 3.19")

  (define (cycle? list)
    (define (iter x y)
      (if (null? y)
          #f
          (if (eq? x y)
              #t
              (if (and (not (null? (cdr y))))
                  (iter (cdr x) (cdr (cdr y)))
                  #f))))
    (if (null? list)
        #f
        (iter list (cdr list))))

  (p (cycle? three))
  (p (cycle? four))
  (p (cycle? seven))
  (p (cycle? cycle))
  
  'done)

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

$ gmake -s sample && ./sample
=> compiled
3.16
3
3
3

3
4
7

3.17
3
3
3

3.18, 3.19
#false
#false
#false
#true
=> done
$