効果的なリスト処理でプログラミングを改善する

Cで、あるいはもっと賢く、Schemeでリンク・リストを使う技法

単方向リストは強力な抽象化であり、これを使うことによって、様々なデータ型を表現できるようになります。こうしたリストを拡張し、任意のデータ型を扱えるようにすると、データ処理用の強力なツールとなります。この記事では、こうしたプロセスを検証します。また、使いやすいリスト指向言語であり、Lispの変種であるSchemeについても解説します。Schemeを使うことによって、Cの複雑さを持ち込まずに、リスト操作機能を実現できるようになります。

Jonathan Bartlett (johnnyb@eskimo.com), Director of Technology, New Medio

Jonathan BartlettはLinuxアセンブリー言語を使ったプログラミングの入門書Programming from the Ground Upの著者です。New Media Worxでの主席開発者であり、顧客向けにWebアプリケーションや、ビデオ、キヨスク、デスクトップなどのアプリケーションを開発しています。連絡先はjohnnyb@eskimo.comです。



2005年 1月 05日

リスト処理は、コンピューターの持つ強力さの一つです。単方向リストは、興味深いアルゴリズムや手法の基礎となっており、プログラミングのあらゆる面に利用できるものです。この記事では、こうした手法と、こうした手法をCの複雑さを持ち込まずに実現できる、単純な言語について解説します。

まず、リンク・リストについて、もう一度調べてみましょう。

リンク・リストの復習

単方向リストは、ノードが順番につながっているデータ構造です。この構造では、各ノードは、データ要素と、つながっている次のノードへのポインターを含んでいます。概念的には、リンクが一つの整数リンク・リストであれば、コンピューター・メモリーの中では、次の図のようになっています。

図1. 数字のリンク・リストの例
An example of a linked list of numbers

この図で矢印は、メモリー中での次のノード位置へのポインターを表します。リストの順序は矢印によって決まり、メモリー内でのノード位置で決まっているわけではないことに注意してください。

最後に、シーケンス最後のノードは矢印ではなく、単純に記号を持っていることに注意してください。これは、これ以上このリストにはノードがないことを意味します。この記号は通常、ヌル値、ヌル・リスト、ヌル・ポインターなどと呼ばれます。

この記事では、単方向リストのみを扱い、「リンク・リスト」と「リスト」はどちらも、単方向リストを意味するものとして使います。

リスト・ノードの構造

C++では、リンク・リストの実装が標準テンプレート・ライブラリーに含まれていますが、ここで紹介する手法には、標準テンプレート・ライブラリーの実装は適当ではありません。

リンク・リストのコーディングは、ごく単純です。例えば上の図で示した整数のリンク・リストは、Cでは次のようなノード構造で表現できます。

リスト1. 基本的な、リンク・リスト・ノード構造
#define NULL 0
struct ll_int_node {
   int data;
   struct ll_int_node *next;
};

ここでは、最初の要素をデータ項目として、また2番目の要素を次の要素へのポインターとして含む構造体(struct)があります。NULLは、単純にヌル・ポインター (0) として定義されますが、これは、ヌル・ポインターは、ポインターとしてはいずれにせよ無効なためです。プログラム中で、この種のリストを変数に持たせるために必要なのは、構造体、ll_int_node型を指すポインターを持つことだけです。このポインターは、リスト中の最初の要素(「ヘッド」と言われます)を指します。

一般的なリスト操作を復習する

標準のリンク・リスト実装では、基本的な2つの更新操作が行われます。リストへのノードの挿入(inserting)と、リストからの削除(removing)の2つです。

リンク・リストに関する私の手法は別の観点に基づいているので、これらの操作の解析には、あまり時間をかけないことにします(私の手法に関しては後ほど説明します)。こうした方法は、ノード構造の割り当て、あるいは割り当て解除を行ってから、対象ノードがリストの中に正しい順番で置かれるようにポインターを修正することによって、容易に実装することができます。

概念的には、単に矢印を移動するだけのことです。ただし、挿入や削除によってリストの先頭が変更された時には、その更新が確実に行われるように注意する必要があります。リンク・リスト操作の基礎について詳しくは、この記事の最後にある参考文献を見てください。

