Lambda the Ultimate

I can't really speak to exceptions in FP langs, but I would disagree that they are bad in imperative langs. Java actually distinguishes between exceptions and errors, and out-of-memory is an error, whilst stream-not-ready is merely an exception. Errors propagate without mention in exception specifications, but I think this is really a design mistake. The reason you want conformity when it comes to exceptions is that if you try to be too smart at one level, you reduce what code can do at a higher level. You throw an exception when it is impossible for you to fulfill a contract. If you are a socket.read() method, and you promise to always return a non-null value that is the result of reading the socket, then you cannot fulfill that promise if the socket is not ready to be read. It is the caller's responsibility to decide whether that exception should be caught or passed. For some callers, such an exception is benign and can be silently caught and ignored or the operation retried. For others, the exception is a more serious problem that should be propagated up the call stack. In Java, you can be fairly discriminating in your exception catching by checking for errors vs. exceptions and by inspecting the results of getCause() [recursively].

on Checked Exceptions.

Personally, I like SOME/NONE of ML or MAYBE of Haskell. Forces one to handle No Value Returned in a much more methodical manner. Exceptions should be reserved for exceptional situations.

Personally, I like SOME/NONE of ML or MAYBE of Haskell. Forces one to handle No Value Returned in a much more methodical manner.

Absolutely. This is one thing I hate about writing robust error handling code in languages like C and C++, especially when you have to deal with a slew of libraries. People tend to use an ad hoc mix of out-of-band signalling (e.g. returning -1), boolean success/failure signalling (with more detailed error information available via a global variable or function), full error information in the return value, etc. It's a mess. If you have to deal with this using only standard C constructs I much prefer the Win32-style discipline where most functions that can fail return HRESULTs and use pointer parameters for returning values. At least it's consistent.

If you have to use C, you don't really have an exception system to use, do you? And if you can write in C++, then why not wrap all that low-level reporting in exceptions to provide the uniform interface? There's a world of difference between C and C++.

If you have to use C, you don't really have an exception system to use, do you? And if you can write in C++, then why not wrap all that low-level reporting in exceptions to provide the uniform interface?

It's not just a matter of wrapping "all that low-level reporting in exceptions to provide the uniform interface". Handling errors via exceptions is a completely different paradigm and in my experience (and that of many others) it makes it very hard to write robust code in the face of errors.

I think one part of the problem is simply that it's hard to look at a piece of code in a system that uses exception handling and tell whether it handles errors correctly. There tends to be no visible difference between a piece of code that intentionally lets an exception through, and a piece of code that was not written with proper handling of errors in mind. With the "old school" way of handling errors, it's very obvious when a piece of code doesn't handle errors: it calls a potentially failing function and doesn't check the return value (or whatever other error signalling mechanism is used).

The other, perhaps more serious, part of the problem is exception safety. Almost entire books have been written about this subject (Sutter's Exceptional C++ and More Exceptional C++ dedicate large parts to exception safety). There seem to be very few programmers who know how to write exception safe code at all well. On the other hand, the style of old school error handling tends to force the programmer to think about clean-up (and if he doesn't it is usually clear from inspection of the code that something was left out) whereas with exception handling it's a lot easier for such things to slip through the cracks.

There's a world of difference between C and C++.

No kidding? :)

I agree that error handling is a very difficult problem, which is why many books are written on it. I disagree that exception handling is intrinsically harder than error handling in general, and I especially disagree that error handling via status checking is easier than error handling via exceptions. The fact is, it is very easy to check a status and have error-unsafe code.

Ideally, programmers would always provide the basic guarantee (as defined by Abrahams here), and note in comments when a function provides the strong or nothrow guarantee. The nothrow guarantee is usually the easiest to determine, unless a function calls into a lot of poorly documented libraries. The strong guarantee follows a characteristic pattern that can be analyzed algorithmically. Oddly enough, the basic guarantee can be the most difficult to analyze, because you have to know the invariants which must hold throughout the function, and if it's a member function, that means you have to know a lot about the class.

But I'm fairly confident that analyzing error correctness in the context of exceptions is more robust than with an ad-hoc context, or even with status codes. Haskell's Maybe preserves locality of flow control, but forces you to propagate Maybe if you need errors to move up layers of code (which is the primary defect of status codes).

