プログラム合成

プログラム合成（Program Synthesis)とは、高レベルの仕様から実行可能なコンピュータプログラムを自動的に生成する技術。コンパイルと比較したとき、プログラム合成の入力となる仕様はアルゴリズム的でない。自動プログラミングとも呼ばれるが、一般に自動プログラミングと言った場合、より実用指向のプログラミングパラダイムを意味する。

概要

プログラム合成の考え方は1960年代に生み出されたもので、人工知能(AI)を応用して「自動プログラマ」を構築するため、数学とプログラミング理論の間の関係を深く研究するところから始まった。AIに対する関心の低下とともに数学的アプローチは間もなく失敗した。一部の研究者は現在も形式的アプローチを研究しているが、それよりも適用領域を限定した純粋な演繹的手法と強力なヒューリスティックスを組み合わせたアプローチが成功を収めた。

プログラム合成の手法としては、次のようなものがある。

形式手法: 合成したいプログラムの性質を論理式で表し、それを自動的に証明する過程でプログラムが合成される。
入出力の例示: プログラムへの入力と出力の例をいくつか示すことで、そのような入出力を生み出すプログラムを合成する。
自然言語理解: 自然言語で書かれたプログラムの仕様を理解し、プログラムを合成する。

プログラム合成の課題

自動生成されたプログラムはしばしば要素の整理が不充分だと考えられている。冗長である事が分かっている部分はそのまま使うのではなく、要素を整理することが望ましい。ただしプログラム言語の制限によってはパターンの繰り返しを使わざるを得ない場合もある。要素の整理の例を以下に挙げる:

 要素の不充分な整理:
   
   x = a + a + a + a + a
    
 要素の良い整理:
   
   x = a * 5    （ここでアスタリスクは乗算を表す）

プログラム合成では上の例のような繰り返しを自動的に行う傾向がある。しかし、よりよいアプローチは、その下の例のように乗算を使って高レベルの抽象化を行うことであると思われる。他の例として、パラメータをアプリケーションのコードではなくファイルやデータベースに入れるといったことも挙げられる。

外部リンク

ソフトウェア工学から見たプログラム合成変換技術玉井哲雄（東京大学）