データを保存する: より一般的なリスト構造

リストに保存したいデータ型ごとに別のリスト・ノード構造を作らなければならないとしたら、特に、一つのリストに複数の型のデータを保存したい場合には、非常に面倒です。そこで、任意のノードに任意のデータ型を保存できる、より汎用的なデータ処理方法を紹介しましょう。

ノード内に任意のデータ型を保存するために、基本的なCデータ型の場合は直接操作され、複合型の場合はポインター経由で操作される構造を定義します。

この、2重のデータ処理モードを実現するために、typetagを使います。typetagは整数の変数であり、その整数の値が、操作されるデータ型を規定します。基本的なCデータ型では、typetagによって、どのデータ型が使われているかを知ることができます。複合型の場合は、単純にポインターを使えば、どの型の構造体にポインターが向いているかをtypetagで知ることができます。リスト2はこの構造の定義を示しています。

リスト2. 汎用のデータ型構造
typedef struct {
   int typetag;
   union {
      long long_member;
      double double_member;
      char char_member;
      void *pointer_member;
   };
} data;
/* Example declaration */
data my_data;

この、汎用データ構造を有効に使うためには、(ポインターの型を含めて)必要な型それぞれに対して、typetagへ設定する値を用意する必要があります。リスト3は、typetagに基づいて様々なデータ型を表示するための、完全なプログラムを示します。

リスト3. typetagを使ったプログラムの例
#include "stdio.h"
/* Typetags for builtin types */
#define TYPETAG_LONG 1
#define TYPETAG_DOUBLE 2
#define TYPETAG_CHAR 3
/* The structure definition from before */
typedef struct {
   int typetag;
   union {
      long long_member;
      double double_member;
      char char_member;
      void *pointer_member;
   };
} data;
/* Example struct */
struct person {
   char name[200];
   char address[200];
};
/* Typetag for a pointer to our struct */
#define TYPETAG_PERSON_PTR 4
void display(data d)
{
   if(d.typetag == TYPETAG_LONG)
   {
      printf("%d\n", d.long_member);
   }
   else if(d.typetag == TYPETAG_PERSON_PTR)
   {
      struct person *p = (struct person *)d.pointer_member;
      printf("%s\n%s\n", p->name, p->address);
   }
   /* I could go on for each type, but this is good enough for an example */
}
int main()
{
   data my_data;
   data more_data;
   struct person *p;
   /* Use the "long" type */
   my_data.typetag = TYPETAG_LONG;
   my_data.long_member = 3;
   /* Use the "person" type */
   p = (struct person *)malloc(sizeof(struct person));
   strcpy(p->name, "Test");
   strcpy(p->address, "Test's Address");
   more_data.typetag = TYPETAG_PERSON_PTR;
   more_data.pointer_member = p;
   display(my_data);
   display(more_data);
   return 0;
}

もっとオブジェクト指向にしたいのであれば、vtablesの配列のインデックスとしてtypetagを使うこともできます。typetagのそうした使い方はこの記事の範囲外ですが、typetagの潜在力を示すものです。しかし、ずっと原始的な私の手法でも、どんなに多くのデータ型をも網羅できる、単一データ構造の概念は用意されています。

この新しい汎用データ型を武器にすると、リスト4のように、非常に汎用的なリスト・ノード構造を作ることができます。

リスト4. 汎用ノードを使ったリンク・リスト
struct generic_node {
   data the_data;
   struct generic_node *next;
};

この、汎用リスト・ノード構造を使うと、中に保存されているデータの型によらず動作するリストとリスト操作を定義することができます。このデータの種別を識別する機構(typetag)は多少のオーバーヘッドを生じますが、リストを次から次に再コーディングする面倒と比較すれば、通常は充分価値のあるものです。

C++では、このオーバーヘッドはテンプレートを使うことで緩和することができます。実際、(Javaの Objectクラスのような)汎用ベース・クラスを作れば、カスタム実装のtypetagを用いた機構ではなく、単にC++言語の型を分類する機構を使うことができます。この方法は、typetag機構を使う方法よりも少し劣りますが(typetag機構は、基本型に対してはポインターのオーバーヘッドがありません)、複合型を相手にする場合、あるいは基本型をクラスの中にラップすることをいとわない場合には、やはり有効です。

