Instantly share code, notes, and snippets.

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.

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.

Owner Author

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) ) )
Owner Author

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 }
Owner Author

bleis-tift commented Nov 16, 2016

 This implementation is based on @pocketberserker's post.

pocketberserker commented Nov 20, 2016

to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.