抽象領域の例
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/23 10:02 UTC 版)
プログラムのある時点で、変数 x に代入されている値の区間が [lx,hx] であるとする。値 v(x) を x に代入していることがその具体化であるとき、v(x) は [lx,hx] の区間にある。変数 x と y の区間が [lx,hx] と [ly,hy] であるとき、x+y ([lx+ly,hx+hy]) や x-y ([lx-hy,hx-ly]) の区間も容易に得られる。これは「厳密な; exact」抽象化であり、例えば x+y の取りうる値の集合はその区間([lx+ly,hx+hy])と正確に対応している。同様のより複雑な定式化が、乗算や除算などについても導出できる。これを interval arithmetics(区間演算)と呼ぶ。 ここで次のような単純なプログラムを見てみよう。 y = x;z = x - y; 一般的な算術型であれば、z の値はゼロになるはずである。しかし、ここで区間演算を行うために x の区間を [0,1] とすると、z の区間は [-1,1] となる。個々の演算は厳密に抽象化されているのに、それを合成した結果は厳密ではない。 問題は明らかである。ここでは x と y の値が等価であるという関係を無視していた。実際、区間の領域では変数間の関係は考慮されない。これを non-relational domain と呼ぶ。non-relational domain は高速で実装が容易であるが、正確とは言えない。 変数間の関係を扱う抽象領域の例として次のものがある。 凸多面体 - 計算コストが高い。 "octagons"(八角形) difference-bound matrices linear equalities そして、これらを組み合わせたものもある。 抽象領域を選んだとき、細かな関係性を保持しようとすれば、計算コストも高くつくのが一般的である。
※この「抽象領域の例」の解説は、「抽象解釈」の解説の一部です。
「抽象領域の例」を含む「抽象解釈」の記事については、「抽象解釈」の概要を参照ください。
- 抽象領域の例のページへのリンク