リンク・リストでメモリーを管理する

リンク・リストに対して手動でメモリー管理をすることも可能ですが、あまり簡単ではありません。例えば、リストからノードを削除する時には、忘れずに、そのノード構造に対するメモリーを解放しなければなりません。これはそれほど難しいことではありませんが、ノードのデータ部分がポインターであったり、ポインターを含んでいたりする場合には、特に、プログラムの中に明確で普遍的なメモリー管理ポリシーがない場合には、問題が起きることになります。

例えば、オリジナルの構造自体ではなく、データ構造のコピーのみをリストに置くことを要求するポリシーの場合には、自由にメモリーを解放することが出来ます。ところが、普通の人は単に共有ポインターを渡すだけでスピードを向上させ、メモリー使用を減らそうとしがちです。そうした場合には、メモリー管理は、もっとずっと複雑になります。

また、メモリー管理に関する難問として、リスト・ノードの部分的共有があります(これについては、この先で説明します)。もしリストのノードを共有していると、リスト要素、あるいはリスト全体を削除したとしても、それらがまだ他で使われている場合には、メモリーを解放するように要求されない可能性があります。

こうしたメモリーの問題があるので、この先では、プログラムにガーベジ・コレクターがあるものと想定することにします。プログラムにガーベジ・コレクターを追加するのは簡単な上、メモリー管理の問題を気にせずに、否応なくデータ構造を共有できるようになります。(もし皆さんが否応なくデータ構造を共有するという経験がないのであれば、楽しみを逃していたことになります。)

データ構造の共有は、注意して行わないと、他の問題にもつながります。これは、ポインターを通してデータ構造を共有する場合には、どれかのポインターによってデータ構造が更新されると、その構造を指すポインターすべてが影響されるからです。

developerWorksの記事、「メモリー管理の内側」(参考文献)では、ガーベジ・コレクターの追加を含めて、様々なメモリー管理手法を解説しています。

では、これから使うリンクの特性を調べてみましょう。


共有サブリストを使って高度なリスト・プログラミングを行う

リンク・リストが扱えるようになったので、これから使うリストに関して、面白い特性を幾つか知っておく必要があります。

  • ノード構造は一方向にしか行かないので、ノード構造は自分の前にあるノード・シーケンスを全く知らない。
  • ノードは自分の前にあるノードのことを全く知らないので、各ノード自体がリストの開始位置である。
  • ノードは自分の前にあるノードのことを全く知らないので、対象のリストは、実際は他の多くのリストのサブリストである可能性がある。

次の図は、リストの持つ、こうした特性を理解するためのものです。

図2. リスト共有の例
Examples of list sharing

この図には3つのリストがあります。最初のリストは(1 57 26 9)というシーケンスです(ここから先では、読みやすくするためにリストを括弧の中に入れて示します)。さて、このリストは幾つかのサブリストを含んでいます。図の中で、一つのサブリストは(57 26 9)として破線で囲まれていますが、(26 9)(9)、それに()なども、最初のリストの、有効なサブリストです。

最後の例、()は、空のリスト、あるいはヌル・リストを参照するものとして使われています。ノードに対する矢印は一方向だけを指すので、サブリストを使う場合には、データへの変更は許されません。

この図には、プレーンなサブリストの他に、共有サブリストの例もあります。リスト(18 32 26 9)は、実は最後の2つのノードをオリジナルのリストと共有しています。これは、オリジナルのリストに加えられる変更が、このリストにも影響することを意味します。従ってこのリストは、最後の2つのノードに対して追加のメモリーを必要としません。また、このリストは他のリストのサブリストであるかも知れず、他のリストも、サブリストとして(26 9)を使っている可能性があります。

先に触れた通り、共有リストを利用するためには、メモリー管理(恐らくガーベジ・コレクション)が必須です。

サブリストを使ってロックを避ける

