Algorithm Alley

Trouble in Paradise

Algorithms are great at describing solutions to problems such as how to sort an array or how to compress a text file. But algorithms don't usually provide all the gory details needed to implement a method of solution--my favorite definition for an algorithm. Error handling, for example, complicates the job of turning an algorithm into a running program. What should an algorithm do to help programmers cast out the demons in their code?

The answer depends on the algorithm's needs, its peculiarities, operating-system requirements, and a host of other variables. How you deal with trouble in paradise also depends on what you consider to be an error. The word error suggests that something has gone wrong, but it isn't practical for algorithms to account for every possible unplanned event such as a hard-drive failure or a bad parity bit in RAM. Instead, errors at the algorithm level are better thought of as exceptional conditions that arise during the course of an algorithm's execution. In this sense, errors are normal, though unusual, values, conditions, or other happenstance that require special handling.

Why, then, do most algorithms ignore exceptional conditions? I've never seen a sorting algorithm that explains, for example, what to do with a stack overflow, even though a proper implementation must plan for that unhappy event. Programmers are expected to understand that, in addition to implementing an algorithm's steps, other details such as error handling are required. Perhaps if algorithms provided more of these details, fewer bugs would be introduced by neglecting to account for potential problems known to the algorithm's designer.

ANSI C++ exceptions provide the tools that algorithms can use to do exactly that. The concepts of exceptions and exception handlers aren't new. They've been around for years but have usually been provided as library functions or operating-system interrupt services. As nonsystem-dependent language elements, exceptions are suitable for incorporating error handling into algorithms. For those who haven't used exceptions, the following is a brief tutorial. After that, I'll list an algorithm in pseudo-Pascal and its implementation in C++, both of which use exceptions to report illegal input values.

C++ Exceptions

What happens at this point is up to you. The program might continue or end, or it could restart the condition that caused the problem. An exception is a mechanism for reporting and dealing with errors--an exception doesn't dictate a course of action. Actually, exceptions aren't limited to error handling. An empty list, for example, could report its bare cupboards as an exceptional condition that requires special treatment. Exceptions can be objects of any type, but they are most conveniently represented as instances of a class. For example, you might declare an Overflow class--it doesn't need any substance, just a name: class Overflow { };. You can throw an instance of the class as an exception, throw Overflow();. Elsewhere, the program can catch the exception in a Catch statement, as in Example 1(b).

The Throw statement throws an object of the Overflow class, which is caught by the Catch statement at another place in the program (never mind exactly where for the moment). The technique might be easier to understand by giving the object a name; see Example 1(c).

You might call error-class member functions for the named exception object. For example, class Overflow could declare a member function Report, as in Example 1(d). The Catch statement can call Report for the thrown exception object to display an error message; see Example 1(e).

Now it's time to toss in another wrinkle--try blocks. Consider the sample function in Example 2(a) that throws a couple of exceptions. If conditionA is True (whatever that is), the function throws a string exception that reports "Big trouble!." If conditionB is true, the function throws an object of the Overflow class, initialized by the default constructor. If the function detects no errors, it returns normally, passing back the return value "123." Throwing an exception immediately terminates the function. In other words, an exception provides functions with an alternate return mechanism. Rather than reserve a special value such as --1 that, if returned by a function, signals an error, exceptions make it possible for functions to return a different type of value that flags a problem.

To enable exception handling, call a function inside a try block. For example, Example 2(b) shows how you might call AnyFunction.

A try block contains one or more statements for which you want to catch exceptions. The most important rule to remember about try blocks is that Catch statements must follow them immediately. You cannot have a try block in one place and Catch statements elsewhere. That would be like having a baseball pitcher in one stadium and the catcher in another. Example 2(c) is a more complete example that keeps all the necessary players in the same ballpark. The expanded code first tries to call AnyFunction. If the function returns normally, the program assigns the function result to x. In that case, the program skips the two Catch statements because there are no exceptions to handle. If AnyFunction throws an exception, however, the try block immediately terminates, and a subsequent Catch statement catches the thrown object.

Exceptions in Practice

There are several other esoteric details concerning exceptions, their declaration forms, and the consequences of throwing exceptions in constructors, destructors, and so forth. My aim here, though, is not to provide a complete tutorial on C++ exceptions, but to introduce the main concepts as a means for dealing with errors in algorithms expressed in Pascal. Example 3 shows a sample algorithm in pseudo-Pascal for raising a real number to any real-number power.

The method uses the formula exp(E * ln(B)), where E is the exponent and B is the base. Textbooks on programming typically list this algorithm, but neglect to account for conditions that cause the method to fail--raising a negative base to a fractional exponent, for instance, and raising zero to an exponent less than zero. As a consequence, many programs that use the standard formula simply halt when fed illegal input--not exactly a robust implementation. In the example, on attempting to raise a negative base to a fractional exponent, Power accounts for illegal arguments by throwing an exception. The resulting Error object completely describes the problem, and it includes copies of the illegal input values: throw Error(b, e);.

I don't know of any Pascal compilers that have Catch, Throw, and Try keywords, so you probably can't run the example as listed. Using an ANSI C++ compiler such as Borland C++ 4.0, however, you can compile and run the algorithm's implementation in Listing One (page 147). The sample program includes a Power function that throws exceptions for illegal arguments. Call Power in a try block like that in Example 4(a). If Power throws an exception, the final output statement is skipped and the try block immediately ends. A subsequent Catch statement can trap the exceptions; see Example 4(b).