But I'm fairly confident that analyzing error correctness in the context of exceptions is more robust than with an ad-hoc context, or even with status codes. Haskell's Maybe preserves locality of flow control, but forces you to propagate Maybe if you need errors to move up layers of code (which is the primary defect of status codes).

While this is strictly true, Maybe also doubles as a monad that'll do the propagation for you. It only really becomes a problem if you find yourself needing to propagate errors through a large chunk of non-monadic code.

How much of that preference is due to the FPness of ML and Haskell, and how much of that is due to languages in general? I don't see how MAYBE is any different than a status code, and I'm sure there's many prior threads on exceptions vs. status codes.

I don't see how MAYBE is any different than a status code

The user of the value of type Maybe a is forced to at least do case analysis if he needs a value of type a. This gives him a chance to think about handling this special value. In other words, the language prevents the programmer from (incorrectly) proving that not(1 + a) == not(a) (pardon my continuation-biased logic).

Status codes are just peripheral information that has no identifiable correlation with the presence or absence of a value. MAYBE identifies an intersection Type wherein a value may or may not be present. Just as an Exception is said to be part of the Interface, MAYBE identifies the lack of a returned value as part of the Type.

It's not really that hard to encode a MAYBE constuct in an OOP language - just wrap the result in a MAYBE class instance that acts as a container for the return value. Does add overhead in that you then have to wrap and then unwrap the return result. And Pattern Matching of FP's makes this process fairly painless (and standard). But I don't think such a pattern to handling non-values should be confined to any particular paradigm.

David, do you ever return a null pointer from your functions in C++, to indicate conditions such as that a value was not found, for example? If so, you're relying on an optional value type (like Maybe). It's useful because (as has been pointed out) it extends the type you're dealing with to include a value which means "no value", without having to reserve a special value of the underlying type, and in such a way that the type system can distinguish code which deals with optional values from code which doesn't, and enforce correct usage.

For example, if you call a function which returns an optional value, and you try to return it to a caller that always expects to receive a valid value, you get a compile-time error. You don't get this with status codes, so that's one important way that optional values are different from status codes.

Of course, the C++ null pointer example is a degenerate case because C++ pointer types include a null value whether you want it or not — there's no type in C++ representing a pointer that can't be null. So you've only experienced part of the benefit of optional types by using null pointers in C++, because you don't get that static-checking benefit.

As Chris touched on, you can implement optional values in any language that lets you create structures, even C: a tagged union type is all you need. However, C/C++ programs don't usually do this, because they don't have the kind of type-based pattern matching that makes it so natural to use such types. It's not necessarily an "FPness" issue, though, except in the sense that FP languages have more disciplined type systems and better support for manipulating types. But the feature could be supported perfectly well in an imperative language. (The real problem with such categorizations is that distinguishing languages on a single dimension, functional vs. imperative, is too simplistic.)

This is all somewhat orthogonal to the issue of exceptions vs. status codes: if you examine those discussions, part of what they're dealing with is the weakness of status codes as usually implemented in mainstream languages. One of those weaknesses arises from the fact many kinds of status codes are out-of-band values being encoded within an existing type, in a way that the type system cannot possibly be aware of. Much of what you thought you knew about the subject changes in the context of languages which make it easy to deal with the issue in a more principled way.

BTW, Pierce's book TAPL is a good reference on the general subject, but failing that, working through one of the tutorials on ML or Haskell is probably a good idea. The only danger is that you might catch functional programming cooties and starting turning off all your C++ buddies when you start dissing the C++ type system. I know, it happened to me.

C++ references are non-null, except when they aren't:

int *p = new int;
int &q = *p;
delete p; // q is now invalid

I distinguish between returning a special value as part of a function's contract, and returning a special value to indicate the function failed. For instance, dynamic_cast<> returns null when the argument cannot be down-casted to the specified type. Since the whole point of dynamic_cast<> is to determine whether the argument is down-castable, it is part of the operator's contract to return null when it is not. In this case, null is a special value, not a status code. Now if the argument pointed to something that wasn't a valid C++ object, and dynamic_cast<> were able to detect that, I would be very upset if it quietly returned null instead of throwing an exception, because returning null on invalid pointer references is *not* part of the defined interface of dynamic_cast<> (and I would think that it's a poorly defined interface if it were).

