Language Idea: Queryable Iterators

[AdamSobieski]

Introduction

Hello. I would like to share and to flesh out some ideas pertaining to an interesting C# language idea: queryable iterators.

C# Iterators

Quoting from this article, we can observe that an iterator function resembling:

class Test
{
    static IEnumerable<int> GetCounter()
    {
        for (int count = 0; count < 10; count++)
        {
            yield return count;
        }
    }
}

can be compiled into something like (metadata attributes stripped for brevity):

internal class Test
{
    private static IEnumerable<int> GetCounter()
    {
        return new <GetCounter>d__0(-2);
    }

    private sealed class <GetCounter>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IEnumerator, IDisposable
    {
        // Fields
        private int <>1__state;
        private int <>2__current;
        private int <>l__initialThreadId;
        public int <count>5__1;

        public <GetCounter>d__0(int <>1__state)
        {
            this.<>1__state = <>1__state;
            this.<>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;
        }

        private bool MoveNext()
        {
            switch (this.<>1__state)
            {
                case 0:
                    this.<>1__state = -1;
                    this.<count>5__1 = 0;
                    while (this.<count>5__1 < 10)
                    {
                        this.<>2__current = this.<count>5__1;
                        this.<>1__state = 1;
                        return true;
                    Label_0046:
                        this.<>1__state = -1;
                        this.<count>5__1++;
                    }
                    break;

                case 1:
                    goto Label_0046;
            }
            return false;
        }

        IEnumerator<int> IEnumerable<int>.GetEnumerator()
        {
            if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
            {
                this.<>1__state = 0;
                return this;
            }
            return new Test.<GetCounter>d__0(0);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<Int32>) this).GetEnumerator();
        }

        void IEnumerator.Reset()
        {
            throw new NotSupportedException();
        }

        void IDisposable.Dispose()
        {
        }

        int IEnumerator<int>.Current
        {
            get
            {
                return this.<>2__current;
            }
        }

        object IEnumerator.Current
        {
            get
            {
                return this.<>2__current;
            }
        }
    }
}

Queryable Iterators

What if developers could express, in hopes of enabling runtime optimizations, something like:

class Test
{
    static IQueryable<int> GetCounter()
    {
        for (int count = 0; count < 10; count++)
        {
            yield return count;
        }
    }
}

In this case, the resultant compiled code could be such so that the private sealed class <GetCounter>d__0 would also implement IQueryable<int> and, thus, IQueryable.

This would entail that the class <GetCounter>d__0 would have properties ElementType, Expression, and Provider.

The matter of implementing ElementType would be simple. For the example, it would return typeof(int).

For the Provider property, a resulting private sealed class <GetCounter>d__0 could, if its private IQueryProvider member, e.g., <>n__provider, were null, activate one using a runtime-default provider type, caching the value. In theory, .NET could provide a default query provider for queryable iterators. As described below, developers could provide custom ones or use third-party ones.

The remaining important matter for consideration, then, would be the nature of the expression tree returned by the Expression property. It could represent: (1) the iterator method before the compiler-time transformation, (2) an InvocationExpression which invokes a useful LambdaExpression, (3) a MethodCallExpression expression, (4) another, perhaps more intricate, technique.

Customizable Query Providers

Developers using queryable iterators might want to provide their own IQueryProvider implementations or to make use of third-party ones. This could be achieved with metadata:

class Test
{
    [QueryProvider(typeof(CustomQueryProvider))]
    static IQueryable<int> GetCounter()
    {
        for (int count = 0; count < 10; count++)
        {
            yield return count;
        }
    }
}

That metadata attribute, or another identically initialized attribute, could be placed on the resulting private sealed class <GetCounter>d__0. The <GetCounter>d__0 class could, for its Provider property, if a private backing field, <>n__provider, were null, activate an instance of that type obtained from its QueryProviderAttribute metadata attribute and assign it to that backing field member, caching the value.

Use Case: C# Logic Programming

Optimizations needn't entirely focus on the streaming outputs from the iteration (see: LINQ). Developers could also perform operations and processing upon input arguments provided to iterator functions. This is the case with some approaches to logic programming in C#, e.g., YieldProlog (YP).

IEnumerable<bool> uncle(object Person, object Uncle)
{
    Variable Parent = new Variable();
    foreach (bool l1 in parent(Person, Parent))
    {
        foreach (bool l2 in brother(Parent, Uncle))
            yield return false;
    }
}

While perhaps beyond the scope of this discussion about queryable iterators as a language idea, the YP C# logic programs unify variables as iterators are iterated, searching for solutions. Outputs can be provided in the form of those instantaneous values on the variables passed to the iterator functions as arguments. Each time that MoveNext() is called on the resultant enumerator, the variables could have different values.

