Being responsible when using tail recursion and exceptions

One very popular habit in F# is tail recursion. Tail recursion allows you to recurse without worrying about stack overflow. But there is a very dangerous problem – infinite recursion.

// This cannot go into an infinite recursion because of
//     a very important controller: stack size.
let rec ``with stack overflow`` x =
    1L + (``with stack overflow`` x)

// Throws StackOverflowException
``with stack overflow`` 0L


// This will go into an infinite recursion because there
//     there is no limiting factor.
let rec ``without stack overflow`` x =
    ``without stack overflow`` x

// Does not return
(``without stack overflow`` : int64 -> int64) 0L


// This is a definition of a new exception type:
/// Infinite Recursion Exception
type InfiniteRecursionException() =
    inherit exn()


// This will not go into an infinite recursion because of
//     a limiting factor that we chose. This does not only
//     allow us to set a limit at our point, but also will
//     emit a more informative exception message.
let ``with infinite recursion limit`` x =
    let rec util x count =
        if count = 1000000000L then
            raise (InfiniteRecursionException())
        util x (count + 1L)
    util x 0L

// Throws InfiniteRecursionException
(``with infinite recursion limit`` : int64 -> int64) 0L

Now, let’s say we have a function which doesn’t have a name which indicates it might fail (with StackOverflowException, InfiniteRecursionException, ArgumentOutOfRangeException etc.). An innocent reader might not notice that our function might be dangerous. For that we should define the attribute “MightFailWithAttribute” which gets an exception type.

open System

// Only for methods. Also, a method can raise several types of exceptions.
[<AttributeUsage(AttributeTargets.Method, AllowMultiple = true)>]
// Gets a type (using typeof<>)
type MightFailWithAttribute (expn : Type) =
    inherit System.Attribute()
// For reflection.
    member this.ExpnType = expn

[<MightFailWith(typeof<StackOverflowException>)>]
let rec ``with stack overflow`` x =
    1L + (``with stack overflow`` x)

``with stack overflow`` 0L


type InfiniteRecursionException() =
    inherit exn()


[<MightFailWith(typeof<InfiniteRecursionException>)>]
let ``with infinite recursion limit`` x =
    let rec util x count =
        if count = 1000000000L then
            raise (InfiniteRecursionException())
        util x (count + 1L)
    util x 0L

(``with infinite recursion limit`` : int64 -> int64) 0L

This is much more reader friendly.
It is also important to distinguish between unlikely exceptions and possible exceptions. For example, in the last code example, the InfiniteRecursionException was quite likely to happen. But look here:

let test() =
    let result = roll_die()
    match result with
    | a when a > 0 && a <= 6 -> printfn "%d" a
    | _ -> failwith "Unexpected!"

The exception here should not be raised. Never. I think that it is very important that likely exceptions will be marked with a helpful exception type, while unlikely exceptions will be marked with a regular System.Exception (like with failwith).

This entry was posted on Saturday, October 9th, 2010 at 9:04 PM and is filed under Default. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

One Response to “Being responsible when using tail recursion and exceptions”

  1. Johann Deneux Says:

    IMHO, using attributes to document functions isn’t optimal, comments are a better fit for that. I think attributes should be used only in cases where you expect tools to process them automatically.

    You indirectly highlighted an interesting side-effect of type inference: “with stack overflow“ doesn’t have int64 as return type. It has helped me detect bugs and infinite recursions in my code before executing it in a couple occasions.

Leave a Reply