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

国持 良行  鈴木 敏之  関本 彰次  

誌名
電子情報通信学会論文誌 D   Vol.J78-D1   No.10   pp.839-849
発行日: 1995/10/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: ソフトウェア基礎
キーワード: 
関数型言語,  高階関数,  ストリクト性,  並列リダクション,  遅延評価,  

本文: PDF(736.5KB)>>
論文を購入




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