それを眺めていたら, EWD221に Raw code for computing DeBruijn-sequence というのがあった.
例えば00011101がB(2,3)で, 最初のパラメータ2は, 記号が0と1の2種類ということ, 後のパラメータ3は, 3個ずつとると, 全てのパターンが得られるということである.
つまり先頭から1ビットずつずらしながら, 3ビットとると
000
001
011
111
110
101
010
100
(最後の2つは, 3ビットとれないので, 始めに循環している)つまり上から順に0, 1, 3, 7, 6, 5, 2, 4とすべて現れる.
Dijkstraのプログラムは, B(2,5)を作るものであった. まず元のプログラムを見ると
array d[0:36];
d[0] := 0; d[1] := 0; d[2] := 0; d[3] := 0; d[4] := 0;
d[5] := 0;
k := 5;
4 < k and k < 36 herhaal
begin j := k-1; geluk := true;
j >= 4 and geluk herhaal
begin gelijk := true; h := 0;
h <= 4 and gelijk herhaal
begin gelijk := (d[k-h] = d[j-h]); h := h+1 end;
gelijk zoja geluk := false; j := j-1
end;
geluk dan
begin k := k+1;
k <= 31 dan d[k] := 0 anders d[k] := d[k-32] end
anders
begin k > 31 zoja k := 31;
d[k] = 1 zoja k := k-1;
d[k] := 1
end
end
見慣れないキーワードがあるが, オランダ語らしい. それでも何となく意味が分かるので, Algol 60風に書き直してみた. ただし型宣言は省略した.
array d[0:36];
d[0] := 0; d[1] := 0; d[2] := 0; d[3] := 0; d[4] := 0;
d[5] := 0;
k := 5;
while 4 < k and k < 36 repeat
begin j := k-1; geluk := true;
while j >= 4 and geluk repeat
begin gelijk := true; h := 0;
while h <= 4 and gelijk repeat
begin gelijk := (d[k-h] = d[j-h]); h := h+1 end;
if gelijk then geluk := false; j := j-1
end;
if geluk then
begin k := k+1; if k <= 31 then d[k] := 0
else d[k] := d[k-32] end
else
begin if k > 31 then k := 31;
if d[k] = 1 then k := k-1;
d[k] := 1
end
end
最初の37語の配列 d は, 32ビットのde Bruijn-sequenceに循環して使う部分の5ビットを追加したものらしい. 最初の6個にとりあえず0を入れた. またkを5にした. kは配列 d で作業中の場所を指しているらしい.
その次 while 4 < k and k < 36 repeat は, kが増えたり減ったりしなが進行し, この範囲を脱出したら終りということであろう.
次は, k, k-1, k-2, k-3, k-4の5ビットと同じパターンがそれ以前のj, j-1, j-2, j-3, j-4ににあるかを見るループである. したがって, まずjをk-1にし, kの5つ組とjの5つ組を比較する.
途中の比較の結果を覚えておくのが, Boolean変数 glukで, まず真にしておく. hとglijkが5つ組の比較を制御する.
hを0から4まで変えながら, 5つ組に相違があればglijkを偽にし, ただちにループから脱出する. 5つが一致していれば, glijkは真のままだ. 一致のものが1組でもあれば, kからの5つ組は使えない. それを伝えるのがglukで, glukが真なら, 過去に同じものはなかった; 偽なら同じものがあったことになる.
それを使うのが, 中ほどの if glukである. 同じものがなければ, kの5つ組は合格で, kを増やし, d[k]に0を入れ, テストに戻る. 失敗なら, d[k]が1の間, kを減らし, 最初の0が見つけ, それを1にする.
とまぁこういうプログラムであった. kが31を越えてからは, はじめの方の値をコピーする. (d[k] := d[k-32])
大体そういうことが分かったので, 実行してみた. それにはSchemeに書き換える.
(define (dijkdebr)
(define d (make-vector 37))
(define k 5)
(define (db0)
(if (and (< 4 k) (< k 36))
(let ((j (- k 1)) (geluk #t))
(define (db1)
(if (and (>= j 4) geluk)
(let ((gelijk #t) (h 0))
(define (db2)
(if (and (<= h 4) gelijk)
(begin (set! gelijk (= (vector-ref d (- k h))
(vector-ref d (- j h))))
(set! h (+ h 1)) (db2))))
(db2)
(if gelijk (set! geluk #f))
(set! j (- j 1)) (db1))))
(db1)
(if geluk
(begin (set! k (+ k 1))
(vector-set! d k (if (<= k 31) 0
(vector-ref d (- k 32)))))
(begin (if (> k 31) (set! k 31))
(if (= (vector-ref d k) 1) (set! k (- k 1)))
(vector-set! d k 1)))
(db0))))
(for-each (lambda (i) (vector-set! d i 0))
'(0 1 2 3 4 5))
(db0)
(display d) 'ok)
(dijkdebr)
一番そとのループに入った時点で, 配列 d を出力したのが, 次である.
左は k の値. その右がdのその時確定している部分である. kを減じている時は, 短くなっている.
5 000000
5 000001
6 0000010
7 00000100
8 000001000
9 0000010000
10 00000100000
10 00000100001
9 0000010001
10 00000100010
10 00000100011
11 000001000110
12 0000010001100
13 00000100011000
14 000001000110000
15 0000010001100000
15 0000010001100001
14 000001000110001
13 00000100011001
14 000001000110010
15 0000010001100100
15 0000010001100101
16 00000100011001010
17 000001000110010100
18 0000010001100101000
18 0000010001100101001
19 00000100011001010010
19 00000100011001010011
20 000001000110010100110
20 000001000110010100111
21 0000010001100101001110
22 00000100011001010011100
23 000001000110010100111000
24 0000010001100101001110000
25 00000100011001010011100000
25 00000100011001010011100001
24 0000010001100101001110001
25 00000100011001010011101011
26 000001000110010100111010110
27 0000010001100101001110101100
27 0000010001100101001110101101
28 00000100011001010011101011010
28 00000100011001010011101011011
29 000001000110010100111010110110
29 000001000110010100111010110111
30 0000010001100101001110101101110
30 0000010001100101001110101101111
31 00000100011001010011101011011110
32 000001000110010100111010110111100
33 0000010001100101001110101101111000
34 00000100011001010011101011011110000
35 000001000110010100111010110111100000
31 000001000110010100111010110111110000
32 000001000110010100111010110111110000
33 000001000110010100111010110111110000
34 000001000110010100111010110111110000
35 000001000110010100111010110111110000
36 0000010001100101001110101101111100000
Dijkstraには, Stepwise refinementでプログラムを作る論文がいくつもあり, それらは, 彼がどう考えてプログラムを考えたかが, 克明に記されている.
このプログラムのように, 結果だけ書いてあるのは, 非常に珍しいが, これでも, 何を考えたかは, 多少推測される.
P.S. プログラムに現れる2つのBoolean 変数のgelukとgelijkだが, 手元のオランダ語の辞書によると, gelukは幸運, gelijkは等価という意味らしい.
0 件のコメント:
コメントを投稿