Semipredicate problem
From Wikipedia, the free encyclopedia
In computer programming, a semipredicate problem occurs when a subroutine intended to return a useful value can fail, but the signalling of failure uses an otherwise valid return value. The problem is that the caller of the subroutine cannot tell what the result means in this case.
Contents |
[edit] Example
The division operation yields a real number, but fails when the denominator is zero. If we were to write a function that performs division, we might choose to return 0 on this invalid input. But on most computer systems, dividing a small number by a very large one can yield 0 as well, due to rounding errors. This means there is no number we can return to uniquely signal attempted division by zero, since all real numbers are in the range of division.
[edit] Practical implications
In the case of division, a convention could be put into place requiring the caller to verify the validity of the input before calling the division function. This is undesirable for two reasons. First, it greatly encumbers all code that performs division. Second, it violates the important principle of encapsulation in programming, whereby treatment of concerns should be contained to one place. If we imagine a more complicated computation than division, the caller may not even know that invalid input is being handed to the target function; indeed, figuring out that the input is invalid may be as costly as performing the entire computation.
[edit] Solutions
The semipredicate problem is not universal among functions that can fail. If the function's range does not cover the entire data type defined for the function, a value known to be impossible under normal computation can be used. For example, consider the function index which takes a string and a substring, and returns the integer index of the substring in the main string. If the search fails, the function may be programmed to return -1 (or any other negative value), since this can never signify a successful result.
This solution has its problems, though; it overloads the natural meaning of a function with an arbitrary convention. First, the programmer must remember specific failure values for many functions, which of course cannot be identical if the functions have different domains. Second, a different implementation of the same function may choose to use a different failure value, resulting in possible bugs when programmers move from environment to environment. Third, as shown above, there may be no available failure value at all. Finally, if the failing function wishes to communicate useful information about why it had failed, one failure value is insufficient.
[edit] OUT variables
In many languages, including those with pointers and those which use pass by reference or an equivalent mechanism, the function can be redesigned to return a boolean value signalling success or failure, with a mutable value being passed to the function intended to store the actual result on success. If multiple error modes are possible, the function may instead of a boolean return an enumeration of results.
[edit] Error codes
Similar to an OUT variable, a global variable can store what error occurred (or simply whether an error occurred). For instance, if an error occurs, and is signaled (generally as above, by an illegal value like -1) the Unix errno variable is set to indicate which value occurred. Using a global has its usual drawbacks: thread safety becomes a concern, and if only one error global is used, its type must be wide enough to contain all interesting information about all possible errors in the system.
[edit] Exceptions
Exceptions are one widely used scheme for solving this problem (as well as others). An error condition is not considered a return value of the function at all; normal control flow is disrupted and explicit handling of the error takes place automatically. Exceptions also clear the calling code of clutter associated with checking return values after each call. They are an example of out of band signalling.
[edit] Expanding the type
In C, a common approach, when possible, is to use a data type deliberately wider than strictly needed by the function. For example, the standard function getchar() is defined with return type int and returns an unsigned char on success or the value EOF (defined by the system but outside the range (0, 255)) on the end of the input or a read error.
In PHP, the usual approach is to return false when the function call fails. For example, a numeric function would normally return a number (int or float), and zero might be a valid response; false is not. Similarly, a function that normally returns a string might sometimes return the empty string as a valid response, but return false on failure. This process of type-juggling necessitates care in testing the return value: use === [i.e. equal and of same type] rather than just == [i.e. equal, after automatic type-conversion]. It works only when the original function is not meant to return a boolean value, and still requires that information about the error be conveyed via other means.
In Haskell and other functional programming languages it is common to use a data type that is just as big as it needs to be to express any possible result. For example, we could write a division function that returned the type Maybe Real, and a getchar returning Either String Char. The first case has only one failure value, Nothing. In the second, a result is either some string with a descriptive error message, or a successfully read character. Haskell's type inference system helps ensure that the caller deal with possible errors. Since the error conditions become explicit in the function type, looking at its signature immediately tells the programmer how to treat errors. Monads keep the code tidy.
