7
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

数学Advent Calendar 2015

Day 21

数学的な問題をそのまま解く〜制約・論理プログラミングの考え方

Posted at

多くの場合、プログラムは「手続き型」や「関数型」といったパラダイムのもとに書かれるものですが、そうでないパラダイムとして制約型や論理型というのがあります。

手続き型のパラダイム

コンピューター自体がメモリに並んだ命令列を読み取って実行していく、という構造をとっていることもあって、アセンブラから高級言語に至るまで、多くの言語で「実行する内容を並べる」手続き型、という仕組みになっています。実行するものを順序通り並べていく、ということで、単純なことをする上では見通しもいいのですが、そもそも「順番通り」に実行しない非同期処理になると、とたんに見通しが悪くなってしまいます。

また、マシンの構造に関連していることもあって、最適化などもやりやすいのは間違いないですが、逆に万人がこれで書く必要もないというのも間違いないところです。

メジャーな非手続き型言語…SQL

では、手続き型というパラダイムを超えた言語にはどのようなものがあるでしょうか。「関数型」という声も聞こえては来ますが、それは置いておいて、ここではSQLを考えてみます。

RDBMSを扱うにはほぼ必須に近い言語のSQLですが、これは手続き型ではありません。

SELECT col1, col2 FROM some_table WHERE other_col >= 5 ORDER BY col1;

上のようにSQL文を書いてみると、どのデータをどんな順番で持ってくるかは書いていますが、そのデータを「どんなふうに」取ってくるかは何も書かれていません。SQLの立脚するモデルは現実のコンピューターではなく、「関係論理」や「関係代数」と呼ばれる数学的なものなのです(厳密にはSQLがこれら2つに則っているかの議論もありますが、それは置いておきます)。このように、手続き型以外のプログラミング言語も存在しますが、総称して「宣言型言語」と呼ばれることもあります。

宣言型言語のメリットとしては、物理的な詳細に立ち入らず、論理的にすっきりした世界で物事を考えられるということがあります。逆に、詳細な最適化を行うのは難しくなります(SQLでは、「どのインデックスを使う」といったヒントを与えることができたりしますが、それでも挙動を直接コントロールすることはできないのでチューニングしづらいです)。

制約プログラミング・論理プログラミング

宣言型に分類されているパラダイムとして、大きく分けると「関数型」「制約型」「論理型」があります。関数型はそこそこメジャーなのでパスして、制約型・論理型について考えていきます。

制約プログラミングは、上で書いたSQLのように、解に必要な「条件」を記述したうえで、それを適切なエンジンに解かせて解を求める、というものです。数学でお馴染みの「線形計画法」がありますが、これも制約プログラミングの一種です。そして、線形計画法に変数が整数という制限をかけた整数計画法というものもあります。

また、それ以外にも、不等式や論理式を組み合わせた条件の列から、それを満たす解を見つける「制約充足問題」(CSP)というのがあります。

論理プログラミングは、論理式を組み合わせて結論を導いていくというようなスタイルです。いちばんわかりやすいものでは充足可能性問題(SAT)があり、近年高速化したSATソルバーを活用して、CSPなど他の問題をSATへ還元して解く、ということもよく行われています。

これらの制約・論理プログラミングは、それ自体をプログラミング言語として使うことは多くないかもしれませんが、ライブラリとして手続き型言語から呼び出す形で使うこともできます。たとえば、JavaScriptからSATソルバーを使うこともできますし、Chefには依存関係を解決する処理のために、CSPのソルバーであるGecodeを使うようになっています。

7
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?