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 usually '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
      do! body ()
      ()    // just add it
    return 10
  }

// compiled successfully
let sample cond body =
  option {
    while cond () do
      return! 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(both call Option.bind), 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))
      )
      // This code means:
      // let! () = if cond then return 10
      // ~~~~~~~   ~~~~~~~~~~~~~~~~~~~~~~
      // ↑         ↑
      // |         This expression is typed to `option<int>`.
      // The continuation needs `option<unit>` because the second argument of `Combine` is wrapped `Delay`. 
      // 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 implementation has never been used because this builder has Delay method that 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.

gistfile2.markdown

Sequence Expression Problems

1. Unnecessary Rule

---

According to the language specification, SeqBuilder has the Return method.

type SeqBuilder() =
    member x.Yield (v) = Seq.singleton v
    member x.YieldFrom (s:seq<_>) = s
    member x.Return(():unit) = Seq.empty
    (* snip *)

But seq { return () } can't compile.

2. Wrong Rule

---

The spec has the following rule:

{| expr1 |} → expr1 ; Seq.empty

But seq { () } and seq { printfn "aaa" } can't compile.

I think async should support such like this:

let f n =
  async {
    let mutable i = 0
    while i < n do
      do! Async.Sleep(100)
      i <- i + 1
    return i
  }

This code is translated as the following code:

let f n =
  let b = async
  b.Delay(fun () ->
    let mutable i = 0
    b.Combine(
      b.While(
        (fun () -> i < n),
        b.Delay(fun () ->
          b.Bind(
            Async.Sleep(100),
            fun () ->
              i <- i + 1
              b.Zero()    // The above code needs `Zero` method.
          )
        )
      ),
      b.Return(i)
    )
  )

If we use the way of Basis.Core then we can improve async.

First, introduce the FlowControl type.

type FlowControl = Break | Continue

Second, add one function into the AsyncBuilderImpl module.

let zeroA () = resultA (Unchecked.defaultof<_>, Continue)

Third, replace a few functions.

  let sequentialA p1 p2 =
    bindA p1
      (function
       | x, Break -> resultA (x, Break)
       | _, Continue -> p2)

  let rec whileA gd prog =
    if gd () then
      sequentialA prog (bindA (zeroA ()) (fun _ -> whileA gd prog))
    else
      zeroA ()

Fourth, replace the AsyncBuilder class.

type AsyncBuilder() =
  member __.Zero() = zeroA ()
  member __.Delay(f) = delayA f
  member __.Return(x) = resultA (x, Break)
  member __.ReturnFrom(x: Async<_>) = bindA x (fun x -> resultA (x, Break))
  member __.Bind(p1, p2) = bindA p1 p2
  member __.Using(g, p) = usingA g p
  member __.While(gd, prog) = whileA gd prog
  member __.For(e, prog) = forA e prog
  member __.Combine(p1, p2) = sequentialA p1 p2
  member __.TryFinally(p, cf) = tryFinallyA cf p
  member __.TryWith(p, cf) = tryWithExnA cf p
  member __.Run(x) = bindA x (fst >> resultA)

These programs are compilable:

let f cond =
  async {
    if cond then
      return "aaa"
    return "bbb"
  }

let f () =
  async {
    let mutable i = 0
    while i < 10 do
      if i = 5 then
        return -1
      i <- i + 1
    return i
  }

let f n xs =
  async {
    for x in xs do
      if x = n then
        return true
    return false
  }

This implementation is based on @pocketberserker's post.

https://gist.github.com/pocketberserker/2f7d9a46dd36876fab0154400eea588c