１０月２日火曜日、晴れ

自作の LISP インタープリターに、これまた本やネットを見ながらあれこれこねくりまわした順列生成プログラムを入れてみる。

(set (quote concat)
 (lambda (xss) (cond
   ((atom xss) xss)
   ((quote else) (append (car xss) (concat (cdr xss)))))))

(set (quote append)
 (lambda (xs ys) (cond
   ((atom xs) ys)
   ((quote else) (cons (car xs) (append (cdr xs) ys))))))

(set (quote ins)
 (lambda (x ys) (cond
   ((atom ys) (cons (cons x ()) ()))
   ((quote else) (cons (cons x ys) (map (lambda (xs) (cons (car ys) xs))
                                        (ins x (cdr ys))))))))

(set (quote map)
 (lambda (f xs) (cond
   ((atom xs) xs)
   ((quote else) (cons (f (car xs)) (map f (cdr xs)))))))

(set (quote perm)
 (lambda (xs) (cond
   ((atom xs) (cons xs ()))
   ((quote else) (concat (map (lambda (xs') (ins (car xs) xs'))
                              (perm (cdr xs))))))))

しかし無念。

個別に動かしてみる限りで concat や map は動いているのだけれど、肝心の perm がバグっている。つまり、リストの結合 concat は

> (concat (quote ((1 2) (3 4) (5 6))))
(1 2 3 4 5 6)

となるし、リストへの関数適用 map は

> (map (lambda (x) (cons x ())) (quote (1 2 3)))
((1) (2) (3))

と、ちゃんと動く。

しかし順列生成 perm は……

> (perm ())
(())
> (perm (quote (1)))
((()))
> (perm (quote (1 2)))
(((()) ()) (() (())))
> (perm (quote (1 2 3)))
((((()) ()) (()) ()) ((()) ((()) ()) ()) ((()) () ((()) ())) ((() (())) () (())) (() (() (())) (())) (() (()) (() (()))))

見た目はちょっと違うけれど、オンラインの Scheme 評価器でチェックすると、動くのよねー。

そして生成された結果を見た感じ、 perm の lambda のパラメーター xs の束縛が余計に評価されている？

> (perm (quote (1)))
((()))

これに関しては () を 1 と読み替えると ((1)) で、

> (perm (quote (1 2)))
(((()) ()) (() (())))

こちらは (()) が 1、 () が 2 だとおもうと ((1 2) (2 1))。
そして、あれ？　(perm '(1 2 3)) はちょっと違うな……

> (perm (quote (1 2 3)))
((((()) ()) (()) ()) ((()) ((()) ()) ()) ((()) () ((()) ())) ((() (())) () (())) (() (() (())) (())) (() (()) (() (()))))

(((()) ()) (()) ())
((()) ((()) ()) ())
((()) () ((()) ()))
((() (())) () (()))
(() (() (())) (()))
(() (()) (() (())))

ええと、 ((()) ()) が 1、 (()) が 2、 () が 3 か。(1 2 3) (2 1 3) (2 3 1)、あれ？　違うな。後半は (() (())) が 1 相当だ。

まあともかく、いまのところわかっているのは、正しく動いていないということだ。ちゃんと原因を突き止めてなおしたい。