SestoftChatonのhaskell-jpルームで2009-07-03と2009-07-04にあった、参照透明性と副作用の定義に関わる話で出てきた論文。積読論文の中にあったので読んでみた。transparency)はQuineによって考えられた概念で、LandinとStracheyによってプログラミング言語の性質として使われるようになった。その定義・使われ方は変化しており、それらは同値ではないという話。それらを、この論文での呼び方で呼ぶと以下のような感じ。(definiteness)変数がそのスコープの中で単一の値を持つこと。xを変数とすると、x-xは常に0になる。side-effects)副作用がないこと。この論文では取り上げていない。(determinacy)関数の値が引数の値だけから決まること。この論文では取り上げていない。この論文では取り上げていない。言ったほうが馴染み深い人も多いかも。この論文では取り上げていない。すべての位置が参照透明なとき、その言語は参照透明という。外延性とライプニッツ則の適用可能性に相当。これらを非決定的な作用的評価順序の言語からはじめて、セマンティクスを変えながら比較している。最初の言語Q0は、非決定的かつ作用的評価順序で、かつ部分式の値ではなく部分式の形によって値が決まる演算子を持つ。参照透明性のすべてを満たさない。unfoldabilityは満たさない。Q1の評価順序を正規順序風にしたQ2は、unfoldabilityは満たすが、definitenessは相変わらず満たさない。Q2をdefinitenessを満たすように変更したQ3は、definitenessは満たすが、unfoldabilityは満たさない。非決定性を諦めたQ4はすべてを満たす。非決定的な言語ではunfoldabilityとdefinitenessが両立出来ないというのには気付いておらず、なるほどと思った。