This is a different scenario than that of streaming output values (see: LINQ) but is also one that a third-party library provider might find interesting to provide optimizations for.

Use Case: LINQ-related Runtime Optimizations

Enumerables

Optimizations are possible with respect to queryable iterators and LINQ operators. Let us consider an optimization-related extension method, Optimize<T>(), resembling the following:

public static IQueryable<T> Optimize<T>(this IQueryable<T> source, IOptimizationConfiguration config)
{
    if (source.Provider is IOptimizingQueryProvider source_optimizer)
    {
        return source_optimizer.Optimize(source.Expression, config);
    }
    else
    {
        var default_optimizer = DefaultOptimizer.Create(config);
        return default_optimizer.Optimize(source);
    }
}

Let us also consider the following two queryable iterator functions:

public IQueryable<int> Function1()
{
    for(int i = 0; i < 10000; ++i)
        yield return i;
}

and

public IQueryable<int> Function2()
{
    for(int i = 10000; i < 20000; ++i)
        yield return i;
}

With the following LINQ:

var result = Function1().Concat(Function2()).Optimize(config);

a resultant queryable iterator function, Function3, might resemble:

public IQueryable<int> Function3()
{
    for(int i = 0; i < 10000; ++i)
        yield return i;

    for(int i = 10000; i < 20000; ++i)
        yield return i;
}

or, if the optimizer detected this edge case, Function3 might resemble:

public IQueryable<int> Function3()
{
    for(int i = 0; i < 20000; ++i)
        yield return i;
}

Next, utilizing the Where operator:

var result = Function1().Where(n => n % 2 == 0).Optimize(config);

a resultant queryable iterator function, Function4, might resemble:

public IQueryable<int> Function4()
{
    for(int i = 0; i < 10000; ++i)
        if(i % 2 == 0)
            yield return i;
}

Similarly, with a combined Where and Select operator:

var result = Function1().Where(n => n % 2 == 0).Select(n => n * n).Optimize(config);

a resultant queryable iterator function, Function5, might resemble:

public IQueryable<int> Function5()
{
    for(int i = 0; i < 10000; ++i)
        if(i % 2 == 0)
            yield return i * i;
}

For a more complex LINQ example, let us add another function:

public IQueryable<int> Function6(int x)
{
    for(int i = x - 10; i < x + 10; ++i)
        yield return i;
}

And a LINQ expression:

var result = Function1().SelectMany(n => Function6(n), (x, y) => {x, y}).Where(p => p.x > p.y).Select(p => p.x * p.y)
    .Optimize(config);

a resultant queryable iterator function, Function7, might resemble:

public IQueryable<int> Function7()
{
    for(int i = 0; i < 10000; ++i)
    {
        for(int j = i - 10; j < i + 10; ++j)
        {
            if(i > j)
            {
                return i * j;
            }
        }
    }
}

With LambdaExpressions available for queryable iterator functions, runtime compilers could produce resultant queryable iterator functions which optimize for, in some cases inlining, those lambda expressions provided for subsequently utilized LINQ operators including, but not limited to, Concat, Where, Select, and SelectMany.

Non-enumerables

Beyond those LINQ operators like Concat, Where, Select, and SelectMany, indicated above, one might wonder about those LINQ operators like All, Any, and Count?

In these regards, we might consider QueryableValue<T> and QueryableCachingValue<T>, classes with which to express "IQueryable for non-enumerables". These would provide non-caching and caching access to object values while also providing ElementType, Provider, and Expression properties.

As envisioned, QueryableValue<T> would consult its backing method each time its value was requested and QueryableCachingValue<T> would cache its value after it was first accessed.

public static partial class QueryableValue
{
    public static QueryableValue<bool> All<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate) { ... }
    public static QueryableValue<bool> Any<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate) { ... }

    public static QueryableValue<int> Count<T>(this IQueryable<T> source) { ... }
    public static QueryableValue<int> Count<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate) { ... }

    ...
}

public static partial class QueryableCachingValue
{
    public static QueryableCachingValue<bool> All<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate) { ... }
    public static QueryableCachingValue<bool> Any<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate) { ... }

    public static QueryableCachingValue<int> Count<T>(this IQueryable<T> source) { ... }
    public static QueryableCachingValue<int> Count<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate) { ... }

    ...
}

With classes resembling those, "IQueryable for non-enumerables", the Optimize() pattern could be expanded to include more of the LINQ operators.

That is, something like:

var result = Function1().Where(n => n % 2 == 0).Count().Optimize(config);

could result in a function resembling Function8, below, being invoked whenever the Value is desired:

