Scheme演習 第2回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治

再帰関数

> (define (fac n)
    (if (= n 0)
        1
        (* n (fac (- n 1)))))
> (fac 4)
24
> (fac 10)
3628800

関数のトレース

> (trace fac)
> (fac 3)
| > (fac 3)
| | > (fac 2)
| | | > (fac 1)
| | | | > (fac 0)
| | | | 1
| | | 1
| | 2
| 6
6
> (untrace fac)

詳しい再帰関数

> (define (fac n)
    (if (= n 0)
        1
        (* n (fac (- n 1)))))
> (trace fac)
(fac)
> (fac 2)
|(fac 2)
| (fac 1)
| |(fac 0)
| |1
| 1
|2
2

再帰の実行効率

> (fac 4)
; => (* 4 (fac 3))
; => (* 4 (* 3 (fac 2)))
; => (* 4 (* 3 (* 2 (fac 1))))
; => (* 4 (* 3 (* 2 (* 1 (fac 0)))))
; => (* 4 (* 3 (* 2 (* 1 1))))
; => (* 4 (* 3 (* 2 1)))
; => (* 4 (* 3 2))
; => (* 4 6)
24

末尾再帰(Tail Recursion)

> (define (fac-tail n multiplier)
    (if (= n 0)
        multiplier
        (fac-tail (- n 1) (* multiplier n))))
> (trace fac-tail)
(fac-tail)
> (define (fac2 n) (fac-tail n 1))
> (fac2 4)
|(fac-tail 4 1)
|(fac-tail 3 4)
|(fac-tail 2 12)
|(fac-tail 1 24)
|(fac-tail 0 24)
|24
24

詳しい末尾再帰

(define (fac-tail n multiplier)
  (if (= n 0)
      multiplier
      (fac-tail (- n 1) (* multiplier n))))

関数の評価順序

call by value
まず引数を先に評価し、その値を使って関数の 本体を評価する。
call by name
引数は評価せずに、関数の本体を評価し、引数を使って いるところに来たら、その引数も評価する。
> (define (p) (p))
> (trace p)
> (p)
| > (p)
| > (p)
| > (p)
| > (p)
*** INTERRUPTED IN ##procedure-name
1> ,d
> (define (test x y) (if (= x 0) 0 y))
> (test 0 (p))
^C*** INTERRUPTED IN p, (stdin)@26.14
1> ,d

シンタックス形式のつづき

define

lambda

注意

再帰関数の説明では「関数だけは自分自身を使って定義できる」と述べ、define,lambaの説明では「関数定義は変数定義のような形の省略形」と述べた。ここに疑問を感じる人も多いであろう。

本当は、「定義のときに自分自身を使えるのは、シンタックス形式lambdaの中だけ」(理由は第4回の環境モデルを参照)というのが正確であり、関数定義もその省略形だから自分自身を使えるのである。

値としての関数

整数 a から b までの和を求めるプログラムを考えてみよう。

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

次に、

    π/8 = 1/(1・3) + 1/(5・7) + 1/(9・11) + … 

を利用して π/8 の近似値(bの大きさによる)を求めるプログラムを考えてみよう。

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1 a (+ a 2)) (pi-sum (+ a 4) b))))

これらはいずれも次のような共通のパターンを持っている。ただし、上の二つの関数と照らし合わせてみると、(NEXT a)は基準となる整数aがどのように変化するかを表し、(TERM a)はそれぞれの項をそのaで表したものである。

(define (NAME a b)
  (if (> a b)
      0
      (+ (TERM a) (NAME (NEXT a) b))))

そこで、ひとつ共通の関数を作り、上のどちらにでも使えるようにしてみよう。

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a) (sum term (next a) next b))))

ここで、引数 term と next で受けとるものは関数(lambda(x) x)と関数(lambda (x) (+ x 1))である。

(define (sum-integers2 a b)
  (sum (lambda (x) x) a (lambda (x) (+ x 1)) b))
>(sum-integers2 1 4)
10
(define (pi-sum2 a b)
  (define (pi-term x) (/ 1 x (+ x 2)))
  (define (pi-next x) (+ x 4))
  (sum pi-term a pi-next b))
> (pi-sum2 1.0 1000.0)
.39244908194872286

関数 sum は、term と next を受けとって、新たな sum のバリエーション(関数)を返すもの、と見ることもできる。

そこで、次のようにしてみる。補助関数 loop の中で必要な term と next は loop の実行中に変化しないので、sum2 の引数を直接参照していることに注意。

(define (sum2 term next)
  (define (loop a b)
    (if (> a b)
        0
        (+ (term a) (loop (next a) b))))
  loop)

ここで sum2 は、中で定義された関数 loop をそのまま返している。

これを使うと、sum-integers は下のようになる。ここで、1 と 4 はloopの引数aとbに渡されている。

(define sum-integers3
  (sum2 (lambda (x) x) (lambda (x) (+ x 1))))
> (sum-integers3 1 4)
10

このように Scheme などの「関数型言語」では関数を引数として渡したり受け取ったりすることができる(高階関数)。

レポート課題2

問1(末尾再帰)

fibonacci 関数は次のように定義される。

ヒント

階乗関数は 2 項間漸化式で定義されていたので、ひとつ前の値(product)のみを持っていれば良かった。

しかし、fibonacci 関数は 3 項間漸化式で定義されているため、ひとつ前だけでなく、ふたつ前も必要となる。

iterative バージョンの関数の引数として、ひとつ前の値、ふたつ前の値、現在の count(と max-count)を受けとって、そこから、現在の値とひとつ前の値を計算してみよう。

時間計測関数

Gambit Schemeの場合
Gambit Scheme (Version 2.5.1) には time という関数があって、 実行時間を表示してくれる。例えば、(fib 10) の実行時間を計りたかっ たら (time (fib 10)) とすれば良い。
guileの場合
guileでは
> guile -s (Schemeスクリプト)
とするとスクリプトの実行ができるのでtimeコマンドを用いて
> time guile -s (Schemeスクリプト) とすれば良い

問2(if 文)

次のような新しい if 文を関数として定義した。

(define (new-if test then-exp else-exp)
  (cond (test then-exp)
        (else else-exp)))

例えば、(new-if (= 1 2) (+ 3 4) (+ 5 6)) などとすれば、正しく 11 を返す。(確かめてみよ。)

これを使って、fac4 を次のように定義した。

(define (fac4 n)
  (new-if (= n 0)
          1
          (* n (fac4 (- n 1)))))

これを使って (fac4 3) としたら、無限ループにおちいってしまった。(確かめてみよ。)これはなぜか。

問3(関数を返す関数)

関数 f(x) の導関数 f'(x) は、小さい数 dx を使って近似的に下のように表せる。

> (define (f1 x) (* x x))
> ((deriv f1 0.001) 5)
10.001000000002591

おさらいとヒント

一般の関数に対する Newton 法は、関数 f(x) とその導関数 f'(x) が与えられたとき、その零点の近似値を次の式で更新していく。

従って、f(an) と 0 との誤差が 0.001 以下になるまで、順に an を求めていく補助再帰関数を定義し、適当な初期値をその補助関数に与えてやればよい。