再帰関数系における依存属性集合の計算法

小野 諭  高橋 直久  

誌名
電子情報通信学会論文誌 D   Vol.J69-D   No.5   pp.714-723
発行日: 1986/05/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: ソフトウェア技法
キーワード: 


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




あらまし: 
関数型言語における関数のノンストリクトネスを表現する方法として,筆者らは先に,依存属性集合(DPS)の概念を提案した.本論文では,再帰関数系のDPSを計算するアルゴリズムに関し,プログラムの不動点理論と関連付けて,その性質と限界を証明している.そして,先に提案したアルゴリズムが必ず真のDPSを含むという意味で安全なこと,一般的に真のDPSを計算するアルゴリズムは存在しないことなどを明らかにしている.DPSは必須引数の概念を一般化したものであり,たとえば,ノンストリクト関数の部分計算法である射影関数法において,部分計算の制御に使用されている.本論文の証明法は,関数型言語の特徴を生かし,プログラムの表示的意味論と関連付けて議論を進めているため,プログラムのオペレーショナルな側面から完全に独立した証明になっている.したがって,本論文の証明は,プログラムの不動点計算規則を実現している任意のオペレーショナル・セマンティクスを持つ一階の関数型言語に適用することができる.