Add support for generating F# quotations and Linq expressions (Expr and Expression)

[kurtschelfthout]

Possible, yes. Easy, probably not. Nice idea though. I'll mark it as up for grabs :)

[moodmosaic]

This looks like an interesting idea :smiley: – I'm just trying to understand how this could possibly work.

Assuming a quotation which represents a variable x of type int:

open Microsoft.FSharp.Quotations

let xvar = Expr.Var(Var("x", typeof<int>)) |> Expr.Cast
// -> val xvar : Expr<int>

and a quotation with the xvar spliced in:

let q = <@ %xvar + 10 @>
// -> val q : Expr<int> 

Now, q can be evaluated with the variable x, e.g. using Unquote:

open Swensen.Unquote

let actual = q |> evalWith (Map.ofList [("x", box 2)])

So the actual value can be verified like so:

open Swensen.Unquote.Assertions

test <@ 2 + 10 = actual @>

---

In the above scenario, where could FsCheck kick-in?

• By generating xvar or q?
• By generating xvar and values for evaluating q?
• Something totally different?

[kurtschelfthout]

I imagined this as a generator for the Expr<'a> type. So it would generate xvar. That said, when I say a generator, in this case it means a generator/shrinker API to generate Expr so that they have a certain form, as I think folks would use this to test code that consumes Expr, and that typically has some preconditions on the shape of the Expr - e.g. at least one that's obvious from your example is the type.

The reason I called this not easy is because essentially, this amounts to generating arbitrary typechecked F# code - though of course initial implementations can be much simpler and still useful.

For example: generating arithmetic expressions, boolean expressions, sequence of method calls starting from a given type <@ fun x : Fluent -> x.Foo().Baz() @>.

[Thorium]

I would have some use for this. Not for Expr but System.Linq.Expressions (.NET lambda expressions) but basically it's the same...

open System
open System.Linq.Expressions

let rnd = System.Random()

let someStopCondition = rnd.NextDouble() > 0.8

/// Usage: randomExpressionType()
let randomExpressionType = 
    let expTypes = Enum.GetValues(typeof<ExpressionType>) 
    fun () -> expTypes.GetValue(rnd.Next(expTypes.Length)) :?> ExpressionType

Now, the expression tree end-node-types are always either ConstantExpressions or ParameterExpressions:

Expression.Constant(rnd.NextDouble() > 0.5, typeof<bool>) :> Expression
Expression.Parameter(typeof<bool>, "p1")

Bool should be supported first and then maybe int.

Now, if you have created the sub-expression, then you could recursively create a little random tree surrounding it:

upcast Expression.MakeUnary(e.NodeType, createSub e.Operand,e.Type,e.Method)
upcast Expression.MakeBinary(e.NodeType, createSub e.Left, createSub e.Right)
upcast Expression.TypeIs(createSub e.Expression, e.TypeOperand)
upcast Expression.Condition(createSub e.Test, createSub e.IfTrue, createSub e.IfFalse)
upcast Expression.MakeMemberAccess(createSub e.Expression, e.Member)
upcast Expression.Call(createSub e.Object, e.Method, e.Arguments |> Seq.map(fun a -> createSub a))
upcast Expression.Lambda(e.Type, createSub e.Body, e.Parameters)
upcast Expression.New(e.Constructor, e.Arguments |> Seq.map(fun a -> createSub a))
upcast Expression.New(e.Constructor, e.Arguments |> Seq.map(fun a -> createSub a), e.Members)
upcast Expression.NewArrayBounds(e.Type.GetElementType(), e.Expressions |> Seq.map(fun e -> createSub e))
upcast Expression.NewArrayInit(e.Type.GetElementType(), e.Expressions |> Seq.map(fun e -> createSub e))
upcast Expression.Invoke(createSub e.Expression, e.Arguments |> Seq.map(fun a -> createSub a))
upcast Expression.MemberInit( (createSub e.NewExpression) :?> NewExpression , e.Bindings) 
upcast Expression.ListInit( (createSub e.NewExpression) :?> NewExpression, e.Initializers)

Of course this would be just random little expressions. I've seen this idea of "You just generate unit tests and then the computer creates a working program." before. It was miniKanren. This is a nice video: https://youtu.be/eQL48qYDwp4 http://minikanren.org/

[kurtschelfthout]

Yes, I saw a propietary version of an Expr generator before and that's basically how it worked.

Funny you mentioned minikanren: https://github.com/kurtschelfthout/fslogic :)