Tuesday, October 27, 2009

Variable references and stack fun!

As I mentioned last time, there are some simple opcodes which are easy to get wrong on your first attempt at writing an interpreter. Section 14 of the Z-machine standard lists the complete table of opcodes and among these are seven which are listed as having a single operand marked as (variable). This means the operation uses the value of that operand as a variable number. This has nothing to do with variable operand types discovered while decoding the instruction.

To help us see what the standard means, we'll use the example of the load opcode. The description for load in the standard is "The value of the variable referred to by the operand is stored in the result." This sounds simple enough and we might try a naive implementation using the methods ReadVariable and Store like so:

ushort variable = this.Operands[0];
ushort value = this.ReadVariable(variable);
this.Store(value);


In most cases this will work properly but there is a corner case where it will fail, namely when the operand value is zero. In this case ReadVariable pops a value off the stack. What's wrong with this? Surely it is correct because section 6.3 of the standard says:

Writing to the stack pointer (variable number $00) pushes a value onto the stack; reading from it pulls a value off. Stack entries are 2-byte words as usual.

Unfortunately this case is not mentioned in the 1.0 standard but it is clarified in version 1.1:

Indirect variable references
----------------------------
In the seven opcodes that take indirect variable references (inc, dec,
inc_chk, dec_chk, load, store, pull), an indirect reference to the stack
pointer does not push or pull the top item of the stack - it is read
or written in place.


For these opcodes only, this behavior overrides that defined in the older standard.

Knowing this, a better implementation is:

ushort variable = this.Operands[0];
ushort value = this.ReadVariable(variable);

this.WriteVariable(variable, value);
this.Store(value);


This writes the value back to the variable immediately after reading, which in the above case would push the popped value back onto the stack. In all other cases, the write essentially does nothing since it is writing an identical value back into the variable. The other six opcodes can be implemented similarly by making sure whenever we read a variable we follow it with a write. I think this is a fairly clean way of dealing with the situation. Although it is possible to allow in-place reads/writes to the stack, doing so requires extras methods or extra parameters to the existing ones to change their behavior.

The rest of this post contains some of my random thoughts about stacks.

Typically a stack will have at least three methods, Push, Pop, and Peek. Sometimes Peek is referred to as Top, although I dislike that naming as it seems less descriptive to me. Push puts a value on the stack, Pop removes a value, and Peek let's you see the top element without removing it.

Why do we only allow read-only access to the top element? It is easy to imagine a method called Poke which allows in-place writes to the top element. If a Poke method seems like an abuse of the stack type, it makes me wonder if Peek might also be. Imagine a stack with just Push and Pop methods. No peeking allowed! You couldn't use the stack as a convenient holding area for the current working element. I'm curious as to what pressure for design changes this might exert and whether they would be good or bad.

Working on this reminded me of some comments about stacks on Eric Lippert's blog. Although I don't remember exactly when it was, the discussion involved whether 'Pop' should return a value or merely throw away the top element. I would argue that Pop should return the top element because it is the inverse of Push. One puts an element in, one takes an element out. With this arrangement, Peek is merely a performance optimization for a common set of operations! The equivalent of Peek could be achieved by a Pop followed by a Push of the same element back again. A hypothetical Poke method to allow in-place writes could just as easily be imagined to be a Pop followed by a Push of an altered value. It is interesting to me that this is a far less common case.

If you prefer Pop not to return a value, then it seems fair that Push not take a value, but rather create a default valued element. If you also added our hypothetical Poke method, you could set the new element to the value you want. From this point of view, Push accepting a value is just a performance improvement for a common set of operations!

What do you think?

6 comments:

  1. C++ stack implementations usually have a void Pop method because of exception-safety concern: the copy constructor of an object could throw an exception, which would corrupt the stack pointer.

    ReplyDelete
  2. Interesting. I guess things are a bit simpler in C#'s case due to the lack of copy constructors.

    I'm not really experienced with C++ but couldn't the Pop method be designed such that an exception in the copy constructor simply leaves the stack pointer where it was?

    ReplyDelete
  3. That copy constructor runs after Pop() and copies the temporary object it returns into the variable where you place it. Because of this, Pop() can't protect the caller from an exception thrown after it exits.

    ReplyDelete
  4. Hmm, what about returning a constant reference? That would avoid the copy constructor wouldn't it?

    It's interesting how language design can affect something as basic as a stack.

    ReplyDelete
  5. Returning a constant reference wouldn't work either, because the reference would point at a certain position in an array, which might be reused later; also, the user might not be happy with a constant object.

    A better choice would be to use a pointer, which is safe because the "copy constructors" for pointers only copy the value of the pointer and can't throw.

    This is the generic solution in C#: "use a class, not a struct". In C# classes are reference types (like pointers and references in C++), while structs are value types. Pointers need no copy constructors (copying a pointer to share it with someone else is different from cloning an object). You can certainly write "copy" constructors in C# too, but because of the automatic memory management and the ease of use of classes you don't need them too often.


    This whole mess isn't necessarily related to C++ or even exception; I'd say its roots are much farther, in the issues of object identity and equality. When are two objects equal? C++ has operator==, C# has operator==, Object.Equals and Object.ReferenceEquals, Java has at least operator== (or how it's called) and Object.equals. (I've been bitten by Java because I was comparing strings with ==).

    I find the C++ approach most clear because when you compare pointers you're sure what it does. Most telling, LISP has a whole plethora of comparison functions: EQ, EQL, EQUAL, EQUALP and various FOO-EQUAL and FOO-=s. Why? Because there's no "one size fits them all". Sometimes we want reference equality, other times we want structural equality, other times we care about types or something else. When we pop something off a stack do we care whether we get back the same thing or only a copy of it? The same thing happens on push (except the interaction between copy constructors and exceptions); in C++0x this is muddled further by the move references.

    A similar issue occurs in C#'s typing of delegates. Two delegate types might have the same signature, but they're still incompatible and this is the reason why lambda functions can't be implicitly typed using var.

    In the meanwhile, we should try be aware whether we need reference or value semantics for our objects, though sometimes it's not enough (what's a string? Why are they immutable in C#?).

    ReplyDelete
  6. There are a couple of ways around the pop problem for stacks in C++ that I can think of, but neither is perfect. If you have a stack of shared_ptr (either boost, tr1 or C++0x will do) then i'm pretty sure that the copy constructor of shared_ptr can't fail. shared_ptr is about the closest you can get to the CLRs reference semantics in standard C++. The problem with that is that it isn't very memory efficient both in size and locality.

    Alternatively, and i'm not sure if this would always work, you could have the pop method take an output reference argument. This way the stack pop function can perform the copy construction before mutating the stack so you can't lose an entry. This has its own problems though - requiring an output parameter means that the caller will need to construct an object to have it overwritten by the stack - that may not be possible, or it may be expensive.

    ReplyDelete