Schemeの課題 --- (5) 23-26

let, let*, letrec

	(let ((局所変数 初期値) ... ) 式1 ... 式n)
	(let* ((局所変数 初期値) ... ) 式1 ... 式n)
	(letrec ((局所変数 初期値) ... ) 式1 ... 式n)

これらは，ある限定されたスコープをもつ局所変数を定義するための特殊フォームである．

xⁿ(n ∈ N)は，次のように再帰的に定義することができる．

これを利用して，xⁿを計算する2引数関数pow2を定義せよ． なお，再帰呼び出しの回数をできるだけ減らすようにすること．

関数f(x)について，方程式f(x)=0の根を探す方法の一つに二分法がある． 二分法では，次の中間値の定理を用いる．

二分法の具体的なアルゴリズムは以下の通りである．

1. まず，f(x₀)f(x₁) < 0となる適当な初期値x₀,x₁を与える．
2. 区間[x₀,x₁]の中点x_mでの関数fの値と中間値の定理を利用することで， (少なくとも一つの)根が存在する範囲を区間[x₀,x₁]の半分に確定する ことができる．
3. そのような範囲が十分に狭いか，あるいは中点x_mでの関数の絶対値｜f(x_m)｜が十分に小さいとき，x_mを方程式の根とする．
4. そうでないときは，2,3の操作を繰り返すことで，範囲を徐々に狭めながら，方程式の根を探す．

二分法を利用して，λ式で表現される関数f(x)と，初期値x₀,x₁が与えられたとき，方程式f(x)=0の根を探す3引数関数half-interval-methodを定義せよ．また，これを利用して，次の方程式の根の一つであるπの近似値を求めてみよ．

  f(x) ≡ sin x = 0

なお，xの絶対値は(abs x)で得られる．また十分に小さい正の数は，次のように定義するとよい．

  (define eps 1.e-10) ;; eps = 10-10

注意: プログラム中でf(x₀)f(x₁) < 0として条件を判定すると， 実際には条件が満たされているにも関わらず， アンダーフローにより誤判定となる場合がある． これを避けるには， 例えばf(x₀) < 0かつf(x₁) > 0または...などと 記述する方法がある．

ループ do

	(do ((局所変数 初期値式 ステップ式) ... ) (終了条件式 式A1 ... 式An) 式B1 ... 式Bm)

doはループを行うための特殊フォームである．

動作は，まず各局所変数に初期値を代入する．初期値式のスコープはdoの外側と 同じである．その後，ループの部分に入る．

ループ中では，まず終了条件式を評価する．ループの中での変数のスコープはdo の外側の変数に，doで宣言された局所変数が新たに加わったものになる．終了条 件式の値が#f以外であれば，式A1 ... 式Anを評価し，式Anの値がdoの式全体の 値となる．n=0 の場合，すなわちループ終了時に評価される式がない場合には， doの式全体の値は不定値となる．終了条件が#f の場合には，式B1 ... 式Bmを評 価する．その後，各局所変数の値をステップ式により評価し，各変数に代入する． 以上を終了条件が満足されるまで繰り返す．

なお，初期値式やステップ式，式A1 ... 式Anの評価順序は，それぞれの中で不 定である．

また，doの式の中では，各局所変数の値をset!により変更することができる．一 般に(set! 変数名 式)は，評価される時にその変数名で参照される変数の値を式 の評価値に変更する．したがって他の場合にも使えるが，この動作は副作用その ものであり，関数型言語としてschemeのプログラムを作成する場合には，set!の 無制限な使用は望ましくない．しかし，doはそもそも手続き的な思考に基づいて プログラムを作成する場合に使用するフォームであり，doの式の中でset!を使用 するのは自然である．

例えば以下の6つのプログラムはどれも1から引数までの整数の和を求めるプログ ラムである．これらのうち，sum0は，再帰呼出を用いていて，授業でこれまで教 えてきた考え方に基づいて書かれたプログラムであり，副作用が用いられていず， 純粋に関数として動作するものになっている．ある意味で最もschemeらしい書き 方であるともいえる．

ところが，sum0は，doを用いたsum3,sum4,sum5のプログラムよりも効率が悪い． 再帰呼出の度にスタックの要素が積み上がるからである．この点を改良して，再 帰呼出を用いながらも，schemeの処理系によっては末尾再帰呼出の最適化を行う ことができ，ループ毎にスタックを積み上げなくても実行ができるようにしたの がsum1である．同じことをletrecを使って行ったのがsum2である．

sum1,sum2のような技法を用いられるならば，再帰呼出を行っていても，コンパ イルすればdoを用いた場合とほとんど同じ効率を得ることが可能である．しかし ながらプログラムの読みやすさということからいえば，sum1やsum2はややトリッ キーなプログラムの書き方にも思えるため，sum3などの方がわかりやすいプログ ラムかも知れない．

