Scheme - 正規順序と作用的順序(遅延評価と手続きunless)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.2(Scheme の変形 - 遅延評価)、4.2.1(正規順序と作用的順序)、問題 4.25を解いてみる。

その他参考書籍

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

問題 4.25

unlessの第2引数で無限ループ(永遠に再帰、実際には処理系の再帰の上限で止まる)が起きる。

評価の過程。

(factorial 5)

(* 5 (factorial 4))

(* 5 (* 4 (factorial 3))

…

(* 5 (* 4 (… (* 0 (factorial -1)))))

(* 5 (* 4 (… (* 0 (* -1 (factorial -2))))))

…

確認。

コード(BBEdit)

sample.scm

(define (unless condition usual-value exceptional-value)
  (if condition exceptional-value usual-value))

(define (factorial n)
  (unless (= n 1)
          (* n (factorial (- n 1)))
          1))

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

 ]=> (factorial 5)

;Aborting!: maximum recursion depth exceeded

作用的順序ではなく、正規順序の言語ではでのunlessの定義は動く。

評価の過程。

(factorial 5)

(unless (= 5 1) (* n (factorial (- n 1))) 1)

(if (= 5 1)
    1
    (* 5 (factorial (- 5 1))))

(* 5 (factorial (- 5 1)))

(* 5 (unless (= (- 5 1) 0)
             (* (- 5 1) (factorial (- (- 5 1) 1)))
             1))

(* 5 (if (= (- 5 1) 0)
         1
         (* (- 5 1) (factorial (- (- 5 1) 1)))))

(* 5 (* (- 5 1) (factorial (- (- 5 1) 1))))

(* 5 (* (- 5 1) (unless (= (- (- 5 1) 1) 0)
                        (* (- (- 5 1) 1)
                           (factorial (- (- (- 5 1) 1)
                                         1)))
                        1)))

(* 5
   (* (- 5
         1)
      (if (= (- (- 5 1) 1) 0)
          1
          (* (- (- 5
                   1)
                1)
             (factorial (- (- (- 5
                                 1)
                              1)
                           1))))))

(* 5
   (* (- 5
         1)
      (* (- (- 5
               1
            1))
         (factorial (- (- (- 5
                             1)
                          1)
                       1)))))

(* 5
   (* (- 5
         1)
      (* (- (- 5
               1
            1))
         (unless (= (- (- (- 5
                             1)
                          1)
                       1)
                    1)
                 (* (- (- (- 5
                             1
                          1)
                       1))
                    (factorial (- (- (- (- 5
                                           1)
                                        1)
                                     1)
                                  1)))
                 1)))

(* 5
   (* (- 5
         1)
      (* (- (- 5
               1)
            1)
         (if (= (- (- (- 5
                         1)
                      1)
                   1)
                1)
             1
             (* (- (- (- 5
                         1
                      1)
                   1))
                (factorial (- (- (- (- 5
                                       1)
                                    1)
                                 1)
                              1)))))))

(* 5
   (* (- 5
         1)
      (* (- (- 5
               1)
            1)
         (* (- (- (- 5
                     1
                  1)
               1))
            (factorial (- (- (- (- 5
                                   1)
                                1)
                             1)
                          1))))))
                       
(* 5
   (* (- 5
         1)
      (* (- (- 5
               1)
            1)
         (* (- (- (- 5
                     1
                  1)
               1))
            (unless (= (- (- (- (- 5
                                   1
                                1)
                             1)
                          1))
                       1)
                    (* (- (- (- (- 5
                                   1)
                                1)
                             1)
                          1)
                       (factorial (- (- (- (- (- 5
                                                 1)
                                              1)
                                           1)
                                        1)
                                     1)))
                    1)))))

(* 5
   (* (- 5
         1)
      (* (- (- 5
               1)
            1)
         (* (- (- (- 5
                     1)
                  1)
               1)
            (if (= (- (- (- (- 5
                               1)
                            1)
                         1)
                      1)
                   1)
                1
                (factorial (- (- (- (- (- 5
                                          1)
                                       1)
                                    1)
                                 1)
                              1)))                

(* 5
   (* (- 5
         1)
      (* (- (- 5
               1)
            1)
         (* (- (- (- 5
                     1
                  1)
               1))
            1))))

(* 5
   (* 4
      (* 3
         (* 2
            1))))

120