日: 2014年1月16日

空リストで数を表現する

6章の最後に、空リストで数を表現するという面白いのが出てくる。
たとえば 0 は ()、1 は (())、2 は (() ()) という具合だ。この数の表現を使っていくつか関数を書いてみよう。
まずは、ゼロかどうかを調べる関数。

gosh> (define sero?
  (lambda (n)
    (null? n)))
sero?
gosh> (sero? '())
#t
gosh> (sero? '(()))
#f

つぎに、add1 に相当する関数。

gosh> (define edd1
  (lambda (n)
    (cons (quote ()) n)))
edd1
gosh> (edd1 '())
(())
gosh> (edd1 '(() ()))
(() () ())

sub1 に相当する関数。

gosh> (define zub1
  (lambda (n)
    (cdr n)))
zub1
gosh> (zub1 '(() ()))
(())
gosh> (zub1 '())
*** ERROR: pair required, but got ()
Stack Trace:
_______________________________________

ゼロ () に zub1 を適用したらエラーになった。0 以上の整数しか扱えないんだな。

算術式の別表現とvalue

6章の続き。算術式の別の表現というのが出てくる。この別の表現というのは次のようなもの。

  • 数
  • ＋の後に2つの算術式が続いたリスト
  • ×の後に2つの算術式が続いたリスト
  • ↑の後に2つの算術式が続いたリスト

この新しい算術式の値を求める関数 value を書け、と。
こんなのでどうだ。

(use mymodule)

(define value
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (car nexp) (quote e+))
      (o+ (value (car (cdr nexp))) (value (car (cdr (cdr nexp))))))
      ((eq? (car nexp) (quote e*))
      (o* (value (car (cdr nexp))) (value (car (cdr (cdr nexp))))))
      (else
        (o^ (value (car (cdr nexp))) (value (car (cdr (cdr nexp)))))))))

(print (value '(e+ 3 8)))
(print (value '(e+ (e* 3 6) (e^ 8 2))))

実行：

^o^ > gosh -I. value2.scm
11
82

うまくいったようだ。
さて、書いてみたコードを見ると、car や cdr が多すぎる。ここで、本（「Scheme手習い」）では、第1の算術式を求める 1st-sub-exp、第2の算術式を求める 2nd-sub-exp、演算子にあたる部分を求める operator を書き、これらを使って value を書き直せ、とある。やってみよう。

(use mymodule)

(define 1st-sub-exp
  (lambda (aexp)
    (car (cdr aexp))))

(define 2nd-sub-exp
  (lambda (aexp)
    (car (cdr (cdr aexp)))))

(define operator
  (lambda (aexp)
    (car aexp)))

(define value
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (operator nexp) (quote e+))
        (o+ (value (1st-sub-exp nexp)) (value (2nd-sub-exp nexp))))
      ((eq? (operator nexp) (quote e*))
        (o* (value (1st-sub-exp nexp)) (value (2nd-sub-exp nexp))))
      (else
        (o^ (value (1st-sub-exp nexp)) (value (2nd-sub-exp nexp)))))))

(print (value '(e+ 3 8)))
(print (value '(e+ (e* 3 6) (e^ 8 2))))

実行：

^o^ > gosh -I. value3.scm
11
82

うまくいった。

最後に、今書いたコードを、最初の算術式の表現、つまり演算子に当たるアトムが中置きに成っている算術式の表現に合うように直せるか、ときた。
これは簡単、1st-sub-exp と operator を書き直せばいい。

(define 1st-sub-exp
  (lambda (aexp)
    (car aexp)))

(define operator
  (lambda (aexp)
    (car (cdr aexp))))

value は書き直す必要がない。なぜなら、value は 1st-sub-exp、2nd-sub-exp、operator という3つの補助関数を使って抽象化されているからだ。こうやって抽象化しておけば、算術式の表現が変わっても補助関数を直すだけでいい、というわけだな。

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