Month: November 2008

In the previous post, I explored the idea that some sentences change meaning if you switch between different names for the same object. Some other sentences don’t change meaning – these ones are referentially transparent, which in non-posh-speak means “you don’t notice if I switch to a different name”.

I’ve now asked some questions on haskell-cafe, and consulted various gurus at my work so I’m a little less confused that I was yesterday. 🙂

How does this concept apply to programming languages?

In haskell, you could say that the “names” were expressions like “2+2” and “sqrt(9)” and the underlying ‘thing’ which was being named are the values which those expressions evaluate to. So the integer “two” has many names – “1+1” and “sqrt(4)” and many others.

That gives us a nice connection back to the Quine definition of “referentially transparent”. Essentially, when we claim that Haskell is RT, its just a shorthand way of saying “you can replace an expression with any other expression that evaluates to the same result, and it won’t affect the overall meaning of the program”.

However, I feel that I’ve just handwaved over a few interesting points.

It’s reasonable to think of “sqrt(4)” as being a name for “2” in haskell because, well, functions always return the same value in haskell. But in Java or C, what kind of name could “rand()” be? The function evaluates to various values and it does this because it uses some kind of additional runtime context/state. So the basic idea that you can always have “names” and underlying “things” is a bit shaky – and we can’t really use Quine’s definition without them. What does it mean to say that C++ is “refentially opaque” if the very idea of names/references is shaky?

The same problem applies to the english-language examples from yesterday. I claimed that “Scotlands capital” was another name for edinburgh-the-city. That’s certainly true today. But it might not be true in 100 years. And perhaps, someone who lives in Glasgow might even disagree that its true today! So names which are co-referent today might not always be co-referent.

There’s a famous-ish example that’s similar too. In the sentence “The King of France is bald”, what kind of thing is being named by ‘The King of France’, given that France is a republic. That’s the kind of thing which keeps philosophers awake at night.

And if you’re into books, you’ll know that the author “Iain M Banks” writes sci-fi but “Iain Banks” writes mainstream fiction. There’s only one human being, but he writes under two “personas”. This makes me think that you have to be pretty careful about the THINGS that you think you are NAMING. In this example, “Iain M Banks” and “Iain Banks” are coreferent if you are discuss the human being, but they are not coreferent if you are discussing his “writing personas”.

There was one more point that I handwaved over. Why do I believe that Haskell really is referentially transparent? I might not trust Simon Peyton Jones when he claims that it is! But to prove some property of a language, you need a formal semantics for the language. And haskell98 doesn’t have that (unlike Standard ML). So there’s no much hope of doing a bottom-up inductive proof over the structure of the language – not just yet anyway. That’s a pity.

I’ll finish off with a couple of links about what RT means and RT and haskell.

Now I’m going to return to finish watching the SICP video which triggered this whole day-long distraction. 🙂

I like understanding why things have the names that they do. Two stories immediately spring to mind: the first is from Michael Faraday, which I wrote about a while ago whilst the second is from Richard Feynman (at 6 mins).

But back to the topic at hand! I know pretty well what the phrase “referentially transparent” means, at least in relation to computer programs. It’s used to describe languages like Haskell where its always safe to replace a function like “foo()” by its return value (eg. 4) without changing the meaning of the program. This is not something which you can do in general for languages like Java or C++ because functions, such as rand(), can potentially return different values each time you call them. Also, if foo() contains printf statement, then the expressions “foo()” and “4” are different beasts, even if foo() does always return 4.

So that’s the concept in question. But why give it a name like “referentially transparent”? What’s “transparent” about it? And what “references” are we talking about? (and how many metajokes could one make here?)

The term “referentially transparent” seems to come from a certain Mr Quine philosophising about natural languages. Let’s do an example, but first we need to look at two things.

Firstly, take a sentence like “Andrew is bigger than a mouse” and erase the word “Andrew” to leave a hole – ie. “??? is bigger than a mouse”. Philosophers call this a CONTEXT. By filling the blanks in the CONTEXT you get back to a sentence.

Secondly, think about the city of Edinburgh. It’s a thing. There are many ways to refer to it: “Edinburgh”, “Scotlands capital”, “the city at 56N 3W”.

Now we’re ready to understand where the phrase “referentially transparent” comes from.

The first word (“referentially”) is talking about the fact that “the Edinburgh thing” has many names. There are many ways to REFERENCE that thing.

You should read “transparent” to mean “doesn’t make a difference”. If Microsoft rewrite Excel so that it runs faster but the UI is identical then you’d say the change was “transparent” to the users. It’s “transparent” in the sense of “you can’t see it”. It DOESN’T mean “you can see all the innards”, like a transparent PC case.

Mr Quine says that a CONTEXT is “referentially transparent” if we can fill the hole with different names for the same underlying thing without affecting the meaning of the sentence.

An example should make this clearer:

• “[Edinburgh] is bigger than a mouse” is true.
• “[Scotlands capital] is bigger than a mouse” is still true.
• “[The city at 56N 3W] is bigger than a mouse” is also true.

So, the truth/meaning of the sentence WASN’T AFFECTED by our choice of which of those three REFERENCES we used. If we want to appear posher, we say that the context “(hole) is bigger than a mouse” is REFENTIALLY TRANSPARENT.

The opposite case is when your choice of name does matter. Quine describes those contexts as being REFERENTIALLY OPAQUE – ie. the changing names are important to the meaning of the sentence. An example would be the context “??? has 9 letters”:

• “[Edinburgh] has 9 letters” is true.
• “[Scotlands capital] has 9 letters” is false.
• “[The city at 56N 3W] has 9 letters” is false.

Therefore the context “??? has 9 letters” does change meaning depending on which name/reference we use. Why? It’s because the sentence is now discussing the name itself rather than the thing.

Actually, that’s not a great example because it’s not very clear what I meant by it – ie. in what ‘sense’ I used the words. If I was twisted, I could claim I intended to say that there was a sculpture exhibit in town which contained nine depictions of alphabet letters – in which case all three sentences would mean the same thing. English is too ambiguous! But the example is sufficient for the purpose of this blog posting.

Now let’s get back to programming languages and see if we can make some connection between what “referentially transparent” means in haskell and what we’ve just seen it means in natural language.

Errm, actually, maybe that’ll wait for another post. I need to get a clearer understanding of why I believe haskell is referentially transparent in the above sense without putting the cart before the horse. Eek, what if Simon Peyton-Jones has been lying to us all along!? I mean, I can’t think of any way to break the RT rules, but that’s very different from a ground-up proof.