リンク・リストの利点の一つは、ロックを避けるために使えることです。例えば、ゲームのプログラミングを行っていると仮定しましょう。このゲームに対して、描画可能なオブジェクトのそれぞれに対してリストを維持し、また、描画スレッドはゲーム・スレッドと独立に実行している、とします。ゲーム中に時々、このリストにオブジェクトを追加したり、リストからオブジェクトを削除したりする必要があるかも知れません。リストからオブジェクトを削除するにはリストのロックが必要ですが、リストにアイテムを追加する(例えば発射された弾丸)場合には、そのアイテムがリストの前に追加されるのであれば、ロックを必要としません。たとえ描画中にゲーム・オブジェクトが追加されたとしても、現在描画されているノードには影響しないことが分かっているので、描画スレッドは何ら気にすることなく、単純にオブジェクトのリストを繰り返します。描画しているのは単に、新しいオブジェクト・リストのサブリストなのです。

この手法は、繰り返しと追加の両方が頻繁に行われるような、順序づけされていない集合がある時には常に効果的です。リストの前に追加するのである限り、既存のリスト構造に触れる必要すらありません。ですから、他のスレッドが既存のリスト構造に対して自由に繰り返しを行うことができます。ただし、リストの前ではなく、最後に要素を追加した場合には、リスト構造自体を直接変更してしまうことに注意してください。もし一つのスレッドがリストの最後に追加を行い、別のスレッドがそのリストに対して繰り返しを行っている場合には、競合条件が起きる可能性があります。

共有サブリストを使って取り消し操作を行う

共有サブリストが非常に有効なアプリケーションは幾つかありますが、その一つが取り消し操作(undo)です。文書を追加専用のリンク・リストとして構成すると、変更を前の状態に戻すことが容易にできるようになります。

そうした文書の一例は次のようになります:(modification3 modification2 modification1 original-document)。この工夫によって、どんな変更も、単にリストのヘッドをサブリストに移動するだけで取り消すことができます。undoを2回行うと、この文書は次のようになります:(modification1 original-document)

規定した点から文書を共有する分岐を作ることによって、その文書の複数バージョンを作ることもできます。これは、例えばCVSにおける分岐の背景にある概念です。オリジナルの文書に対する変更セットとして、先に示した変更の他に(branch-modification2 branch-modification1 modification1 original-document)を作ることもできます。

リストを使ってツリーを表現する

リストは、マルチ・ノードのツリーを表現するために使うこともできます。バイナリー・ツリーは、データ値と左右のポインターを持つノードで表現されます。ただし、単なる左右分岐以上のツリーを要求するデータ構造も数多くあります。リストを使うと、そうしたツリーが非常にうまく表現できるようになります。

リスト構造が扱えるのは直線的に連続した値のみではなく、共有サブリストを使って「逆ツリー(inverted trees)」を扱うこともできるように思えるかも知れませんが、そうではありません。複数のリストが同じサブリストを共有している場合には、図として見るとツリーのように見えるかも知れませんが、リストは一方向に直線的にしか進めないので、ある分岐から別の分岐に行くことはできないのです。ですから本当のツリーを表現するためには、別の方法が必要です。

上記では、ノード中で任意のデータ型が使えるようにするための、付加型の使い方を説明しました。この概念を使うと、リスト・ノードへのポインターをノードに保存することもでき、リスト・ノードに対するデータとしてのリストを持てるようになります。下記がその一例です。

図3. リンク・リストを使ったツリーの例
An example of a tree using linked lists

それぞれのノードは、ブランチあるいはリーフです。これは、単純にリストをリスト内の値として使うことで、括弧標記で表現することができます。前の図は、 (((15 42) 22 18) 32 (6 2))のように表現することができます。これを調べてみると、単に3つの要素、つまり(element1 element2 element3)という3つの要素のリストにすぎないことが分かります。ここでelement1はリストであり、element2は数字の32、element3はリスト(6 2)です。element1に対するリストは、それ自体、最初の要素がリスト(15 42)であるツリーであり、残りの2つの要素が2218です。つまり、リストのリストを使うことで、任意の数のブランチとリーフを持つツリーを表現できるのです。

ツリーを使って構文を表現する

