オブジェクト指向言語による
構成的アルゴリズムの実現
数理7研
00669
村上 拓真
構成的アルゴリズムとは
関数プログラミング
 アルゴリズム自体の最適化
 少数の基本関数と変換規則

foldl (+) 0 (map square [1, 2, 3, 4])
= foldl (+) 0 [1, 4, 9, 16]
= 0 + 1 + 4 + 9 + 16
= 30
関数型と手続き型

手続き型プログラミング
– 実行するハードウェアを意識した設計
– 変数で「状態」を操作(チューリング・マシン)
– アーキテクチャに沿った最適化

関数型プログラミング
– 数学的記述を可能にする設計
– 関数の定義と組み合わせによる処理(λ計算)
– アルゴリズムそのものを最適化(研究段階)
研究の目的と課題

構成的アルゴリズムを手続き型言語で実現
– アルゴリズム指向のプログラムを広く実行できる
– 動作速度の検証
– 関数型言語と手続き型言語の対応を発見する

解決すべき課題
– データ構造の設計
• データ+アクセス+制御構造
– 「関数に対する計算」の手続き型言語での実現
• 高階関数の扱い
• 関数合成の扱い
方法



構成的アルゴリズムを実現するデータ構造
– データと基本関数をクラス化
– 高階のデータ型の扱い
– 関数との整合性
「関数の計算」の手続き型言語での実現
– 高階関数・関数合成の操作
– 型=定義域、値域の扱い
プログラム変換
– 構成的アルゴリズムに沿ったプログラムの変換
構成的アルゴリズムとは
最初の例のJavaでの記述
public static void main(String[] args){
IntList list = new IntList(1, 2, 3, 4);
list = list.map(square);
int output = list.foldl(plus, 0);
}
 基本関数をメソッドとするデータ構造
 関数自体が1つのオブジェクト


軸普封鴎

PDFファイル - 萩城下町マラソン

構成的アルゴリズムに対する Javaプログラムの生成