高階関数を対象としたlazyな関数型言語についての並列リダクション

概要

論文の詳細を見る
関数型言語は,式の意味が明解であることやプログラムを形式的に検証し得ること等の点から広い分野に利用されている.また,高階関数が取り扱える言語では,簡潔かつ多様な式の記述が可能となる.しかし,高階の関数型言語の処理系については並列化があまり進んでいない.本論文では,強く型付け可能な高階関数(および式)を対象とするlazyな関数型言語を定義し,その言語による式についての並列リダクションアルゴリズムΓを示す.強く型付け可能な関数(および式)を対象とするのは,ある型をもつ式の値が,その型の意味領域の最小元と異なる場合には,常にその式から簡約形と呼ぶ形式の式へリダクションする特定の戦略が存在し,そこでリダクションを停止できることによる.まず,そのようなリダクションとして,逐次型の必須最外リダクションを定義する.続いて,それを並列(グラフ)リダクションに拡張したアルゴリズムΓを示す.また,両戦略の完全性,すなわち上に述べたようにリダクションが停止することも補題として明らかにしている.
社団法人電子情報通信学会の論文
1995-10-25