等価変換型プログラムをかじる

2008年11月26日(水)
若槻 俊宏

基礎理論からわかること

 いつの間にかねじれてしまった宣言型プログラミングの本質をあらためて考えてみると、本当にやりたかったことは、問題の定義とその解法を分離して、それぞれを独立して理論化していくことだったと考えられます。

 宣言型プログラミングは、仕様と実装を同一視するため、問題の定義に解法が深く侵入してしまい、分離不可能なものとなっています。そのため、問題ドメインごとに、効率化のためのさまざまなデータ構造と、それを扱うための手続き(制約ソルバー)が拡張された、多くの言語が次々と開発されるようになりました。結果として、命令型プログラミングと同様に、まとまりに欠ける混迷状態となってしまっています。

 プログラミングという概念が、より広く、より複雑なものになってきているのですから、どこが一番上のレイヤーで、どこが一番下なのかということは一意に決まりませんし、決めるべきではありません。また、問題ドメインが多様化してきているのですから、プログラミングの基礎となる理論は、特定の問題ドメインに依存しない一般的なものであることが望ましいと言えます(図1)。

等価変換型プログラミング

 さて、そのような理論的枠組みを構築するためには、プログラミングをどのように位置付けて考えれば良いのでしょうか?

 ここで1つの可能性として、等価変換(Equivalent Transformation;ET)に基づく問題解決の枠組みを紹介します。もちろん、これが絶対的な答えというつもりはありませんし、より良い枠組みがありましたら、ぜひ筆者に教えていただきたいところです。

 ETパラダイムはまだ歴史が浅く、入門書や教科書などは整備されていません。論文はたくさん出ていますが、研究者以外の方々にそれを読めというのは乱暴ですし、ハードルが高いのではないかと思います。正直なところ、今回の連載のような一般のメディアに紹介するのはまだ時期尚早なのではないかとも悩みました。しかし、この理論からは多くの示唆が得られると考え、何らかの参考になることを願い紹介させていただきます。

 とはいえ筆者自身は一介の学生にすぎないので、フォローできている理論の範囲はとても限定されたものです。また、間違いや誤解、理解不足な点も多く存在すると思います。以下は完ぺきな解説ではなく、あくまでも現時点での私なりの理解だということをあらかじめお断りさせていただきます。

 ETパラダイムは、もともとは90年代初頭に北海道大学で行われていた、コンピュータに自然言語を処理させるための基礎研究に端を発しています。本質的にあいまいである自然言語をコンピュータに理解させるためには、具体例からのルール抽出、ルールの最適化やそこからのプログラム生成、制約充足問題の並列処理などが複雑に絡み合った、極めて広範囲にまたがる高度なプログラム構築技術が必要とされたからです。

 人間が話す自然言語は、形式的に文法が定義された人工言語(プログラミング言語が代表例です)とは異なり、解釈が一意には定まらないあいまいなものです。そのため、(コンパイラの用語で言うところの)字句解析、構文解析、意味解析などの各工程をきれいに分割することが難しく、すべてを並列に行い、ありえない可能性をそのつど枝刈りしながら進めなくては、あっという間に可能性が爆発的に増えてしまいます。

 人間の知能という極めて高度なシステムを研究するAI(人工知能)分野では、常により強力なプログラミング技術が求められ、その発展を後押ししてきました。例えば「第3回:宣言型プログラミングの可能性と限界(http://www.thinkit.co.jp/article/157/3/)」に紹介したPrologも、もともとは自然言語処理研究から生まれた言語です。また、なじみ深い方が多いと思われるオブジェクト指向プログラミングも、もともとはAIの階層型の知識表現(フレーム理論)研究の影響があります。

北海道大学大学院
北海道大学大学院 情報科学研究科 博士後期課程(D1)。当初はAI研究に興味を持っていたのだが、現在のプログラミング技術の水準では不十分だと考え、いつの間にかプログラミングの基礎理論を研究する道に。大学院時代は、等価変換に基づく問題解決、特にルール型プログラムから命令型プログラムを合成するための理論について研究。2008年11月21日付けで、京都マイクロコンピュータ株式会社に入社予定。今後はデバッガ技術に基づきソフトウエアとハードウエアの本質を突き詰めて行くつもりである。http://alohakun.blog7.fc2.com/

Think ITメルマガ会員登録受付中

Think ITでは、技術情報が詰まったメールマガジン「Think IT Weekly」の配信サービスを提供しています。メルマガ会員登録を済ませれば、メルマガだけでなく、さまざまな限定特典を入手できるようになります。

Think ITメルマガ会員のサービス内容を見る

他にもこの記事が読まれています