Scheme - 手続きとその生成するプロセス(木構造再帰(再帰的プロセスを反復的プロセスに変換))

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

開発環境

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

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.2(木構造再帰)、問題 1.11.を解いてみる。

その他参考書籍

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

問題 1.11.

コード(BBEdit, Emacs)

sample.scm

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

;; 再帰的プロセス
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2
            (f (- n 2)))
         (* 3
            (f (- n 3))))))

;; 反復的プロセスに変換
(define (g n)
  (g-iter 2 1 0 n))

(define (g-iter a b c counter)
  (if (= counter 0)
      c
      (g-iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- counter 1))))

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

$ gosh
gosh> (load "./sample.scm")
#t
gosh> (f 1)
1
gosh> (f 2)
2
gosh> (f 3)
4
gosh> (f 4)
11
gosh> (f 5)
25
gosh> (f 10)
1892
gosh> (f 20)
10771211
gosh> (f 30)
61354575194
gosh> (f 40)
^C*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  n

  1  (f (- n 1))
        At line 8 of "./sample.scm"
  2  (f (- n 1))
        At line 8 of "./sample.scm"
  3  (f (- n 1))
        At line 8 of "./sample.scm"
  4  (f (- n 1))
        At line 8 of "./sample.scm"
  5  (f (- n 2))
        At line 10 of "./sample.scm"
  6  (f (- n 1))
        At line 8 of "./sample.scm"
  7  (f (- n 2))
        At line 10 of "./sample.scm"
  8  (f (- n 2))
        At line 10 of "./sample.scm"
  9  (f (- n 1))
        At line 8 of "./sample.scm"
 10  (f (- n 2))
        At line 10 of "./sample.scm"
 11  (f (- n 1))
        At line 8 of "./sample.scm"
 12  (f (- n 1))
        At line 8 of "./sample.scm"
 13  (f (- n 2))
        At line 10 of "./sample.scm"
 14  (f (- n 1))
        At line 8 of "./sample.scm"
 15  (f (- n 3))
        At line 12 of "./sample.scm"
 16  (f (- n 1))
        At line 8 of "./sample.scm"
 17  (f (- n 2))
        At line 10 of "./sample.scm"
 18  (f (- n 1))
        At line 8 of "./sample.scm"
 19  (f (- n 1))
        At line 8 of "./sample.scm"
 20  (f (- n 1))
        At line 8 of "./sample.scm"
 21  (f (- n 2))
        At line 10 of "./sample.scm"
 22  (f (- n 1))
        At line 8 of "./sample.scm"
 23  (f (- n 2))
        At line 10 of "./sample.scm"
 24  (f (- n 1))
        At line 8 of "./sample.scm"
 25  (f (- n 1))
        At line 8 of "./sample.scm"
 26  (f (- n 1))
        At line 8 of "./sample.scm"
 27  (f (- n 1))
        At line 8 of "./sample.scm"
gosh> (g 1)
1
gosh> (g 2)
2
gosh> (g 3)
4
gosh> (g 4)
11
gosh> (g 5)
25
gosh> (g 10)
1892
gosh> (g 20)
10771211
gosh> (g 30)
61354575194
gosh> (g 40)
349485574054925
gosh> (g 50)
1990726300381593467
gosh> (g 100)
11937765839880230562825561449279733086
gosh> (exit)
$