ツリーの使い方として素晴らしいのは、コンピューター言語の構文をツリーで表現することです。コンピューター言語は、階層構造を持った言語構成体ツリーと見ることができます。最上部にはプログラム全体があります。このプログラムは、任意の数の表現から成る、任意の数のステートメントから構成されています。こうした点から見ると、ツリーは(特にマルチ・ノードのツリーは)コンピューター言語を表現するために理想的なものです。

一例として、次のような構文を持つ、ifステートメントを構文解析する例を見てみましょう。

リスト5. ifステートメントの構文の例
if(x > y)
{
   call_some_function(a, b, c);
}

この表現では、各リストの最初の要素は言語の演算子、動作、あるいはファンクション・コールを表し、残りの要素は引き数を表します。これに対する構文解析ツリーは、次のようなものになります。

図4. リンク・リストを使った構文解析ツリーの例
An example of a parse tree using linked lists

これは、(if (> x y) (call_some_function a b c))として書き出すことができます。構文解析ツリーを処理する時には、最初に演算子/ファンクションをリストすることに注意してください。これは、引き数の処理方法を知る前に、どんな演算子またはファンクションを扱うのかを知る必要があるためです。

非常に面白いのは、異なった言語であっても構文解析ツリーの大部分は非常に似ている、ということです。ほとんどの言語では、ifステートメントやファンクション・コールを、基本的に同じ方法で構文解析します。ただし、構文解析ツリーに対して直接操作する言語があったとしたら、面白いことになるでしょう。実際、そうした言語があるのです。これを次のセクションで取り上げます。


リスト操作のために設計された言語

これまでは、リストとリスト操作に関して、幾つか興味深い特徴を説明しました。

  • リストに対してリスト・ノード・データ構造を使う
  • typetagを使い、リスト・ノードや変数が任意型のデータを保存できるようにする
  • リストの共有と、サブリストの使い方
  • ガーベジ・コレクションを使うことで、リストに対するメモリー管理を容易にする
  • 括弧標記でリストを表現する

これらはどれも便利なものですが、実際にC言語の中で行うのは、少しばかり面倒です。typetagを割り当てたり、共用体の適当なメンバーにデータを割り当てたり、リスト・ノードを手動で処理したりするのは手間がかかります。ガーベジ・コレクターを使うのは、どのようなガーベジ・コレクターを使うのかにより、容易であったり困難であったりします。括弧標記は素晴らしいものですが、C言語では使うことができません。

もしプログラミング言語がこうした手法すべてを取り込み、その言語に統合されたものの一部として機能を提供してくれれば、非常に便利です。

そうした言語は存在しており、それがLispです。Lispは巨大な言語であり、扱いにくいものですが、Schemeと呼ばれる、強力かつ単純な派生言語があるのです。標準Scheme文書は、索引を含めても50ページほどしかありません。

Schemeの構文の紹介

Schemeはほとんど完全にリストに基づいており、データには、アトムとリストという2種類があります。(ベクターもあるのですが、ここでは取り上げません。)アトムというのは、数字や文字列、文字など、基本的なデータ片です。リストというのは、アトムやリスト、あるいはその両方のリンク・リストです。Schemeで書かれたプログラムも単なるリストにすぎず、またこれは、先ほど取り上げたような構文解析ツリーでもあります。実際、先ほど見た構文解析ツリーの例は、ほとんど有効なSchemeプログラムと言えるものです。

例えば、(if (> 7 5) (display "Hello There!\n"))は、具体的な、実行可能Schemeプログラムです。このプログラムは7と5を比較しますが、7は5よりも大きいので、画面には「Hello There!」が表示されます。

Schemeプログラムを実行するには、Schemeインタープリターが必要です。Linuxを実行している場合であれば、恐らくGUILEというSchemeインタープリターがインストールされているはずです。GUILEを使ってSchemeプログラムを実行するには、単純にguile -s filename.scmをタイプします。

Schemeでの変数定義と変数の使い方

