リンケージを持たない。したがって , リン ケージの内部・外部の区別は , 外部定義さ れる識別子か , プロックの内部て、 extern を 指定して宣言された , オプジェクトないし は関数の識別子にだけ適用て、きるというこ とて、ある。 これらの条件を解説するためのサンプル として , List 3 を見てほしい。これはふたっ こて、は f00. c と bar. c と名づ のファイル・・ ・・・から構成されるプログラムて、ある。 3 個の変数名が登場する。 i, j, k て、ある。 こて、注目すべきは ( B ) 点における j の宣言て、 ある。 f00. c の中て、 j だけは最初に static と宣 言されている。このため , f00. c の j は (B) 点 て、 extern と指定されているにもかかわらず 「すて、に行われた宣言のリンケージ」て、ある 「内部リンケージ」を持つ識別子となる。し たがって , f00. c の j が参照する変数は , bar. c の j が参照する変数とは別物になる。 一方 , i および k は外部リンケージを持つ識 別子として解釈され , ふたつのファイルて、 共通の変数を参照することになる ( Fig. 6 ) 。 なぜならば , ( A ) 点て、 extern 指定されている i は , すて、に最初に記憶クラス指定子なしの 宣言が行われている。このため , 「すて、に外 部リンケージて、あると宣言されている」こと になり , したがって , 二度目の宣言て、はそ れと同じリンケージ , すなわち外部リンケ ージを持っと解釈される。そして (C) 点て、 e xtern 指定されている k は , これが f00. c にお ける最初の宣言て、ある。この場合には , 「フ ァイルスコープて、その識別子の宣言が行わ れていない場合 , それは外部リンケージ」と いう規則に従い , 外部リンケージを有する ようになる。 この結果 , ふたつのファイルをリンクし て f00. exe を作り , それを動作させると , i の 値は 123 , k の値は 789 と表示されるが , j の値 は 0 になる (Fig. 7 ) 。値 456 が設定されるのは bar. c の j て、あって , f00. c の j には値が設定さ れないためて、ある ( foo. c の j が参照するのは 静的な変数なのて、 , 実行時ルーチンのスタ 114 C MAGAZINE 1993 4 9 ANSI 3.1.2.2 の規則 げ , within a tarnslation unit, the same identifier appears with bOth internal and externallinkage, the behavior is undefined. ( 訳 ) ひとつのコンバイル単位内に , 同一の識別子が内部リンケージおよび外部リンケー ジの両方を伴って出現した場合には , その結果は未定義である。 Fig. 8 ANSI 3.1.2.5 の規則 同一のオプジェクトもしくは関数に対するすべての宣言は適合型でなされなければならな い。それが守られない場合には , その結果は不定である。 Fig. ートアップて、初期値 0 が設定される ) 。 以上の説明から , オプジェクトて、あって も , 関数て、あっても , ひとつの識別子に対 して , 同一のコンパイル単位内て、「最初に st atic をつけて宣言し , その後に extern をつけ て宣言する」ことは間違いて、はないことがわ かった。つまり , その場合には内部リンケ ージとなるわけてある。さらに , 関数の場 合て、あれば「最初に static をつけて宣言し , その後には記憶クラス指定子を明示せずに 言する」ことも許され , それは二度目に e xtern をつけたのと同じ意味て、あるというこ ともわかった。 て、は , この逆を行ったらどうなるだろう か。すなわち「最初に extern をつけて宣言 し , 後から static をつけて宣言する」という のを , ひとつのコンパイル単位内て、行った 場合て、ある。本連載第 14 回て、引用したのだ が ,ANSI 3.1.2.5 には Fig. 8 の規則が存在 する。 しかし , 「リンケージ」の相違は「型」の相 違には含まれないということに注意してほ いい換えればリンケージが違ってい ても , 両者の型は適合型なのて、あり , 上記 3.1.2.5 の制約に違反しているわけて、はな い。したがって , このようなリンケージの 差異から生じる問題 ( が , あるとしたら , そ れ ) に関する規約は別途定めておかなければ ならない。そこて、 , この場合に関して , AN SI 3.1.2.2 に Fig. 9 の規定がある。 ということて、 , ANSI て、はその結果は未定 義 (undefined) ということになっている。実 際の処理系て、は , 工ラーになったり警告に なったり , あるいは拡張機能として暗黙の 内に内部リンケージに置き換えて処理して しまったりする。たまたま「黙って処理する」 処理系を使っているとそれが正しいと思い 込みがちだが , それは処理系依存の機能て、 あるということを認識してほしい なお , いうまて、もなくここて、あげたルー ルは , 最初に static と宣言し , 後に extern と 宣言した場合には当てはまらない。この場 合は , 後から宣言した extern は「外部リンケ ージ」を指定するものて、はなく , 「それまて、 に宣言されていれば , それと同じリンケー ジを採用する。宣言されていなければ外部 リンケージとする」という弱い指定だからて、 ある。 以上のまとめとして , これまて、とは別な 観点からリンケージ決定のルールを手短に 説明してみよう。 こて、「消極的な外部リンケージの指定」 リンケージの指定となる。 c をつけていないことは , 消極的な外部 ること , あるいは関数の場合には stati オプジェクトの場合には extern をつけ ンケージを指定する。 子をつけないことは , 積極的に外部リ (c) オプジェクトの場合 , 記憶クラス指定 ンケージを指定する。 (b) static をつけることは , 積極的に内部リ 言された時点て、決定する。 リンケージは , その識別子が最初に宣 (d) (a) とは , すて、に内部リンケージが指定されて
員 N 引 mo 化 List 4 ローカルで extern と指定したが先に static 宣言があった場合 LiSt 22 : 23 : 25 : 27 : * File: quux. c 28 : 29 : #include く stdio. h> 30 : int qux(void); 32 : int quux(void); 33 : 34 : ニ 1 2 3 : 35 : 36 : #define PR(x) 37 : 38 : int main(void) 40 : PR(qux()); return 0 : * F ⅱ e : qux. c 2 : 3 : S t a t i c i nt i : 4 : 5 : 6 : int qux(void) extern int i; 8 : 9 : return 信 1 3 : int quux(void) extern int 20 : return i : printf(#x ニ %dYn ” いた場合 , それに従うということを意味して 記憶クラス指定子とその効果 TabIe 1 いる。リンケージはその識別子が最初に宣 記憶クラス 指定子なし 言された ( 出現した ) 時点て、決定するという ルールは , シングルバスの処理系を考慮し たためて、あるようだ。ある種の処理系て、は , 識別子のリンケージが内部て、あるのか , 外 部て、あるのかに応じて , コード生成の仕方 が変わる場合があるため , とにかく最初の 関数 ファイル / プロック 時点て、それを決定してしまうという方針な 外部リンケージ * 1 内部リンケージ スコープ共通 のて、ある。 * 1 これらは「消極的な外部リンケージの指定」でしかない ックて、は , プロックスコープの変数 i を宣言 もうひとつ例をあげておこう。 List 4 を見 は「未定義」て、あるとされているのて、 , 何が てほしい。このプログラムは , ふたつのフ している。さらに quux 本体の中にローカル 起きても不思議はないということて、ある。 アイル qux. c と quux. c をリンクして動かすこ な ( 入れ子になった ) プロックを置き , その 現実の処理系て、は , このネストしたプロッ とを意図している (main は quux. c に含まれる )。 内側て、 extern をつけて再び i を宣言してい クにおける i も , 静的リンケージを持つもの まず注目してほしいのは qux. c の関数 qux て、 る。この場合どのように解釈されるべきだ として処理するものがほとんどのようて、あ ある。関数 qux の内部て、はローカルに ( プロ こては , quux の本体て、プロック ろうか。 る。 スコープの i を宣言してしまったため , 内側 ックスコープて、 ) , 識別子 i を extern として宣 なお ,extern あるいは static というキーワ のプロックて、は i に対する「ファイルスコープ ードは , リンケージと同時に記憶クラスを 言している。 こうすると , いったいどのよ うに解釈されるのだろうか。 の可視の宣言」はないということになる。と 指示するキーワードて、もある。というか , いうことは , i は「外部リンケージ」を持って この識別子は , 前述の「ファイルスコープ 呼び名は「記憶クラス指定子 (storage class いるということになるはずて、ある。という の可視の宣言」があったと解釈されるため , specifier) 」て、あるから , むしろこれらは本 それと同じリンケージを持つようになる。 ことは , quux. c の i と同じものを参照するの 来 , 記憶クラスを指定するためのキーワー この場合 , 最初に静的リンケージを持っフ ドて、あり , 補助的にリンケージも指示する だろうか・・ ァイルスコープの i が宣言されているため , 残念ながら , そうはうまくいかない な ということになる。 qux にローカルな i も静的リンケージを持っ ぜならば , このケースて、は「ひとつのコンパ ところが , C の場合 , これらのキーワード i となる。 イル単位内に , 同一の識別子が内部リンケ が果たす役目は , それが用いられている場 次には , 同じくファイル qux. c の関数 quu ージおよび外部リンケージの両方を伴って 所 ( 分脈 ) と , 対象としている識別子が何を x に注目してほしい。関数 quux の本体のプロ 出現している」ということになり , その結果 表すものて、あるかによって微妙に意味が変 exte rn を明示 static を明示 静的記憶 外部リンケージ * 1 ファイル スコープ 外部リンケージ 動的記憶 プロック スコープ リンケージなし オプジェクト 内部リンケージ 静的記憶 内部リンケージ 外部リンケージ * 1 静的記憶 ANSI C ー more 115
X 68 k 活用講座 List 6 List 1 : / * system include * / 2 : #include く stdi0. h> 3 : #include く interupt. h> 4 : 5 : #ifdef DEV_GCC 6 : / * Develop 版 GCC 拡張 * / 7 : DOSCALL INTVCG (short) ; 8 : DOSCALL INTVCS (short, VOid 9 : DOSCALL PRINT (char * ) ; : #else 11 : #include く doslib. h> 12 : #endif 14 : 15 : stdin,stdout が XC Ver 依存のため 16 : sprintf でマクロにしておく 17 : * / ョ 18 : #define Fprint(buf, fmt, mes) : 19 : do { sprintf ((buf), (fmt), (mes)) , ー 20 : PRINT ((buf)) ; 21 : 」 22 : } while ( の 23 : 24 : 25 : static struct { int flag; ー 26 : 27 : uns i gned short s r—reg ; int pc—reg : 28 : ー 29 : Char *mes ; 30 : } trapbuf; ー 31 : 14 ) ( ) : 、 32 : static VOid (*trap— 33 : 34 : void (*usr—abort) (void) : 35 : extern int _maln; ー 36 : 38 : static void 卩 39 : trap14(void) 40 : ( PRAMREG (code, PRAMREG (add, 42 : SET_FRAME (a5) : ー 43 : char *P =(char *)add; ー 44 : 3 45 : / * code からエラーを分析 * / 46 : switch (code&Oxffff) 48 : case 2 : ー 49 : / * バスエラー * / 50 : trapbuf. flag ニ code; 51 : ”バスエラーが発生しました” trapbuf. mes break : 53 : case 3 : 54 : / * アドレスエラー * / 55 : trapbuf. flag = code; 56 : trapbuf. mes = " アドレスエラーが発生しました " ・ 58 : ー 61 : ー 63 : 65 : 66 : 68 : ー 69 : ー 74 : ー 75 : 1 76 : ー 77 : ー 80 : 朝 82 : ー 83 : } ー 84 : 85 : static void 86 : my—abort(void) char buf[64] ; 88 : INTVCS(0x2e, trap_14) ; 89 : if (usr-abort) ー 90 : usr—abort ( ) : ー 91 : if (trapbuf. flag 〉の ー 92 : extern i nt _SSTA ; 94 : ー 95 : extern i nt _PSTA ; ー 96 : trapbuf. flag = 0 ; Fprint (buf, ” Xs#r%n ” , trapbuf. mes) : Fpr int (buf, ” pc=XX ” , trapbuf. pc_reg) : 98 : Fprint (buf, offset=XX%r#n ” , trapbuf. pc_reg ー (int) & main); 99 : exit(512); 100 : は 01 : 1 102 : は 03 : は 04 : は 05 : ロ 06 : : 107. : 108 : : 109 : VOid q10 : init—trap14 (void) は 11 : trap—14 ニ (void *)INTVCG (Ox2e) : q12 : INTVCS (0x2e, trap14) : d13 : : 114 : INTVCS (0xfff2, my_abort) : : 115 : INTVCS (0xfff1, my_abort) ; は 16 break : case 4 : / * おかしな命令 * / trapbuf. flag = code; trapbuf. mes ニ”おかしな命令を実行しました” break : if ((code &0xff0 の ) if ((code &0xff) trapbuf. flag ー 1 ; trapbu f. mes ”ドライブの準備ができていません”・ if (trapbuf. flag Ⅱ (code&0xffff) = = Ox1f Ⅱ (code&0xffff) trapbuf. sr_reg = *(short *)p; p + = 2 : trapbuf. pc_reg = *(int *)p; asm ("#tmove. 響 #$ff, d0*n#ttrap # 15 \ n " ) ; IJUMP_RTE() ; ニ 0X301f ) IJUMP(trap_14) ; / * ェラー種別フラグ * / / * 工ラー時の SR / * 工ラー時の PC / * メッセージ / * 元の trap 14 ペクタを保存 * / / * ユーザーのアポート処理関数 * / / * スタートアップのダミー * / 定 指 りりに 叮ー【 0 タタを ススタ ジジン レレイ タタポ メメ一 ララレ Fprint (buf, ” Xs*r*n ” , trapbuf. mes) ; exit ( 256 ) ; 用て、きるのて、 , ディスクに XC Ver. 1 対応 扱うことがて、きます 0List 6 がそのハンドラ は , SIGBUS や SIGILL などて、扱う種類のハ の . a 形式 , および XC Ver. 2 対応の lib 形式 の例て、す。工ラーハンドラは一種の割り込 ンドラは , 今のところ自前て、処理してやる として収録してあります。また , ライプラ み処理なのて、 , intrupt. h を #include して割り しか方法がないのて、す。 リ自体は GCC に依存しませんのて、 , XC て、コ 込み処理として記述します。 さて自前て、エラーを処理するわけて、すが , ンパイルしたプログラムに対してもエラー 先ほども書いたようにエラー種別のパラメ 工ラー八ンドラ ( List 6 ) ハンドリングが可能て、す。 ータは d7 経由て、渡されるのて、 , そのままて、 は C て、扱うことはて、きません。通常はアセン 1 ~ 1 2 行 それて、は List 6 について詳細に説明しま プラて、ハンドラを記述するのて、しようが , す。なお , この List 6 はライプラリとして活 X68000 に特化した XGCC て、はこれを容易に システムヘッダを #include しておきます。 X68k 活用講座 121
引 mo extern 指定が必ずしも外部リンケージを意味しない例 内部リンケージの例 List LiSt 1 より乙ワ 0 4 ・れり 2 : * F ⅱ e : f00. c 3 : 4 : #include く stdio. h> 5 : 6 : 7 : s ta t i c i n t j : 8 : 9 : extern int i; 1 0 : extern int j; 1 1 : extern int k; 13 : #define PR(X) 1 5 : void bar(void); 1 7 : int main(void) bar(); PR ( i ) ; 20 : PR(j); PR(k); 22 : 23 : return 0 : 24 : } 25 : * F ⅱ e : bar. c 28 : extern int i; 29 : i n t j = 456 ; 30 : i n t k : 78 9 ; 32 : 33 : void bar(void) 34 : { = 123 : 35 : 36 : } s t at i c i n t i ; static int foo(void) return i; / * ten ta t i ve de f i n i t i on 外部リンケージ * / / * ten tat i ve de f i n i t i on 内部リンケージ * / / * (A): declaration 外部リンケージ * / / * (B): declaration 内部リンケージ * / / * (C): declaration 外部リンケージ * / printf()x ' : %dYn" に記憶クラス指定子がない場合には , そ れは外部リンケージになる。 ④そして , 次の識別子はリンケージなして、 ある。 オプジェクトて、も関数て、もないもの として宣言された識別子。 関数のパラメータの識別子。 プロックの内部て、宣言されたオプジ ェクトの識別子て、あって , 記憶クラ ス指定子として extern が指定されて いないもの。 これだけて、は理解しにくいのて、 , 順次解 説を加えよう。 ①の条件だが , これがいちばん単純なケ ースて、ある。ファイルスコープを持ち , か する宣言が行われていた場合には , extern つ static と指定されていれば , 関数の識別子 て、あれ , オプジェクトの識別子て、あれ , 内 の指定は意味を持たず , すて、に行われてい るリンケージと同じと解釈される。 部リンケージになる。たとえば , List 2 に示 す変数 i ( オプジェクトの識別子 ) や , 関数 ③の条件は , 記憶クラス指定子が明示さ foo ( 関数の識別子 ) の宣言がそうて、ある。 れていない場合て、あるが , この場合にはオ プジェクトと関数て、扱いが変わる。オプジ ②の条件は要注意て、ある。識別子の宣言 時に「 extern 」が指定されていれば , その識 ェクトの場合には , 無条件に外部リンケー 別子は当然に外部リンケージを持っという ジを持っことになる。 一方 , 関数の場合には「あたかも extern が ことになるだろうと考えがちて、あるが , 実 指定されていたかのように」決定するのて、あ はそう単純にはいかないのて、ある。このケ る。したがって , 関数の場合には上記②の ースて、はまず , その識別子に対するファイ ルールに従うことになる。 ルスコープの宣言がすて、に行われているの ④の条件て、は , 最初の「オプジェクトて、も かどうかが間題になる ( この場合 , 逆に問題 関数て、もない」識別子というものに関して補 の識別子の宣言がファイルスコープて、行わ 足が必要かもしれない。これは具体的には , れているかどうかは関係しない ) 。 ここて、 , extern が有効になり , 識別子が外 ラベル名 , 構造体・共用体・列挙のタグ名 , 部リンケージを有するようになるのは , そ 構造体・共用体のメンバ名 , 列挙定数名 , れまて、にファイルスコープて、その識別子の そして typedef 名などて、ある。そして , プロ 宣言が行われていない場合にかぎられる。 ックの内側て、局所的に宣言された識別子は すて、にファイルスコープて、その識別子に関 ( それが extern と指定されていないかぎり ) , ジジジ ケケケ ンンン 部部部 外外外 0 0 Fig. 6 i, j, k の実体が取られるようす bar. C f00. C 123 CéJ 789 ( j に対応する実体だけはふたつある ) Fig. 7 List 3 の実行結果 C : *ACM18>foo = 123 k: 789 ANSI C ー more 113
List 2 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : } 1 5 4 : 156 : 157 : 158 : { 159 : 160 : 161 : 162 : 16 3 : 164 : 166 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 1 7 6 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 1 8 4 : 185 : 1 6 5 : / * して探索していくのて , 手順を求めること 先探索の場合は , 1 手目 , 2 手目・・・・・と並行 のて , 手順の表示は容易て、す。一方 , 幅優 ク ) の場合は解の手順に添って探索を進める 表示方法て、す。深さ優先探索 ( バックトラッ 次に考えなければならないのは , 手順の ラムを作ることにしました。 て , まずはデータ圧縮なしの単純なプログ す。先に紹介した Kernighan らの勧めに従っ 点からは , データ圧縮の必要はなさそうて、 以下て、済む計算になります。メモリ容量の イトの配列て表現したとしても , 5K バイト マス目ひとつに 1 バイトをあてて盤面を 8 バ き方の総数は少ないて、すね。したがって , ては 3 * 6 ! / 4 = 540 通りになります。意外に置 並べる方法は , 6 ! / 4 通りて、すから , トータル 個のヒ。ース ( 空白もピースとして数える ) を ヒ。ースの置き方は 3 通りて、す。そのほかの 6 は横方向にしか移動てきませんから , この なければなりません。上段に置かれた電燈 総数を調べてメモリ所要量の見積もりをし ちてす。このため , まずビースの並べ方の 幅優先探索はとにかくメモリを消費しが / * 最初に戻る * / こに来るのはアルゴリズム上ありえない * / cannot happen (position). Yn") ; fprintf(stderr, exit(l); 1 5 5 : / * ハッシュ表への格納 * / board_t *insert(board-t *P, char *board, BOARD_SIZE) ; memCPY()- 〉 board. board. p->POS-space = SPos; return p; prev; p->prev int SPOS, board-t *prev) / * 盤面をコピーする * / / * 空白の位置をコピー * / / * 直前の局面をコピー * / パズルの解法本体 167 : / * ハッシュ表に登録するとともに、必要であればキューにも格納する * / board-t *insert_and_enqueue(char *board, int spos, board-t *p; ー position(board) : if (empty(*p)) { insert(), board, SPOS, prev) : enQueue(p) : } se i f (p ー f i n i sh-P0 i n t ) { return p; d i spl ay (p) ; prev : p->prev void init-board(void) board_t *prev) / * 盤面の初期化 * / / * ハッシュ表上の位置を返す * / / * 表示する * / / * 前の盤のポインタをセットして * / / * 最終状態か ? * / / * キューにも登録する * / / * 空なら表に登録して * / / * ハッシュ表上の位置を得る * / がやっかいて、す。 にまとめています。具体的には , 重複チェ 終局面に到達したことのチェックをひとつ このプログラムて、は , 重複チェックと最 り気にならないようてす。 はあまり依存しないのて、 , 速度低下はあま ハッシュ表の検索時間は , 表の大きさに てサーチしています。 クニックは用いずに , すべての局面を含め にしたのて , 前節て、紹介した検索省略のテ このように , すべての局面を記憶すること 出しにより正順に戻して表示しています。 られます。このプログラムて、は , 再帰呼び どっていくと , 正解に至る手順が逆順に得 タを入れておくことにしました。これをた す構造体の中に「直前の局面」を示すポイン ておくことがて、きます。そこて、 , 局面を示 数が少ないため , 途中経過をすべて記憶し たまたまビースチェンジの場合は局面の 186 : 187 . 188 : 1 8 9 : 190 : 191 : 192 : 193 : 1 9 4 : 1 9 5 : 1 9 6 : 1 9 7 : 199 : 200 : 201 : 202 : 203 : 204 : 2 ℃ 5 : 206 : } 207 : 208 : 209 : 210 : 211 : 2 1 2 : 213 : 214 : 215 : 2 1 6 : 2 18 : 219 : static char start[BOARD_SIZE] = {LIGHT_L, LIGHT_R, LETT_N, LETT_O, LETT_O, LETT_F, LETT_F, SPACE} : static char finishCBOARD_SIZE] = {LIGHT_L, LIGHT_R, LETT_O, LETT_N, LETT_O, LETT_F, LETT_F, SPACE} ; / * 初期状態をハッシュ表とキューに格納する * / insert(position(finish), finish, 7 , NULL); finish-point / * 最終状態をハッシュ表に格納し、その位置を憶えておく * / insert-and-enqueue(start, 7 , NULL) : 19 8 : / * 長いピース ( 電燈 ) かどうかの判定 : マクロ * / #define is_long_piece(piece) ((piece) VOid swap-pieces(char *board, int spos, int ppos) = boardCsPos] : ニ boardCpPos] : temp; char temp board[sPos] board [PPOS] void moveUp(board-t *aBoard) char boardCBOARD-SIZE] ; int sPos; SPOS aBoard->pos_space; if (sPos 〉 : BOARD_WIDTH) return; = LIGHT_L Ⅱ (piece) = LIGHT_R) / * ピースの入れ替え * / / * ピースを上に動かしてみる * / / * ピースを上に動かせない * / / * スペースが下段だと if (is-long-piece(aBoard->board[sPos + BOARD_WIDTH])) / * 横長だと上に動かせない * / return, svap-pieces(board, sPOS, sPos + BOARD-WIDTH) : / * ピースと空白を入れ替え * / / * 盤面をコピーしてから * / memcpy(board, aBoard->board, BOARD-SIZE) : 74 C M AGAZIN E 1 3 4
List 2 74 : 76 : 77 : / * 78 : 79 : 80 : { 81 : 82 : 83 : 85 : 86 : 88 : 89 : 91 : 92 : 94 : 95 : 96 : 98 : 99 : 100 : 101 . 102 : 103 : 104 : { 106 : 107 : 109 : 1 10 : 1 12 : / * 1 14 : 1 15 : 116 : 1 17 : 1 1 9 : 120 : 121 : 122 : } 1 23 : 12 5 : 12 6 : 12 7 : 128 : 129 : 130 : 131 : 1 32 : 133 : 134 : 135 : } 136 : 137 : 138 : { 1 39 : 140 : 1 41 : 1 4 2 : 143 : 1 4 4 : 1 4 5 : 4 : i く 8 : i + + ) return queue[q-top 十十 ] : 表示表関係のモジュール void display-board(board-t *p, int n) %4dYn ” printf(" dispIayTabIe[p printf("%s ” 0 ; i く 4 ; i + + ) for (i static char *displayTable[] i n t i : / * 盤 1 枚の表示 * / int display-l (board-t *p) for (i printf("%s" printf("YnYn ” ): i nt n : = NULL) return 0 : = display-l(p->prev) : n displ ay-board (P. return n 十 1 : dispIayTableCp init-queue() : 108 : #endif printf("%n%n"); display-l(p); 105 : #ifndef NO_DISPLAY VOid display(board-t *p) / * 手順表示 ( 下請、再帰 ) * / / * 呼出側が、何手目かを帰す * / / * 空なら黙って戻る * / / * 呼出側は 0 手目 * / / * まず自分より前を表示してから * / / * キューを空にして戻る * / / * 表示モード * / / * 手順の表示 * / / * 呼出元の手数を教える / * 自分自身を表示する 実践アルゴリズ路解法のテクニック への応用 「ピースチェンジ」 はプログラムリスト (List 2 ) のコメントを参 グラムの解説は簡略にとどめます。詳しく 誌面が残り少なくなってきたのて、 , プロ 手順を求めるというものて、す。 せて , 下段の状態にするための最少手数の い 0Fig. 6 の上段の状態からピースを移動さ チェンジの説明は Fig. 6 をごらんくださ た「ピースチェンジ」を選びました。ビース ' 91 年 9 月号の「 C マガ電脳クラブ」に出題され こて、は , よりやさしい例題として , 本誌 ピュータて、解くことは時間的に困難て、す。 あまりに多い ( 16 の階乗 ) ため , 通常のコン しかし , 15 パズルは調べるべき局面の数が 俗に「プラパズル」と呼ばれるパズル群てす。 の代表例は , 「 15 パズル」や「箱入り娘」など 紹介しましよう。幅優先探索て、解ける間題 こて、 , 幅優先探索の応用プログラムを 考にしていただくことにして , こては設 ハッシュ表関係のモジュール board-t tabIeCHASH-SIZE] ; board-t *finish-point, void init-table(void) table[i]. pos_space : EMPTY; for ( i : 0 : i く HAS H_S IZE : i + + ) / * ハッシュテープル * / / * 完成状態の格納位置 * / / * ハッシュテープルの初期化 * / / * することで、未使用を表す / * pos ー space に特別な値を格納 * / 124 : / * empty : ハッシュ表の項目が空であるかの判定用マクロ * / #define empty(X) ((X) . pos-space ニ = EMPTY) / * ハッシュ関数 * / int hash(char *board) unsigned x; for (x ニ 0 : i く BOARD_SIZE; return (int)(x % HASH-SIZE); X (x くく 2 ) + board[i]; i 十十 ) / * ハッシュ値の計算 * / / * 元の格納位置を返す / * 同一の盤面が格納ずみであれば、 / * 盤面を格納すべき位置を返す board_t *posi tion(char *board) I, P : p = hash(board) : for (i = 0 : i く HASH-SIZE; return &table[p]; i f ( + + p > = HASH-SIZE) int 十十 i ) if (empty(table[p]) Ⅱ memcmp(table[p]. board, board, BOARD_SIZE) / * ハッシュ表をオーパーしたら * / 計に際して考慮したことを説明します。 Fig. 6 ピースチェンジ体誌 ' 91 年 9 月号より ) ピースチェンジ 今月はスライディングプロックパズルだ。 今月のノヾスル 数の解を求めていただきたい。 動きの途中経過もしつかり書いて , 最少手 だ。何手て完成てきるだろうか。ビースの 2 の状態にしたい。「 NO 」を「 ON 」にするの の状態からビースをすべらせて移動し , Fig. Fig. 1 のようにビースが配置されている。 実践アルゴリズム戦略 0 F F 0 F F 73
画・かなっス交 素らしし ) ソ 7 ト不 よーし夫々的に 売リ出ど でまね 川謝論 2 Li st 2 ごは、さ ? もく し ) らんいらん び SP7 。ロテクト をもん / ユ = ットを使っも 余訐を コ一も防止 使うちない / しましう。 0 ヨ 300 : #ifdef 301 : main(){ 302 : int 303 : set-rsv-words() ; 304 : for (i = 0 : i く MAX_SYM; i + + ) { 305 : if (sym-table[i]. type) 306 : ヨ printf("%s%n" 307 : sym-tabIeCi]. symbol); 308 : printf("%dYn" conflict); 309 : 310 : } 312 : #endif / / HASH_DEBUG 313 : ヨ 3 1 5 : 3 1 6 : Hash word & store table addressing is 叩 en hash ⅵ th simple quotient method * 3 1 8 : 3 1 9 : 320 : add_table(word, size, type) 321 : char *word; 322 : int S i ze ; 323 : int type; 324 : { 325 : register int 326 : for (n ニ hash(word, size) : sym-table[n). type ! = EMPTY; n ニ REHASH(n)){ 327 : if ( !strcmp(sym-tabIeCn]. symbol, word)) 328 : / * already registered 329 : return; 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : } 338 : 339 : int 340 : hash(word, size) 341 : Char *word; 342 : int S ー ze ; 343 : { 344 : unsigned int sum; 345 : wh ⅱ e (s i ze-- 〉の { 346 : sum 十 = *word 十十 ; 347 : 348 : (sum / MAX-SYM) + 1 ; 349 : quot return sum % MAX_SYM; 350 : 35 1 : 352 : 353 : 354 : char *rsv_wd ロ 'autO ” ” break' 355 : 'default ” 356 : ” float ” 'for ” 357 : ” return' ” short ” 358 : ” struct ” ” swi tch ” 359 : ” VOid" "volatile ” 360 : 361 : / * special keyword * / 362 : ” far' far ” "huge" _huge" 363 : interrupt" pascal" 'fortran 364 : -pascal" ' cdecl" interrupt" 365 : 366 : / * preprocessor direcitives * / 367 : "endif ” ” define ” ” e ⅱ f ” 368 : error 'line ” ” undef ” ” include ” 369 : pragma 370 : 371 : 372 : 374 : 375 : Set reserved words i ntO hash tabl e 376 : 378 : set_rsv_words() 379 : { 380 : register int 381 : for (n = 0 ; *rsv-wdCn] : + + n ) { 382 : add-tabIe(rsv-wdCn], strIen(rsv-wdCn]), RSV-WD); 383 : 384 : 385 : } HASH_DEBUG 6 そして - らわああ やられた一 から JSP7 デクト ュニ、トを使みう , て言 1 のに ち せ る上け“ ( ら こ 0 P 0 sym-tabIeCn]. type type; sym-tabIeCn]. symbOl max_used; strcpy(max-used, word) ; max_used 十ニ size; *max dsed 十十 ーし、し ) つこしなし ) よウに JSP AX ・ NEC PC -9801 シリーズ ( ラップトップ機を除く ) ・ソフトユニット装着数最大 1 5 個 ・消費電流十 5V 50mA MAX. ・ホードタイプ ・プリンターポートタイプ ーパソコン用アプリケーションソフトの著作権、使用 権を保護するためのハードプロテクトて、す。 ■ソフトウェアユーザのバックアップコヒ。ーは自由てす。 本器はソフトウェア製作・販売元を対象とした製品です。 問合せ 0482-61- ロ 041 代 コンビュータ計測・制御システム 襯十条電子株式会社 〒 333 埼玉県川口市小谷場Ⅱ幻 く資料請求番号 131 〉 Conference Room 131 const ” continue "extern" enum ” i n t ” "long register sizeof ” ” static ” uns igned' ” Char 'else ” case ” dou 国 e ” goto" signed' "typedef" ”ⅶⅱ e ” near asm near ” cdecl" ” ifndef ” ” ifdef ” JSP BASE しハ TIT
NS mo 化 を得ない ) 。 結局 , List 5 のふたつのファイルをそれぞ れコンパイルし , リンクを行うと , 正しく 実行形式のファイルがて、きるはずて、ある。 実行結果を Fig. 11 に示す。 さて , こて、 zot. c をちょっと修正して , extern int il ・ という行を次のように変えるとどうなる かを考えてみてほしい int il ; 修正というのは , extern を削除しただけ て、ある。こうすると , 元は Ref, すなわち参 照て、あったはずのこの行が , tentative def inition に変わってしまう。ところが , この 行は zot. c に存在するため , この tentative d efinition は zot. c の中て、新たに il という変数を 定義したことになる。その結果 , ANSI に忠 実な処理系て、あれば , このように変更した ファイルをコンパイルすることは正常に行 ことがて、きるべきだが , リンク時に il が フ 重 ( 多重 ) に定義されているというエラーに なるかもしれない 「かもしれない」という婉曲な表現になっ ているのは , ANSI 3.7 において , 外部リン ケージを持っと宣言された識別子の外部定 義が行われる回数に関しては , ( 本稿冒頭て、 も引用したように ) 意味規則の項に Fig. 12 の ように記載されているものの , それに違反 した場合にはエラーになるとは記されてい ないからて、ある。一般に ANSI て、は「必要が ある (shall) 」と書かれている部分に違反した 結果は未定義 (undefined) て、あるとしている にとどまる。 しかし , いずれにせよ , そのような記述 は望ましくない。定義は全モジュールの中 て、ひとつだけにすべきて、ある。 [ 注 ] [ * 1 ] translation-unit は , 直訳すれば翻訳 単位になるのだろうが , 語感的な趣味 に基づいてコンパイル単位と訳してい Fig. 10 ANSI 3.7.2 「外部オプジェクトの定義」より あるオプジェクトに対する識別子の宣言であって , それがファイルスコープと初期化子 を持つ場合には , それはその識別子に対する外部定義 ( extern 引 definition)C ある。 あるオプジェクトに対する識別子の宣言であって , それがファイルスコープを持ってい て , かっ初期化子がなく , そして記憶クラス指定子がないか , あるいは記憶クラス指定子 として static が指定されている場合には , それはその識別子に対する仮定義 ( tentative definition)C ある。 もしひとつのコンバイル単位の中でひとつの識別子に対して複数の仮定義が行われてい て , かっ , そのコンノヾイル単位の中ではその識別子に対する外部定義が行われていない場 合には , そのコンバイル単位で , その識別子に対して , ファイルスコープで , 型としては そのコンノヾイル単位の終端におけるその識別子に対する合成型で , そして初期化子の値は 0 に等しいというような , あたかもそのような宣言が行われているかのように振る舞う。 仮定義 (tentative definition) を用いた例 List * F ⅱ e : baz. c 2 : 3 : 4 : #include く stdi0. h> 5 : 6 : int i 1 : 7 : i n t i 2 = 5 67 ; 8 : s t a t i c i n t i 3 ; 9 : 10 : i n t i 1 ; i n t i 2 ; 12 : s t a t i c i n t i 3 ニ 789 : 14 : #define PR(X) 16 : vo i d z 0 t ()o i d ) : 17 : 18 : int main(void) zot(); 20 : 朝 PR ( i D ; PR(i2); 22 : PR(i3); 23 : return 0 : 24 : 26 : 27 : / * 28 : * F ⅱ e : zo t. c 29 : 30 : ex t ern i n t i 1 : 32 : VOid zot(void) 3 3 : { 34 . = 123 ; / * t en t at i ve de f i n i t i on * / / * external definition * / / * tentative definition * / / * tentative definition * / / * ten tat i ve de f i n i t i on * / / * external definition * / printf()x ' 朝 Fig. 11 List 5 の実行結果 C ・ *ACM18>baz = 123 i2 = 567 i3 = 7 89 Fig. 12 ANS13.7 「意味規則」より ( 再掲 ) 外部リンケージを持っと宣言された識別子が式の中て用いられる場合 ( ただし , sizeof のオ ペランドの一部である場合を除く ) , プログラム全体のどこかにおいて , その識別子に対す る外部定義が正確に一度だけ行われている必要がある。 118 C MAGAZINE 1993 4
て、 , とくにどういう特徴を持つものを定義 というのか」という意味て、ある。まず , ひと こは「宣日 つの説明は ANSI 3.5 にある。 の意味解説 (Semantics) なのだが , Fig. 3 の ように記されている。 ということて、 , 一般的な区別もあながち 間違いて、はないことがわかる。ただしこの 文章の「 also 」からも , C て、は定義とは宣言の 一部て、あるということが明白て、ある。 ANS I の説明を読むときには , この微妙な区別を 念頭に入れておかないと , 意味が擱めない 部分が少なからず存在する。たとえば 3.7 の 「制約条項 (Constrants) 」 (Fig. 4 ) を考えて みよう。 こて、問題なのは「外部定義 ( external de finition) 」とは何かなのだが , それは同じ 3. 7 の意味解説の部分て、 Fig. 5 のように述べら れている。 再び , 外部定義とは , 特別な外部宣言な のて、ある。 こて、 , 意味解説の文章の後半 は , 制約条項の文章の後半とよく似ている ことに気がっく。両者の違いはリンケージ が内部か外部かという点と , 外部定義が正 確にひとつだけ存在するべきて、ある場所が 「当該コンパイル単位の中」て、あるのか「プロ グラムの全体のどこか」て、あるのかという点 て、ある。しかし , これらの文章からは , 実 は「いっていること」だけて、なく , 「否定して こと」も読み取らなければいけない まず重要なことは , 言及されているのは 「定義」て、あり , したがって , 「定義て、はない 宣言」については言及されていないことて、あ る。すなわち , 「定義て、はない宣言」が行わ れる回数に関する制約は一切ないというこ とて、ある。 一般に「定義て、はない宣言」は ( それぞれの 宣言が指定している型がお互いに適合する ものて、あるかぎり ) 何度行ってもよい。それ らの識別子は , 「外部リンケージ」なのか「内 部リンケージ」なのかがわかっているのて、あ るから , 少なくとも宣言されていることは 明らかて、ある ( もちろん , その宣言が , すな 112 C MAGAZINE 1993 4 わち定義かもしれないのだが ) 。 次に , 識別子が「式の中て、用いられる」場 合については「正確に一度だけ外部定義カ哘 われている」必要があるのだが , て、は「式の 中て、用いられていない」場合にはどうなのか という点が問題て、ある。これは , その識別 子が外部リンケージを持っている場合 , 「外 部定義は必ずしも必要ない」のて、ある。内部 リンケージの場合の解釈は後述するが , そ の場合には自動的に定義が行われたとみな されてしまう。 なお , 「 sizeof のオペランドの一部」が例外 として除外されるのは , このときにはその オプジェクトのサイズ ( したがって , その型 ) だけが重要て、あり , 実際にそれに記憶領域 が割り当てられているかどうかは関係ない からて、ある。 それ以外て、式の中て、用いられる場合 , そ のアドレスが必要になる。いい換えればそ の lvalue が必要になる。このため , 必ずそれ に対して記憶領域を割り付けておかなけれ ばならない。そのためにはどこかて、一度定 義されていれば十分て、あり , もし二度以上 定義されていると , お互いに記憶領域を確 保しあって衝突してしまうのて、 , それはた だ一度だけ定義されていることが必要なの て、ある。 とにかく , 結論としていえることのひと つは , 「定義」と「宣言」に排他的な意味を持 たせて区別するということは , ANSI 標準に かぎらず , C て、は一般にて、きないということ て、ある。あくまて「定義」とは宣言の特殊な ものて、ある。そのことを忘れてはならない リンケージ 次に , リンケージについて説明しよう。 リンケージとは , 相異なるスコープやあ るいは同一のスコープて、一度以上宣言した 識別子に対して , それらが同一のオプジェ クトや関数を参照しているということを示 すための機構て、ある。 ANSI C には三つのリンケージが存在す る。すなわち外部リンケージ , 内部リンケ ージ , そしてリンケージなして、ある。ひと つのプログラムを形成する複数のコンパイ ル単位やライプラリにおいて , 外部リンケ ージを有する特定の識別子の各実例 ( instan (e) は , 同一のオプジェクトあるいは関数を 意味する。単一のコンパイル単位の内部て、 は , 内部リンケージを有する特定の識別子 の各実例は , 同一のオプジェクトあるいは 関数を意味する。そしてリンケージなしの 識別子は , それぞれ一意な実体を意味する のて、ある。 これらの規則は , もっと大ざっぱにいえ ば , 外部リンケージとはリンカに対する外 部シンボ、ルとして出力される実体て、あり , 内部リンケージとは , 外部シンポルとして は出力されないが , ひとつのコンパイル単 位の中て、は共通の実体て、ある。そしてリン ケージなしとは , 宣言ごとに別の実体が生 み出されるものて、ある。 具体的には , リンケージは次のように決 定する (ANSI 3.1.2.2 ) 。 ①オプジェクトもしくは関数に対する識別 子の宣言がファイルスコープを持ってい て , かっ static という記憶クラス指定子を 有している場合 , その識別子は内部リン ケージになる。 ②オプジェクトもしくは関数に対する識別 子の宣言が extern という記憶クラス指定 子を有していて , かっ同じ識別子に関し てファイルスコープの可視な宣言が存在 すれば , その宣言と同じリンケージを有 する。もしその識別子に関するファイル スコープの可視な宣言が存在していなけ れば , その識別子は外部リンケージを有 する。 ③関数に対する識別子の宣言に記憶クラス 指定子がない場合には , そのリンケージ はあたかも記憶クラス指定子として exte rn が指定されていたかのように決定され る。オプジェクトに対する識別子の宣言
List 4 保養のため温泉へ行って 飲み過きで 体を壊したようなドジ インターバルタイマて、起動するプロセス には , 上記④の制約があるため , この TSR の VSYNC 割り込みを利用するバージョンを 書いてみました。それが coffee. c(List 4 ) て、 す。 VSYNC 割り込みは CRT の垂直同期 ( サイ クルが 1 / 60 秒 ) がトリガて、すから , この場合 も , 毎回の割り込みて、律儀に計時をする必 要はありません。そのへんの工夫を , coun ter という変数を使って割り込みルーチン no tice ( ) の中に盛り込んて、います。 MS ー DOS の TSR が「悪名高い」のは , 性質 が安定て、ないからてすね。この coffee. c も , 他のプログラムとの相性が悪いと正常に動 作しません ( 私の場合 , DOSKEY.COM とい う , DOS 5.0 が提供している TSR70 ログラ ムとの相性が最悪に悪かった ) 。 何かと相性が悪いときは , UsrIntr の値を いろいろ変えてみてください ( 他プログラム における VSYNC 割り込みの使い方に不具合 の原因があるときは , この方法は対策には なりませんが ) 。 プログラミング初心者の方への 重要な警告 割り込みプログラムの制作 ~ デバッグは 茨の道て、す。ときには , 思いもかけぬ大惨 事が起きたりもします。重要なファイル類 ( たとえば制作途上の各段階のソースファイ ル ) は , 必ず別途 , フロッピーなどの上に安 全にバックアップをとってから , プログラ ミング ( とくに危険な時点は , 新たな . EXE を初めて実行するとき ) に取り組んてくださ なお , この coffee. c に関しても , 上記の① ~ ③の制約はそのまま当てはまりますから , ご利用にあたっては注意してください 0 これらの TSR プログラムを作るにあたっ 39 : 40 : } 42 : void dormir( int seconds ) / / see tea. c 44 : long ⅱ m i t : 45 : limit ニ get-biostime() 十 seconds; 46 : while( get-biostime() く limit ) 48 : 49 : } 50 : 51 : VOid interrupt nevint18( unsigned bp, unsigned di, unsigned si, unsigned ds, 52 : unsigned es, uns igned dX,• unsigned CX, unsigned bx, 53 : unsigned ax, unsigned ip, unsigned CS, unsigned flgs ) 54 : { 〃 see 参考文献① : pp63 void interrupt (*intrsave)() : 55 : 56 : uns igned tempDS; 57 : static unsigned oldAX; 58 : 59 : intrsave ニ oldint18; 60 : tempDS : _DS; 引 dAX = ax : 62 : ES = es : _BX = bx ; 63 : _DS = ds : CX = _DX ニ dx; _AX ニ ax; 64 : CX; 〃自分のスタックからコール (because DS may have been changed) intrsave() : 66 : 67 : _AX; 68 : bx ー _BX; _DS ニ tempDS; 69 : 70 : if( ! invsync ) { switch( oIdAX > > 8 ) { case OXOe: case 0x0f: 74 : case 0X14 : 75 : case 0xla: 76 : case OxIb: gen-vsync() ; 77 : 79 : 80 : } 82 : VOid interrupt newvsync( unsigned bp, unsigned di, unsigned Si, unsigned dS, unsigned es, unsigned dX, unsi gned CX, uns igned bx, 83 : unsigned ax, unsigned ip, unsigned CS, unsigned flgs ) 84 : 87 : 88 : 89 : 93 : 94 : 95 : 96 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : } 105 : 106 : VOid interrupt notice( unsigned bp, unsigned di. unsigned si, unsigned uns igned es, unsigned dX, unsigned CX, uns igned bX, 107 : uns igned ax, unsigned ip, unsigned uns igned flgs ) 108 : 109 : { / / This is ユーサ・フ。砒ス 110 : long t i me ; 111 : enable(); 1 12 : / / UsrIntr へ・クタを他にも使用している場合用 113 : / / oldusrintr(); 十十 counter; if( counter > 30 ) { 〃毎回の vsync で計時する必要はない 1 16 : 117 : counter time ニ get-biostime(); 1 18 : if( time > = next-t ) { 119 : switch ( turn ) { 120 : 121 : case 0 : turn return time; d i sabl e ( ) ; if( invsync ) { oldvsync() : }else{ i nvsync oldSS = _SS; oldSP ニ _SP; _SS ニ _DS; (unsigned)stkstrt; _SP : enable() : geninterrupt( Usrlntr ) : / / ユーサ・フ。ロセスを実行 oldvsync() : disable(); _SS : oldSS; _SP ニ oldSP; gen_vsync() ; i nvsync いいいいををリいいいーをりをい C 言語フォーラム 97