Do expressions have much to do with referential transparency?

In other words, can a programming language be referentially transparent even if not everything is an expression?

And can you say that if in a programming language, everything is an expression, then it is referentially transparent?

I think the question is a bit poorly stated because it uses the term "expression" in an unclear way. So for the purposes of this answer let us say that an expression is a term which does not trigger any computational effects (such as divergence, I/O, mutation of state, exceptions, etc.). In Algol-like languages the opposite of expression is a command. I will say term for any piece of syntax.

I shall take referential transparency to mean that we may replace a term with its value without changing the program. More precisely, we obtain an observationally equivalent program when we replace the term with its value. Note however that referential transparency is not sensitive to efficiency, as replacing a term with its value almost always results in a more efficient program.

For example:

-
print "Hello, world!" is not referentially transparent because it returns the unit value (void is a horrible, horrible misnomer because it suggests that no value is returned, when in fact the trivial value is returned; in contrast, raising an exception return no value) -- if we substitute the unit value, the program won't print anything anymore

-
x = x + 3 is not referentially transparent because it changes state (the value of x)

-
3 + 4 is referentially transparent because we may substitute it with 7 safely

-
while true do skip done is an infinite loop, which is not referentially transparent. If we replace it just with skip (the unit value) then the program might do things it otherwise would not, such as launch missiles.

I hope you see now why your question is unclear. If you define "expression" as "free from all effects" then almost by definition it will be referentially transparent. If you define "expression" syntactically as "such and such syntactic forms are expressions", then we would have to check whether the syntax allows us to construct terms which are not referentially transparent.

One more point: it does not make sense to say that a programming language is referentially transparent, but rather that a particular term or a program is referentially transparent. So we should interpret the question from the first sentence as "if a programming language contains terms that trigger computational effects, must it have some non-transparent terms?", and I think then "yes" is the obvious answer because we just consider a command which triggers a computational effect.

You then ask about languages in which "everything is an expression". Well, that would be a pure language whose only possible effect is non-termination (because of infinite recursive calls). Depending on the language evaluation strategy this may or may not cause expressions to be referentially non-transparent. For example, in Haskell sometimes it does not matter that an expression is non-terminating because Haskell won't evaluate it until it is needed, which may be never. But in general non-termination is the thing to worry about in a pure language.

There are languages in which all terms are referentially transparent by design. Such languages cannot be Turing complete, however (assuming they have sane syntax). An example is Agda, which does not allow you to write a non-terminating expression, but it is still very powerful as a programming language, and a proof assistant.

A far more interesting question is whether a term can be referentially transparent even though it triggers computational effects. The answer is positive, and useful. Many data structures are self-modifying but they look referentially transparent from the outside, let me just mention splay trees as a famous example. Another example are caching strategies where lookups are cached (state change) so that they may be answered faster in the future. It is an interesting challenge for programming languages to properly account for such phenomena so that compilers can see what is going on and take advantage of the situation. For example, in a splay tree we may reorder lookups and updates, or if we work with two splay trees it does not matter which tree we work with first (so long as the data is not migrating between them). Note however.

I hope that answers your questions a bit by putting them into wider context.

StackExchange Computer Science Q#13414, answer score: 2