An exception is simply a change in control flow and, if I'm not mistaken, this can be modeled easily in a purely functional system. I imagine a real system like Scheme, Racket, etc. would use call/cc, but I can best explain this with Continuation Passing Style[1].

Suppose you have some function like:

  (define (foo x y)
    (+ (/ x y) 1))

And you call it:

  > (* (foo 4 2) 3)
  9

the previous expression is equivalent to: ((4 / 2) + 1) * 3.

Now, suppose instead you call it with a bogus argument:

  > (* (foo 4 0) 3)
  Error: / expects the second argument to be non-zero!

Obviously, an error must be thrown because there is no reasonable answer to the quotient of 4/0.

Now, let me introduce CPS. To evaluate (+ (/ 4 2) 1) we must first evaluate (/ 4 2), then we can add 1 to the result. Written in a Scheme/Lisp language this looks like:

  (let ((result (/ 4 2)))
    (+ result 1))

The body of this let form is the "continuation" of (/ 4 2), which is a fancy way of saying it's what we should do next. One of the neat things about Scheme/Lisp is that we can write let expressions as function applications, like this:

  ((lambda (result) (+ result 1)) (/ 4 2))

So now we have a function which represents what we should do when we're done with (/ 4 2).

  k := (lambda (result) (+ result 1)) ; continuations are often called k

Now we are ready to add real power. Let us modify our call to foo as follows:

  ((lambda (result) (* result 3)) (foo 4 2))

But, why not let foo decide its own future by passing the continuation as an argument which foo can decide to use, or not!

  (foo 4 2 (lambda (result) (* result 3)))

Now, foo can say "Hey, I'm all done, I'm gonna call my continuation and keep evaluating!", or foo can say "No way man, shit hit the fan, we cannot continue evaluating!" This is how foo can be given that behavior:

  (define (foo x y k)
    (if (zero? y)
        "Uh-oh, you gave me a divisor of zero. I don't know what happens in black holes!"
        (k (+ (/ x y) 1))) ; I'll divide, then add, then give the result to my continuation

Furthermore, primitive operations like /, +, and * can be also be modified to accept continuations so the final program looks like:

  (define (foo x y k)
    (if (zero? y)
        "Uh-oh, you gave me a divisor of zero. I don't know what happens in black holes!"
        (/ x y (lambda (quotient)
                 (+ quotient 1 k)))))

  > (foo 4 2 (lambda (result) (* result 3)))
  9
  > (foo 4 0 (lambda (result) (* result 3)))
  "Uh-oh, you gave me a divisor of zero. I don't know what happens in black holes!"

I encourage you to experiment with turning simple arithmetic programs into CPS-style. It's really enlightening and let's you experiment with highly abnormal control flow (much more than just implementing exceptions). In Scheme, Racket, and languages like them, you can use call/cc and let/cc to have access to continuations without this laborious rewriting process. In fact, continuations are used to model the interactions of a web server written in Racket[2].

TL;DR: Exceptions can be modeled in a completely functional way, and the manner in which you do this opens up a really cool world of control flow mucking.

[1] http://en.wikipedia.org/wiki/Continuation-passing_style

[2] http://pre.racket-lang.org/docs/html/more/index.html#(part._...

edit: added a TL;DR and a reference to Racket's example of applying continuations to web server interactions

edit2: formatting

Synchronous exceptions are debatable. For example, a library function throwing an exception may require its callers to use "finally" clauses (or similar constructs in other languages) in order to maintain Exception Safety.

Also, a common property of "pure" functions is that it doesn't matter what order you call them in. But if you reorder calls to functions which can throw exceptions, you may get different results.

Asynchronous exceptions on the other hand are usually fine. For example, square-root library library functions aren't defined in terms of how much stack space is available on the machine; they're defined in terms of their argument.

Systems which have asynchronous exceptions ideally permit programs to handle them with code at carefully chosen places, rather than code spread around everywhere.

I don't think pure functions are supposed to throw exceptions, instead they should return error values.

Yes, but they usually use some form of monad to hold either an exception or a value.

The implementation of >>= (haskell calls it bind, buts it's useful to think of it like an overloaded ";" that takes a continuation as a parameter ) examines the return value and decided wether to run the normal path or the exception path...

It doesn't quite perform the same as exceptions do (it burdens both paths with if checks, whereas imperative exceptions only burden the error path)

But the code you write looks almost identical to exception handling code. It doesn't look like something using if checks.

The Maybe and Either type classes are typically used to model exceptions in Haskell.

There's actually some discussion about how to handle errors in Haskell. See: http://blog.ezyang.com/2011/08/8-ways-to-report-errors-in-ha...