Bottom Propagation

BottomType is a value made popular in functional programming circles where it is often written as , an upside-down T. Like nil, bottom represents almost no information other than its presence. Unlike nil, functions applied to bottom are not in error, though they are likely to also yield bottom.

The name bottom suggests the minimal energy/entropy state of a calculation that has reached bottom. It doesn't imply that there is anything particularly wrong with this situation.

JohnIsner points out ...

---

I have seen Bottom Propagation used in the design of complex container classes in C++, and I have often used it myself. Consider a Multimap<T,U>, which maps a key of type T to zero or more pointers of type U*. Bottom Propagation lets the client chain operations like this:

        MultiMap?<int,int> m;
        ...
        int* ip = m.row(4).iter().first();

Without Bottom Propagation, the client is forced to hold intermediate results in temporaries and test them:

        MultiMapRow?<int,int> r = m.row(4);
        int* ip = 0;

        if( r ){
                MultiMapIter?<int,int> it = r.iter();

                if(it){
                        ip = it.next();  
                }
        }
        if( ip ){
                // success
        }else{
                // failure
        }

In this code, it is obvious that the client doesn't care WHY the operation failed, but only whether it succeeded or not (it could fail because the MultiMap? has no key of 4 OR because the set of pointers associated with key 4 is empty). When this is the case, as I believe it often is in real programs, Bottom Propagation leads to much cleaner code. Note that with Bottom Propagation, the long-winded version is also perfectly legal.

---

IeeeSevenFiftyFour Floating Point specifies values called "quiet NaNs" [NotaNumber], that behave like bottom. (All mathematical operations that have NotaNumber as an argument will return NotaNumber; including tests for equality and the like--NotaNumber represents an undefined or indeterminate result; not a specific singularity which is discrete from all other possible numbers. The one exception is that IEEE 754 does provide an "is this NaN" operation which returns true or false depending on whether or not the argument is NotaNumber.)

Bottom is similar to ExceptionalValue, except that the latter can carry an explanation making it not quite bottom.

Bottom is similar to NullObject, except that the latter participates in computations in small but meaningful ways while bottom is happy to simply propagate.

Bottom is similar to InfiniteRecursion, because if you really need to know the value of it, it will take a long time to get it.

Bottom can be viewed as the "return value" of a function (or continuation) that never returns.

Bottom is semantically identical to the 'empty' relation of any multi-function in relational programming (and its smarter brothers, constraint and logic programming, where expressions may evaluate to more than one solution). Exceptions and timeouts and proof can abort search paths and result in the empty relation. This result propagates if nothing is specified for continuing computation in the event no solution is found.

---

The Maybe Monad in Haskell can work like this. If any intermediate value in the computation evaluates to Nothing, then the whole computation evaluates to Nothing and nothing further is evaluated. (To avoid potential confusion, note that the 'Maybe Monad' isn't the Maybe abstract type; rather, it is built atop it.)

The List Monad in Haskell can also work like this - acting as 'bottom' in the 'empty relation' sense. This also propagates (mapping operations unto empty lists aborts in exactly the same manner as a match against 'Nothing'). The difference here is that the Maybe Monad allows for zero or one answers, whereas the List Monad allows for zero or one or infinity answers.

---

CategoryException