ソートするコードの生成(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関数だけでこのサイズというのが問題なのだろうか。