The Little Schemer 六章

The Little Schemer 六章の主題は抽象化。
(1 + 2) って式を (+ 1 2) と表すことだって可能だよね、と言う話から始めて、抽象化したプログラムの書き方を勉強していく一連の流れは見事。
最終的には(() () ())で３を表すような系を構築しようっていう話になる。原始的な表し方から記述を作っていくと言うところで思わずalohakunのマクロの話を思い出して見返したら、やはり最低次元から構築していくことについて書いてあった。計算論の授業でもやったけど、λ計算から順番に計算を作ってゆけるんだっていうことを追体験してるんだよなあ。
っていうのは実は４章の内容なんだけど、いま再確認した。
今回の主題は抽象化だから、Lispでプログラミングする際に上のレイヤは下の実装にかかわらず動作するように作ろう！というのがテーマだ。

以下、コードども。

;; 中置記法の式または単なる数字かどうかのチェック
(defun my-numbered? (aexp)
  (cond
   ((atom aexp)
    (numberp aexp))
   ((null (cdr aexp))
    (my-numbered? (car aexp)))
   ((or (equal (car (cdr aexp)) '*)
	(equal (car (cdr aexp)) '+)
	(equal (car (cdr aexp)) '^))
    (and (my-numbered? (car aexp))
	 (my-numbered? (cdr (cdr aexp)))))
   (t nil)))

;; Little Schemerの方のnumbered?
(defun numbered? (aexp)
  (cond
   ((atom aexp) (numberp aexp))
   (t
    (and (numbered? (car aexp))
	 (numbered? (car (cdr (cdr aexp))))))))

;; 中置記法をevaluateする関数。和・乗・べき計算に対応。
;; ツリー構造にも耐える作りですよ！
(defun my-value* (nexp)
  (cond
   ((atom nexp) nexp)
   ((null (cdr nexp)) (my-value (car nexp)))
   (t (cond ((equal (car (cdr nexp)) '*)
	     (* (my-value (car nexp))
		(my-value (cddr nexp))))
	    ((equal (car (cdr nexp)) '+)
	     (+ (my-value (car nexp))
		(my-value (cddr nexp))))
	    ((equal (car (cdr nexp)) '^)
	     (^ (my-value (car nexp))
		(my-value (cddr nexp))))))))

;; 準備。テーマとは関係ないよ。
(defun eq? (a1 a2)
  (equal a1 a2))
(defun ^ (num1 num2)
  (cond
   ((zero? num2) 1)
   ((one? num2) num1)
   (t
    (* num1 (^ num1 (sub1 num2))))))
(defun sub1 (num)
  (- num 1))
(defun zero? (num)
  (eq num 0))
(defun one? (num)
  (eq num 1))

;; 前置記法の式の条件
(defun 1st-sub-exp (aexp)
  (car (cdr aexp)))
(defun 2nd-sub-exp (aexp)
  (car (cdr (cdr aexp))))
(defun operator (aexp)
  (car aexp))

;; 抽象化を用いて書き直されたvalue
(defun value (nexp)
  (cond
   ((atom nexp) nexp)
   ((eq? (operator nexp) '+)
    (+ (value (1st-sub-exp nexp))
       (value (2nd-sub-exp nexp))))
   ((eq? (operator nexp) '*)
    (* (value (1st-sub-exp nexp))
       (value (2nd-sub-exp nexp))))
   ((eq? (operator nexp) '^)
    (^ (value (1st-sub-exp nexp))
       (value (2nd-sub-exp nexp))))))

;; 中置記法の式の条件
;; valueは変えなくていいわけです
;; ちなみに2ndも変えなくていいんだけど、
;; 後置記法との切り替えも考えて一応含めておく
(defun 1st-sub-exp (aexp)
  (car aexp))
(defun 2nd-sub-exp (aexp)
  (car (cdr (cdr aexp))))
(defun operator (aexp)
  (car (cdr aexp)))

;; (() () ()) represents for 3
;; つまり、カッコを三つ並べたの(nil nil nil)が
;; ３を表すような抽象化をしてみろ、っていうのが主題
;; 以下、そのための幾つかの実装をするという流れ。
(defun sero? (n)
  (null n))
(defun edd1 (n)
  (cons nil n))
(defun zub1 (n)
  (cdr n))
(defun re+ (n m)
  (cond
   ((sero? m) n)
   (t (edd1 (re+ n (zub1 m))))))

そんな感じ。
+と*と^とかの、どう見てもそっくりな動作をさせてるところとかは、マクロにするのが良いんじゃないかなーと思った。関数渡してまんま評価させれば良いとかそういう話かも。試してないゴメン。

今回ははてな記法に邪魔されることが多いなぁ。文頭に+でリストになるとか、二つの半角カッコで註釈になるとか。ちなみに半角カッコは ( で記述できる模様。便利。
エスケープシーケンスについての参考記事：はてな記法におけるエスケープシーケンスの利用 - 自己否定回路 〜駄目サークルの駄目Blog〜