Semipredicate problem
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.
, 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. However, if the numerator
is 0, the result is 0 too. Also, even if a nonzero numerator is required, 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.
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.
defined for the function, a value known to be impossible under normal computation can be used. For example, consider the function
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, if the failing function wishes to communicate useful information about why it had failed, one failure value is insufficient. Fourth, a signed integer halves the possible index range to be able to store the sign bit
.
Various techniques for returning multiple values include:
can store what error occurred (or simply whether an error occurred).
For instance, if an error occurs, and is signalled (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.
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 clutter associated with checking return values after each call. They are an example of out of band signalling.
, a common approach, when possible, is to use a data type deliberately wider than strictly needed by the function. For example, the standard function
s, such as PHP
and Lisp, the usual approach is to return "false", "none" or "null" when the function call fails. This works by returning a different type to the normal return type (thus expanding the type). It is a dynamically-typed equivalent to returning a null pointer.
For example, a numeric function normally returns a number (int or float), and while 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: e.g. in PHP, 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.
, which has only one failure value,
: 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. In addition, tagged unions and option types form monads
when endowed with appropriate functions: this may be used to keep the code tidy by automatically propagating unhandled error conditions.
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, a semipredicate problem occurs when a subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
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.
Example
ThedivisionDivision (mathematics)right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
operation yields a real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
, but fails when the denominator is zero
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
. If we were to write a function that performs division, we might choose to return 0 on this invalid input. However, if the numerator
Fraction (mathematics)
A fraction represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, we specify how many parts of a certain size there are, for example, one-half, five-eighths and three-quarters.A common or "vulgar" fraction, such as 1/2, 5/8, 3/4, etc., consists...
is 0, the result is 0 too. Also, even if a nonzero numerator is required, dividing a small number by a very large one can yield 0 as well, due to rounding errors
Round-off error
A round-off error, also called rounding error, is the difference between the calculated approximation of a number and its exact mathematical value. Numerical analysis specifically tries to estimate this error when using approximation equations and/or algorithms, especially when using finitely many...
. This means there is no number we can return to uniquely signal attempted division by zero, since all real numbers are in the range
Range (mathematics)
In mathematics, the range of a function refers to either the codomain or the image of the function, depending upon usage. This ambiguity is illustrated by the function f that maps real numbers to real numbers with f = x^2. Some books say that range of this function is its codomain, the set of all...
of division.
Practical implications
In the case of division, a conventionConvention (norm)
A convention is a set of agreed, stipulated or generally accepted standards, norms, social norms or criteria, often taking the form of a custom....
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.
Solutions
The semipredicate problem is not universal among functions that can fail. If the function's range does not cover the entire data typeData type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
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 integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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
Implementation
Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.-Computer Science:...
of the same function may choose to use a different failure value, resulting in possible bugs
Software bug
A software bug is the common term used to describe an error, flaw, mistake, failure, or fault in a computer program or system that produces an incorrect or unexpected result, or causes it to behave in unintended ways. Most bugs arise from mistakes and errors made by people in either a program's...
when programmers move from environment to environment. Third, if the failing function wishes to communicate useful information about why it had failed, one failure value is insufficient. Fourth, a signed integer halves the possible index range to be able to store the sign bit
Sign bit
In computer science, the sign bit is a bit in a computer numbering format that indicates the sign of a number. In IEEE format, the sign bit is the leftmost bit...
.
Multivalued return
Many languages allow, through one mechanism or another, a function to return multiple values. If this is available, the function can be redesigned to return a boolean value signalling success or failure, in addition to its primary return value. If multiple error modes are possible, the function may instead of a boolean return an enumeration of error codes.Various techniques for returning multiple values include:
- Returning a tupleTupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
of values. - Languages with pointers, and those that allow pass by reference, or an equivalent mechanism, can allow for multivalued return by designating some parameters as "out" arguments. In this case, the function could just return the error value, with a mutable value being passed to the function intended to store the actual result upon success.
- Some logic programmingLogic programmingLogic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
languages don't even have specific "return" values, returning all data through "out" arguments.
Global exit-status variable
Similar to an "out" argument, a global variableGlobal variable
In computer programming, a global variable is a variable that is accessible in every scope . Interaction mechanisms with global variables are called global environment mechanisms...
can store what error occurred (or simply whether an error occurred).
For instance, if an error occurs, and is signalled (generally as above, by an illegal value like -1)
the Unix errno
Error code
In computer programming, error codes are enumerated messages that correspond to faults in a specific software application. They are typically used to identify faulty hardware, software, or incorrect user input in programming languages that lack exception handling, although they are sometimes also...
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.
Exceptions
ExceptionsException handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
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
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
is disrupted and explicit handling of the error takes place automatically. Exceptions also clear the clutter associated with checking return values after each call. They are an example of out of band signalling.
Manually created hybrid types
In CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, 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 (implementation defined but outside the range [0, 255]) on the end of the input or a read error.Nullable reference-types
In languages with pointers or references, one solution is to return a pointer to a value, rather than the value itself. This return pointer can then be NULL, to indicate an error. This approach may cause some overhead, and is typically suited to functions that return a pointer anyway. Although this prevents the referenced value to be allocated at address 0, which is usually defined as NULL.Implicitly hybrid types
In scripting languageScripting language
A scripting language, script language, or extension language is a programming language that allows control of one or more applications. "Scripts" are distinct from the core code of the application, as they are usually written in a different language and are often created or at least modified by the...
s, such as PHP
PHP
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
and Lisp, the usual approach is to return "false", "none" or "null" when the function call fails. This works by returning a different type to the normal return type (thus expanding the type). It is a dynamically-typed equivalent to returning a null pointer.
For example, a numeric function normally returns a number (int or float), and while 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: e.g. in PHP, 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.
Explicitly hybrid types
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 typeMaybe Real, and a getchar returning Either String Char. The first is an option typeOption type
In programming languages and type theory, an option type or maybe type is a polymorphic type that represents encapsulation of an optional value; e.g. it is used as the return type of functions which may or may not return a meaningful value when they're applied...
, which has only one failure value,
Nothing. The second case is a tagged unionTagged union
In computer science, a tagged union, also called a variant, variant record, discriminated union, or disjoint union, is a data structure used to hold a value that could take on several different, but fixed types. Only one of the types can be in use at any one time, and a tag field explicitly...
: a result is either some string with a descriptive error message, or a successfully read character. Haskell's type inference
Type inference
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
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. In addition, tagged unions and option types form monads
Monads in functional programming
In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model...
when endowed with appropriate functions: this may be used to keep the code tidy by automatically propagating unhandled error conditions.