先に触れた通り、Schemeプログラムは単なるリストの集合です。各リストは構文解析ツリーであり、Schemeの評価器(evaluator)を通して実行され、結果を生成します。評価器が処理する基本的なケースには次の4つがあります。

  • そのデータは変数名か? 変数名であれば、変数を取得し、値を返します。ファンクション名であれば、そのファンクションを返します。
  • そのデータはリストか? リストでない場合には、データは単なる定数値であり、その値を返します。
  • リストの最初の要素がSpecial Formの(ファンクションではない演算子)名前か? そうであれば、そのSpecial Formに対する、評価器の内部プロシージャーを実行し、結果を返します。
  • それ以外の場合は、リストの各要素に対して評価器を実行します。最初の要素はファンクションに対して評価する必要があり、そのファンクションは、その他のリスト要素を引き数として呼ばれます。ファンクションの結果が、結果として返されます。

まず、変数名の定義に使われるSpecial Form(正にその通り、defineと呼ばれます)を見てみましょう。defineステートメントは、(define variablename value) のようになります。その後から変数に加えられる変更は、set!Special Formを使って行われます。set!Special Formはdefineと同じように動作しますが、変数が既に定義された後に使われます。

こうしたSpecial Formを試すために、次のプログラムを実行してみます。

リスト6. Schemeでの変数名定義
(define x 200) ;Sets x to be 200
(define y x) ;Sets y to be x, which is evaluated to 200
(define a 50) ;Sets a to be 50
(define b a) ;Sets b to be a, which is evaluted to 50
(set! b 300) ;Sets b to be 300.  Note that this does not affect the value of a
(display "x is ") ;display displays its argument, a string in this case
(display x) ;here, x is evaluated, and its result is displayed
(newline) ;newline just prints a newline
(display "y is ") ;now we are doing the same for the other variables
(display y)
(newline)
(display "a is ")
(display a)
(newline)
(display "b is ")
(display b)
(newline)

名前からも明らかなように、displayはその引き数を出力する機能であり、newlineは単純に改行コードを出力する機能です。

値として使いたい表現であれば、どんな表現でも使うことができます。例えば、加算機能(Schemeでは+ と呼ばれます)を使って値を計算することができます。表現の一部として、if Special Formを含めることさえ可能です。

こうした概念を使った、もう一つのコード例が下記です。

リスト7. より複雑なScheme表現を使ったプログラムの例
(define a 20)
(define b (+ 20 a)) ;b is given the result of (+ 20 a).  Remember that the function name
                    ; is always listed first in the list
(define c (if (> b a) b a)) ;read this as "if b is greater than a then b else a"
(define d (if (eq? c b) "B and C are equal" "B and C are not equal"))
(set! a (+ a a a)) ;a is tripled, and then a is set to the resulting value
(display "a is ") ;now we're just printing out all our variables
(display a)
(newline)
(display "b is ")
(display b)
(newline)
(display "c is ")
(display c)
(newline)
(display "d is ")
(display d)
(newline)

どんな変数に対しても、どんな型のデータでも割り当てられることに注意してください。先のプログラムでは、整数と文字列データの両方を使っており、どのデータ型が使われているかをScheme言語に対して伝える必要はありませんでした。Schemeは、内部的にtypetagを使うことによってデータ型の違いを区別しています。

Schemeでリストを作る

当然のことながら、そもそもSchemeを使う理由は、リスト操作を行うためです。Schemeでは、リスト・ノードはペア(pairs)と呼ばれます。ペアの下半分はリスト・ノードへのポインターである必要はないので、ペアは上記にCで示したノード構造とは少し異なります。ただし、ここの説明では、リスト・ノードを扱うのと全く同じようにペアを扱います。

Schemeはリストを、ヌル・リスト、あるいは下半分がリストであるペアとして定義します。これは、リストの中で使われているペアの下半分が常にリストを指すことを意味しています。リストの最後に達したことは、()として書かれるヌル・リストに突き当たることで分かります。

Schemeでリスト・ノードを作るには、consファンクションを使います。cons(constructを表します)は、ノード・データと、ペアの下半分が指すリスト、という2つの引き数を取ります。いまリストを始めるところであれば、ヌル・リストを使います。例えば下記です。