Listing One's Power function also shows one way to use exceptions to trap errors in source-code implementations--a function that doesn't account for all possible input values, for example. Enable the last commented statement in Power to throw the exception "Implementation Error" if the preceding code doesn't account for all possible exponent and base arguments (see the Error class's default constructor). This statement causes the compiler to generate an expected "Unreachable Code" warning. The warning is desirable in this case because it indicates that the preceding statements provide for all possible exit paths from Power.

Unhandled Exceptions

Your Turn

Example 1: (a) An exception handler can catch and display a message;

(b) a program can catch an exception in a Catch statement; (c) using the Throw statement; (d) class Overflow declares a member function Report; (e) displaying an error message.

<b>(a)</b>
catch (char* message) {
  cout 
    << "Error! -- " 
    << message 
    << endl;
}

<b>(b)</b>
catch (Overflow) {
  cout 
    << "Overflow detected!" 
    << endl;

}

<b>(c)</b>
catch (Overflow overObject) {
  // ...
}

<b>(d)</b>
class Overflow {
  void Report() { 
    cout 
      << "Error: overflow" 
      << endl;
  }
};

<b>(e)</b>
catch (Overflow overObject) {
  overObject.Report();
}

Example 2: (a) Throwing exceptions; (b) enabling exception handling by calling a function inside a try block; (c) calling AnyFunction.

<b>(a)</b>
int AnyFunction()
{
  if (conditionA) 
    throw "Big trouble!";
  if (conditionB) 
    throw Overflow();
  return 123;  // normal return
}

<b>(b)</b>
try {
  int x = AnyFunction();
}

<b>(c)</b>
try {
  cout << "Here we go! << endl;
  int x = AnyFunction();
  cout << "x == " << x << endl;
}
catch (char* message) {
  cout << "Error! -- " 
    << message << endl;
}
catch (Overflow) {
  cout << "Overflow!" << endl;
}

Example 3: Pseudocode for Algorithm #19 (Power).

function Power(Base, Exponent: double):
double;
  function Pow(B, E: double): double;
  begin
    Pow := exp(E * ln(B))
  end;
begin
  if (Base > 0.0) then
    Power := Pow(Base, Exponent)
else if (Base < 0.0) then
  begin
    if frac(Exponent) = 0.0 then
      if odd(trunc(Exponent)) then
        Power := -Pow(-Base, Exponent)
      else
        Power := Pow(-Base, Exponent)
    else
      Throw Error(Base, Exponent)
  end else
  begin
    if Exponent = 0.0 then
      Power := 1.0
    else if Exponent < 1.0 then
      Throw Error(Base, Exponent)
    else
      Power := 0.0
  end
end;

Example 4: (a) Calling Power in a try block; (b) trapping exceptions with a Catch statement.

<b>(a)</b>
try {
  double base, exponent, result
  // ... prompt for base and exponent
  result = Power(base, exponent);
  cout << "result == " << result << endl;
};

<b>(b)</b>
catch (Error& e) {
  e.Report();
  return -1;
}
return 0;

[LISTING ONE]

// powex.cpp -- Implementation of Power function
// requires Borland C++ 4.0 or ANSI C++ compiler with exceptions
// Copyright (c) 1994 by Tom Swan. All rights reserved

#include <iostream.h>
#include <math.h>

class Error;

double Pow(double b, double e);
double Power(double b, double e) throw(Error);

class Error {
  double b;    // Base
  double e;    // Exponent
public:
  Error()
    { cout << "Implementation error!" << endl; }
  Error(double bb, double ee)
    : b(bb), e(ee) { }
  void Report();
};

int main()
{
  cout << "Power Demonstration\n\n";
  cout << "This program displays the result of raising\n";
  cout << "a value (base) to a power (exponent). To\n";
  cout << "force an exception, enter a negative base\n";
  cout << "and a fractional exponent (e.g. -4 and 1.5)\n";
  cout << "Or, enter a zero base and an exponent less than\n";
  cout << "zero.\n\n";
  try {
    double base, exponent, result;
    cout << "base? ";
    cin >> base;
    cout << "exponent? ";
    cin >> exponent;
    result = Power(base, exponent);
    cout << "result == " << result << endl;
  }
  catch (Error& e) {
    e.Report();
    return -1;
  }
  return 0;
}

// Subfunction to Power
double Pow(double b, double e)
{
  return exp(e * log(b));
}

// Return b raised to the e power
double Power(double b, double e) throw(Error)
{
  if (b > 0.0) return Pow(b, e);
  if (b < 0.0) {
    double ipart;
    double fpart = modf(e, &ipart);
    if (fpart == 0) {
      if (fmod(ipart, 2) != 0)  // i.e. ipart is odd
        return -Pow(-b, e);
      else
        return Pow(-b, e);
    } else
      throw Error(b, e);
  } else {
    if (e == 0.0) return 1.0;
    if (e < 1.0) throw Error(b, e);
    return 0.0;
  }
//  throw Error();  // Unreachable code warning expected
}

// Display values that caused an exception
void
Error::Report()
{
  cout << "Domain error:"
    << " base:" << b
    << " exponent:" << e
    << endl
    << "Press Enter to continue...";
  char c;
  char buffer[80];
  if (cin.peek() == '\n') cin.get(c);
  cin.getline(buffer, sizeof(buffer) - 1);
}