練習問題 (解答例)


1. 関数 func と整数 n を引数にとり、 f(0) + ... + f(n) を 計算する
     summation f n
を定義せよ
二通りつくってみました。まずは一つ目。
(define (summation-1 f n)
  (if (< n 0)
      0
      (+ (summation-1 f (- n 1))
	 (f n))))
これは、ほとんどそのまんま。つまり、(summation f -i) を 0 と定義し、 その後は再帰的な定義にしたがって、n >= 0に対し
      (summation-1 f n) = (+ (f n) (summantion-1 f (- n 1)))
と記述したものである。

もう一つは、map と apply を用いたもの。

(define (enumerate-interval begin end)
  (if (> begin end)
      '()
      (cons begin
	    (enumerate-interval (+ 1 begin) end))))

(define (summation-0 f n)
  (apply + (map f (enumerate-interval 0 n))))
整数列発生器を用いて、 (0 ... n) を生成し、次に map を用いて f(n)のリストを生成し、 最後に + を適用したものである。

問題にもどる

2. あるデータ構造 X は、X もしくは整数を要素とするリストであるとする。 X に含まれる全整数を平坦に並べたリスト Y を作る flatten をつくれ。 但し、 X 内での順序は保たれるものとする。
これについては、map と apply をもちいたものを載せておく。当然だが、 他の解もいろいろ存在する。 ということで、色々な flatten 関数の等価性をいうのは難しそうだと思って頂けたでしょうか?
(define (flatten expr)
  (if (list? expr)
      (apply append (map flatten expr))
      (list expr)))

問題にもどる

3. 以下の関数 fold (畳み込み関数)を定義せよ。

     fold f (x0 ... xn) b = (f x0 (f x1 (.... (f xn b)..)))
     fold f () b = b
また、fold をもちいて length を定義せよ。 また、sum = 1 + ... + n, prod = 1 * ... * n fold を用いて定義せよ。
fold 関数は上の定義から簡単に作ることが出来る。 この畳み込み関数は、リストの最後の要素から順々に (f item b) を計算し、その値を新たな b として、 その手前の要素に対して繰り返すということをしている。 つまり、length については、初期値 0 として、一要素毎に、 b の値を increment すれば良いだけである。
(define (fold f expr b)
  (if (null? expr)
      b
      (f (car expr) (fold f (cdr expr) b))))

(define (incB item b) (+ b 1))
(define (my-length expr) (fold incB expr 0))
また、 1 + .. + n がしたければ和の単位元 0 を初期値 b に設定し、 fとして + 演算を行えば良いのであり、 1 * .. * n がしたければ単位元 1 を初期値 b に設定し、 fとして * 演算を行えば良いだけである。
(define (my-sum expr) (fold + expr 0))
(define (my-prod expr) (fold * expr 1))

問題にもどる

4. 簡単な Scheme の式評価器を完成させよ。
難しかったか、以外に簡単だったか、こんなものでしょうと思うかは、 人それぞれでしょう。 この問題は、問題を解くことよりも evaluator というのは、 こんな感じに作れるのだと言うことを教えたかったので出しました。 続編ありです。

で、足りないのものを定義して行きましょう。 まずは、 prim-expr?, if-expr?, application? という 3 種類の expression を判定する関数。 この分類は、 expressions の定義に基づいて数字もしくは真偽値か、if 式か、関数の適用 の形をしているかを分類しています。


(define (prim-expr? expr)
  (or (number? expr) (boolean? expr)))

(define (if-expr? expr) 
  (and (list? expr)
       (eq? (car expr) 'if)
       (= 4 (length expr))))

; 但し、if 構文等の判定が終わった後使われる場合。
(define (application? expr) (list? expr)) 
次に、 cond/then/else-expr, operator, operands という if, application に関する selector の定義。

(define (cond-expr if-expr) (cadr if-expr))
(define (then-expr if-expr) (caddr if-expr))
(define (else-expr if-expr) (cadddr if-expr))

(define (operator expr) (car expr))
(define (operands expr) (cdr expr))
では、そろそろ evaluator の方について説明して行きましょう。 まずは、 eval-if eval-expr は、 if 文の場合は、 (eval-if cond-expr then-expr else-expr) を呼びます。 if 文の評価順序は、まず、 cond-expr を評価して、 その値に応じて then-expr もしくは else-expr を評価します。 これを そのまま記述すると以下のようになります。

(define (eval-if cond-expr then-expr else-expr)
  (if (eval-expr cond-expr)
      (eval-expr then-expr)
      (eval-expr else-expr)))
次に、関数の適用部について。 eval-expr では、まず関数部分と引数部分に切り分けて、 引数部分について評価(eval-arguments)をおこなっています。 つまり、 eval-arguents では、引数のリストを評価するわけです。 map をつかってもいいんですが、副作用がある場合のことも考え、 引数の評価順(すなわち第一引数から評価する)をまもるべく以下のように定義しています。
(define (eval-arguments operands) (eval-exprs-inorder operands))

(define (eval-exprs-inorder exprs) 
  (if (null? exprs)
      '()
      (cons (eval-expr (car exprs))
	    (eval-exprs-inorder (cdr exprs)))))

関数部分と引数の"値"が求まった時点で、関数の適用をおこないます。 apply-proc を呼び出します。 今回は組み込み関数しか使っていませんので、 apply-primitive-procedure を呼び出すことになります。 この中では、組み込み関数名に対応した Scheme の関数を primitive-procedure-to-scheme-primitive を使って求め、 引数の値に対して apply することで、 その組み込み関数を適用した値を求めています。


(define (apply-primitive-procedure procedure arguments)
  (apply (primitive-procedure-to-scheme-primitive procedure)
	 arguments))

これで、もう動くはずです。試してみましょう。

> (eval-expr '(+ (* 1 2 3 4) (- 10 2 3) 4))
33
> (eval-expr '(if (> 2 4) (* 8 9) 2))
2
この時点で、このScheme のサブセットが普通のSchemeに対して足りないものは、 大きく二つ、つまり変数(と値との束縛関係: 環境)とユーザ定義の関数です。

問題にもどる


99.10.7/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp