ソートするコードの生成(http://ja.doukaku.org/63/)

今どう書く.orgにアクセスできなくなってるみたいです。

Meta-Loopless Sortsの改題です．

n個の整数をソートするプログラムを生成するプログラム gensort を書いて下さい．条件は以下のとおり

1. 生成するプログラム，生成されたプログラムは同じ言語にして下さい．

2. 生成したプログラムはファイルに書き込んでください．

3. 生成されたプログラムでは最初に n 個の整数を読み込んで， n個の変数を初期化してください．「可能なら」変数名は，アルファベット 一文字で a，b，c … の順で使ってください．n = 5 なら 変数は a, b, c, d, e です．

4. 生成されたプログラムでは，if 文あるいは if 式で2つの変数を比較して いって，変数の順が確定したら，その順で変数の値を出力するようにして 下さい．

5. 生成される側のプログラムでのアルゴリズムやデータ構造を工夫する問題では ありません :)

出力プログラム例のPascalのプログラムが、大小関係を < だけで比較してるということは、引数のリストに同じ数値は含まれないということですかね。あと、「生成されたプログラムでは，if 文あるいは if 式で2つの変数を比較して いって」といことでしたが、下のコードでは一気に比較してます。反則かも。

;組合せを生成する関数
(defun combination (lst)
(let (combi)
(labels ((rec (l acc)
(if (null l)
(push acc combi)
(loop for e in l
collect (rec (remove e l) (cons e acc))))))
(rec lst nil)
combi)))
;ソート関数生成関数
; ソート対象は、同じ値は含まれないものとする。
(defun gensort-func (n)
(if (not (< 0 n 27)) (error "out of range. n is between 1 and 26."))
(let* ((arg-lst (loop for i from 1 to n collect (intern (string (code-char (+ 64 i))))))
(combinations (combination arg-lst)))
`(defun my-sort ,arg-lst
,@(loop for combi in combinations
collect `(if (< ,@combi)
(format t "~{~d~^,~}~%" (list ,@combi)))))))
;my-sort.lispへのソート関数の保存
(defun gensort (n)
(with-open-file (s "my-sort.lisp" :direction :output)
(prin1 (gensort-func n) s)))

計測用コード

;計測
(loop for lst in '((3 4)
(1 2 3)
(3 4 5 6)
(6 2 5 1 9)
(8 3 2 5 1 3)
(4 1 9 2 8 5 3)
(9 1 8 2 7 3 6 5)
(0 9 1 8 2 7 3 6 5)
(0 9 1 8 2 7 3 6 5 10))
do
(let ((len (length lst)))
(format t "=== ~d ~a===~%" len lst)
(format t "--gensort~%")
(time (gensort len))
(format t "--load function~%")
(time (load "my-sort.lisp"))
(format t "--exec~%")
(time (apply #'my-sort lst))))

defmacroで関数を生成して、生成された関数を呼出すのが普通なので、生成した関数を一度ファイルに保存するというのが、lisp的には奇妙な処理になってしまっています。

で、clisp上での実行結果(コンパイル済)は、途中で、「*** – Program stack overflow. RESET」となりました。要素数8の時の “my-sort.lisp” のロード中にstack overflowが出ました。この時点で、my-sort.lispの中身は、40,320行(2,985,984バイト)でした。1関数だけでこのサイズというのが問題なのだろうか。