Scheme - 超言語的抽象(Scheme の変形 - 遅延評価(正規順序と作用的順序(手続きunlessと階乗)))

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

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: 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
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 4.25.

循環、無限ループ(再帰)になる。

順に評価して置き換えモデルでみる。

(factorial 5)

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

;; 第2引数の評価について
(* 5 (factorial 4))

(factorial 4)
(unless (= 4 1)
        (* 4 (factorial 3))
        1)
;; 第2引数の評価について
(* 4 (factorial 3))

(factorial 3)
(unless (= 3 1)
        (* 3 (factorial 2))
        1)
;; 第2引数の評価について
(* 3 (factorial 2))

(factorial 2)
(unless (= 2 1)
        (* 2 (factorial 1))
        1)
;; 第2引数の評価について
(* 2 (factorial 1))

(factorial 1)
(unless (= 1 1)
        (* 1 (factorial 0))
        1)
;; 第2引数の評価について
(* 1 (factorial 0))

(factorial 0)
(unless (= 0 1)
        (* 0 (factorial -1))
        1)
;; 無限に続く

確認。

コード(BBEdit, Emacs)

input.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

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

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

(print (factorial 5))

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

$ ./sample25.scm 
  C-c C-cgosh: "unhandled-signal-error": unhandled signal 2 (SIGINT)
$

正規順序の言語の場合、評価は

(factorial 5)

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

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

(if #f
    1
    (* 5 (factorial (- 5 1))))

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

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

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

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

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

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

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

(* 5
   (* 4
      (* 3
         (* 2
            (if (= (- (- (- (- 5 1) 1) 1) 1) 1)
                1
                (* (- (- (- (- 5 1) 1) 1) 1)
                   (factorial (- (- (- (- (- 5 1) 1) 1) 1) 1))))))))

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

120

となり、動く。