Scheme演習 第2回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治
[Table of Contents] [Index] [携帯版]

再帰関数
  • 変数を定義するときとは違い、関数を定義するときには未定義の変数や関数を本体で使用できる。それらは関数を実際に使用するときまでに定義されていれば良い。
  • このことを利用し、自分自身を使用して定義されている関数を再帰関数と言う。
  • 下記は n の階乗を求める関数 (fac n) である
> (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)
  • traceができない処理系ではslibのtraceを使うと良い
    ( Gaucheの場合は (use slib) として (require 'trace) とする)
  • 再帰関数についてもっと詳しく
  • 再帰の実行効率へ

詳しい再帰関数
> (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 n) で (fac 2) が呼ばれた場合
    • (= 2 0) は #f なので 2 * (fac 1) を求める
    • (fac 1)を求める
      • (= 1 0) は #f なので 1 * (fac 0) を求める
      • (fac 0)を求める
        • (= 0 0) は #t なので 1 を返す
      • 1 * (fac 0) = 1 を返す
    • 2 * (fac 1) = 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
  • 上で定義した fac では例えば (fac 4)を計算する時 4 * (fac 3) を返すので (fac 3) を計算する間も

    (fac 3)で求まる結果に 4 を掛ける

    という処理を行うためのスペースが必要であり、実行効率が悪い
  • 具体的には(fac n) を呼び出した際に n に比例したスペースを使う
    • ここでいうスペースとは、「残っている計算」を計算機が覚えておくためのスペースのことである。

末尾再帰(Tail Recursion)
  • (fac-tail n multiplier) は !n × multiplier を返す関数である
> (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
  • fac-tail では 計算を残さずに再帰的に関数を呼び出している様子がわかる
  • fac-tail のように関数の末尾で再帰呼び出しをすることを末尾再帰と言う
  • 末尾再帰呼び出しでは、「残っている計算」というものが無いので、実行効率がよい
  • 注意事項
    • 本来は fac-tail は fac2 の内部関数として記述すべきだが、今回は説明のため別々に定義した
    • また、可読性は末尾再帰の方が悪い場合が多い
  • 末尾再帰についてもっと詳しく
  • 関数の評価順序へ

詳しい末尾再帰
  • 末尾再帰で記述すると実行効率が良くなるのは Schemeの処理系が 末尾再帰呼び出しをループに変換してくれるからである
(define (fac-tail n multiplier)
  (if (= n 0)
      multiplier
      (fac-tail (- n 1) (* multiplier n))))
  • この fac-tail では末尾の fac-tail の呼び出しの際に引数の値だけ(n を (- n 1) に, multiplier を (* multiplier n) に)変えて同じ関数を実行するというループに変換される
  • より詳しくは なんでも再帰 あたりを参照

関数の評価順序
  • そもそも関数の評価順序には大きく分けて二種類ある。
call by value
まず引数を先に評価し、その値を使って関数の 本体を評価する。
call by name
引数は評価せずに、関数の本体を評価し、引数を使って いるところに来たら、その引数も評価する。
  • 今、関数 p を次のように定義したとする。引数は無い。
    • これは自分自身を必ず呼ぶ関数であり、実行が停止しない。
> (define (p) (p))
> (trace p)
> (p)
| > (p)
| > (p)
| > (p)
| > (p)
*** INTERRUPTED IN ##procedure-name
1> ,d
  • さらに、関数 test を次のように定義したとする。
    • これは引数 xが 0 ならば 0 を返し、引数 yは使用されない。
> (define (test x y) (if (= x 0) 0 y))
  • しかし下の実行例からわかるように、引数 yとしてpの実行結果を与えると、停止しなくなる。
> (test 0 (p))
^C*** INTERRUPTED IN p, (stdin)@26.14
1> ,d
  • このことから、Scheme では call by value を採用していることがわかる。
  • 一方、if などのシンタックス形式は、独自の評価順序を採用しており、必ずしも全ての引数を評価しない。

シンタックス形式のつづき
  • 関数適用では call by value に従ってあらかじめ全部の引数を評価するが、そうしないで特殊な処理をするのがシンタックス形式である。
  • 今回は以下のシンタックス形式を説明する
    • define
    • lambda

define
  • define
    • 関数を定義するときは
    (define (<変数> ...) <式> ...)
    
      この第2の形式は、実は
    (define <変数> (lambda (...) <式> ...))
    
      の省略形。
    • この二つの形式の違いは、下の表現の違いのようなもの。
    (define (f x) (+ x 1))
    (define f (lambda (x) (+ x 1)))
    
    f(x) = x + 1
    f: x |-> x + 1
    

lambda
  • lambda
    • 関数を作るシンタックス形式。形式は
    (lambda (<変数> ...) <式> ...)
    
    • これで、パラメタとして (<変数> ...) を受けとったら、<式> ... を順番に評価し、最後の値を返り値として返す関数を返す。
    • パラメタはなくても良い。(その場合は (lambda () <式> ...) という形式になる。)
    • 例えば、
    (lambda (x y) (write x) (display " ") (+ x y))
    
      は x と y をパラメタとして受けとり、x の値を表示した後に、空白を表示して、x+y を返す関数。
    • これ自体が関数なので、今までの関数の様に名前を付けなくても、直接引数を与えて実行させることができる。
    > (define add (lambda (x y) (write x) (display " ") (+ x y)))
    > (add 1 2)
    1 3
    > ((lambda (x y) (write x) (display " ") (+ x y)) 1 2)
    1 3
    

注意

再帰関数の説明では「関数だけは自分自身を使って定義できる」と述べ、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 関数は次のように定義される。

  • この定義をそのまま使って関数 (fib1 n) を作れ。
  • 末尾再帰を使って、n に対して線形の時間で求める関数 (fib2 n) を作れ。その際、ブロック構造を用いて、トップレベルに定義する関数は fib2 のみとせよ。
  • ふたつのプログラムを同じ引数で実行してみて、時間を比較せよ。さらにその時間の違いの理由について考察せよ。

ヒント

階乗関数は 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 を使って近似的に下のように表せる。

  • 1 引数関数 f と小さい数 dx を受けとったら、その導関数を返すような関数 deriv を作れ。
    • すなわち、((deriv f dx) n) のように実行すると、結果として f'(n) の値を返す。
> (define (f1 x) (* x x))
> ((deriv f1 0.001) 5)
10.001000000002591
  • Newton 法を使って、1 引数の関数 f が与えられた時にf(x) = 0 の実数解を1つ求めるプログラムを作れ。精度は、f(x) と 0 の差の絶対値が 0.001 以下とする。
    • 用いる dx は0.001とする。
    • 実際に、f(x) = x2 - 4 やその他の関数に対して適用してみよ。

おさらいとヒント

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

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



This page is generated by mtd2html.