Daily, 2010/10/15: mutable state and scope vs. extent

I'm going to make this short, because I've been laggard with my dailies, and the practical solution is to make them quicker to post!

Today, we finished up our implementation of mutable state using boxes.  We touched again on the crucial idea that state "threads" through evaluation in a very different way from environments, in particular in a dynamic fashion.  Mutable state's dynamic nature makes it both useful and dangerous to use.

In fact, it's even harder to understand where state changes come from than identifier bindings in dynamic scoping.  That's because an identifier instance's binding in dynamic scope must be present in the dynamic context of the instance, the "call stack" in machine-oriented terminology.  However, state changes can propagate from outside the dynamic context.

Our tree-labeling example illustrated that.  Consider this tree:

  (node (leaf 0) (leaf 0))

When we label it, we'll make a recursive call on the left branch.  The recursive call sets the leaf's contents to 1 and updates the counter's state.  That function call is then over and gone: no longer "on the call stack", no longer part of the dynamic context of the program's evaluation.  Then, we make a recursive call to label the right branch, and the label is 2 (not 1) because of changes that occurred in a function that's already over and done with.

The other important idea we discussed stems from the dynamic, threaded nature of the store.  Identifiers have static scope (which we want), but the contents of the store have dynamic extent because they can escape the static scope in which they are created.

In our interpreter, we have no problem because we never remove anything from the store.  So, values in the store have unlimited extent.

In C and C++, memory that is allocated "on the stack" (generally space associated with local variables of functions) is reclaimed when the function that allocated it terminates, at the same moment that the variable's name also goes out of scope.

This can cause serious problems with code like this from class:

  int * next(int * x)

  {

    int y = *x + 1;

    return &y;

  }

This code compiles and may even run correctly, but it may also cause immediate or distant errors, depending on the structure of the program in which it is called and the implementation details of the compiler and machine used.  Yuck!

(My version of gcc warns me about returning &y. Good for it!  But it gives no warning when I change return &y; to return next(&y); or even if I call a different function expecting an int*.)

Lastly, I made a rather muddled point about whether we store values or store locations in the environment.  I may defer discussion of this to tutorial on Tuesday.

Cheers,

Steve