Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
In the second sentence, did you mean "check the value of a"? –  delnan Jan 23 '13 at 16:59
1  
@delnan I did, fixed. Thanks for pointing it out. –  David Chouinard Jan 23 '13 at 17:00
1  
relevant en.wikipedia.org/wiki/… –  jk. Jan 24 '13 at 10:44

3 Answers 3

up vote 10 down vote accepted

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

share|improve this answer
3  
It is worth noting that some parts of Haskell (IORef, MVar, etc) are mutable and behave as references (hpaste.org/81192) –  jozefg Jan 23 '13 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.)

share|improve this answer
1  
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. –  Jörg W Mittag Jan 23 '13 at 22:12
1  
@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.) –  Gilles Jan 23 '13 at 22:19
1  
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? –  Jörg W Mittag Jan 23 '13 at 22:33
2  
@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. –  Gilles Jan 23 '13 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!)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.