public QueryableValue<int> Function8()
{
    int count = 0;

    for(int i = 0; i < 10000; ++i)
        if(i % 2 == 0)
            ++count;

    return count;
}

or only when first desired:

public QueryableCachingValue<int> Function8()
{
    int count = 0;

    for(int i = 0; i < 10000; ++i)
        if(i % 2 == 0)
            ++count;

    return count;
}

Potential Complexities

Some complexities may arise from the LINQ AST not supporting expressiveness for all of the newest C# language features.

The simplest approach to having an inspectable expression tree for a queryable iterator is to use an InvocationExpression upon a LambdaExpression which represents the program logic of the pre-compiler-transformed queryable iterator. However, as it is an iterator, it utilizes yield return, and there is not a YieldReturnExpression in the LINQ AST. Accordingly, other approaches can be explored.

Other Uses and Related Scenarios

Beyond developers hoping to optimize queryable iterator functions at runtime with LINQ, queryable iterators would be a convenient way to easily create useful IQueryable<T> instances.

Other, related scenarios include considering return types of IObservable<T> and, in particular, IQbservable<T> as well as mappings between IEnumerable<T> and IObservable<T> and IQueryable<T> and IQbservable<T>. These mappings would be desired to work and to be interoperable with queryable iterators.

var result = Function1().ToQbservable();

Conclusion

Thank you.

[CyrusNajmabadi]

What if developers could express, in hopes of enabling runtime optimizations,

What optimizations would this enable.

Generally speaking, we don't do language features based on speculation that there will be performance. Rather, we want to see that performance is lacking, and has no way to obtain, and then we design with a drive to solve that performance issue.

This allows us to actually validate the language/solution, and not end up with something that doesn't actually work in practice.

[AdamSobieski]

@HaloFour, as considered, there would be runtime-compile-related overhead and, thereafter, each time that the resultant iterator functions were run, a speedup. Long-running software applications, e.g., servers and services, could be benefitted.

Also, in addition to IEnumerable<T> and IQueryable<T>, there are IObservable<T>, and IQbservable<T> and Async varieties of all of these. The Reactive libraries include methods with which to transform between these pull- and push-based models. Maybe optimization ideas for IQueryable<T> could benefit IQbservable<T>.

Brainstorming, runtime optimizations needn't be only provided by the Optimize() extension method. There could be an interface for IQueryProvider instances, IOptimizingQueryProvider, with an Optimize() method on it.

public static IQueryable<T> Optimize<T>(this IQueryable<T> source, IOptimizationConfiguration config)
{
  if(source.Provider is IOptimizingQueryProvider o)
  {
    return o.Optimize(source.Expression, config);
  }
  else
  {
    var optimizer = DefaultOptimizer.Create(config);
    return optimizer.Optimize(source);
  }
}

I'm not opposed to this idea. However, it seems like linq would be the place to start with this.

Excellent. Ok, I will focus on LINQ-related scenarios for forthcoming source-code examples.

[AdamSobieski]

I added some LINQ-related source-code examples to the proposal post. In the revised proposal, I broach optimizations for enumerable-related scenarios like Concat, Select, SelectMany, and Where. I also broach optimization ideas for non-enumerable-related scenarios like All, Any, and Count. What do you think?

[CyrusNajmabadi]

I added some LINQ-related source-code examples to the proposal post. In the revised proposal, I broach optimizations for enumerable-related scenarios like Concat, Select, SelectMany, and Where.

I see the examples, but what I don't see in the entire post is: "why".

Because, "why" would we do this? This is asking for a tremendous amount of design and work, without any reason given for why this is actually a good thing.

Literally zero real world cases have been brought up besides 'YieldProlog' (a completely used library). And even for that library no real world examples were made for how this would actually help.

As such, this seems like a post made just for intellectual exploration. While that can be fun, and I understand the interest in some to explore that realm, it really isn't driven by the thing we care most about: is this valuable to the ecosystem.

Given a week of discussion, and no real world practical value, it definitely feels like yours is more to please the mind versus provide value.

[AdamSobieski]

Yes, I see that adding these language features would entail a significant amount of design and development. I will put some thought into more compelling elevator pitches or sales pitches for queryable iterators, beyond enabling runtime compiler optimizations. I sense that these ideas aren't as popular here as I thought that they would be. Ah well, back to the drawing board.

[CyrusNajmabadi]

I sense that these ideas aren't as popular here 

Agreed. Speculative value, and no real customer identified, will always take a backseat to real gains, with tons of customers indicating support and presenting real world usecases where the feature would be beneficial.

If you find anything in the real world that would benefit, def let us know. Thanks!