Yes, even the STL returns std::pair<T, bool> for insert() operations, and Boost has Boost.Optional, which is exactly the same as Maybe, semantically speaking. The use cases for those mechanisms are not lost on me. What is lost on me is using Boost.Optional as a return value any time a function can fail. If I saw someone coding that way, I would be strongly tempted to lash them with an enormous wet noodle.

Now I argue that the reason Maybe is natural for FP coders is because they really *really* like their functions to return, and especially to return a value. And Maybe allows both of those conditions to always hold. And perhaps within FP langs, that is the better way to do it (given all the complications that come with exception handling). But in imperative languages like C++ and Java, there is no such pressure to always return a value, or even to always return. In that case, I think it is much better to write your code as if it always succeeds, but still does The Right Thing when it does not. That means that when I write:

  int foo(int y)
  {
    int* x = new int(42);
    int z = *x + y;
    delete x;
    return z;
  }

I want to assume that the allocation will succeed, and if it doesn't, then I will put the exception handling code where *I* think it should go, rather than where the language thinks it should go (spelling Boost.Optional as Maybe):

  int foo(int y)
  {
    Maybe<int*> x = new int(42);
    if (!x) { std::err 

Or even worse, the viral Maybe:
  Maybe<int> foo(int y)
  {
    Maybe<int*> x = new int(42);
    Maybe<int> z = !x ? Maybe<int>() : **x + y;
    if (!!x) delete *x;
    return z;
  }

Now you tell me which is the best version.

I guess I wasn't clear, I'm not suggesting that optional values be used for all exceptional cases. That's why I said the issue of optional values was somewhat orthogonal to that of exceptions. There are appropriate places for both. In your examples, I don't think any sane FPer would suggest using an optional value for that kind of failure condition. Again, I recommend working through an FP language tutorial to get a better sense for things like this.

Functional languages like the ML family support exceptions just fine, and it makes sense to use them to handle failure conditions. However, there are many other cases in which having the ability to define and use an optional value type is very useful.

Boost's optional type demonstrates the point that any language with structures can implement optional values, but it also demonstrates that this doesn't necessarily make the approach very usable. For a start, you have to spell out the type explicitly wherever you use it, and the type is not just called "Maybe", it's called e.g. "boost::optional<int>". In FP languages, the equivalent type would be something like "Maybe int" or "int option", but you almost never have to spell it out explicitly: instead, a function which returns a value "Maybe x" is automatically inferred to have type like "Maybe X" (where X is whatever the type of x is), both in its definition and at its call sites.

Features like this, and built in pattern matching (not faked with e.g. operator overloading), make using option types very natural and consistent. It's a little like the difference between doing OO in C and doing it in C++: it's easier and more natural in C++ because the language has explicit support for it.

A big reason you see so many different ways of handling optional/special values in a language like C++ is because it doesn't provide a really natural, integrated way to handle the issue. That leads to a lack of integration between disparate components which Per Vognsen also mentioned: null pointers, std::pair, boost::optional, -1, HRESULT, etc. etc. It can also create a temptation to use some other approach like exceptions, when an optional value would otherwise make more sense.

I don't mind spelling out types in C++ code, because I'm used to it, and it's a good sanity check when looking at other people's code. Type inference is nice, but makes it harder to tell if someone else knows what they're talking about without running the code through the compiler. As far as the variability in optional value handling, I'd say it only has partially to do with a "natural" support mechanism. I'd say it has as much to do with two other factors: language evolution and abstraction cost. The fact that C++ inherits C's codebase implies that it also inherits coding conventions that are three decades old. That isn't C++'s fault outside of the fact that it chose to be compatible with C. That's where you get most of the status code type values.

When it comes to "modern" approaches like std::pair<> and Boost.Optional vs., say, null pointers, there is some conscious computation of the abstraction cost involved. Boost.Optional should have little runtime overhead, and yet it will probably be non-zero on most platforms. But then there is also the compile-time overhead, which, insignificant in the early days of C++, is now a serious issue. So most C++ programmers would agree that Boost.Optional ought to be the de facto way to deal with optional values, as much so perhaps as "Maybe", but the C++ committee didn't have the luxury of standardizing it when the STL was being considered for inclusion in the standard, which is why we have std::pair<> instead.

So I would say that it is the evolution of technology, and not necessarily a technical lack in this particular instance. Pattern matching is nice, but it's a different way of doing things which doesn't necessarily translate well to the imperative world. It's entirely possible that Boost.Optional will be considered for future inclusion in the SCL, thus giving it the same status as Maybe. It will always be more verbose because C++ is more verbose, but don't assume that because Haskell got it right the first time that it's because it provides a better builtin mechanism. Haskell is a much newer language and enjoys the benefit of much hindsight. Consider that Haskell doesn't really let you make the choice between a super-fast null-pointer check vs. a high-level mechanism that carries around a certain amount of abstraction baggage. A good deal of the redundancy in C++ is due to implementation choices such as these. And I consider that the language's primary strength, not a weakness.

I don't mind spelling out types in C++ code, because I'm used to it, and it's a good sanity check when looking at other people's code. Type inference is nice, but makes it harder to tell if someone else knows what they're talking about without running the code through the compiler.

I don't know about the experienced FP people, but by my limited experience, Haskell code is exceptionally (no pun intended) easy to read, even without type annotations. The type annotations do make it easier, however. I think there is an issue with the differring idea of "function" between the imperative people and the FP world: in FP, a function is small, and does one thing well. It usually does it perfectly. In most imperative languages, you can't abstract the pattern away easily enough to make "trivial" patterns worth the effort.

Haskell is a much newer language and enjoys the benefit of much hindsight.

Sure, Haskell is relatively young when it comes to programming languages, but Haskell isn't the only FP language. ML (and many other FP languages) were around at the time C++ was born.

Haskell doesn't really let you make the choice between a super-fast null-pointer check vs. a high-level mechanism that carries around a certain amount of abstraction baggage

I'm not sure what you mean here. Care to elaborate?

Haskell doesn't really let you make the choice between a super-fast null-pointer check vs. a high-level mechanism that carries around a certain amount of abstraction baggage

I'm not sure what you mean here. Care to elaborate?

Ok, I think I can make the case that Maybe is more expensive than a simple comparison and direct function call, but probably not that the direct route is not possible in Haskell. However, I would be terribly curious to see how Haskell does compile my C++ version to assembly, and how it compares to the C++ version.

No, it isn't. Pattern matching can be (and is) compiled to efficient code by modern FP compilers. In the case of Maybe, which has two constructors, one nullary and the other unary, matching can be done using a single comparison and a conditional jump. The same goes for the representation of Maybe values. In the general case, Maybe can be implemented as a pointer: Nothing = null pointer, Just x = pointer to x. In specific cases a modern compiler ahould even be able to eliminate the pointer (and heap allocation) away.

Pattern matching is nice, but it's a different way of doing things which doesn't necessarily translate well to the imperative world.

It translates fine, all it takes is a tagged union type. It'd even make a sensible extension to C++.

A spoonful of sugar might not cure the viral Maybe's, but it does makes the medicine go down better. Haskell has better sugar and better abstractions (not that you couldn't do something similar in C++)...

import Monad  --for liftM2

main = print $ foo 9

new = Just

foo  y = do x = \x -> return $ x + y

-- ...getting nicer...
foo3 y = liftM2 (+) (new 42) (Just y)

-- ...My personal favorite...
instance Num a => Num (Maybe a) where
    (+) = liftM2 (+)

foo4 y = new 42 + (Just y)

Doesn't it say something when one of the monad tutorials uses the case of Maybe propagation to motivate the use of monads? If Maybe is so great, why do we need the aid of the most non-intuitive language device ever invented?

So, how would you implement that example in C++? Exceptions for when a sheep is missing a parent? (I'm curious, not arguing, I swear ;)

In this case, the nature of the problem defines not having a parent as an expected condition, so I would simply assign this condition the value of null, and traffic in pointers:

class sheep
{
public:
    sheep(sheep* mother, sheep* father)
        : mother_(mother), father_(father) { }
    friend sheep* mother(sheep* s) { return s ? s->mother_ : 0; }
    friend sheep* father(sheep* s) { return s ? s->father_ : 0; }
private:
    sheep* mother_;
    sheep* father_;
};

sheep* maternal_grandmother(sheep* s)
{
    return mother(mother(s));
}

sheep* greatgreatgreatgrandfather(sheep* s)
{
    return father(father(mother(father(mother(s)))));
}

Look, ma! No monads! Yes, a monad would also have been a viable solution here. But it wouldn't have been natural. Now granted, I cheated by moving mother() and father() out of the class, and the monad combines them into one function. But that's a small optimization compared to the fact that my solution scales just as well as the monadic one.

You changed the domain of the functions. Here is an equivalent example in SML:

signature SHEEP =
   sig
      type t
      val mother : t option -> t option
      val father : t option -> t option
   end

functor SheepAlgs (S : SHEEP) =
   struct
      open S
      val maternal_grandmother =
          mother o mother
      val greatgreatgreatgrandfather =
          father o father o mother o father o mother
   end

(The module stuff (signature and functor) is there just so that the code can be compiled without actually implementing the functions mother and father. Also, maybe is spelled option in SML.)

OK, now I'm arguing. :) I thought you might be suggesting that there was some other way to handle the Sheep problem, without using optional values, and I was curious about what you had in mind. You implied that you didn't think Maybe was so great, and then turned around and used it (in the form of a null pointer) in your example.

The Sheep example is using a stripped-down example just to illustrate a point, that you can use monads to transparently propagate things behind the scenes, improving abstraction and modularity. As your C++ and Vesa's example show, in such a simple case you can redesign it cleanly without monads, but the point is that there are cases where the usage pattern in the monad example arise and can't be so easily designed out.

So, I submit that there's certainly no indictment of optional values or Maybe here, nor of monads. Perhaps the tutorial should make it clearer that the example is a bit too simple to illustrate why you would want to structure a program like that in the first place.

My objection isn't to Maybe, as it should be clear to any programmer that optional values have a time and a place. My objection is to using Maybe as an error propagation device. I don't think the sheep example is such a case, but it illustrates exactly what happens when you try it. You end up encoding the failure modes into the types of functions and parameters, which is a terrible way to program, IMO. Most of the code we write should not care how or when code below it fails, nor should it even be aware of all the ways in which it can fail. When it does, the code becomes brittle, etc. All the arguments against status codes apply. My comment was on the observation that propagating status codes through Maybe requires additional work, and I don't think that work is justified if you have any decent alternatives (like *ahem* exceptions). Whether reading from a device and receiving no data is an error or a normal result is a matter of plenty of debate. I would tend to say that it's not an error, unless you have a very specially defined device (like, say, an RNG that isn't supposed to fail). But if you go from the callee using Maybe to signal no data to the call stack using Maybe to signal unexpected-read-error, that's where I have to object, monads or no.

There's also a time and place for handling exceptions in the form of continuations (try/catch). Problem is that handling all forms of conditions as continuations leads to its own set of problems.

Since we've been discussing relational databases, take the case of null values returned by a query. Should a null value be handled as an exception? Well, in some instances you would and in some instances you wouldn't. For example, if you knew the database had a NOT NULL referential constraint on the data, then you'd probably treat it as an Error (as opposed to exception). If the column allows NULLs, then you'd probably check to see if it were null, thus pre-empting the error. Or you may just want to pass that decision on up the call stack (without using exception signaling, or continuations) - and as part of that process you may not want to introduce a type error.

My objection is to using Maybe as an error propagation device.

You end up encoding the failure modes into the types of functions and parameters, which is a terrible way to program, IMO.

I think that you probably mean that then changes to an implementation of a module could require (otherwise unnecessary) changes to the interface (or signature) of the module. This is a valid concern in some cases, but not universally.

My objection is to using Maybe as an error propagation device.

Right, and I've already acknowledged that there's a place for exceptions, for handling failure conditions. But if you "don't think the Sheep example is such a case", then the question I asked re the monad issue still stands, how do you deal with such cases if they arise?

Assume, for example, that you've used boost::optional in a case where it really seems appropriate to use an optional value, and then down the road you find yourself needing to write code like that in the Sheep example. Do you redesign your program? What's wrong with the monad solution in such a case?

I don't think the sheep example is such a case, but it illustrates exactly what happens when you try it.

It illustrates something that can happen with optional values in general, and you've acknowledged that optional values have a place. Where does that leave you with respect to dealing with such code?

The either type (generic sum type) (in ML syntax)

datatype ('a, 'b) either = LEFT of 'a | RIGHT of 'b

provides a bigger hammer for dealing with errors in FP languages. First of all, you can represent option (maybe) using either:

type 'a option = ('a, unit) either

Using either you can express a function that either returns a value or an error code.