Referential transparency?
Joachim Durchholz
also a vague idea what it means.
But does anybody have a clear definition of it? Preferrable one that
helps to understand why it's advantageouy, but anything that's more than
handwaving will do for the moment <g>
Regards,
Joachim
--
This is not an official statement from my employer.
Oliver Braun
> "referential transparency" ... a clear definition of it?
The following definitions of referential transparency are quoted from a
USENET News article by Tom DeBoni <deb...@llnl.gov>
"The phrase 'referentially transparent' is used to describe notations
where only the meaning (value) of immediate component expressions
(sentences/phrases) is significant in determining the meaning of a
compound expression (sentence/phrase). Since expressions are equal if
and only if they have the same meaning, referential transparency means
that substitutivity of equality holds (i.e. equal subexpressions can be
interchanged in the context of a larger expression to give equal
results)." Reade, Chris; Elements of Functional Programming, p. 10;
Addison-Wesley, 1989.
"The fundamental property of mathematical functions which enables us to
plug together block boxes [he is referring here to 'built-in functions
or primitives' described in a previous paragraph] in this way is the
property of 'referential transparency.' There are a number of intuitive
reading of the term, but essentially it means that each expression
denotes a single value which cannot be changed by evaluating the
expression or by allowing different parts of a program to share the
expression. Evaluation of the expression simply changes the form of the
expression but never its value. All references to the value are
therefore equivalent to the value itself and the fact that the
expression may be referred to from other parts of the program is of no
concern." Field, Anthony, and Harrison, Peter G.; Functional
Programming, p. 10; Addison-Wesley, 1988.
"The most important feature of mathematical notation is that an
expression is used solely to describe (or denote) a value. In other
words, the meaning of an expression is its value and there are no other
effects, hidden or otherwise, in any procedure for actually obtaining
it. Furthermore, the value of an expression depends only on the values
of its constituent expressions (if any) and these subexpressions may be
replaced freely by others possessing the same value. ... The
characteristic property of mathematical expressions described here is
called "referential transparency." Bird, Richard, and Wadler, Philip;
Introduction to Functional Programming, p. 4; Prentice Hall, 1988.
My informal read on the term in question is that there are no side
effects. A function written in a truly functional language, which
evaluates an expression and returns its value, does nothing else. A
routine written in an imperative language, such as Fortran, Pascal, or
C, which evaluates the same expression, may also change a value in a
memory location having nothing to do with the expression being
evaluated; for instance, it may set a Boolean value indicating that the
expression has indeed been evaluated. While it may appear harmless, this
side effect prevents the substitution of the expression's value for the
invocation of the routine that evaluates it. Thus, the imperative
language routine is (potentially) referentially opaque. In functional
languages, referential opaqueness is forbidden and referential
transparency is mandatory. There's just no other way to do things; if
there is, the language is not functional.
--- end quote ---
HTH, Olli
--
« GCS/IT/M dx s++: a- C+++>$ UBL++ P++@ L++@ E--- W++ N+ o+ !K w- O+ M? »
« V PS PE Y+ PGP+ t 5? X- R-- tv+ b+++ DI- D---- G++ e++++ h--- r+++ y*@ »
Torben Ægidius Mogensen
There once was a girl from Dundee
Who never wrote programs in C
She felt that destruction
Lacked the seduction
Of referential transparency
Torben Mogensen (tor...@diku.dk)
Ulf Wiger
Oliver> My informal read on the term in question is that there are
Oliver> no side effects.
Of course, in the strictest sense, there will be side effects, such
as consumption of CPU cycles and memory. Even referentially transparent
functions will affect timing aspects, which might critically alter the
behaviour of a system with many concurrent tasks.
This may seem like nit-picking, but in large complex systems, this
is highly relevant. For example, one could statically prove that a
certain function is functionally equivalent to a previous version
(perhaps apart from using a much more efficient algorithm). This doesn't
necessarily mean that significant testing will not still be required,
for the reasons mentioned above. At a system level, any useful system will
of course have lots of side effects (if it means to do anything useful.)
It does, however, mean that one doesn't have to experimentally verify
the correctness, or functional equivalence, of the function, which is
a huge advantage in itself.
/Uffe
Matthias Blume
> I've heard the term "referential transparency" many times now. I have
> also a vague idea what it means.
> But does anybody have a clear definition of it? Preferrable one that
> helps to understand why it's advantageouy, but anything that's more
> than handwaving will do for the moment <g>
"Referential transparency" is often described as "being able to
substitute equals for equals". Of course, this is a completely
vacuous statement, since "equal" ought to be defined in terms of
substitutability. In other words, if you can't substitute X for Y in
all contexts, then the meaning of X is quite obviously not equal to
that of Y. By that argument, all programming languages are trivially
referentially transparent.
People who get all excited about referential transparency are really
merely after a simpler notion of "equality" than the one *defined* by
substitutability. Such a simpler, ad-hoc notion of equality (e.g.,
one that is based on syntactic equations written down by the
programmer) -- let's call it E -- can make reasoning about programs
easier: If I know that my language is "referentially transparent with
respect to the equivalence relation E", then if I can somehow prove
that X E Y, I also know that I can freely substitute any X with Y in
any context without having to worry about changing the overall meaning
of my program.
--
-Matthias
Alan Baljeu
"Ulf Wiger" <Ulf....@ericsson-cut-to-reply.com> wrote in message
news:xcz3cyb...@etxb.ericsson.se...
> >>>>> "Oliver" == Oliver Braun <use...@unsane.de> writes:
>
> Oliver> My informal read on the term in question is that there are
> Oliver> no side effects.
>
> Of course, in the strictest sense, there will be side effects, such
> as consumption of CPU cycles and memory. Even referentially transparent
> functions will affect timing aspects, which might critically alter the
> behaviour of a system with many concurrent tasks.
critically depend on the precise timing of an referentially transparent
function. Are there examples of this?)
This brings to mind the following function.
function x(a) // semi-transparent?
{ append a into '~/hello.txt';
return 2 * a;
}
On its own, the function might be considered 'referentially transparent'
since you can call the function from anywhere with the same value and always
get the same result. It's only when you incorporate somewhere something
which reads 'hello.txt' that x becomes not transparent.
function y(a) // not transparent
{
x(a);
return read data from '~/hello.txt';
}
Now, what about this:
function z(c) // externally pretty transparent, internally a real mess.
{
empty file ~/hello.txt
let b = x(c)
a = y(c) // which is quite different from a=y(c); b=x(c). Not
transparent.
return pair(a, b)
}
Functional programming is largely about avoiding this mess, and then about
all the more advanced methods of computing you can use because your
functions are easier to understand.
Stefan Axelsson
> (Aside: I find it difficult to believe people are writing programs which
> critically depend on the precise timing of an referentially transparent
> function. Are there examples of this?)
> Functional programming is largely about avoiding this mess, and then about
> all the more advanced methods of computing you can use because your
> functions are easier to understand.
Well, using one of your own loose definition of referential
transparency, then yes, indeed within Ericsson we do write functions
that "depend critically on the precise timing of ... function(s)".
Being coloured by RUP I now tend to see the world (well parts of my
professional world anyway) in terms functional and non-functional
requirements/properties, where a functional property of a program is
what it 'does' in a sense, i.e. 'this function adds two numbers and
returns the sum', and the non-functional properties describe
everything else, i.e. 'and the inputs are 32bit signed entities and it
takes 2 microseconds to do that for all inputs.' (In the following
'functional' will refer to the former meaning and not 'functional
programming' unless stated otherwise.)
Now, when we typically discuss referential transparency then we
typically only address the functional aspects, as you did in your
examples. And that's all good and well, one of the saving graces of
functional programming is indeed that these are easily dealt with
(though there's another thread about that). Using other programming
languages even the functional requirements aren't trivial, just look
at many of the non-functional (as in functional programming here)
entries for the ICFP, that often doesn't even make it to the final
round because of trivially not meeting their (functional)
specification.
However, and this is the clincher, meeting the functional requirements
doesn't sell any ATM switches or GSN nodes, since their functional
behaviour is mostly dictated by standards. Sure, you can (and we do)
go beyond those and develop your product in the non-standardised areas
of functionality, such as ease of use, OAM, upgrade etc, but that
will only get you so far. Now, of course, the beauty of Erlang in this
case is that since the functional part is easily enough dealt with, we
have more time to spend on the difficult i.e. non-functional bits,
such as, availability, capacity (performance), security and the
like.
And in doing so, in a highly redundant distributed Erlang based
product, you bet your sweet ass, that we replace functionally
referentially transparent functions with others that exhibit other
timing performance, lest they miss a (soft) deadline and trigger
recovery behaviour, with the associated penalties. ;-)
Stefan,
--
Stefan Axelsson (email at http://www.ce.chalmers.se/staff/sax)
Ulf Wiger
Alan> "Ulf Wiger" <Ulf....@ericsson-cut-to-reply.com> wrote in
>> Of course, in the strictest sense, there will be side effects,
>> such as consumption of CPU cycles and memory. Even referentially
>> transparent functions will affect timing aspects, which might
>> critically alter the behaviour of a system with many concurrent
>> tasks.
Alan> (Aside: I find it difficult to believe people are writing
Alan> programs which critically depend on the precise timing of an
Alan> referentially transparent function. Are there examples of
Alan> this?)
Well, Stefan A. has responded already (for the uninitiated, "RUP" stands
for "Rational Unified Process".)
If you replace "are" with "should be", then I agree with you.
I am convinced that relying on timing behaviour in complex software
is a terrible mistake, and I can't come up with a good example of
where it is unavoidable to do so (I'm sure I can come up with good
examples of where it is difficult to completely eliminate timing
dependencies, but I will resist the temptation for now.)
When we verify our systems, it's not enough to simply assume that such
dependencies don't exist. Formally verifying the correctness of concurrent
and distributed programs is certainly an interesting research area, and
I believe that we are making som pretty good progress there
(see for example: http://www.erlang.se/euc/01/thomas2001.ps)
/Uffe
Stefan Axelsson
> Well, Stefan A. has responded already (for the uninitiated, "RUP"
> stands for "Rational Unified Process".)
Well, it's depressing enough having to work with it to have to spell
it out... ;-)
> If you replace "are" with "should be", then I agree with you. I am
> convinced that relying on timing behaviour in complex software is a
> terrible mistake,
Well, to pick nits, that's perhaps overstated. Could we agree on "To
rely on timing behaviour for the *correctness* of complex software is
a terrible mistake" if we by correctness mean meeting the functional
(as in RUP sense) requirements? Obviously if we're in the real time
business, then time will play a role, whether we like it or not.
Of course, speaking of the mathematics of functional programming, and
referential transparency, we limit ourselves to one side of the
matter. And that's incidentally my main gripe with Haskell, that it's
near impossible for the programmer to have an understanding, or at
least an intuitive understanding, of the time/space behaviour of his
programs. That makes it less useful in a (or at least many) realistic
setting(s).
Now, that's not to say that these non-functional properties cannot be
reasoned about mathematically, see for example Lars Pareto's PhD
thesis. I'm sure much more is/has going on in this area. (Though
perhaps not as much as could be going on).
> When we verify our systems, it's not enough to simply assume that
> such dependencies don't exist. Formally verifying the correctness of
> concurrent and distributed programs is certainly an interesting
> research area, and I believe that we are making som pretty good
> progress there (see for example:
> http://www.erlang.se/euc/01/thomas2001.ps)
I hadn't seen that reference before, I'll be sure to look it up.
P.S. Please don't construe my arguments as variations of those that
are so often heard from 'C' programmers and the like, i.e. that
speed is everything. Quite the contrary, correctness is IMHO the
top priority (though not always absolute correctness). But, and
that's my main point, the fun really only begins when functional
correctness have been achieved.
Peter Sestoft
> "Referential transparency" is often described as "being able to
> substitute equals for equals". Of course, this is a completely
> vacuous statement, since "equal" ought to be defined in terms of
> substitutability. In other words, if you can't substitute X for Y in
> all contexts, then the meaning of X is quite obviously not equal to
> that of Y.
What you define here should rather be called `extensionality' of the
context of X and Y.
The philosopher W v O Quine (in the 1950s) gives this example of
referential opacity (that is, lack of referential transparency). It
may be true that
(a) Tegucigalpa = the capital of Honduras
(b) Philip believes that Tegucigalpa is in Nicaragua
yet you cannot conclude
(c) Philip believes that the capital of Honduras is in Nicaragua
The context `believes that' is referentially opaque.
In a trivial way, the string quote context "..." in a programming
language is referentially opaque; although
2+2 = 4
it is not the case that
"2+2" = "4"
Some years ago Harald Sondergaard and I tried to dispel the confusion
in a paper:
@Article{Soendergaard:1990:ReferentialTransparency,
author = "H. S{\o}ndergaard and P. Sestoft",
title = "Referential Transparency, Definiteness and Unfoldability",
journal = "Acta Informatica",
year = "1990",
volume = "27",
pages = "505-517",
note = ""}
The executive summary (very executive indeed) is that the meaning of
`referential transparency' in the programming language community has
very little to do with the meaning originally intended by the
philosopher W v O Quine (1960).
Christopher Strachey adopted the term in his 1967 summer school
lecture notes that were finally published (thanks to Olivier Danvy,
Peter Mosses and others) as
Christopher Strachey: Fundamental Concepts in Programming
Languages, 1967. Reprinted in Higher-order and symbolic
computation 13 (2000) 11-49.
From there it spread in the programming language community, and
somehow began to mean (roughly) `free of side effects'.
What conclusion to draw from this? Perhaps we should just say `free
of side effects' when that is (roughly) what we mean.
Peter Sestoft
--
Department of Mathematics and Physics * http://www.dina.kvl.dk/~sestoft/
Royal Veterinary and Agricultural University * Tel +45 3528 2334
Thorvaldsensvej 40, DK-1871 Frederiksberg C, Denmark * Fax +45 3528 2350
Markus Mottl
> The executive summary (very executive indeed) is that the meaning of
> `referential transparency' in the programming language community has
> very little to do with the meaning originally intended by the
> philosopher W v O Quine (1960).
This is also the conclusion of this article:
http://sources.redhat.com/ml/guile/1998-08/msg00401.html
What we usually consider "referentially transparent" was called "purely
referential" by Quine, whereas "referentially transparent" in Quine's
definition, who actually took it from Russel and Whitehead's "Principa
Mathematica", would rather correspond to the "hygenic" property of
certain macro systems. I haven't checked the original literature for
this though...
> What conclusion to draw from this? Perhaps we should just say `free
> of side effects' when that is (roughly) what we mean.
Well, this term also doesn't quite hit what we mean, because "purely
functional" programs do have side effects, but those are handled in, hm,
"purely referential" ways. Maybe it would just suffice to say "purely
functional"?
Regards,
Markus Mottl
--
Markus Mottl mar...@oefai.at
Austrian Research Institute
for Artificial Intelligence http://www.oefai.at/~markus
Stefan Axelsson
> What conclusion to draw from this? Perhaps we should just say `free
> of side effects' when that is (roughly) what we mean.
Interesting reference, thanks.
This begs the question though; what is 'free of side effects'? As
we've argued earlier, timing behaviour may or may not be a side effect
depending on your world view. Is there a commonly agreed upon
definition of 'side effect'?
Google didn't turn up anything useful. I did find the pharmacological
definition of side effect: "any unintended effect..." That would
roughly translate to 'bug' in our field, but i feel that equating side
effects with bugs may be overstating the case, even on
comp.lang.functional. ;-)
Matthias Blume
> > What conclusion to draw from this? Perhaps we should just say `free
> > of side effects' when that is (roughly) what we mean.
>
> Well, this term also doesn't quite hit what we mean, because "purely
> functional" programs do have side effects, but those are handled in, hm,
> "purely referential" ways. Maybe it would just suffice to say "purely
> functional"?
That is not right. A purely functional program, indeed, does not have
side effects. However, a purely functional program is free to
calculate a value in the domain of "computations" (aka, monadic
value). Only "performing" that computation will then have side
effects.
Matthias
Markus Mottl
> Markus Mottl <mo...@miss.wu-wien.ac.at> writes:
>> Well, this term also doesn't quite hit what we mean, because "purely
>> functional" programs do have side effects, but those are handled in, hm,
>> "purely referential" ways. Maybe it would just suffice to say "purely
>> functional"?
> That is not right. A purely functional program, indeed, does not
> have side effects. However, a purely functional program is free to
> calculate a value in the domain of "computations" (aka, monadic value).
> Only "performing" that computation will then have side effects.
In a strict sense you are right. Monads help structuring computations,
and in the case of Haskell this means that you specify a computation that
can cause I/O (I/O-monad), which is then executed by the runtime. But
it is really a matter of definition, whether one can say that running
a functional program does not cause side effects.
Joachim Durchholz
> (Aside: I find it difficult to believe people are writing programs which
> critically depend on the precise timing of an referentially transparent
> function. Are there examples of this?)
Of course. Any referentially transparent function that's called from a
timing-dependent piece of code.
And there exist plenty of strange timing dependencies. For example, I
was once involved in a project that had to talk to some hardware over a
serial line. The problem was: there was no flow control. You had to send
the data in the exact right timing, else the receiving end of the line
would either reread the byte that you had previously sent, or it would
miss a byte. (Synchronization was via a too high-level handshake
protocol. One of the worst-designed interfaces that I have seen in my life.)
What made things really messy was that the processor driving that serial
line also had to keep two or three other processes running.
Regards,
Joachim--
Peter G. Hancock
> I am convinced that relying on timing behaviour in complex software
> is a terrible mistake, and I can't come up with a good example of
> where it is unavoidable to do so (I'm sure I can come up with good
> examples of where it is difficult to completely eliminate timing
> dependencies, but I will resist the temptation for now.)
Isn't consensus an example? Didn't Lynch and someone prove that
there's no entirely asynchronous algorithm to solve the consensus problem?
So you have to rely on timing behaviour of clocks, at least.
Peter Hancock
Ulf Wiger
>>>>> "Ulf" == Ulf Wiger <Ulf....@ericsson-cut-to-reply.com> writes:
>> I am convinced that relying on timing behaviour in complex
>> software is a terrible mistake, and I can't come up with a good
>> example of where it is unavoidable to do so (I'm sure I can come
>> up with good examples of where it is difficult to completely
>> eliminate timing dependencies, but I will resist the temptation
>> for now.)
P> Isn't consensus an example? Didn't Lynch and someone prove that
P> there's no entirely asynchronous algorithm to solve the consensus
P> problem? So you have to rely on timing behaviour of clocks, at
P> least.
I haven't read that proof, but it's probably sound. (:
Personally, I try to avoid relying on concensus, and opt for master-slave
(I know, politically incorrect name) solutions as far as possible.
One might say that leader election is still a concensus problem, and it
is surely a difficult one, where timing issues easily come into play,
but there are tricks...
/Uffe
Stefan Axelsson
> One might say that leader election is still a concensus problem, and it
> is surely a difficult one, where timing issues easily come into play,
> but there are tricks...
Such as?
Ulf Wiger
e> , Ulf Wiger wrote:
>> One might say that leader election is still a concensus problem,
>> and it is surely a difficult one, where timing issues easily come
>> into play, but there are tricks...
S.A.> Such as?
Well, we are (or rather Thomas Arts is) working on a new leader election
protocol which looks extremely promising, but I don't want to forgoe his
continued work.
Basically, leader election in a stable system is dead simple: one can
rely on a global ordering (e.g. a pre-sorted precedence list, or
comparing process identifiers), and simply choose the "preferred" candidate.
If all candidates are equal, any ordering scheme will do; if not, one may
have to offer a plug-in capability to allow for a custom selection, but
that's no harder than writing a customizable sorting function.
One may simply broadcast a 'hello' to all candidates, and then patiently
collect replies; once all replies are received, one knows who the leader
should be, and given a well-defined global ordering, one knows that everyone
agrees. One assumption that greatly simplifies things is that you know the
candidates in advance.
Now to the problems:
Not all candidates may reply. They may not be there initially, but appear
in the middle of the negotiation; or they may crash upon receipt of the
'hello'; worse yet, they may get halfway through, crash and then re-enter
the negotiation. This can make it very hard to converge upon a decision.
The trick needed is one that lets a candidate know that it has enough
votes, and for this it needs to know how many could vote, and how many
are not able to vote at the time.
One may, for example, simply disqualify candidates that are not up when
the 'hello' is sent. This assumes that we can rely on the 'hello' to
actually arrive if the process is up. In Erlang, we can safely make that
assumption. We can also monitor any process (remote or local) and receive
a 'DOWN' message if that process is not alive; then we know that it should
be removed from the candidate list.
One of the really hairy problems to consider is that two processes may
lose contact even though both of them are still alive. This will partition
the decision space, and we cannot rely on global ordering, or consistent
information throughout the system. Essentially, two leaders will be selected,
and if the communication link reappears, we have a conflict.
In Erlang, we can configure the "nodes" so that they cannot reconnect
unless one of the nodes restarts. Then, using a "backdoor" mechanism, we
can detect the problem and restart one of the participants.
Another solution is to allow two leaders, and then perform a merge if a
conflict arises. This may not work in the general case, but we've been
reasonably successful doing that in some cases.
/Uffe
Peter G. Hancock
> Well, we are (or rather Thomas Arts is) working on a new leader election
> protocol which looks extremely promising, but I don't want to forgoe his
> continued work.
Most likely the people know about the Paxos algorithm of Lamport,
which bears directly on consensus and leadership election. But in
case not (horror!), here's a snip from a TLA file among the TLA tools
accessible via http://lamport.org
(* This module describes an algorithm for implementing the consensus *)
(* specification of module SynodSpec, in the presence of nonByzantine *)
(* failures. The idea is that the processors should elect a leader, and *)
(* the leader will try to commit a value. Progress requires that a *)
(* unique leader is elected. However, safety is guaranteed even if more *)
(* than one processor thinks it is leader. Such an algorithm is useful *)
(* because it's not hard to implement a leader election algorithm that *)
(* works most of the time--that is, when the system is stable, and there *)
(* are no new failures. If the election algorithm fails, no harm is done *)
(* because safety is maintained. *)
So one wonders if the crucial thing is not leader election, but the protocol
followed by entities that think they are leaders.
Peter Hancock