Ex. 4.50
p.258 analyze-amb を改造する。選択肢のリストをランダムにシャッフルする。
(use gauche.sequence) (define (ramb? exp) (tagged-list? exp 'ramb)) ; 追加 (define (ramb-choices exp) (shuffle (cdr exp))) ; 追加。選択肢のリストをシャッフルする。 ;;; p.258 analyze-amb とほぼ同じ (define (analyze-ramb exp) ; 追加 (let ((cprocs (map analyze (ramb-choices exp)))) ; ここを変えるだけ ... 以下は p.258 analyze-amb とまったく同じ (define (analyze exp) ;; p.234 analyze (cond ((self-evaluating? exp) ... ((ramb? exp) (analyze-ramb exp)) ; 追加 ...
gosh だと、shuffle 関数があるので簡単。shuffle 関数ない場合の自作例は以下のとおり(性能悪し)
;;; p.132 脚注 (define (rand-update x) (modulo (+ (* x 1103515245) 12345) 2147483647)) (define random-init 12345) ;;; 任意 ;;; p.132 (define rand (let ((x random-init)) (lambda () (set! x (rand-update x)) x))) ;;;シャッフルコア (バブルソート的に隣同士をランダムに入れ替える) (define (shuffle-1 x) (if (null? (cdr x)) x (if (odd? (rand)) (cons (car x) (shuffle-1 (cdr x))) (cons (cadr x) (shuffle-1 (cons (car x) (cddr x))))))) ;;;シャッフル関数(適当に100回くらい入れ替えを実行する) (define (shuffle x) (define (loop n x) (if (= 1 n) x (loop (- n 1)(shuffle-1 x)))) (loop 100 x))
アリッサの問題というのは、p.253 Ex.4.49の脚注によると、単語を文法どおりに組み合わせて自動的に文書を作ろうとしたが、文法の許す再帰性のためいくつかの文章間で振動してしまうということ(らしい。間違ってるかも。)ランダムに選択するならこの振動は回避できるらしい。(げげ、4.49 飛ばしてた。忘れてた。)
しかし、よく考えると、ramb でリストをランダムにしてもアリッサの問題の助けにはあまりならない。
rambでリストをランダムにして振動を回避しても、ramb を複数重ねた探索ツリーを深さ優先で探索する限り、似たような文が吐き出されるという状況は改善されないと思われるから。
本当の解決は、探索ツリーの上下左右、いたるところを飛び回るような探索をしなければならないが、、、これはちょっと難しいかも。