Lambda the Ultimate

If you changed the set! to increment the *global variable* then I would not consider it to be referentially transparent. Even though the immediate returned value is transparent, the function is returning a global value - it just doesn't get returned via the function call stack.

Simply setting the global value to a constant (or even to a value of an input parameter) is predictable in that the function will always produce the same results for any given input. I would conclude that every function implicitly gets passed and returned an environment. Though setting things in the environment is not explicit as a return value, I'd still think it'd have to be considered in the question of whether a function is RI.

To hold otherwise would be to say that all procedures are referentially transparent because they always return the same value (void*).

If two equal expressions can be substituted for each other without changing the meaning of the program, then the expressions are referentially transparent.

If a function has side effects, like your 'f', then this substitution cannot be performed, because e.g. substituting (f x) with (+ x 1) results in a change in the meaning of the program, since the side effect will no longer occur.

Regarding "rand", it relies on side effects, if you implement it entirely within a language; or else it relies on some external source of side effects.

This definition explains why the connection between side effects and referential transparency is so close: for example, side effects generated by I/O procedures similarly break referential transparency, which they would not do by the definition given in the first sentence of the Wikipedia entry.

(Note that on the discussion page of the Wikipedia entry, "Skaller" points out the incorrectness of the Wikipedia definition and gives a better one: "Referential transparency is a property of a syntactic element, typically expressions, namely that elaboration of the expression results in the same value independently of location of the expression and time of evaluation.")

If two equal expressions can be substituted for each other without changing the meaning of the program, then the expressions are referentially transparent.

But that definition is tricky! Consider f and g in this rather contrived example:

(define (f x)
  (set! *global-variable* 1)
  (+ x 1))

(define (g x)
  (let ((y 1))
    (set! *global-variable* y)
    (+ x y)))

Here f and g both return equal values and exchanging the f for g does not change the meaning of the program, but neither you nor I would consider either expression referentially transparent. At first I thought you should have said all equal expressions, instead of two, but that doesn't help, because I can come up with a expression that is not referentially transparent for any referentially transparent expression, and exchanging those would change the meaning of the program. In other words: this definition is simple, but not very precise.

I think Chris’s definition, that the environment is implicitly a parameter to all expressions, is more precise, but there are still questions regarding what that means. Performing operations on the passed environment that changes it (using set! on a variable in the passed environment) makes a expression not referentially transparent. However, a person might get confused and conclude that using set! in a let expression that shadows a variable of the enclosing environment is not referentially transparent, because it appears to change the enclosing environment, when in fact, it doesn’t. The more I think about it, as soon as you allow yourself an expression like set!, you have to understand how environments are passed around, created, and destroyed in scheme, in order to understand when you can use such a expression inside another expression and still have referential transparency. I suppose this is why many consider side effects such a big deal: if we allow them, we have to have much more intimate knowledge of system details to use it without shooting ourselves in the foot.

What is a Purely Functional Language. It provides a mildly complex but fairly comprehensive approach and mentions the issues with various other definitions of "purely functional".

Looks interesting and informative.

(f 1) returns the same result both times, just at two seperate memory addresses, which is what eq? tests.

If they are distinguishable in any way from within the language, they are not "the same", no. Jacob's point is that by exposing EQ?, referential transparency is broken, which is a well-understood and well-known fact in the Lisp/Scheme community, I think.

It has a practical consequence in that a compiler cannot legally transform (foo (cons 1 1) (cons 1 1)) into (let ((x (cons 1 1))) (foo x x)) as an optimization, for instance. This, and similar subexpression eliminations, would be legal in the absense of EQ?.

I see.

It has a practical consequence in that a compiler cannot legally transform (foo (cons 1 1) (cons 1 1)) into (let ((x (cons 1 1))) (foo x x)) as an optimization, for instance. This, and similar subexpression eliminations, would be legal in the absense of EQ?.

Given immutable cons-cells, right?

"Given immutable cons-cells, right?"

Yes, indeed. I'd assumed the original poster was interested in unobvious sources of referential non-transparency, mutable state being among the more obvious. :)

Equal Rights for Functional Objects

I just read through the paper, and it seems quite compelling (at least for strict languages).

Has anyone actually implemented EGAL?