The Startup
Published in

The Startup

Four Models of Error Handling for Stacks

Error handling is part of every programmer’s regular work. There will always be cases where our code won’t work, and it is our job to make sure that does not take down the whole application. We want to build sturdy applications without bugs or crashes. In this post, we explore four different models for handling error cases in our code. Optimally all code would fail gracefully, and not simply crash the application. However, this is often easier said than done, which is why we need a flurry of techniques for handling it.

The techniques described here range from very basic to very advanced, each has pros and cons. As with most things, there is no silver bullet. The best we can do is to have enough tools under our belt, so we can choose the best one for a given situation.

The running example in this post is the familiar stack data structure. Examples are implemented in Java, but any modern object-oriented language should be similar. If you want to play around with the examples you can access the source code at my GitHub (@maxipaxi). In the repo, each type is implemented as a layer on top of the most advanced version.

There are conventionally two error cases in a stack: Popping something off an empty stack, and pushing something on a full-stack. In our implementation each element has a pointer to the next element, eliminating the latter error type. Therefore we concentrate on pop. To reduce the complexity we assume that pop only removes an element without returning it, as we can just use peek to look at it.

Error codes

The simplest way to handle the case when we pop something off an empty stack is to return some special value signifying whether the operation succeeded or not. In Java, this value is often null when working with classes or generics, -1 when we work with integral types, and a boolean when there is no return value.

This is the case here:

boolean pop() {
if (isEmpty()) {
return false;
} else {
advanceHeadPointer();
return true;
}
}

The primary advantage of this is its simplicity. It is easy to implement, and easy to understand. Unfortunately, it is also easy to miss. We are not required to check the return value, and when we use null we may have just postponed the crash to when we someday get the inevitable NullPointerException.

Exceptions

Going one step up we can choose to throw an exception immediately. We can even make it checked so the receiver is forced to deal with it.

void pop() {
if (isEmpty()) {
throw new EmptyStackException();
} else {
advanceHeadPointer();
}
}

Again, very simple. We also preserve the return type and therefore the signature of the method, which we like. Some disadvantages include exceptions being generally slow in Java, so we better hope it doesn’t happen. By default, a lot of exceptions in Java are unchecked (like the one used here) which means the receiver may not remember to check it, and we are in the same case as above.

Blocking

What we want is to make sure there is something in the stack before trying to pop it. If we are in a multi-threaded application we have the option to simply wait until something is there. So if the stack is empty we lock the thread and wait, then when something is pushed we resume work.

Stack() {
available = new Semaphore(0);
}
void push(T element) {
putElement(T);
available.release();
}
void pop() {
available.acquireUninterruptibly();
advanceHeadPointer();
}
T peek() {
available.acquireUninterruptibly();
available.release();
return head.element;
}

This method is more complicated, because we need to be sure that another thread will push something, otherwise we have deadlocked our thread. Additionally, concurrency is a constant strain on our mental capacity, so if we can abstract it away that is usually preferable.

Typing

The ultimate safety is to encode our knowledge in the types, so the compiler knows what is going on. This means that it will check — and even prove — that our code cannot error (from popping). We achieve this by utilizing some complicated generics. Whenever we have complicated code we should justify it! In this case, since this is a library and not something that changes often that is probably acceptable.

Explaining how the generics was built is out of the scope of this post, leave a comment if you’d like to see a future post on that. However, we can explain the general principles.

These stacks are in one of two states:

  1. One where we know some invariant, like:
  • this stack has exactly X elements, or
  • this stack has at least X element.

These are expressed in the type of the stack, eg. the type of a stack we know has exactly two ints would be: NonEmptyStack<Integer,NonEmptyStack<Integer,EmptyStack<Integer>>>

Here we can directly pop elements, with no worry that it will ever fail. The compiler can promise us that!

2. Another state where we know nothing about the stack.

We can still push as normal and it is always possible to go from state 1 to 2, called forgetting. But in this case, the only method for looking at the stack then is through a visitor, forcing us to handle both the case where we know it is empty, and the case where we know it is not:

stack.apply(new Visitor<>() {
public T apply(EmptyStack<T> s) {
throw new EmptyStackException();
}
public <R extends Stack<T, R>> T apply(NonEmptyStack<T, R> s) {
return s.peek;
}
});

Because the type of the stack changes we also have to make it immutable. I honestly prefer it this way in any circumstance. But it has the unfortunate side effect that we have to chain calls or make a new variable every time we do an operation:

var st = new EmptyStack<Integer>()
.push(3)
.push(2)
var st2 = st.push(1);
Assertions.assertEquals(2, st.peek); // st is unchanged
Assertions.assertEquals(1, st2.peek);

The primary advantage of this technique is that it is the safest. It is also the most general way to implement stacks, since we implemented the other kinds as layers on top of this one. Another advantage is that we can take advantage of invariants when we make the compiler know about them. Finally, even if we change something at any point in the future, the compiler checks that we have not broken any invariants around this stack.

The disadvantage is that this technique is difficult to learn and difficult to get right. It is not feasible for code that changes often, but it might be worth building the capabilities when we maintain some internal critical libraries. Or if we have a very low tolerance for failure.

Conclusion

We have looked at four different models for how to handle errors:

  • Using error codes we rely on the receiver to check the return value.
  • Using exceptions we can force the receiver to handle if something goes wrong.
  • Using threads we can rely on blocking to make sure the error does not occur.
  • Using types the compiler either can guarantee that the error cannot happen, or force us to handle it.

They all have their use cases, the most important thing is that our error handling is deliberate and we are aware of what our risks are. No one wants to get a mars rover stuck, or give people hundreds of times too much x-ray.

I discuss dangerous invariants much more in my book about refactoring, check it out here:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Christian Clausen

Christian Clausen

I live by my mentor’s words: “The key to being consistently brilliant is: hard work, every day.”