Imperative computation in F# (II.) - Writing break and continue

As I already wrote in the first part of this series, the F# language doesn't support some of the language constructs known from imperative languages such as C#. In particular, we cannot use imperative return statement that returns the result of a function from any place in the function code. In functional languages, every construct is an expression, so to get the overall result of the function, the F# language evaluates the expression and the value of the expression is used as the result. In the previous article, we've seen that we can simulate this construct in the F# language using F# computation expressions and I showed how to implement computation named imperative that allows us to write for example the exists function for working with sequences like this:

let exists f inp = imperative {
  for v in inp do 
    if f(v) then return true
  return false }

In this article, we're going to look at two more imperative constructs and we're going to talk about break and continue. We'll see that we can quite easily extend the computation builder from the previous article to allow writing code that is syntactically very close to what you would write in C#. As I already mentioned, there are of course some performance overheads when using computation expressions, but I find it very interesting how nice imperative syntax we can get in functional F#:

imperative { 
  for x in 1 .. 10 do 
    if (x % 3 = 0) then do! continue
    printfn "number = %d" x }

The only difference between this code and the code we'd probably write if F# supported continue as a keyword is that we need to wrap the code inside the imperative computation and that we need to add the do! primitive before the continue value. Now that we've seen an example of using the continue value inside the imperative computations, let's look how we can extend the computation builder from the previous article to add this feature...

Supporting break and continue

To add support for the break and continue primitives, we'll need to slightly modify the type that represents the computation and then update the computation builder that we implemented in the previous article. As you can probably guess, the largest changes will be done in the code that builds computation representing two F# looping constructs - for and while loops. Let's start by looking at the computation type.

Designing the computation type

In the previous part of the series, we represented the computation as a function that takes unit as the argument and returns option<'T>. This allowed us to represent the case when the computation hasn't yet finished, because the return primitive wasn't used (the function returns None) and the case when the computation already has some result value (returning Some). To support the two jumping constructs, we'll need to add a case that represents a computation that is jumping out of the iteration of a loop. We can declare the type like this:

type ImperativeResult<'T> = 
  | ImpValue of 'T
  | ImpJump of bool
  | ImpNone 
  
type Imperative<'T> = unit -> ImperativeResult<'T>

The ImperativeResult<'T> type is in principle just an extension of the option<'T> type that adds one case - the ImpJump discriminator. The bool parameter specifies whether we want to continue executing the next iteration of the loop after we break out of the current iteration. The value will be true when the user calls the continue primitive and for break we'll set it to false. The actual type that represents the computation is again just a function that returns one of the possible computation results.

Implementing the computation builder

We'll split the implementation of the computation expression builder in a similar way as in the previous article and we'll start with the basic primitives that aren't related to loops.

type ImperativeBuilder() = 
  // When returning a value, we'll use the 'ImpValue' discriminator
  member x.Return(v) : Imperative<_> = 
    (fun () -> ImpValue(v))
  // Expression that doesn't represent any value returns 'ImpNone'
  member x.Zero() = (fun () -> ImpNone)
  
  // Create a delayed imperative computation from a function
  member x.Delay(f:unit -> Imperative<_>) = 
    (fun () -> f()())

  // Combine two delayed computations that may return or jump
  member x.Combine(a, b) = (fun () ->
    match a() with 
    // The computation doesn't have value - evaluate the next
    | ImpNone -> b() 
    // If the computation returned value or called break/return
    // we'll propagate the value representing the result
    | res -> res)
  
  // Execute the imperative computation given as the argument  
  member x.Run<'T>(imp) = 
    // When the computation returns 'ImpJump' it is an indication
    // that 'break' or 'continue' was used incorrectly.
    match imp() with
    | ImpValue(v) -> v
    | ImpJump _ -> failwith "Invalid use of break/continue!"
    | _ -> failwith "No value has been returend!"

let imperative = new ImperativeBuilder()  

If you compare the listing with the code from the previous article, you'll see that there are relatively few changes. First of all, we've changed all occurrences of None into ImpNone and also all uses of Some into ImpValue, which are our new representations of missing or present values. However, there are a few places where we needed to modify the code to correctly handle ImpJump values. In the Combine primitive, we're now returning the result of the first computation not only when it is a result created using return, but also when the user uses break or continue and we'll get the ImpJump value. This means that when we're combining two pieces of computations inside the body of the loop, we won't execute the second computation if the first one contained a jumping construct. As a next change, we also added a new case to the Run primitive which returns an error if the computation ends with a value representing a jump. This means that a break or continue construct was used outside of a loop, which is incorrect.

Adding support for loops

