Idea: Use Source Generators to rewrite LINQ expressions

[louthy]

This has been going around my head for a while, I'm not sure if it's possible, but want to get it written down just in case.

Problem: LINQ expressions come with lambda allocation and contextual type allocation costs, this means their performance isn't as good as writing imperative code.

Possible solution: Use Source Generators to find LINQ expressions that evaluate to known language-ext monadic types. Replace the LINQ expression with an 'unrolled' version that runs imperatively. It won't remove all lambda usage, but would significantly reduce it.

[iamim]

Maybe new F# 6 resumable code feature could be useful somehow? https://github.com/fsharp/fslang-design/blob/main/FSharp-6.0/FS-1087-resumable-code.md

[bmazzarol]

@louthy had a think about this the other day as well and have a different idea.

How about instead of a source generator, we create 4 new effect types that have at their heart Expression instead of Func.

This is how it works in my head (does not mean it works, so please be kind if its actually a really dumb idea),

Create the new effect structs,

public readonly struct EffExpr<T>
{
    readonly Expression<Func<Fin<A>>> thunk;
    ...
    public EffExpr(Expression<Func<Fin<A>>> thunk) =>
        this.thunk = thunk;

    /// <summary>
    /// Compiles the effect
    /// </summary>
    [Pure, MethodImpl(Opt.Default)]
    public Eff<A> Compile() =>
        EffMaybe<A>(Thunk.Compile);
    ...
}

public readonly struct EffExpr<RT,T>
{
    readonly Expression<Func<RT,Fin<A>>> thunk;
    ...
}

public readonly struct AffExpr<T>
{
    readonly Expression<Func<ValueTask<Fin<A>>>> thunk;
    ...
}

public readonly struct AffExpr<RT,T>
{
    readonly Expression<Func<RT,ValueTask<Fin<A>>>> thunk;
    ...
}

They can have the same constructors and operations on them as Aff and Eff, but they can only be compiled, not run directly.

We could then implement all the operations (Map, Bind, Filter...) by building expressions.

It has the following benefits,

• Elimination of all lambda allocations, we could rewrite them away
• Other smart rewriting rules (not that I understand or know how to implement any of them), like those performed by GHC, could be applied to the expression tree
• Would look just like the standard Aff and Eff usage, but would (in my head) perform better.
• There is nothing like this, (that I know about, besides the linq optimizers for IEnumerable) and so might be a real feature

It has the following negatives,

• Library code maintenance, I had a quick go at implementing Map at the expression level and it was a bit like inception and I wanted to rest my brain
• Expression quirks could cause many issues, which would then also increase the maintenance cost. All I know is that the majority of bugs registered against EfCore relate to Expressions and trying to write executable code at runtime.