Extended computation expressions without for..in..do
Asked Answered
Z

2

24

What I mean by extended computation expressions is computation expressions with custom keywords defined via CustomOperation attribute.

When reading about extended computation expressions, I come across very cool IL DSL by @kvb:

let il = ILBuilder()

// will return 42 when called
// val fortyTwoFn : (unit -> int)
let fortyTwoFn = 
    il {
        ldc_i4 6
        ldc_i4_0
        ldc_i4 7
        add
        mul
        ret
    }

I wonder how the operations compose without using for..in..do construct. My gut feeling is that it starts with x.Zero member, but I haven't found any reference to verify that.

If the example above is too technical, here is a similar DSL where components of a slide are listed without for..in..do:

page {
      title "Happy New Year F# community"
      item "May F# continue to shine as it did in 2012"
      code @"…"
      button (…)
} |> SlideShow.show

I have a few closely related questions:

  • How does one define or use extended computation expressions without For member (i.e. provide a small complete example)? I don't worry much if they aren't monads any longer, I'm interested in them in developing DSLs.
  • Can we use extended computation expressions with let! and return!? If yes, is there any reason of not doing so? I ask these questions because I haven't encountered any example using let! and return!.
Zoogeography answered 1/1, 2013 at 12:37 Comment(0)
C
14

I'm glad you liked the IL example. The best way to understand how expressions are desugared is probably to look at the spec (though it's a bit dense...).

There we can see that something like

C {
    op1
    op2
}

gets desugared as follows:

T([<CustomOperator>]op1; [<CustomOperator>]op2, [], fun v -> v, true) ⇒
CL([<CustomOperator>]op1; [<CustomOperator>]op2, [], C.Yield(), false) ⇒
CL([<CustomOperator>]op2, [], 〚 [<CustomOperator>]op1, C.Yield() |][], false) ⇒
CL([<CustomOperator>]op2, [], C.Op1(C.Yield()), false) ⇒
〚 [<CustomOperator>]op2, C.Op1(C.Yield()) 〛[] ⇒
C.Op2(C.Op1(C.Yield()))

As to why Yield() is used rather than Zero, it's because if there were variables in scope (e.g. because you used some lets, or were in a for loop, etc.), then you would get Yield (v1,v2,...) but Zero clearly can't be used this way. Note that this means adding a superfluous let x = 1 into Tomas's lr example will fail to compile, because Yield will be called with an argument of type int rather than unit.

There's another trick which can help understand the compiled form of computation expressions, which is to (ab)use the auto-quotation support for computation expressions in F# 3. Just define a do-nothing Quote member and make Run just return its argument:

member __.Quote() = ()
member __.Run(q) = q

Now your computation expression will evaluate to the quotation of its desugared form. This can be pretty handy when debugging things.

Chatter answered 2/1, 2013 at 22:13 Comment(5)
Actually I was waiting for your answer. Do you have your IL DSL document or publish anywhere? It would be a very good example to gain understanding and inspiration. The trick with Quote member will be helpful too. Thanks.Zoogeography
@Zoogeography - No, it's not currently published anywhere - it's really just a very simple proof of concept with a lot of limitations. I'll try to clean it up a bit and get it out in some form in the near future.Chatter
@Zoogeography - it's now published at github.com/kbattocchi/ILBuilder. Sorry for the delay.Chatter
Can you please elaborate on this Quote trick a little bit. I'm sure it's easy but I can't find any docs on it and it is not obvious to me how to employ it.Reade
@uosɐſ On your computation builder, add Quote and Run members as in my answer. Then whenever you evaluate your computation expression (e.g. myBuilder { myOp1; myOp2 }) the result will be an Expr<_> containing the set of calls that the compiler would have made if you hadn't added the Quote method. Hope that helps.Chatter
R
9

I have to admit I do not fully understand how computation expressions work when you use query expression features like the CustomOperation attribute. But here are some remarks from some my experiments that might help....

Firstly, I think it is not possible to freely combine standard computation expression features (return! etc.) with custom operations. Some combinations are apparently allowed, but not all. For example, if I define custom operation left and return! then I can only use the custom operation before return!:

// Does not compile              // Compiles and works
moves { return! lr               moves { left 
        left }                           return! lr }

As for the computations that use only custom operations, most common cusotom operations (orderBy, reverse and this kind) have a type M<'T> -> M<'T> where M<'T> is some (possibly generic) type that represent the thing we're building (e.g. a list).

For example, if we want to build a value that represents a sequence of left/right moves, we can use the following Commands type:

type Command = Left | Right 
type Commands = Commands of Command list

Custom operations like left and right can then transform Commands into Commands and append the new step to the end of the list. Something like:

type MovesBuilder() =
  [<CustomOperation("left")>]
  member x.Left(Commands c) = Commands(c @ [Left])
  [<CustomOperation("right")>]
  member x.Right(Commands c) = Commands(c @ [Right])

Note this is different from yield which returns just a single operation - or command - and so yield needs Combine to combine multiple individual steps if you use custom operations, then you never need to combine anything because the custom operations gradually build the Commands value as a whole. It only needs some initial empty Commands value that is used at the beginning...

Now, I would expect to see Zero there, but it actually calls Yield with unit as an argument, so you need:

member x.Yield( () ) = 
  Commands[]

I'm not sure why this is the case, but Zero is quite often defined as Yield (), so perhaps the goal is to use the default definition (but as I said, I'd also expect to use Zero here...)

I think combining custom operations with computation expressions makes sense. While I have strong opinions on how standard computation expressions should be used, I do not really have any good intuition about computations with custom operations - I think the community still needs to figure this out :-). But for example, you can extend the above computation like this:

member x.Bind(Commands c1, f) = 
  let (Commands c2) = f () in Commands(c1 @ c2)
member x.For(c, f) = x.Bind(c, f)
member x.Return(a) = x.Yield(a)

(At some point, the translation will start requiring For and Return, but here they can be defined just like Bind and Yield - and I do not fully understand when is which alternative used).

Then you can write something like:

let moves = MovesBuilder()

let lr = 
  moves { left
          right }    
let res =
  moves { left
          do! lr
          left 
          do! lr }
Ricercare answered 1/1, 2013 at 15:53 Comment(1)
Thanks Tomas. Your answer cleared up a few doubts. As much as I like this feature, it remains mysterious to me. The lack of documentation (or even semantics) is the main problem.Zoogeography

© 2022 - 2024 — McMap. All rights reserved.