Most of the interesting changes in the code will be in the parts that implement looping constructs. In particular, we'll use a different primitive for composing iterations of the loop - in the previous article we just used the Combine member from both While and For. However, in the new version, we'll need to handle loops differently. Before the computation can start a new iteration of a loop, it needs to check whether the previous iteration returned ImpJump. If it returned value representing break then we'll need to break the loop immediately without returning a result. If the previous iteration contained the continue construct, then we'll just continue executing the next iteration - the jump represented by continue was already performed because we didn't run any more code after reaching the continue primitive in the previous iteration (this is the case, because the Combine primitive doesn't call the second computation when it gets ImpJump as the result from the first one).

type ImperativeBuilder with 
  // A local helper used when composing iterations of loops
  // in the 'For' and 'While' primitives below.
  member x.CombineLoop(a, b) = (fun () ->
    match a() with 
    // When the last iteration returns a value, propagate the result
    | ImpValue(v) -> ImpValue(v) 
    // The last iteration contained 'break', so we'll 
    // return missing value as the result from the loop
    | ImpJump(false) -> ImpNone
    // When the last iteration didn't contain any special construct
    // or when it ended with 'continue', we'll continue looping
    | ImpJump(true)
    | ImpNone -> b() )
  
  // 'For' and 'While' members that implement the looping constructs
  // are similar as in the previous version, with the exception that they
  // compose iterations using the special 'CombineLoop' primitive
  member x.For(inp:seq<_>, f) =
    let rec loop(en:IEnumerator<_>) = 
      if not(en.MoveNext()) then x.Zero() else
        x.CombineLoop(f(en.Current), x.Delay(fun () -> loop(en)))
    loop(inp.GetEnumerator())
  member x.While(gd, body) = 
    let rec loop() =
      if not(gd()) then x.Zero() else
        x.CombineLoop(body, x.Delay(fun () -> loop()))
    loop()         
  
  // A call to this member is inserted when we use the 'do!' construct. If the 'v'
  // value is either 'break' or 'continue', we will return 'ImpJump' as the result
  member x.Bind(v:Imperative<unit>, f : unit -> Imperative<_>) = (fun () ->
    match v() with
    | ImpJump(kind) -> ImpJump(kind)
    | _ -> f()() )
     
// Primitives that return the 'ImpJump' value when executed 
let break = (fun () -> ImpJump(false))
let continue = (fun () -> ImpJump(true))

As you can see, we've added a primitive named CombineLoop and used it instead of the usual Combine when implementing the looping constructs. The reason for this change is that once we introduce break and continue, we need to handle them differently when composing for example a sequence of statements and when composing iterations of a loop.

The listing also defines two primitive values of the Imperative<'T> type that simply return the ImpJump result. Note that these give us the only way we can use to build a computation that contains jumps. We've also added the Bind member to the computation builder, which means that we can now write do! inside the computation expression. The only values of the Imperative<'T> type that we have available are break and continue, so they are the only two primitives that we can use with the do! construct.

Using 'break' and 'continue' in F#

Now we have everything we need to write imperative loops with break or continue in F#. I'm sure you know many cases where these primitives are useful, so let's just briefly look at two simple snippets that demonstrate how we can use them. In the first example, we'll write a for loop and we'll use continue to skip evaluation of some iterations of the loop:

> imperative { 
    for x in 1 .. 5 do 
      if (x % 2 = 0) then do! continue
      printfn "number = %d" x };;
number = 1
number = 3
number = 5

The second example will use a while loop with true as the condition. However, we can now jump out of the loop, so the loop isn't infinite as it may look. We're using a single mutable variable (using F# reference cell) and we increment it in each iteration. When the number reaches some number, we'll stop looping using break:

    
> imperative { 
    let x = ref 1
    while true do
      if (!x % 4 = 0) then do! break
      printfn "number = %d" !x
      x := !x + 1 };;
number = 1
number = 2
number = 3

Summary

As I already wrote in the introduction and in the first article of this series, the most interesting thing about the imperative computation builder is that it gives us a surprisingly elegant syntax to write imperative constructs in F#. The syntax almost doesn't differ from you'd write if F# supported these imperative constructs directly. On the other hand, the performance may be an issue, because computation expressions are translated into member calls that take lambda functions as arguments, so there is definitely some overhead.

The purpose of this article is first of all to demonstrate the flexibility of the F# language and to show an implementation of an interesting computation expression. Actually, writing break and continue in functional languages isn't a new idea. There is an example how to do this using the continuation monad in Haskell [1] and Brian McNamara has posted a translation of this in F# [2]. However, none of these get us a very pleasant syntax, which is I believe quite important aspect.

Downloads & References

• Download the example source code

• [1] The Continuation monad - haskell.org
• [2] Best way to express this? - A reply by Brian McNamara at cs.hubfs.net