Subject: Locatives
From: James Nicholas Deibel (jdeibel@cs.washington.edu)
Date: Thu Apr 18 2002 - 18:36:35 PDT
A few of you probably recall Matt mentioning that I would discuss the
book's use of locatives in quiz section. For the record, I did not forget
this. In working out a good explanation, I concluded that having a
written record would be better than an in-class discussion (and would
have less chance of me issuing a series of profanities on the subject).
First, let me say that the use of locatives by the authors (in my
opinion) was motivated by pure laziness. The book describes their
motivations on pages 12-15. It is important to realize this book was
written prior to object-oriented programming languages being the norm.
Primarily, locatives address the issue of traversing linked structures.
For example, the linked list implementation we are used to requires two
node pointers. One pointer points to the current node and the other to
the previous node in the list. Furthermore, there are issues we have to
deal with in inserting items at the head of the list.
Lewis and Denemberg's complaint with this approach is that it uses two
pointers (a waste of memory if you view that way) and it causes the need
for lots of special cases in insert and delete functions in a linked
structure. They "solved" this by creating a structure called the
locative. Each time a value is assigned to a locative, the locative also
stores where (in memory) that value came from. This place in memory is
called the locative's locative value.
For the most part, you will not see them use locatives much in the code in
the text. However, there are some instances. Primarily, there is a
distinction between a regular arrow (only one horizontal bar), <-, and a
double-arrow (two horizontal bars), <=. If P <= Q, then the value of Q is
assigned not to the memory location pointed to by P but instead the value
of Q is assigned to the locative value of P (the memory location where P
last got its value). As their examples show, this cuts down on special
cases and makes them need less pointers.
Locatives, are, however, not cleanly implementable in any language that I
know of. In fact, the space saved by using only one pointer is a false
savings. The locative would still have to store the memory address of
where it got its last value; this is the same space requirement as a
pointer! The only advantage to a locative is that it makes code smaller
in size. However, as a lot of software engineers will tell you, code
length is not an indication of code quality. Perhaps Lewis and Denemberg
can read locative code easily, but I doubt it holds for many others.
Fortunately, locatives occur only infrequently in the book. Most of the
time, we will provide pseudocode that does not use them. To deal with
locatives in the book's code, remember that it is essentially a shorthand
for having a second pointer that lags behind the main one. Be wary of any
special cases the locative might be hiding, particularly those cases where
the pointers deal with the end or the beginning of a linked structure.
And, as always, ask Kevin, Matt, or myself to help you decipher the code.
nick deibel
jdeibel@cs.washington.edu
-- assume nothing is mundane. life is automatically more perplexing.
This archive was generated by hypermail 2b25 : Thu Apr 18 2002 - 18:36:48 PDT