2
$\begingroup$

Almost all type-theoretical treatments of references that I've studied introduce references as accompanied with at least three operations (sometimes including the fourth):

  1. Construction (allocation): $ \text{ref } e $
  2. Elimination (dereferencing): $ !e $
  3. Updating: $ e_1 := e_2 $
  4. (not as common) Destruction (deallocation): $ \text{free } e $

My question is this: Would references be of any use without updating (construct #3 above)? If so, what would be a common use? Does the ability to use updates with references lend any more "power" to a language? You can answer assuming either the presence or absence of construct #4 above; if it affects your answer, please explain how.

$\endgroup$
  • 1
    $\begingroup$ What is your meaning of "power"? Since there are Turing complete language/computation models that don't need references, there should be no trouble at that front. You would get immutability/referential integrity/name it, however, which would be nice. You'd have to copy everything, though. By now it sounds like functional programming, doesn't it? $\endgroup$ – Raphael Jan 22 '14 at 15:39
  • $\begingroup$ @Raphael, it's open to your interpretation. I'm just trying to get a general sense of what is offered by updating. $\endgroup$ – BlueBomber Jan 22 '14 at 21:59
3
$\begingroup$

References are useful even if you don't update the object, since copying objects takes memory and time. When passing a reference, only a pointer is passed. But suppose that you were passing a string - it could take far longer to copy the entire string. This is why language like C++ support constant references, which are references that cannot be updated.

$\endgroup$
  • $\begingroup$ I understand at lower levels (that is, closer to machine language than the actual level of the programming language), that you can save space by only storing one object (instead of potentially many), but in this case, couldn't you claim the same thing about a language that doesn't have references at all? $\endgroup$ – BlueBomber Jan 22 '14 at 22:01
  • $\begingroup$ I can, and it can sometimes cause problems (the recent C++ standard, for example, attempts to fix some such problems). You don't actually need references, pointers are enough, or hidden references like in python. $\endgroup$ – Yuval Filmus Jan 22 '14 at 23:00
  • $\begingroup$ Functional languages work just fine by never updating anything. $\endgroup$ – vonbrand Jan 24 '14 at 13:25
  • $\begingroup$ If you never update anything, it will be hard, for example, to compute a histogram. $\endgroup$ – Yuval Filmus Jan 24 '14 at 15:02
2
$\begingroup$

Another thought, it's very easy to implement parametric polymorphism if all objects are boxed. Indeed that's how data in Haskell, *ML, and most other languages are stored.

Sure the operations are not explicit, but

case Just 1 {- Allocation -} of
  Just x {- dereferencing/fetching -} -> x + 1

and then garbage collection ~~ deallocation.

This is important since if things are really pointers, they can be treated as all having the same size on the stack.

It also has the benefit of simplifying optimizations you'd expect like sharing which fall out almost naturally of having data be pointers under the covers.

$\endgroup$
1
$\begingroup$

For a new object to be useful, it must be possible to keep the reference at least long enough to dereference it once. In many cases, that will require some means of copying the return from the object-construction method to the input parameter of the dereferencing method. There are a number of situations in which objects could be useful even if no other means of copying the reference were possible. Indeed, there are a number of situations where objects would be made more useful if the system could guarantee that particular object references were unique (meaning that no other reference could possibly identify the same object). Code which encapsulates state by holding the only reference to a mutable object may modify the state encapsulated by the reference by modifying the object identified thereby. If other references to the same object might exist for the purpose of encapsulating its state, however, changing the state encapsulated by a reference without changing the state encapsulated by those other references would require constructing a new object, modifying it, and holding a reference to that. When the former style of update is possible, it's often more efficient than the latter. Unfortunately, the only way to know it's safe is to know that one holds the only reference to the object in question--an invariant which many languages provide little if any help in enforcing.

$\endgroup$
1
$\begingroup$

I think there is a confusion between two separate notions of "reference".

When C or C++ talk about "references" in the sense of call-by-reference, they are talking about pointers to data objects.

When ML or Glasgow Haskell talk about "references", they are talking about mutable cells.

These are two completely different concepts, but the same terminology is used. There is absolutely no connection between the two concepts.

I personally prefer the C/C++ sense of "reference", which was originally introduced by Tony Hoare in Algol W. The ML terminology comes from Algol 68, designed by a group of European Computer Scientists with perhaps a questionable grasp of the English language. They should have just called them "mutable cells" instead of "references". Whenever you read the term "reference" in a type theory paper, best to translate it mentally as "mutable cell". That is what they are.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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