gistfile1.markdown

Computation Expression Problems

1. The translation rule of do! e;

In the language specification, the translation rule of do! e; is defined as follows:

T(do! e;, V, C, q) = T(let! () = src(e) in b.Return(), V, C, q)

And the signature of Return is 'a -> M<'a>, so the type of do! e; results M<unit>.

Basis.Core has an implementation of option computation builder. With using the builder, the following code can't compile.

let sample cond body =
  option {
    while cond () do
      do! body ()
    return 10
  }

Because the current F# compiler translates this code into the following:

let sample cond body =
  let b = option
  b.Run(
    b.Delay(fun () ->
      b.Combine(
        b.While(
          cond,
          b.Delay(fun () ->
            b.Bind(
              body (),
              fun () -> b.Return() // this returns `option<unit>`
            )
          )
        ),
        b.Delay(fun () ->
          b.Return(10) // but this returns `option<int>`
        )
      )
    )
  )

I think b.Zero() should be used in the rule of do! e;, instead of b.Return().

More Samples

// compiled successfully
let sample cond body =
  option {
    while cond () do
      return! body ()
    return 10
  }

// compiled successfully
let sample cond body =
  option {
    while cond () do
      do! body ()
      ()
    return 10
  }

// compiled successfully
let sample cond body =
  option {
    while cond () do
      let! () = body ()
      ()
    return 10
  }

// compiled successfully
let sample cond body =
  option {
    while cond () do
      let! () = body ()
      return 0
    return 10
  }

2. FSharpx and ExtCore have builders that can break valid code

FSharpx

FSharpx.Extras has MaybeBuilder. But the implementation of Combine seems to be wrong because the following code can't compile:

let sample cond =
  maybe {
    if cond then
      return 10
    return 0
  }

This code is translated as the following code:

let sample cond =
  let b = maybe
  b.Run(
    b.Delay(fun () ->
      b.Combine(
        (if cond then b.Return(10) else b.Zero()),
        b.Delay(fun () -> b.Return(0))
      )
    )
  )

The Combine and the Bind of FSharpx.Extras are identical, so the code is equal to:

let sample cond =
  let b = maybe
  b.Run(
    b.Delay(fun () ->
      b.Bind(
        (if cond then b.Return(10) else b.Zero()),
        b.Delay(fun () -> b.Return(0))
      )
      // continuation needs option<unit> but if expr type is option<int>, this code results:
      // let! () = if cond then return 10
      // return 0
    )
  )

ExtCore

ExtCore has MaybeBuilder. This builder has two Combine methods.

This implementation is the same as the one of FSharpx.Extra. So this library has the same problem as FSharpx.

Another problem is: Other implementations have never been used because this builder has Delay method and it does not invoke the argument.

Finally, the signature of While also seems to be wrong. So the following code can't get compiled:

let sample cond body =
  maybe {
    while cond () do
      return 0
    return 10
  }

On the other hand, the following code can:

let sample cond body =
  maybe {
    while cond () do
      return ()
    return 10
  }

3. async

async has the same problem as ExtCore. The signature of While is (unit -> bool) * Async<unit> -> Async<unit>. So the following code can't compile:

let sample cond body =
  async {
    while cond () do
      return 1
    return 10
  }

But this can:

let sample cond body =
  async {
    while cond () do
      return ()
    return 10
  }

async provides Zero as well. So async has another problem.

let sample cond =
  async {
    if cond then
      return 0
    return 1
  }

Many imperative programmers expect the same behavior with the following code:

let sample cond =
  asyn {
    if cond then
      return 0
    else
      return 1
  }

But the code can't compile.

Zero should be mzero but async has no zero-value. So essentially async can not provide Zero.