the scala purity test

I believe the definition of referential transparency is as follows:

let f : A -> B

forall t[B] st t is referentially transparent, forall a, t[f(a)] = t[b] where b = f(a)

So, forall referentially transparent terms that use f(a), you can replace f(a) with its value without changing the value of the term.

It is important to note that f may not be pure in its implementation.  A good example of this is memoization, which requires impurity at some level (lazy val and modules are both memoized).  The only thing that matters for referential transparency is the value substitutability.

Daniel

On Tue, Oct 4, 2011 at 11:42 AM, Paul Phillips <paulp@improving.org> wrote:

HIJACK:

On Tue, Oct 4, 2011 at 9:28 AM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:
>> a pure function that throws an exception
>
> ... is not a pure function -- at least not for the definition of "pure" that
> I'm? used to from the same book of definitions, throwing an exception is
> considered an effect (the throws clause in Java is actually part of a
> lightweight type and effect system)

Can we go to extempore's big book of questions asked via comments?
This arose in the course of fixing issues in the optimizer where
the -optimise compiled code behaved differently, leading back to
the assessment performed by the following method, which though it is
called "isPureExpr" seems to be testing something different than that
in your "big book of definitions."

TreeInfo.scala:

/** Is tree a stable and pure expression?
 *  !!! Clarification on what is meant by "pure" here would be appreciated.
 *  This implementation allows both modules and lazy vals, which are pure in
 *  the sense that they always return the same result, but which are also
 *  side effecting.  So for now, "pure" != "not side effecting".
 */
 def isPureExpr(tree: Tree): Boolean = ...


So, if purity means what you suggest (which is what my book of definitions
says too) this function is wrongly named.  What is the right name? Is
it "isReferentiallyTransparent" or... ?

On Tue, Oct 4, 2011 at 10:00 AM, Daniel Spiewak wrote:
> I believe the definition of referential transparency is as follows:

OK, that is helpful but let me phrase my question less ambiguously.

object Foo { println("Hi! I'm Foo") }
def f = Foo

def XXX(method f) = false
def YYY(method f) = true

Limiting ourselves to possible answers like "isPure",
"isReferentiallyTransparent", "isIdempotent",
"isSomeOtherTermYouKnowAndIDoNot", answer these questions:

A) The correct name for XXX is...
B) The correct name for YYY is...

TreeInfo.scala:

/** Is tree a stable and pure expression?
 *  !!! Clarification on what is meant by "pure" here would be appreciated.
 *  This implementation allows both modules and lazy vals, which are pure in
 *  the sense that they always return the same result, but which are also
 *  side effecting.  So for now, "pure" != "not side effecting".
 */
 def isPureExpr(tree: Tree): Boolean = ...


So, if purity means what you suggest (which is what my book of definitions
says too) this function is wrongly named.  What is the right name? Is
it "isReferentiallyTransparent" or... ?

I would suggest a variation on "isSafeToInline"
referentially transparent expressions can freely (and repeatedly) be inlined without changing the observable behavior of a program  (observations: which value does it evaluate to? does it terminate/throw an exception? -- but not: how long does it run, how much memory does it consume)
termination effects are a special case, since we can observe changes in how many times a program prints "hello world", but not in how many times it terminates or throws an (uncaught) exception (since that's game over on the first try), so we can sneakily change a program from throwing once to throwing multiple time without being "caught"
so, some impure expressions can be treated in the same way as referentially transparent ones when it comes to inlining

XXX = isPure
YYY = isReferentiallyTransparent
XXX = YYY = isIdempotent  (actually, this one is weird, when you think about it, but true in a really cool way)

There are probably some other important ones that come out here, but I suspect that size: Set[TermIKnowAndYouDoNot] => Int returns a value very close to 0.

Daniel

On Tue, Oct 4, 2011 at 12:06 PM, Paul Phillips <paulp@improving.org> wrote:

On Tue, Oct 4, 2011 at 10:00 AM, Daniel Spiewak <djspiewak@gmail.com> wrote:
> I believe the definition of referential transparency is as follows:

OK, that is helpful but let me phrase my question less ambiguously.

object Foo { println("Hi! I'm Foo") }
def f = Foo

 def XXX(method f) = false
 def YYY(method f) = true

Limiting ourselves to possible answers like "isPure",
"isReferentiallyTransparent", "isIdempotent",
"isSomeOtherTermYouKnowAndIDoNot", answer these questions:

A) The correct name for XXX is...
B) The correct name for YYY is...