As I roughly understand the substitution model (with referential transparency(RT)), you can de-compose a function into its simplest parts. If the expression is RT, then you can de-compose the expression and always get the same result.
Yes, the intuition is quite right. Here are a few pointers to get more precise:
Like you said, any RT expression should have a single
"result". That is, given a factorial(5)
expression in the program, it should always yield the same "result". So, if a certain factorial(5)
is in the program and it yields 120, it should always yields 120 regardless of which "step order" it is expanded/computed -- regardless of time.
Example: the factorial
function.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
There are a few considerations with this explanation.
First of all, keep in mind the different evaluation models (see applicative vs. normal order) may yield different "results" for the same RT expression.
def first(y, z):
return y
def second(x):
return second(x)
first(2, second(3)) # result depends on eval. model
In the code above, first
and second
are referentially transparent, and yet, the expression at the end yields different "results" if evaluated under normal order and applicative order (under the latter, the expression does not halt).
....which leads to the use of "result" in quotes. Since it is not required of an expression to halt, it may not produce a value. So using "result" is kind of blurry. One can say an RT expression always yields the same computations
under an evaluation model.
Third, it may be required to see two foo(50)
appearing in the program in different locations as different expressions -- each one yielding their own results that might differ from each other. For instance, if the language allows dynamic scope, both expressions, though lexically identical, are different. In perl:
sub foo {
my $x = shift;
return $x + $y; # y is dynamic scope var
}
sub a {
local $y = 10;
return &foo(50); # expanded to 60
}
sub b {
local $y = 20;
return &foo(50); # expanded to 70
}
Dynamic scope misleads because it make it easy for one to think x
is the only input for foo
, when in reality, it is x
and y
. One way to see the difference is to transform the program into an equivalent one without dynamic scope -- that is, passing explicitly the parameters, so instead of defining foo(x)
, we define foo(x, y)
and pass y
explicitly in the callers.
The point is, we are always under a function
mindset: given a certain input for an expression, we are given a corresponding "result". If we give the same input, we should always expect the same "result".
Now, what about the following code?
def foo():
global y
y = y + 1
return y
y = 10
foo() # yields 11
foo() # yields 12
The foo
procedure breaks RT because there are redefinitions. That is, we defined y
in one point, and latter on, redefined that same y
. In the perl example above, the y
s are different bindings though they share the same letter name "y". Here the y
s are actually the same. That's why we say (re)assignment is a meta operation: you are in fact changing the definition of your program.
Roughly, people usually depict the difference as follows: in a side-effect free setting, you have a mapping from input -> output
. In an "imperative" setting, you have input -> ouput
in the context of a state
that can change through time.
Now, instead of just substituting expressions for their corresponding values, one also has to apply transformations to the state
at each operation that requires it (and of course, expressions may consult that same state
to perform computations).
So, if in a side-effect free program all we need to know to compute an expression is its individual input, in an imperative program, we need to know the inputs and the entire state, for each computational step. Reasoning is the first to suffer a big blow (now, to debug a problematic procedure, you need the input and the core dump). Certain tricks are rendered impractical, like memoization. But also, concurrency and parallelism becomes much more challenging.