Devising test of Haskell's value/reference semantics

In imperative languages, it is trivial to devise a programming test of language's use of "value semantics" or "reference semantics". One could do the following and check the value of `a` (where `Vertex {one, two, three :: Integer}`):

``````a := Vertex 3 4 5
b := a
one b   :=  6
two b   :=  8
three b := 10
``````

However, since variables are immutable in functional languages, this test won't work in such languages.

I know very little about Haskell (and functional programming in general), but my understanding is that it uses value semantics. Is it possible to devise a programming experiment that would distinguish between a "ref record" and a "val record" in Haskell?

• In the second sentence, did you mean "check the value of `a`"?
– user7043
Commented Jan 23, 2013 at 16:59
• relevant en.wikipedia.org/wiki/…
– jk.
Commented Jan 24, 2013 at 10:44
• Haskell is referentially transparent,[1] which means that 'value semantics' and 'reference semantics' are equivalent in Haskell. [1] Programming language geeks will have a long debate over that statement, but it's quite traditional to use it in the sense I just did. Commented Sep 11, 2017 at 19:31

There is no such test, because, without mutability, the distinction isn't meaningful (as you demonstrated).

• It is worth noting that some parts of Haskell (`IORef`, `MVar`, etc) are mutable and behave as references (hpaste.org/81192) Commented Jan 23, 2013 at 23:15

Haskell does not have references (a reference is a mutable object, and Haskell does not have (directly-accessible) mutable objects). Therefore function calls use value semantics, kind of by default. This is in fact an important property of pure functional languages: a function cannot modify its argument.

Value semantics does not imply that copying happens under the hood. You only need to copy the part of a value that the function modifies, which in a pure language means you never need to copy anything.

However, this isn't the whole story. In a sense, Haskell has reference semantics.

While it is meaningless to test whether a function modifies its argument (it never does), you can test whether a function uses (part of) its argument. Supply it with an argument that does not terminate. If the function call terminates, you know the function didn't use its argument.

``````let bottom = bottom
let ignore x = 1
ignore bottom
``````

If you evaluate `bottom`, it does not terminate: `bottom` expands to itself, ad nauseam. The term `bottom` cannot have a value. But if you evaluate `ignore bottom`, the value is `1`. This shows that calling the function `ignore` does not require to calculating the value of its argument. In this sense, Haskell has a reference semantics: what a function receives is not a value but something that allows this value to be found. The technical term is call by name (as opposed to call by value).

(More precisely, Haskell implementations use call by need. In call by value, the argument of a function is evaluated exactly once, just before calling the function. In call by name, the argument is evaluated each time it is used, which can range from never to as many times as the function wants. In call by need, the argument is evaluated at most once: it is evaluated the first time it is used, or never if it isn't used.)

• Of course, again, in a pure language call-by-need and call-by-name are indistinguishable. Call-by-need then simply becomes an optimization strategy. Commented Jan 23, 2013 at 22:12
• @JörgWMittag Good point, I forgot to mention that. (By the way, to nitpick, call-by-need is not always more efficient than call-by-name when operating in finite memory.) Commented Jan 23, 2013 at 22:19
• Yeah, but who has only finite memory? We're all using Turing Machines, right? Seriously: I suppose that is because you a certain bookkeeping overhead regarding whether or not you "need" the value, right? E.g. thunks or something like that? Commented Jan 23, 2013 at 22:33
• @JörgWMittag But even in a Turing machine, memory is a limitation in that if you keep more stuff around, reaching the useful stuff requires more back-and-forth of the tape. On real computers, this is called poor cache locality. Commented Jan 23, 2013 at 22:37

It is impossible to distinguish between them. What this means is that the compiler is free to choose to use whatever semantics it sees fit for optimum performance.

In particular, functional languages are typically described as having value semantics, because that matches our conceptual model of them, but they are often implemented using reference semantics because that's more efficient. (No need to copy something that can't be changed!)