The King's Museum

ソフトウェアエンジニアのブログ。

Scheme 手習い(5)

第6章:影法師

numbered?

(define (numbered? aexp)
   (cond [(atom? aexp) #t]
         [(eq? '+ (car (cdr aexp)))
          (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))]
         [(eq? '* (car (cdr aexp)))
          (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))]
         [(eq? '^ (car (cdr aexp)))
          (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))]
         [else #f]))

渡された S 式が (1 + 1) のように演算子が中央にあるような表現式(算術式)かどうかを確認する関数。

aexp がアトムの場合には true。 aexp が演算子で構成されている場合は、それぞれの項が numbered? であるかを再帰的に調べる。

value

(define (value aexp)
  (cond [(atom? aexp) aexp]
        [(eq? '+ (car (cdr aexp)))
          (+ (value (car aexp)) (value (car (cdr (cdr aexp)))))]
        [(eq? '* (car (cdr aexp)))
          (* (value (car aexp)) (value (car (cdr (cdr aexp)))))]
        [(eq? '^ (car (cdr aexp)))
          (expt (value (car aexp)) (value (car (cdr (cdr aexp)))))]

aexp を評価する関数。

numbered? と似たような構造。ちがうのは実際の計算を行うところ。

第7の戒律

【第7の戒律】

性質を同じくするすべての構成部分について再帰すべし。

すなわち、

  • リストの全ての部分リストについて

  • 算術式のすべての部分式について

value2

(define (value aexp)
  (cond [(atom? aexp) aexp]
        [(eq? '+ (car aexp))
         (+ (value (car (cdr aexp))) (value (car (cdr (cdr aexp)))))]
        [(eq? '* (car aexp))
         (* (value (car (cdr aexp))) (value (car (cdr (cdr aexp)))))]
        [(eq? '^ (car aexp))
         (expt (value (car (cdr aexp))) (value (car (cdr (cdr aexp)))))]))

(+ 1 1) のように演算子が先頭にある場合の算術式を計算する関数。

最初の numbered? と異なるのは演算子や部分式を取得する car や cdr の部分のみ。

value3

算術式の表現として次のようなバリエーションが考えられる。

  • (+ 1 1)
  • (1 + 1)
  • (1 1 +)

変わるのは演算子の位置と部分式の位置だけ。 その部分を取得する関数を次のように抽象化できる。

  • 1つ目の部分式を取得する関数:1st-sub-exp
  • 2つ目の部分式を取得する関数:2nd-sub-exp
  • 演算子を取得する関数:operator
(define (value aexp)
  (cond [(atom? aexp) aexp]
        [(eq? '+ (operator aexp))
         (+ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))]
        [(eq? '* (operator aexp))
         (* (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))]
        [(eq? '* (operator aexp))
         (expt (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))]))

たとえば、(1 1 +) のような表現式の場合にはそれぞれの関数は次のようになる。

(define (1st-sub-exp aexp)
  (car aexp))
(define (2nd-sub-exp aexp)
  (car (cdr aexp)))
(define (operator aexp)
  (car (cdr (cdr aexp))))

第8の戒律

【第8の戒律】

表現から抽象化するに際し、補助関数を使用すべし。

数を空リストで表現する

ここからは数を空リストで表現した場合の演算を実装する。

たとえば、1 は (())、3 は (() () ()) で表現する。

sero?

(define (sero? n)
  (null? n))

zero? に対応する関数。空リストかどうかを調べる。

edd1

(define (edd1 n)
  (cons '() n))

add1 に対応する関数。空リストを一つ増やす。

zub1

(define (zub1 n)
  (cdr n))

sub1 に対応する関数。空リストを一つ少なくする。

+

(define (+ n m)
  (cond [(sero? m) n]
        [else (edd1 (+ n (zub1 m)))]))

足し算を定義する。

ただし、このケースでは lat? の条件を満たさない(たしかにその通りだが、、、)。

タイトルの「影法師」が何の比喩なのかは分からず…。

(c) The King's Museum