[ 横着 ] プログラミング⑩ 図 4 Gauche による Scheme プログラミンク列 % gosh gosh> (list 1 2 3 4 5 6 7 8 9 10 ) ( 1 2 3 4 5 6 7 8 9 10 ) gosh> ( + 1 2 3 4 5 6 7 8 9 10 ) 55 gosh> (map (lambda (x) ( * x 2 ) ) (list 1 2 3 4 5 6 7 8 9 10 ) ) ( 2 4 6 8 10 12 14 16 18 20 ) gosh> (apply + (map (lambda (x) ( * x 2 ) ) (list 1 2 3 4 5 6 7 8 9 10 ) ) ) 110 ルフィルタでも振分け規則をプログラミング言語ふうに書 けるが、 Scheme ほど柔軟ではない。 迷惑メールを自重辰分けするツールとしては、 Spam- Assassin のノ、気か咼いようだ。 SpamAssassin は、遺伝 的アルゴリズムで算出したスコアを規則ごとに割り当て、 その合言によって迷惑メールかどうかを判定する。 振分けをしない派 メールの検索が十分に速けれは振分けなどする必要はな い、という考え方もある。この場合、すべてのメールを振 り分けすに 1 カ所に溜めておく。そして、 foo メーリン グリストのメールをまとめて読みたくなったときは、、 X ー ML-Name: f 。。 " て検索して仮想的なフォルダを作成す る、というように重加勺に振り分ける。 この、、振分けをしない派 " を実現するために、メールを データベースで一括管理したり、全文検索システムと ; 叫秀 できるメーラーがある。しかし、あまり流行っていないと ころをみると、メールをこまめに振り分けておくはうが、 必要なときに、、えいやっ ! " と検索して振り分けるよりも人 間の匪質に適しているのかもしれない。が、この点につい てはまだよく分かっていない。メーリングリストのように 振分け規則か明白な場合は、必要なときに検索して振り分 ける去でも間題なさそうだが、、、友人 " や、、研究 " など、 機朝勺な振分けカ攤しい区分については、日頃から手作業 UNIX MAGAZINE 2002 ユ 2 8 http://spamassassin ・ org/ コマンドラインで g 。 sh コマンドを実行すると、対話 例を紹介する。 以下では、 Gauche による Scheme のプログラミング Scheme プログラミングの例 て振り分けていくしかないのかもしれない。 モードでインタープリタか起動さプログラムを 1 行入 力するたびに結果区ってくる ( 図 4 ) 。 図の例では上から順に ・ 1 から 10 までのリストを作る ・ 1 から 10 までのリストの合計を言 1 算する ・ 1 から 10 までのリストの各要素をそれぞれ 2 倍する ・ 1 から 10 までのリストの各要素をそれぞれ 2 倍して合 計を言 1 算する という処理をおこなっている。この例から、 Scheme フロ グラミングには次の 3 つの特徴があることが分かる。 ・リストを多用する。 ・ (lambda (x) … ) という無名関数を多用する。 ・プログラムの見た目がエキセントリックである。 最大の特徴は最後の、、見た目 " の間題である。 C 言語を 知っていれは、なんとなく Perl のプログラムは読める し、 PerI を知っていれば、なんとなく Ruby のフログラ ムカ売める。しかし、 Scheme の場合はそうはいかない。 Scheme を含め、 Lisp 全般を私カ蒟も堂してきたのは、 の見た目の独特さによるところカ吠きい。 しかし、この問題は慣れてしまえばどうということは ない。括弧が多いのは、プログラムとデータを S 式と いう同じ構造で扱う Lisp の特徴を反映したものである。 Scheme プログラミングの参考書としては、『計算機プロ グラムの構造と角物も [ 2 ] か完評がある。これは Scheme そのものの参考書ではなく、 Scheme を使ったプログラミ ングの孝第斗書である。 scheme の言士様は R5RS (Revised5 Report on the Algorithmic Language Scheme)9 という文書に、 9 http://www.schemers.org/Documents/Standards/ R5RS/ 151
特集プログラミング入門 図 25 リンクの張りなおし XXX 図 26 削除の木好・ XXX 200 YYY YYY ZZZ これとは逆に要素を削除する場合は、削除したい要素の 直前の要素を prev 変数にとっておきます。 次のようなコードを実行します。 p = prev¯>next ; prev—>next = p—>next ; free(p) ; この状態で、 prev の次のデータを削除するため、そのデータを変数 に取り出しておき、 prev の next を取り出したデータの next を指すようにします ( 図 26 ) 。これでリストからの データの削除は完了しますが、取り除いたデータの領域を 解放するために free 関数を呼び出します。 知原のデータを削除するときは、これとは異なる次のよ うな特別なコードが必です。 p = start ; start = p—>next ; free(p) ; リスト内部のノードを操作するのではなく、リストの先 頭を指している変数自身を変更する必要があるため、同し コードでは実現できないのです。 目的のデータを削除するためにその直前のノードも必 なのは、直前のノードの next メンバーも変更しなけれは ならないからです。削除したいデータではなく、その直前 のデータをイ尉寺しなけれは・いけないのは、なんとなく向 的ではありません。それだけならまだいいとしても、この 制限があるために、知頁のノードを操作するとき、特別な コードが必要になってしまうのです。 リストの先頭と内側でコードが変わってしまう問題に は、地直にダミー要素を追加すれは対処できます。地頁の 要素を操作するときには、 prev に頁のダミー要素を保 持しておけば、その他の場合とまったくい膕なコードカ俐 UNIX MAGAZINE 2002.12 用できます。ただし、その際には最初に空のリストを作る ときに少々複雑な処理が必要になります。 start = (list)malloc(sizeof (listelem) ) ; start—>next = NULL ; start—>elem = 0 ; ダミー要素のために領域を石呆し、その next を NULL とすることで空リストとします。 これまで、リンクされたリストでは、リストの終端とし て NULL を用いていましたが、さきほども触れたように これは必頭ではありません。たとえば、末尾のノードが先 頭のノードを指すようにすることも可能です。この場合、 119 指しているのか削除したい要素だとすると、次のコードを たとえば、削除のコードをみてみましよう。変数 p が ます。 をみつけたときに、その要素を耐作できるようになり ポインタをオ絲タします。こうすることで、処理対象の要素 が、 prev には next の反対、つまり、直前の要素を指す next と elem はリンクされたリストの場合と同様です } *dlist, dlistelem; etype elem ; struct —dlist *prev ; struct _dlist *next ; typedef struct —dlist { えば、次のようなデータ構造が考えられます。 の要素を指すようなリンクも追加してしまうのです。たと では、次の要素だけをリンクとしてもっていましたが、前 この間題を鮹夬するのは簡単です。リンクされたリスト の間題か発生します。 も後ろは簡単にみられても、前のはうはみられないのでこ れたリストでは、ある要素をみているとき、その要素より 要素を取り出さなければならないのは同しです。リンクさ 扱えるようになりますが、処理の対象となる要素の直前の 知頁にダミー要素を挿入すれば、すべての要素を同様に ニ重にリンクされたリスト タ構造としては、この循環リストが適しています。 が次々に何かをおこなっていくような様子を表現するデー リスト " と呼んだりしますが、テープルに着席した人たち に並んだデータ構造も作れます。このような構造を、、循環 ダミーのノードを設けなけれは、すべての要素がリング状
特集プログラミング入門 図 22 身長頂に並べた見 この図では next が上に描かれていますが、これは数 多くのデータを並べたときに見やすくするためです。メン バーはどんな順番で書いてもかまいませんが、次の要素を 指すメンバーを一番上に描くと分かりやすくなります。 の図を基本として身長順に並べたデータを表すと、図 22 のようになります。 最後のデータの next には、ポインタとしては有効では ない値の NULL が入っています。それを示すために、 こでは斜線を引いています ( これ以外に、接地記号を描い たり、箱のなかに直接 NULL と書くこともあります ) 。 最後のノードは、ここで紹介した NULL を利用する方 リンクされたリスト など、さまざまなガ去があります。 ・最後のノードの next は自分自身を指す特殊なノードを ・最後のノードの next がその要素自身を指す 最後のノードの next が先頭の要素をまー 法以外て表すこともできます。たとえば、 118 このようなデータ型を用いてリス・トを構築すると、 に定義された etype 型になっています。 はデータを一尉寺するためのメンバーで、そのデータ型は別 elem ここで next が次の要素を指すためのメンバー } *list, listelem; etype elem; struct _1ist *next ; typedef struct —list { 次のようなものです。 リンクされたリストの構造体としての典型的な宣言は、 タ構造が、まさしくリンクされたリストです。 どから紹介している、リンクを用いて次の要素を孑嗣ーデー は、、リンクされたリスト (linkedlist)" でしよう。さきほ 再帰的データ構造のなかで、もっとも基本的なもの 図 23 要素の作成とリンクの張りなおし XXX 図 24 新しい要素乍成 YYY = NULL ; 200 1ist start list p; p = (list)malloc(sizeof (listelem)) ; p—>elem = 100 ; p— >next start ; start = p, といったコードになるでしよう。このコードでは、 etype が int であると仮定しています。リストの先頭をイ墹寺する のが start 変数です。一日判勺にリストの要素尉寺するた めの p 変数も旦言しています。 コードの後半部分では、データをリストの知直に追加し ています。ここでは空のリストの先頭に要素お助日してい ますが、すでにデータが追加されているリストの場合にも コードは同じです。ます、リストの要素をオ内する領域を 石呆し、 next メンバーにはこれまでのリストを指定しま す。さらに、 elem メンバーには登録したいデータを指定 し、変に start 変数がいま作った要素を指すようにしま す ( 図 23 ) 。 リストの途中 ( または末尾 ) にデータを追加する場合、 追加する直前の要素を prev 変数か指しているとすると、 次のようなコードを実行することになります。 p = (list)malloc(sizeof(listelem) ) ; p—>val = 200 ; p—>next = prev—>next ; prev—>next = p , 新たに要素を作り、実際のデータを登録します ( 図 24 ) 。 さらに、作成した要素の後ろに、もともとの prev の後 ろに続くものをつなぎます。また、 prev がいま作った要 素を孑なうにすれは、要素窈助日は完了します ( 図 25 ) 。 UNIX MAGAZINE 2002.12
特集・プログラミング入門 図 33 データのロ後の擲告 も、 prev と next を入れ替えるだけで、 POP 関数を作る ことができます。 その他の言語の場合 今回は c 言語でデクを作成してみましたが、 Perl を使 えば、もうすこし簡単に見できます。というのも、 で作成した 4 つの関数 (unshift 、 push 、 shift 、 pop) は、 perl では配列 ( リスト ) に対する操作としてシステムに備 わっているからです。デクをネ川月化するには、空のリスト 新たな要素をイ寺する領域を石呆し、そこに値を埋め込 を作ります。しかし、あらかしめ宣言されていなければ空 みます。さらに、その next をデクの麪頁要素を孑茆よう のリストとして扱われるので、明カ勺に空のリストを作る にし、 prev はデクのダミー要素を指すようにします。そ 必要すらありません。デクカ啌かどうかは、配列か空かど して、もともとの地頁要素の prev を新たに作成したノー うかを謌・ヾることで簡単に石忍できます。 ドとし、デクのダミー要素の next も作成したノードとし 去も広注目を集めているオプジェクト指向型スクリプト ます。これで、デクの先頭に要素を追加できました。な 高語 Ruby も、 perl と同しく 4 つの関数をもっていま こでは unshift 関数しか示していませんが、 prev す。これに加えて、先頭要素を参照する first 、末尾要素 お、 と next を入れ替えるだけで push 関数もまったく同様に を参照する last などもあるので、 Ruby でもデクは簡単 作れます。 に実現できます。 10 を unshift 、 20 を push 、 30 を unshift すると、図 リストの操作か得意な言語は、これら以外にもたくさん 33 のような構造になります。 あります。たとえば Lisp は、その名称が LISt Processor データの取出しも、落ち着いてリンクの張りなおしをお に由来することからも分かるように、リストの処理か得意 こなえば問題はありません。 shift 関数で頁からデータ 中の得意です。ただし、 Lisp で扱うリストは普通のリン を取り除き、 pop 関数で末尾からデータを取り除きます。 クされたリストに近いものなので、スタックやキューとし また、これらの関数は取り除いたデータの値を返すものと て使うぶんにはよくても、デクとして利用しようとすると します。ここでは、 shift 関数をみていきましよう。 ちょっと苦労します。 皆さんがよく使う言語では、リストやデクが手軽に扱え int るでしようか。一度石忍、しておくと、何かのときに役立つ shift (deque q) かもしれません。 ( いまいずみ・たかし千葉大学 ) 20 30 V ; deque p; if (empty(q) ) return 0 ; p = q¯>next ; q—>next = p¯>next ; q—>next—>prev = q; v = p—>val ・ free(p) ; return v; お詫びと訂正 前号の「特集・プログラミング入門」に下記の尉直があり ました。お詫びして訂正いたします。 ・ 113 ページ左段の「構造化フ。ログラミング」の項 誤 : do—until 付区し ) 正 : do—while 併駒区し ) ます、デクが空でないことを石忍し、続いてダミー要素 の next 、すなわち地頁の要素を p にイ尉寺します。さらに、 この要素を二重にリンクされたリストから注意架く切り離 し、そのノードにオ絲タされている値を返します。この場合 125 UNIX MAGAZINE 2002 ユ 2
特集・プログラミング入門 ニ重にリンクされたリストでの削除 図 27 をすぐに指し示すことができます。 リストを使う便利なデータ構造 リストについての説明をひととおり終えたところで、リ スト橢置を利用して作成できるイ叫リなデータ構造を 3 つほ ど紹介しておきましよう。 スタック 最初はスタックです。、、スタック・オーバーフロー " や 1 算機のスタックポインタ " 、あるいは、、局所変数はス タックにとられる " など、この用語はいろいろな場面で使 われます。これらは、いすれも以下に紹介するスタックと いうデータ構造と関係があります。 スタックは、データを順番に入れてゆくことができ、取 り出すときは最後に入れたものから順に取り出せるという 実行すれ ( 誚リ除できます ( 図 27 ) 。 データ構造です。 p¯>prev—>next = p¯>next ; 机の上に書類がうずたかく積まれている状況を想像して p—>next—>prev = p—>prev ; free (p) ; みましよう。強引に下から抜き出そうものなら、書類の 山カ繃れて大騒ぎになってしまいます。そんなところに新 データの追加についても、みつけてある要素の直前に追 たに重要な ( 不要な ? ) 書類が届くと、その山の上に積ん 加するのも簡単です ( 図 28 ) 。 でいくことになるでしよう。ある日、仕事がひと段落し、 q = (dlist)malloc(sizeof(dlistelem) ) ; 溜まっている書類の整理にとりかかります。この場合も、 q->elem = 300 ; q—>next = p ; 下のほうから書類を抜き出すことはできないので、一番上 q—>prev = p—>prev; にある : 書類から順番に処理していきます。ある程度書類が p—>prev—>next = q; p—>prev = q; 減ったところでふたたひ新たな書類が届くと、残っている 書類の山の上に積まれていきます。したがって、最初に置 それほど便利なら、いつでも二重にリンクされたリスト いた書類は、その他のすべての書類の処理か終らなければ を使えばよいと思うかもしれません。しかし、よく見てく 取り出せません。 ださい。リンクの数が 2 倍になっているために、それぞれ の操作にかかる手間もほば 2 倍になっています。通常のリ 通常、スタックに対しては、次の 4 不鶤頁の操作を定義 ンクされたリストで処理が可能な場合には、この手間を嫌 します 9 。 ってリンクされたリストを利用することもよくあります。 empty : スタックが空かどうかを調べる。 二重にリンクされたリストでも、その末端については何 push : スタックに 1 つデータを積む。 通りかの表現ガ去があります。もちろん、両端に NULL pop : スタックから 1 つデータを取り出す。 を代入しておくこともできますし、循環リストになるよう top : スタックの一番上にあるデータを見る。 にそれぞれ逆の端のノードを指してもかまいません。さら に、ダミー要素も含めて循環リストの形式にしておくこと これらの操作と、スタックを作る操作を C 言語で定義 も可能です。つまり、先頭の要素の前、末尾の要素の後 してみましよう。 ろにダミー要素を配置するのです。このようになっている と、ダミー要素を指すポインタをもつだけで、う頁と末尾 9 pop と top を 1 つ窈篥作として定す - る場合もあります。 XXX ZZZ YYY ニ重にリンクされたリストでの自加 図 28 XXX ZZZ 一三ロ 300 120 UNIX MAGAZINE 2002 ユ 2
特集・プログラミング入門 図 31 dequeue 操作後のキュー 図 32 空のデク 100 struct —deque *prev ; int va1 ; } *deque, dequeelem; 新しいデクを作るときは、ダミーノードのみの一重にリ ンクされたリストを作ります。 deque new—deque (void) 実際に削除する操作は、キューカ啌でないときにおこな います。よくみると、この操作では地頁にあるダミー要素 deque q; か取り除かれてしまいます。しかし、これでよいのです。 q = (deque)malloc(sizeof (dequeelem)) ; if (q = = NULL) return NULL ; 図 31 を見てください。これは、さきはど 100 を追加 q—>next = q->prev = q; したキューに対して dequeue 操作をおこなったあとの様 q— >val return q; 子を示しています。 enqueue によって」助日された要素カ戯ってはいますが、 これはダミー要素として扱えばいいでしよう。 p = q—>head; q—>head = p— >next ; free(p) ; return V ; こで作成される構造は、図 32 のようになっています。 デクカ啌かどうかを調べるのは簡単です。 next か prev のどちらでもかまいませんが、これらが自分自身を指して いるかどうかを調べるだけです。 int empty(deque q) return (q & & q->next 次は、データ窈巣作です。リストの地寬こデータを j 助日 するのが unshift 関数、リストの末尾にデータを追加する のが push 関数だとしましよう。すると、 unshift 関数は 次のように言当できます。 int unshift(deque q, int v) deque p ; p = (deque)malloc(sizeof (dequeelem) ) ; if (p NULL ) return 0 ; p —>va1 V ; p —>next = q—>next ; p—>prev >next— >prev = p ; q —>next テク 3 番目に紹介するデータ構造はデク (double-ended queue) です。これは、両頭待ち行列などと呼ばれること もあります。名前は難しそうですが、データ構造としては 単純で、ちょうどスタックとキューの両方の機能をもつよ うなものです。 スタックやキューでは、データの追加や削除は、あらか しめ決められたどちらか一方の端でしかおこなえません。 これに対し、デクでは j 助日や削除の操作がどちらの端でも 自由にできます。見方を変えれは、キューやスタックがデ クク芋殊な形態ともいえるでしよう。 デクを実現する場合は、両端で自由な処理ができなけれ ばならないので、二重にリンクされたリストを使うとよい でしよう。ダミー要素を設け、リンクを循環したリンクに しておくとプログラムか簡単になります。 では、プログラムを見てみましよう。まず、データ構造 です。二重にリンクされたリストとして deque 型を宣言 しています。 typedef struct —deque { struct —deque *next ; 124 UNIX MAGAZINE 2002.12
特集・プログラミング入門 キューに 100 をミロ 図 30 図 29 空のキュー 100 0 キューにデータを追加する enqueue では、リストの末 尾に要素お助日し、 tail によって新たに追加された要素を 指すようにします。 int enqueue (queue q, int v) list p; p = (list)malloc(sizeof(listelem)) ; if (p = = NULL) return 0 ; p->val = v; p—>next = NULL ; q—>tail—>next = p ; q—>tail = p; return V ; typedef struct —list struct —list *next ; int va1 ; } *list, listelem; typedef struct —queue { list head; 1ist tai1; } *queue , queueelem; 前半では、普通のリンクされたリストを宣言していま すが、これがキューを表す実体となる部分です。後半の queue 型でリストの麪直と末尾をイ尉寺し、アドレスがユー ザーに渡されます。 最初に空のキューを作るのは、空のスタックの場合より も操作がすこし複雑になります。ます、ダミー要素だけの さきほどの空のキュー ( 図 29 ) に値 100 を追加すると、 空のリストを作り、 head と tail の両方がその要素を孑嗣ー 図 30 のように変わります。 ようにすればいいでしよう。 キューの知頁の値を見る peek 操作では、ダミーの要素 の次にある要素の値を取得する必要があります。これは、 queue new—queue (void) ( アロー演算子のオンパレードになってしまいますか ) 次 のように実現できるでしよう。 queue q; q = (queue)malloc(sizeof (queueelem)) ; int if (q = = NULL) return NULL ; peek(queue q) q—>tail = q—>head (list)malloc(sizeof(listelem)) ; if (q & & q—>head & & q—>head—>next) q—>head—>next = NULL ・ return q—>head¯>next—>val ; q—>head—>val = 0 ; return 0 ; return q; 最後はキューの地頁からデータを取り除く操作です。ス タックの p 叩操作と同様、取り除いた : 麪頁の値を返すよ うにしましよう。そのため、ます peek 関数を呼び出して 頁の値をイ尉寺しておきます。 最初に空のキューを作ったときの様子は、図 29 のよう に表せます。 この図からも分かるように、キューか空の場合は head と tail が同し要素を指します。この性質を利用すれは、 empty 関数はきわめて簡単です。 int empty (queue q) return (q & & q—>head int dequeue (queue q) int v = peek(q) ; list p; if (empty(q)) return 0 ; = q->tail) ; 123 UNIX MAGAZINE 2002.12
特集・プログラミング入門 以下では、スタックを表現するためのデータ構造とし て、リンクされたリストを使います。スタックを実現す る場合は、データの追加や削除をおこなうのは片方の端か らだけです。かならすリストの : 麪頁でおこなうことにすれ は、逆向きのリンクは不要なので、鵰屯なリンクされたリ ストで - ト分です。ただし、スタック作成用の関数から返さ れた値はユーザーの缶旺に置かれてしまうため、スタッ クに値が追加されるたびにその値を変更するわけにはいき ません。そこで、リストにダミーの要素を設け、実際の処 理はダミーの要素より後ろ側でおこなうことにします。 この方針に従うと、データ構造はおのすと決まってき うしておけば、ユーサーに渡した値を変更せすにスタック } *stack, stackelem; int va1 ; struct _stack *next ; typedef struct —stack ます。 の内容を変えられます。 ドを作り、その next が NULL を指すようにすればいい 最初にスタックを作成するための関数は、ダミーのノー 仮定しています。 こでは、スタックにオ褓内するデータは整委哲 ! ! であると stack s ; new—stack (void) stack でしよう。 スタックか空かどうかの石忍は、渡された値がスタック のダミーノードになります。 クしています。関数自身の戻り値は、いま作成したばかり この関数では、 malloc 関数の戻り値もきちんとチェッ return S ; s—>next = NULL ; if (s = = NULL) return NULL ; S (stack)malloc(sizeof (stackelem) ) ; を示すものか、さらにスタックにデータか存在するかを調 べれば簡単に実現できます。 int empty (stack s) return (S s—>next = = NULL ) ; UNIX MAGAZINE 2002.12 この検査では、まず s が NULL でないことを石忍して から next メンバーの内容を調べています。これにより、 誤って NULL か渡されたとしてもプログラムが異常終了 しないようにしています。 スタック上にデータを積んでゆく push 命令の引数は、 スタック自身と、スタックに積む値てす。 int push(stack s, int v) stack p; p = (stack)malloc(sizeof (stackelem) ) ; if (p = = NULL) return 0 ; p—>val = v ; p— >ne xt s—>next ; s—>next = p; return V ; 新たな要素のために領域を石呆し、その val メンバーに 値を代入して、リストの地頁の要素として追加することで 実現しています。 その時点でのスタックトップ ( スタックの一番ー E) の値 を調べる top 関数は、スタックが空でないことを石忍し て、頁の要素ロ絲タされている値を返します。 int top(stack s) if (s & & s—>next) return s—>next—>val ; return 0 ; スタックに要素がない場合はエラーを示す値を返したい ところですが、スタックトップはすべての整数になりうる こでは、 0 ( ゼロ ) ので、これといった値がありません。 を返すことにしています。 次は、スタックからデータを取り出して捨てる pop 関 数です。 top 関数があるので pop 関数では値を捨てれば よいのですが、せつかくなので、戻り値としてその値を返 return V ; free(p) ; s—>next = p—>next ; p = s—>next ; int v = top(s) ; stack p; pop (stack s) int しています。 121
ー横【着ープログラミング⑩ 図 7 対応する括弧をハイライト新 まオ図 File Edit 0 005 日ⅶ e T00 は Help ー設定 っても 大丈夫でづよ 表 1 S 式を扱うための Emacs のキー操イ乍 意味 S 式を削除する S 式をマークする 1 っ先の S 式にカーソルを進める 1 つ前の S 式にカーソルを戻す 前後の S 式の啣を入れ替える S 式をインデントする 1 つ前の S 式を削除する 1 っ先のリストにカーソルを進める 1 つ前のリストにカーソルを戻す 1 つ内側のリストにカーソルを進める 1 っ外側のリストにカーソルを戻す C- M- k C-M-SPC C-M- f C-M-b C-M-t C-M-q C- M-Backspace へメールを送信するには、大のようにこの関数を呼び出 C-M-n す。メールは標準入力から読み込むものとする。 C- M-p C- M-d (send—mail "localhost" 25 (current—input—port) C- M- u "foo@example.org/ "bar@example. com") S 式を扱うキー操作 このように、 Gauche を使えば Perl や Ruby と同様 Emacs には、 S 式を扱うのに便利なキー操作か数多く の手軽さで Scheme による実用的なプログラムか書ける。 用意されている。これらをすべて暗記する必要はないが、 Emacs で楽々 S 式 C-M-klO と C-M-SPC (SPC はスペースキー ) は億えて おくと便利である。開き括弧の上にカーソルを置き、 C- M-k を叩けば対応する括弧の内側をすべて削除できる。 S 式は、括リ励ゞ多くて煩わしいという理由で毛嫌いされ S 式を扱うキー操作を表 1 にまとめておく。 ることが多い。瓜については、物黼 5 雄氏の次のような Lisp モードや Scheme モードでは、 TAB キーを押す 言葉がある [ 3 ] 。 だけで適切に S 式をインデントできる。 scmail の設定フ 「弟子が尋ねた。『先生、私は先生がカッコをまるて魔術 ァイルでは最初の行に、 師のように扱っているのを常々苟匱しています。どうすれ ー * ー scheme ー * ー ば先生のようになれるのでしようか ? 』 というコメントを入 Emacs で設疋ファイルを開くと 師『えっ ? カッコ ? あ、そうか。そんなものもあったな。 Scheme モードで編集できるようにしている。 いやあ、すっかり忘れておったわ』」 このよ第也に達するのは難しいとしても、 Emacs を使え 括弧の色を薄くする ば S 式を上交的容易に操作できる。すくなくとも私は、 画面上か話弧だらけという見た目をやわらげるために、 Emacs を使っているぶんには括弧の存在はさほど気にな Emacs で Scheme のプログラムを書くときは瓜の色を らなくなってきた。 薄くしている。 Scheme でしばらく試して気分がよかった ので、 C 言語でも同様に括弧の色を薄くしてみた ( 図 8 ) 。 対応する括弧をハイライト表示する 瓜の色を薄くするには、図 9 の設定を ~/. emacs に加 /. emacs に次の 1 行を追加すると、対応する瓜をハ えればいい。 イライト表示させることかできる。 おわりに (show—paren-mode) 今回は、私が開発したメールフィルタ scmail をとり show-paren-mode では、カーソルが開き括弧の上お よひ閉じ括弧の直後にきたときに、対応する瓜が自動酌 あげ、あわせて Scheme プログラミング刎列を紹介した。 scmail はこだわりをもって Scheme で実装したが、プロ にハイライト表示される。図 7 では、閉し括弧の直後に カーソルを置き、対応する 2 っ窈舌弧をハイライト表示さ 10 control キーと Alt (Meta) キーを押しながら k キーを押す。また は、 ESC キーを押してから ControI キーと k キーをこ押す。 せている。 153 UNIX MAGAZINE 2002 ユ 2
特集プログラミング入門 ます、スタックトップの値をイ尉寺しておき、地直の要 素を捨てればこの操作は完了です。 スタックは、一時的に状態を保存しておいてほかの作 業をおこない、あとでもとの状態に戻す場合などに便利で す。たとえば、数式を逆ポーランド去に変「彡したり、文 中に現オ・しる括弧の対応をとったりするような場合に使えま す。 次のプログラムは、スタックを使って括弧の対応を調べ while ()c = getchar() ) !=EOF) s = new_stack() ; int C ; stack s ; main(void) int るものです。 switch(c) { case ) ( push(s , case [ ) push(s , case ) { push (s , case ) ] case ' } break; break ; break; if (POP(S) ! = c) { exit(O) ; exit(l); printf ( "Unba1anced\n" ) ; if (!empty(s)) { exit(l); printf ("Unba1anced\n") ; 122 もエラーメッセージを出力します。 る閉じ瓜のない瓜があったことになるので、このとき の入力を読み終えてもスタックか空でない場合は、対応す かしいのでエラーメッセージを出力します。また、すべて 等しいかを石忍します。これ力等しくなければ、何かがお 凵刮瓜をみつけた場合は、そ功ゞスタックトップの記号と 括弧をスタックに積んでゆきます。逆に、入力のなかに閉 入力のなかに開き括弧をみつけるたびに、対応する閉し キュー もう 1 つの有用なデータ構造はキュー (queue) です。 スタックは、最後に入れたデータか最初に出てくるため、 LIFO とか FILO などと呼ばれますが、キューは最初に入 れたデータか最初に取り出されるために FIFO (First ln FirstOut) と呼ばれます。スタックと同じく、キューも 基本的なデータ構造であり、計算機の世界でもさまざまな ところに顔を出します。たとえば、オペレーティング・シ ステムは一殳にプロセスキューを用いてプロセスの管理を おこないますし、ネットワークを介してデータをやりとり する場合は、メッセージキューにメッセージを登録するこ ともあります。 キューは、筒のようなものをイメージすると分かりやす いかもしれません。片方の端からどんどんデータをる当求で きますが、取り出せるのはもう一方の端からだけです。し たがって、最初に入れたデータが最初に取り出されるとい うわけです。 通常、キューに対しては、次の 4 不頁の操作を定義し ます 10 empty : キューか空かどうかを調べる。 enqueue : キューに 1 つデータを j 助日する。 dequeue : キューから 1 つデータを取り出す。 peek : キューの知直のデータを見る。 それでは、これらの操作とキューを作る操作を c 言語 で定義してみましよう。 キューを表現するデータ構造としては、基本的にはリン クされたリストを使います。ただし、通常どおりに麪頁だ けをイ尉寺しているとデータの追加や削除が両端でおこなえ ません。そこで、知頁だけでなく、末尾の要素もイ尉寺する ことにします。データを追加するときは末尾の要素に j 助日 し、データを削除するときは麪頁の要素から削除します。 キューを表すデータ構造としてユーサーに返す値は、この リストの両端を閑寺するデータ構造のアドレスにしておき ます。こうしておけば、 : 麪頁や末尾の要素か変わっても、 その部分を書き換えられるようになります。 この方針に従ってデータ構造を作ると、次のようになり ます。 10 キュークメ昜合も、 dequeue が peek の彳難リを兼ねる場合があります。 UNIX MAGAZINE 2002.12