Referentially Transparent Scheme

What features from R5RS would have to be removed if one wanted a referentially transparent scheme?

In Lisp In Small Pieces, Christian states that assignment, side-effects, and continuations break referential transparency. So I would assume that one would have to remove any destructive operators such as set!, set-car!, set-cdr!, as well as removing call/cc.

I also thought that defining global variables (via define) would be removed though I would imagine if you dropped the availability of set! the use of define in the global context would not be much of an issue.

Am I looking at this the right way? Are there other things that have side-effects in Scheme that I am not aware of? Is there more information on this topic that I can look and learn more?

Best regards,

MJ Stahl

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

IO ...

Input and Output are sideeffects!

The wikipedia description is

The wikipedia description is pretty succinct: "In computer programming, a referentially transparent function is one that, given the same parameter(s), always returns the same result."

From your comments, I would say that two ideas are conflicting; that of referential transparency and that of side effects. In a strict sense, in spite of the use of a function like set! or set-car! that would alter the state of one or another variable, a function in scheme could still be referentially transparent -- that is, return a predictable result. For example:

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

F is referentially transparent, but it also causes a side effect.

Personally, I think that side effects and referential transparency have different concerns. In a language where side effects are forbidden, the question the compiler/interpreter must ask is: will this function do something other than return its result? Where referential transparency is required, the question is: will this function return a predictable result?

When I think about RT, I think about the "rand" function. That would seem to be the prime example of a function that breaks RT, because it never returns the same result.

Depends what you mean by "return"

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*).

Better definition (ignore Wikipedia)

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.")

Tricky

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

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".

Thanks!

Looks interesting and informative.

eq? is enough to break referential transparency


Welcome to MzScheme version 300.3, Copyright (c) 2004-2006 PLT Scheme Inc.
> (define (f x) (lambda () x))
> (eq? (f 1) (f 1))
#f

nope

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

Err

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

I see.

Except...

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?

Sure

"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" implemented?

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

Has anyone actually implemented EGAL?

you might want to look at cha

you might want to look at chaitin's subset of lisp. i don't know if it's referentially transparent, but i don't recall it having pointer equality, input, or continuations. on the other hand i only skimmed it briefly.