リスト8. consとヌル・リストを使うプログラムの例
(define myfirstschemelist (cons 23 '()))

consはちょうど、Schemeペアでの特別なmallocのようなものです。また、Schemeではガーベジ・コレクションが行われるので、ペアの解放に煩わされる必要がありません。単にペアの使用を止めさえすれば、Schemeランタイムがペアのクリーン・アップをしてくれます。

ヌル・リストの前にある単一引用符は、()をデータとして使っていること、構文解析ツリーの一部として使っているのではないことをSchemeに伝えるために使われています。

次は、3、4、5という数字から成るリストの作り方を示す、Schemeでのプログラムです。

リスト9. リストの作り方を示すプログラムの例
(define mylist '()) ;The null list is a list
(set! mylist (cons 5 mylist)) ;This constructs a new node with 5 as the data, and set!
                              ; makes mylist now point to the new node
(set! mylist (cons 3 (cons 4 mylist))) ;This constructs two nodes in one statement. The
                                       ; result of the second cons is used as the second
                                       ; argument of the first cons.
(display mylist) ; let's see what we've created!
(newline)

次のプログラム・リストでは、これを使って共有サブリスト作る方法を示しています。

リスト10. サブリストを示すプログラムの例
(define a '(1 2 3)) ;remember, ' means to treat the list as data, so now the variable a
                    ; contains (1 2 3)
(define b (cons "Hello" a)) ;remember, each list element can be of any type.
(define c (cons 55 a)) ;Lists b and c are now both sharing list a as a sublist
(define d (cons 23 (cons "My name is Fred" (cons 22.5 b)))) ;This shares list b, which
                                                            ; shares list a
;Let's print them out
(display "a is ")
(display a)
(newline)
(display "b is ")
(display b)
(newline)
(display "c is ")
(display c)
(newline)
(display "d is ")
(display d)
(newline)

混乱を避けるために、各リスト・ノードを書き出すのは無駄なことではありません。consがリスト・ノードを作ることを忘れないでください。

便利なリストにするためには、データを取得できる必要があります。リストの最初の要素からデータを取得するためのファンクションはcarと呼ばれます(この名前は、昔のアセンブリー言語命令からの遺物です)。リストの、次のノードを取得するには、cdrというファンクションを使う必要があります。これは単に値のみではなく、全ノードを取得することに注意してください(値のみを取得するには、結果に対してcarを行う必要があります)。

前のプログラムに次のコードを追加すると、carcdrの使い方が分かりると思います。

リスト11. carとcdrの使い方を示すプログラムの例
(define e (car d)) ;e now has the data of the first node of d
(define f (cdr d)) ;f now has the list starting AFTER the first node of d
(define g (car (cdr d))) ;g now has the data of the second node of d
(define h (car (cdr (cdr (cdr (cdr d)))))) ;h now has hte data of the 5th node of d
(define i (cdr (cdr (cdr (cdr d))))) ;i now has the 4th sublist of d
(display "e is ")
(display e)
(newline)
(display "f is ")
(display f)
(newline)
(display "g is ")
(display g)
(newline)
(display "h is ")
(display h)
(newline)
(display "i is ")
(display i)
(newline)]

Schemeで、リストに対して繰り返しを行う

Schemeには、他の言語にもある通常の制御構造の他に、特にリストを扱うための特別な制御構造があります。その中で最も重要なものがmapであり、リストのすべての要素に対してファンクションを割り当てます。これは、(map function list-to-process)のように呼ばれます。従ってmapを使うためには、ファンクションの定義方法を知っている必要があります。

Schemeでは、名前のないプロシージャーを作って返すlambda Special Formを使って、ファンクションを定義します。返されるプロシージャーには、defineを使って名前をつけるか、あるいは単純にそのまま使います。lambdaの最初の引き数は、そのファンクションが取ることのできる引き数のリストです。lambdaに対する他の引き数は、ファンクションが呼ばれた時に評価される表現です。

次は、リストの各要素に対して数字2を追加し、その結果のリストを返す簡単なファンクションです。

リスト12. リストに対する繰り返しを示すための、Schemeプログラムの例
(define my-list '(1 2 3)) ;our original list
(define new-list
  (map
    (lambda (x)   ;(x) is the argument list -- this takes one argument, called x
      (+ x 2)     ;add 2 to x and return the value
    )
    my-list       ;this is the list to run it on.
  )
)
(display "the original list is ")
(display my-list)
(newline)
(display "the resulting list is ")
(display new-list)
(newline)

ご覧の通り、これによって全く新しいリストができます。このリストは、オリジナル・リストの全要素に対してそれぞれファンクションを割り当てた結果できたものです。しかも、オリジナルのリストは変わらないままです。

先に説明した通り、繰り返し使えるような名前をファンクションにつけることもできます。例えば次のようなものです。

リスト13. Schemeでのファンクションの作り方と名前の付け方を示すプログラム例
(define addtwo (lambda (x) (+ x 2)))
(display (addtwo 5))
(newline)
(display (map addtwo '(3 4 5)))
(newline)

大部分のプログラミング言語では、ファンクションを定義することと名前をつけることは同じ操作です。Schemeではこれを、ファンクションを定義するlambdaと、名前を与えるdefineという2つの別プロシージャーに分割しているのです。

一般的に言ってSchemeは、プログラムの最も基本的な構成ブロックを提供しており、特有な、そして変わった使い方ができるようになっています。例えばファンクションを作ることと名前をつけることを分離していることによって、通常の名前付きファンクションを普通にコーディングできる一方で、コード内のどこででも匿名ファンクションを作ることができます。


最後に

単一リンクのリストは強力な抽象化であり、非常に多くのデータ型を表現できます。リストを拡張して、任意のデータ型を扱ったり、ガーベジ・コレクションを使用可能にしたり、リスト指向構文を使って操作したりすることで、データ処理に新しい道が開けることになります。

表現力豊かで強力なScheme言語は、リスト操作にとって素晴らしいものであり、理解や把握も容易にできます。この記事は、Schemeのようなリスト指向言語によってリスト操作がいかに容易になるかを示すための、単なる入門にすぎません。Scheme言語を使えば、Cの構造やCメモリーを扱う困難、あるいはtypetagを直接扱う困難に苦しまずに、C実装の強力さを達成することができるのです。

参考文献

  • スタンフォード大学のコンンピューター・サイエンス学部が、26ページに渡る、C/C++でのリンク・リストの紹介を提供しています。
  • The National Institute of Standards and Technology(米国標準技術局)による、Dictionary of Algorithms and Data Structuresには、リンク・リストの項目があります。
  • Donald KnuthがFundamental Algorithmsの中で、リンク・リストとその操作について、詳細に説明しています。
  • Gtk+には、この記事で取り上げたtypetag機構と非常に似た、GtkArgsと言われるシステムがあります(2.x APIでは、GValuesとして知られています)。GType APIの情報も非常に有用です。
  • 整数を扱う場合には、MzSchemeによるtypetag実装が、より高速でコンパクトです。
  • How to Design ProgramsはSchemeプログラミング入門に最適な本です。Schemeプログラマーとしてどう考えるべきかを、しっかりと教えてくれます。
  • Teach Yourself Scheme in Fixnum DaysはSchemeに関する素晴らしいオンライン・チュートリアルであり、入門的な概念についても高度な概念についても説明しています。
  • The Scheme R5RS standardは、多くのScheme実装がどのように動作するかについて説明しています。
  • Essentials of Programming Languagesは、Scheme言語の使い方の概念を拡張し、他のプログラミング言語に対する(構文解析ツリーの例にあるような)実行可能メタ言語として使用する方法を解説しています。
  • メモリー管理の内側(developerWorks, 2004年11月)は、Linuxプログラマーに使用可能なメモリー管理手法を概説しています。
  • GNU Cライブラリーのオーバーライド(developerWorks, 2000年4月)は、GLibユーティリティー・ライブラリーについて説明しています。このライブラリーを使うと、Cでのプログラミングが劇的に容易になります。
  • Data Structures: Make the right choice(developerWorks, 2004年9月)は、データ構造の選び方がアプリケーションの操作やパフォーマンスにどう影響するかを説明しています。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=228958
ArticleTitle=効果的なリスト処理でプログラミングを改善する
publish-date=01052005