Pick a markdown and code style:
Computer scientists are human and as such they make mistakes. Famous computer scientist Anthony Hoare made numerous important contributions including Quicksort and Monitors (as in semaphores and monitors). Yet he also admitted to making one horrible mistake. At a software conference in 2009, he apologized for inventing the null pointer. In his own words,
"I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years."
In the spirit of admitting mistakes, I confess that during most of the 25+ years that I've been teaching students how to program, I made little effort to properly teach error handling techniques. I've written many programs for teaching my classes but few of them handled errors properly. Take for example the following function (in Java, but it could be in many languages), which returned the largest value in an array of integers:
public static int largest(int[] A) {
int answer = A[0];
for(int i=1;i<A.length;i++)
if (A[i]>answer) answer = A[i];
return answer;
}
This function fails to handle multiple errors, one of them is when the
actual argument A is null. It's also possible to have a non-null but
zero-length array, in which case A[0] would throw and ArrayIndexOutofBounds
exception.
My excuses for writing such erroneous code are numerous:
Most academic computer scientists are not engineers and are concerned with more intellectually meaningful problems. Some academics would just say that the domain of the function is "restricted to non-empty arrays", as if that would make the problem go away.
It's already so hard to just teach students how to program and appreciate algorithmic principles such as time/space complexity. Adding error-handling code distracts from the main principles and makes teaching that much harder.
The error-handling paradigm employed by Java and many other languages, namely the raising and catching of exceptions, is not sufficient.
I was certainly not alone in making the first two excuses. The first I now find embarrassing; the second has some truth to it, but is still not justifiable. Only the third excuse is something I will still claim as valid today. More and more people are coming to realize that exceptions are not a good approach to error-handling.
In the event of an error when calling largest, Java will throw either a
NullPointerException or ArrayIndexOutOfBoundsException.
In a semester when I'm "good", I would add a line to the above function
if (A==null || A.length==0)
throw new RuntimeException("invalid input to function 'largest'");
Of course throwing an exception alone is not enough: they have to be caught. But where should the exception be caught? First of all, there is often no way to handle the exceptions locally. In this example, we cannot effectively add a try-catch block inside the function because it's still obliged to return an integer. But in the event of an empty array, any integer that it returns would surely be wrong. We have no choice but to differ error handling elsewhere. This is unfortunate because we want our function to encapsulate an algorithm. However, the error handling aspect of the algorithm escapes the encapsulation.
There is also no clear, general strategy as to where to catch the
exceptions externally. If we simply place a try-catch around every
call to the function, we may well run into the same problem again
(what to return from the calling function). There is another problem
with exceptions, which is that they're dynamically scoped. The
exception is caught by the nearest catch as determined at
runtime. In other words, if we write:
try {
if (/*some condition*/) f(); else g();
} catch (NullPointerException npe) { /* error handling code */ }
It is not possible to say with certainty that "any null pointer exception
that occurs inside the try block will be handled by the provided
error handling code." It may be the case that function f or g has
it's own exception handler. It depends on what happens at runtime. This
dynamic nature of exceptions makes it even harder for us to write code
that encapsulate error handling. Even if all exceptions are required to
be eventually caught (which subclasses of RuntimeException are not),
the problem of exception handling is a global, and not a local one.
And in a semester when I'm "bad", I'd just write
public static void main(String[] args) throws Exception
just to avoid having to catch any darn exception.
Whether it's Java or another language, the fact is that exceptions run contrary to the principles of abstraction and information hiding that we'd like to have in high-level programming. Of course it is possible to write error-free programs by catching and handling all exceptions in just the right places, but there are few general strategies on how to do so.
Even in situations where error-handling code with exceptions are not
difficult to write, the whole process of error-handling can still be
tedious, repetitive and distracting from the main task of implementing
an algorithm. As an academic computer scientist trained originally in
functional and logic programming, I'd much to prefer to write
"declarative" code. We call it "referential transparency". Suppose
we wish to apply a series of functions to a value, we'd like to just
write "h(g(f(x)))" or maybe "x.f().g().h()". But we often can't,
because f, for example, may return null or some invalid value not
acceptable to g. We have to break up the simple, declarative code and
add a bunch of if-else checks and try-catch blocks. Now the code
looks ... decidedly not declarative.
I'd like to tell my students "whenever you find yourself writing code that's tedious and repetitive, it's time to find a higher form of abstraction that will encapsulate the tediousness and allow us to write code that's simple and clear again." Using a variable instead of many constants, using a vector instead of many variables, writing a function that encapsulates an algorithm, writing a generic class are all examples of what I mean by this kind of abstraction.
A monad is an abstraction that applies to virtually all functions and types. Monads in programming originated from the study of category theory and its application to functional programming languages (e.g. Haskell and OCaml). Most programming languages including C++ and Java are acquiring more functional programming features.
Mathematically, a monad is a monoid in the category of endofunctors.
In the following definitions I will use both functional programming
syntax in the form of lambda expressions, as well as object-oriented
syntax in the form of method calls on objects. A lambda expression is
a nameless function that implements (in Java) an interface containing one
required function. For example, (x -> x*1.5) would implement
java.util.function.Function<Integer,Double>. The type of the lambda expression
is inferred from the interface that it instantiates.
A monad is defined by specifying a Kleisli Triple:
M that maps any type A to M<A>.unit from values of type A to values of type M<A>bind of type M<A> -> (A -> M<B>) -> M<B>. That is,
a function that takes an object of type M<A> and then a function from
A to M<B>, and returns an object of type M<B>.I will write applications of the bind combinator in the object-oriented style:
m.bind(f) to mean that bind is applied to m, then to the function f,
where f is usually a lambda expression. This will make the syntax of composing
a series of binds much cleaner: m.bind(f).bind(g).bind(h) ....
Such a triple must form a (non-commutative) monoid. The unit map
must be a left-identity of bind in the sense that x -> (unit(x).bind(f))
(unit composed with bind) is equivalent to f. It should also be possible
to see unit as a right-identity in the sense that a.bind(unit)
is equivalent to a. In full-scale functional programming languages
such as Haskell, bind is assigned an infix operator >>= so we can
write these laws more naturally as unit(x) >>= f = f(x) and a >>= unit = a. Furthermore, bind must be associative in the sense that
(a >>= f) >>= g = a >>= (x -> (f(x) >>= g))
In java-ish syntax, this means
a.bind(f).bind(g)is equivalent toa.bind(x -> f(x).bind(g)).
Associativity is an important component of referential transparency.
For example, unit(3).bind(x -> unit(x*0.5)) may return an object of
type M<Float> that's equivalent to unit(1.5).
In a particular monad, the bind operation may perform some additional work
before applying its functional argument to the encapsulated value, such
as checking if the value is null. In this way bind can encapsulate
"mundane" tasks such as error handling.
This may be a lot to take in for someone who's not familiar with functional programming, and certainly can be very confusing to intro-level students. There are various tutorials that try to explain monads in simplified terms. One such tutorial even claims that if you understood what monads are, you will lose the ability to explain it to others. I believe that the best way to teach the monad abstraction is to start with a very specific monad, which also happens to be how monads are used most often in programming: the encapsulation of error-handling.
A monad maps programs from an imperfect world, fraught with errors, to a more perfect world of mathematical functions that can be composed without obstruction.
Java is by now almost three decades old and so much of that language is based on exception handling and the possibility of pointers being null. null is the default value of any reference type. Perhaps no other popular language is more susceptible to the null pointer problem than Java. It will be difficult to completely avoid null, and exceptions, but modern java is beginning to offer some alternatives. It is be possible to define our own monadic type within java (and we will do so below) but Java offers the java.util.Optional type which is intended to be used with the interfaces of java.util.function.
Optional is the first component of the Kleisli triple: a type
constructor that maps any type T to type Optional<T>. The second
element, unit, comes in the form of the Optional.of function,
whereas bind is called Optional.flatMap. In addition to these,
there are a number of other functions on the Optional
class, such as map and orElse. Not all of these methods are
mathematically pure. The get method is definitely not. As the name
suggests, an object of type Optional<A> possibly holds a value of
type A. It is also possible that the object does not contain a
value. An "empty Optional" is formed with the method Optional.empty().
(Please note that the requirements of a Kleisli triple says nothing
about the contents of objects, only their types, so .empty is not
considered part of the triple but is specific to the Optional monad).
We can rewrite the "largest" function as follows:
public static Optional<Integer> largest(int[] A) {
if (A==null || A.length==0) return Optional.empty();
int answer = A[0];
for(int i=1;i<A.length;i++)
if (A[i]>answer) answer = A[i];
return Optional.of(answer);
}
Notice that the error handling code is local, independent of what
happens elsewhere. While the original largest function is not a
total function on all values of type int[], the new function is.
The function does not return an integer. If one tried to use the
return value as an integer, it will result in a compiler error.
Compiler errors are virtually zero-cost compared to runtime errors.
int[] A = {4,3,7,2};
int z = 3 * largest(new int[]{4,3,7,2}); // compiler error!
The programmer is forced to confront the fact that it's possible that
no value was returned by the function call. When using the value returned
by such a function, we must apply flatMap (bind) or a similar function
such as map. map is a specialized form of flatMap that
takes an Optional<A>, a function A -> B and
returns an Optional<B> object. a.map(f) is equivalent to
a.flatMap(x -> Optional.of(f(x))).
largest(new int[]{4,3,7,2})
.map(x -> 3 * x)
.ifPresent(x -> {System.out.println("Result = "+x);});
The key here is that .map will have no effect on the monad if it is
empty. It will not throw any exceptions; it would just return an
empty optional. If the array
passed to largest is null or of zero length, the code just does nothing.
This is because the bind (flatMap) of this monad checks if the value is
actually present before apply its function to it.
The .ifPresent method is only different from map in that the mapped
procedure does not return a value.
On the other hand, we can also write
var max =
Optional.of(new int[]{})
.flatMap(x->largest(x)) // java won't accept .flatMap(largest)
.orElseGet( () -> { //retrieves value or apply procedure to compute it
System.err.println("no largest value found, returning 0 as default");
return 0;
});
Which would set max to 0 in settings where such a default is appropriate.
As another sample application of Optional, we create an object adapter for
java.util.HashMap. The principle methods of this class are
put(key,value) and get(key). The get(key) function of HashMap
returns null if no value associated with the key is found. This fact
alone must be responsible for some of that billion dollars worth of
pain that Hoare initiated. Our object adapter will try to alleviate
the suffering.
import java.util.Optional;
import java.util.HashMap;
public class SafeHash<KT,VT> {
private HashMap<KT,VT> HM; // internal object to be adapted to new interface
public SafeHash() { HM = new HashMap<KT,VT>(); } // constructor
public int size() { return HM.size(); }
public Optional<VT> get(KT key) {
VT val = H.get(key); // can be null
if (val==null) return Optional.empty();
else return Optional.of(val);
}//get
public SafeHash<KT,VT> put(KT key, VT val) {
if (key!=null && val!=null) HM.put(key,val);
return this;
}//SafeHash returns 'this' so operations can be chained using .
}
We can apply the new class as follows:
var GPV = new SafeHash<String,Double>(); // grade-point value map
GPV.put("A", 4.0)
.put("B", 3.0)
.put("C", 2.0)
.put("D", 1.0)
.put("F", 0.0)
.get("E") // non-existent key, get empty Optional
.map(x -> x * 2.0) // still empty Optional, but no error
.ifPresent(x -> System.out.println("it's worth twice as much at Hofstra: "+x)).
Nothing will be printed by this code, but there is no null pointer exception,
which is what you would get with java.util.HashMap.get. Of course, you can
also avoid the exception by checking if (... == null), but the point is that
there is no requirement to write the if. The monadic approach, on the other
hand, leads you to write code that would not compile if the possibility of
errors are not taken into consideration.
As mentioned above, it's difficult to be rid of exceptions and null
pointers completely in a language like Java. Even with the Optional
class there are ways to circumvent the safety that monads promise.
Chief among these is the Optional.get method. Given a value x of
type Optional<A>, x.get() will return a value of type A. But if
there is no value to get, then an exception will be throw, and we're
back to where we started. An irresponsible programmer can call
.get() on any Optional-typed object without checking if the Optional
actually contains a value. The justification for .get() may be that
some programmers are just not comfortable with lambda expressions, and
will not be able to write any programs without it. But the potential
cost is that it could render the concept useless, and Optional.empty()
will suffer much of the same consequences as the null pointer. We can
at least experiment with trying to live without .get.
It is, however, possible to define our own Monad. In the following three classes
I define for Java the rough equivalent of the Result Monad found in Rust and
other languages. Yes, since embracing Rust much of my perspective on programming
have changed. But the issue of error handling and monads predates Rust and is
relevant to all programming languages. Result<A,B> is a disjunctive
type: it consists of either a value of type A or a value of type B. Usually,
A represent successful computations and B represent error objects, replacing
exception objects. In our examples, B is String, indicating some error message.
The monadic functors bind, map, etc take functions that instantiate
java.util.function interfaces designed for functional programming. In particular,
Function<A,B> represent functions A -> B. Typically, functions are
allowed to be contravariant in the domain (? super A) and covariant in the
codmain (? extends B).
Result<V,E> is implemented as a public abstract superclass with two
non-public subclasses, OkResult holding a value of type V and
ErrResult holding a value of type E. The constructors of the
subclasses are internal to the package. Publicly, Result objects
can only be created by calling the functions Ok and Err.
Besides the required monadic functions (unit is Ok), I've
added several more that might be useful, including match and match_do. Each of
these functors take two functions, to be applied to either an Ok value or an error
(Err) object. Not all methods are mathematically sound, such as map_mutate,
which changes an existing Result instead of creating a new one. It's added for
efficiency. Missing however, is the .get function of the Optional class. The
closest methods to .get are orElse, which requires a default value to be
specified in case there is nothing to get, and getOr, which requires a function
to be specified that computes a compatibly typed value from an error object.
Our implementation of this monad is purer then even Rust's, which contains a
.get()-like function (unwrap).
package ResultMonad;
import java.util.function.*;
public abstract class Result<V,E> {
// Abstract methods
public abstract boolean is_ok(); // contains V value if true
public abstract V orElse(V Default);
public abstract V getOr(Function<? super E,? extends V> errfun);
public abstract <U> Result<U,E> map(Function<? super V, ? extends U> f);
public abstract <U> Result<U,E> bind(Function<? super V, Result<U,E>> f);
public abstract void ifOk(Consumer<? super V> c);
public abstract <U> U match(Function<? super V, ? extends U> okfun,
Function<? super E, ? extends U> errfun);
public abstract void match_do(Consumer<? super V> okfun,
Consumer<? super E> errfun);
public abstract Result<V,E> map_mutate(Function<? super V,? extends V> mut);
// Non-abstract methods
public <U> Result<U,E> flatMap(Function<? super V, Result<U,E>> f) {
return bind(f);
} // flatMap is alias for bind
public static <A,B> Result<A,B> Ok(A v) {
return new OkResult<A,B>(v);
}//static, polymorphic Ok
public static <A,B> Result<A,B> Err(B e) {
return new ErrResult<A,B>(e);
}//static, polymorphic Err
// apply a function W*V -> U on two results
@SuppressWarnings("unchecked")
public <U,W> Result<U,E> chain(Result<W,E> other, BiFunction<? super V, ? super W, ? extends U> binop) {
return this.match(
_ok1 -> other.map(_ok2 -> binop.apply(_ok1,_ok2)),
_err -> (ErrResult<U,E>)this //new ErrResult<U,E>(_err)
);
}//chain
// if other result is Err, do not change current result
@SuppressWarnings("unchecked")
public <W> Result<V,E> if_and(Result<W,E> other, BiFunction<? super V, ? super W, ? extends V> binop) {
return other.match(
_ok -> this.map(_ok1 -> binop.apply(_ok1,_ok)),
_err -> this
);
}//if_and
// combine two results into one for a pair
public <U> Result<pair<V,U>,E> zip(Result<U,E> second) {
return this.bind(x -> second.bind(y -> Ok(new pair<V,U>(x,y))));
}//zip (non-abstract) function
// transform into java.util.Optional
public java.util.Optional<V> toOptional() {
return
this.match(_ok -> java.util.Optional.of(_ok), //ok
err -> java.util.Optional.empty() //err
);
}//toOptional
}//Result abstract class
class OkResult<V,E> extends Result<V,E>
{
private V val;
OkResult(V v) { // constructor accessible only inside package
if (v==null) throw new Error("null pointers not allowed in result");
val=v;
}
public V orElse(V Default) { return val; }
public V getOr(Function<? super E,? extends V> errfun) {
return val;
}
public boolean is_ok() {return true;}
public <U> Result<U,E> map(Function<? super V, ? extends U> f) {
return new OkResult<U,E>(f.apply(val));
}//map
public <U> Result<U,E> bind(Function<? super V, Result<U,E>> f) {
return f.apply(val);
} //bind (flatmap)
public void ifOk(Consumer<? super V> c) { c.accept(val); }
public <U> U match(Function<? super V, ? extends U> okfun,
Function<? super E, ? extends U> errfun) {
return okfun.apply(val);
}//match
public void match_do(Consumer<? super V> okfun,
Consumer<? super E> errfun) {
okfun.accept(val);
}//match_do
public Result<V,E> map_mutate(Function<? super V,? extends V> mut) {
val = mut.apply(val);
return this;
}
}//OkResult
@SuppressWarnings("unchecked")
class ErrResult<V,E> extends Result<V,E>
{
private E errobj;
ErrResult(E e) { errobj = e; }
public boolean is_ok() {return false;}
public V orElse(V Default) { return Default; }
public V getOr(Function<? super E,? extends V> errfun) {
return errfun.apply(errobj);
}
public <U> Result<U,E> map(Function<? super V, ? extends U> f) {
return (ErrResult<U,E>)this; //get compiler warning if not suppressed
//return new ErrResult<U,E>(errobj); //no warning but not efficient
}//map
public <U> Result<U,E> bind(Function<? super V, Result<U,E>> f) {
return (ErrResult<U,E>)this;
} //bind (flatmap)
public void ifOk(Consumer<? super V> c) {}
public <U> U match(Function<? super V, ? extends U> okfun,
Function<? super E, ? extends U> errfun) {
return errfun.apply(errobj);
}//match
public void match_do(Consumer<? super V> okfun,
Consumer<? super E> errfun) {
errfun.accept(errobj);
}//match_do
public Result<V,E> map_mutate(Function<? super V,? extends V> mut) {
return this;
}
}//ErrResult
Unlike an empty Optional object, an ErrResult object carries more information,
usually in the form of some error message. The following complete program
demonstrates the ResultMonad package. I've included two monadic functions,
safemod, which will not divide by zero, and an adapted version of java's
Integer.parseInt function, which is often used to process command-line arguments.
import ResultMonad.*;
public class resulttesting
{
// for convenience
static <A,B> Result<A,B> Ok(A x) { return Result.Ok(x); }
static <A,B> Result<A,B> Err(B x) { return Result.Err(x); }
static Result<Integer,String> safemod(int x, int y) {
if (y==0) return Err("division of "+x+" by zero");
else return Ok(x%y);
}
// adopt existing Java method to use Result instead of exceptions
static Result<Integer,String> parseint(String[] argv, int i) {
Result<Integer,String> answer = Err("invalid args to parseint");
if (argv==null || i<0 || i>=argv.length) return answer;
try {
answer = Ok(Integer.parseInt(argv[i]));
}
catch (Exception e) {
answer = Err("string "+argv[i]+" cannot be parsed to integer");
}
return answer;
}//parseint
public static void main(String[] args) {
parseint(args,0) // Ok or Err
.map(x -> x*x) // Ok if above is Ok, else Err
.map_mutate(x -> x-9) // Ok if above is Ok, else Err
//.bind(x -> safemod(100,x)) // Ok or Err
.match(
_ok -> safemod(100,_ok),
_err -> Err(_err+";\ncan't continue due to previous error")
)
.bind(x -> parseint(args,1).map(y -> (Integer)x-y))
.chain(parseint(args,1),
(x,y) -> x+y
)
.match_do(
_ok -> {
System.out.println("Result = "+ _ok);
}, // Ok case
_err -> {
System.out.println("ERROR: "+ _err);
} // Err case
); // match_do
}//main
}//resulttesting
// run java resulttesting
// java resulttesting 10 20
// java resulttesting 3
// java resulttesting abc
// The typecast (Integer)x is required because of possible contravariance
// in the domain of the function passed to bind.
As demonstrated, the monad can be implemented in any object oriented
programming language. Newer languages restrict where null is
allowed to appear. Kotlin's compiler even enforces that an object's
been checked to be null before allowing it to be accessed. C++ 2017
added an optional type, but the monadic functions that are equivalent
to bind, map, etc. are not available until C++ 2023 is released.
However, I've written an experimental
option_ptr class in
C++ that will try to combine the functionality of a monad with that of
a smart pointer. The implementation will not rely on virtual
functions like in Java in difference to the core C++ concept of Zero
Overhead Abstraction. Instead, the internal representation will use
nullptr, but it will be presented to the user as an empty optional
object.
There cannot be a "conclusion" to these thoughts because the final word on the effectiveness of the monadic approach to error-handling is yet to be written. We cannot answer the question academically: it would have to come from the cumulative experiences of the software industry in the coming decades. It is a fact that the trend in programming language development is turning against exception-handling and becoming more functionally oriented. The success of new languages such as Rust, which embraces the approach we espoused here, gives us hope that we're on the right path.
From a pedagogical perspective, yes there's a lot for programmers to learn in order to apply this new approach to handling errors. But the learning curve would not be as steep once a series of good examples becomes available. These examples will form a new set of design patterns for the composition of error-free programs.
In the Spring semester of 2023, I for the first time have abandoned exceptions in teaching an intermediate level course on data structures and object oriented programming in Java. It is always difficult to teach higher forms of abstraction. Many students struggle with understanding and appreciating the simplest form of functional abstraction. It gets progressively more difficult as we introduce recursive functions, second-order functions, interfaces and abstract classes, etc. Monads are yet another level of abstraction. Yes, it makes teaching even more difficult, but what choice do we have? We cannot continue to preach to our students a pretty picture of abstract data types and encapsulated algorithms when error handling doesn't fit the picture. Monads allow us to return to the pulpit. The effort that we will spend teaching, and the effort that students will spend on learning these advanced programming techniques are still far less costly than another billion dollars worth of pain.