{{ message }}

Instantly share code, notes, and snippets.

Last active May 29, 2017

# 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 ()
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`.

# 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.

1. Wrong Rule

The spec has the following rule:

`{| expr1 |} → expr1 ; Seq.empty`

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

### bleis-tift commented Nov 14, 2016

 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) ) )```

### bleis-tift commented Nov 16, 2016

 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 }```

### bleis-tift commented Nov 16, 2016

 This implementation is based on @pocketberserker's post.