いずれも，動作速度やメモリ使用量を除けば同じ結果をもたらすプログラムであ る．しかし考え方や利用しているフォームが異なるものになっている．それぞれ を比較して，違いを理解して欲しい．

  (define (sum0 n)
      (if (= n 0) 0
          (+ n (sum0 (- n 1)))))

  (define (sum1 n)
      (define (sum n m)
          (if (= n 0) m
              (sum (- n 1) (+ n m))))
      (sum n 0))

  (define (sum2 n)
      (letrec
          ((sum (lambda (n m)
                    (if (= n 0) m
                        (sum (- n 1) (+ n m))))))
	  (sum n 0)))

  (define (sum3 n)
      (do ((s 0 (+ s n))
           (n n (- n 1)))
          ((= n 0) s)))

  (define (sum4 n)
      (do ((s 0))
          ((= n 0) s)
	  (set! s (+ s n))
	  (set! n (- n 1))))

  (define (sum5 n)
      (do ((i 0 (+ i 1))
           (s 0))
          ((= i n) (+ s i))
	  (set! s (+ s i))))

階乗を求める関数factを，doを使って書け． ただし以前の階乗計算の関数を定義する課題で do文を用いた者は今回は再帰呼出しにより求めるプログラムを提出すること．

破壊的リスト操作 set-car!, set-cdr!

	(set-car! 式1 式2)
	(set-cdr! 式1 式2)

set-car!とset-cdr!はconsセルの中身を書換える関数である．それぞれ，式1を 評価して得られたリストの最初のconsセルのcar部あるいはcdr部の中身を式2を 評価して得られたリストへのポインタに書換える．結果として，引数に与えたリ ストが破壊されることになる．

例:
	(define x '(a b))
	(define y '((1 2) (3 4)))
	(set-car! (cdr x) (cadr y))
とすると，xの値は
	(a (3 4))
となる．その後，
	(set-cdr! (cdr x) (car y))
とすると，xの値は
	(a (3 4) 1 2)
となる．

schemeは基本的には関数型プログラミングの考えに基づいてプログラムを書くよ うに設計されている．これは，副作用や状態の変化がない，あるいはできるだけ 目立たない形でプログラムを書くように設計されているということでもある． このことは，consセルについても同じであり，consやlistなどでconsセルを新た に利用した場合，セルの中身を書換えずに処理を行うようにプログラムを記述す る場合が多い．書換えの必要が生じた場合には，新たにconsセルを割り当てて， その際にセルの中身を書換えるようにしている．

しかし，効率を向上させたり，あるいは循環しているリストを用いたりする場合 など，ある種のプログラミング上の技法を用いる場合には，consセルの中身を書 換える必要が生じる．このような場合にはset-car!, set-cdr!を用いることにな る．

例えば，非常に大きいS式で表されるようなリストがあり，その一部を書換えた いとする．そのような場合に，書換え前のリストをその後には使用しないことが はっきりわかっていれば，該当部分のみをset-car!やset-cdr!などを使って書換 えればよい．そうしないと，consセルを大量に消費することになるであろう．

あるいは，使用するアルゴリズムによっては，循環しているリストを使う場合が ある．例えば，双方向リンクトリストを使用するアルゴリズムをschemeで素直に 実現すれば，当然循環リストを使うことになる．

ここでの説明からわかるようにset-car!やset-cdr!は通常は特別な目的のために 限定して用いるべきものであり，無制限に使用するとわかりにくいプログラムに なったり，原因を突き止めにくいBUGを引き起こすことになりかねない．

2つのリストを繋ぐ関数join!を，set-cdr!を使って書け．ただし，データ操作や 結果を表すためにconsセルを新たに消費してはならない(インタープリタによる プログラムの実行のためなどにconsセルを消費するのは可)．また，下の動作例 を参考にして，join! を使う際に気をつけるべきことを書け．

	==> (join! '(a b c d) '(e f g))
	(a b c d e f g)
	==> (join! '(a b c d) '())
	(a b c d)
	==> (join! '() '(e f g))
	(e f g)
	==> (define x '(a b c))
	==> (define y '(d e f))
	==> (define z '(1 2 3))
	==> x
	(a b c)
	==> y
	(d e f)
	==> z
	(1 2 3)
	==> (join! x y)
	(a b c d e f)
	==> x
	(a b c d e f)
	==> (join! y z)
	(d e f 1 2 3)
	==> x
	(a b c d e f 1 2 3)
	==> (join! z z)
	どうなるでしょうか?  <-- 「どうなるでしょうか?」と表示されるわけではありません．