Feature Request: Recursive Iterators (non-quadratic)

[gafter]

@AdamSpeight2008 commented on Fri Jan 16 2015

Current if you want write a recursive based iterator function.

Iterator Function TreeWalk(Of T) ( curr As BinaryNode(Of T)) : IEnumerable(Of BinaryNode(Of T))
  If curr Is Nothing Then Return Enumerable.Empty(Of BinaryNode(Of T))
  ForEach node In TreeWalk( curr.Left )
    Yield node
  Next
  Yield curr
  ForEach node In TreeWalk( curr.Righ )
    Yield node
  Next
End Function

it ends up being Quadratic runtime

If I could express the Iterator / Yielder as a parameter I could linearise the runtime.

Iteration Function TreeWalk( n : BinaryNode, iterator As ?? ) : IEnumerable(Of T)
  If n Is Nothing Then Exit Functon
  If n.Left IsNot Nothing Then TreeWalk(n.Left, Iterator)
  Yield n.Value on Iterator
  If n.Righ IsNot Nothing Then TreeWalk(n.Righ, Iterator)
End Function

---

@ufcpp commented on Fri Jan 16 2015

👍
I'd like this fearure to be added to C# too.

---

@mattwar commented on Fri Jan 16 2015

It's a nice feature, and we had it on the list when we did IEnumerable, or the release after, not entirely sure. But it is kind of niche feature. I think the syntax was going to be something like:

yield foreach x

Erik Meijer had an algorithm to make it near non-recursive.

---

@AdamSpeight2008 commented on Sat Jan 17 2015

@mattwar
Don't confuse

yield foreach recFN with yield x On iter

yield foreach recFN is equivalent to

foreach(x in recFN) 
{
 yield x;
}

Which is still Quadratic.

This does something different. Let's use another example. Yielding the permutations of a list of items.

private iterator _Perm<T>( items : T[], len : int, res : T[] , iter : Iterator<T[]> ) : IE< T[] >
{
  if( items.Length = len )
  {
   Yield res On iter;
  } else
  {
    for(var i = 1 To items.Length)
    {
      _Perm<T>( items.Skip(1).ToArray(), len, res.Concate( items.Take(1) , iter );
      items = items.Rotate();
    }
  }
}


public Rotate<T>( this a : T[] ) : T[]
{
  return a.Skip(1).Concate( a.Take(1) ).ToArray();
}`

Let's create the public method the initiates the iterator and calls the method.

public Perm<T>( this items : T[] , size : int ) : IE< T[] >
{
  if( items == null ) return Empty<T[]>();
  if( items.Length = 0 ) return Empty<T[]>();
  if( size < 1 ) return Empty<T[]>();
  if( size > items.Length ) size = items.Length;
  return _Perm<T>( items , size, {} , Iterator.Create( _Perm<T> ) );
}

Iterator.Create( _Perm<T> ); create the single instance of the iterator / yielder that is use through out the recursive calls.
Maybe an attribute[Iterator(Recusive:= True)] on the function, creates the "linearised" state-machine.

---

@mattwar commented on Sat Jan 17 2015

The yield foreach I was referring to was just a syntax. It did not translate to a foreach instruction and required a very different codegen for the iterator methods.

---

@theoy commented on Tue Jan 20 2015

I think it already has the VB tag, right?

Am I confused about something?

Cheers,
--Theo

From: Adam Speight [mailto:notifications@github.com]
Sent: Tuesday, January 20, 2015 3:21 PM
To: dotnet/roslyn
Cc: Theo Yaung
Subject: Re: [roslyn] Feature Request: Recursive Iterators (non-quadratic) (#15)

@theoyhttps://github.com/theoy Co-Evolution? Why no VB.net tag?

—
Reply to this email directly or view it on GitHubhttps://github.com/dotnet/roslyn/issues/15#issuecomment-70755229.

---

@AdamSpeight2008 commented on Tue Jan 20 2015

I missed the tag, then replied. Then saw the tag, so removed to comment. DOH!

---

@HaloFour commented on Tue Jan 20 2015

Didn't we discuss this in some length on the codeplex forums? If I recall while there was an alternate algorithm which made these scenarios much faster they were also found to be much slower for the common non-nested cases.

---

@weltkante commented on Fri May 01 2015

For reference, the paper about "yield foreach" with non-quadratic runtime (part of the Spec# work)

http://research.microsoft.com/en-us/projects/specsharp/iterators.pdf

---

@AlexRadch commented on Tue Jan 12 2016

I think it may be more comfortable to add yield foreach of IEnumerable as syntax sugar for loop with yield return.

IEnumerable<BinaryNode<T>> TreeWalk<T>(BinaryNode<T> curr)
{
    if (curr == null) yield break;
    yield foreach TreeWalk(curr.Left); // Syntax  sugar for loop with yield return
    yield return curr;
    yield foreach TreeWalk(curr.Rigth); // Syntax  sugar for loop with yield return
}

---

@AlexRadch commented on Tue Jan 12 2016

Here dotnet/roslyn#7630 suggested yield foreach

yield foreach TreeWalk(curr.Left); // Syntax  sugar for loop with yield return

---

@AdamSpeight2008 commented on Tue Jan 12 2016

@AlexRadch
My opinion yield foreach xs wouldn't be a good addition to the language, makes it too easy to implement the quadratic case. What do we gain by having it? 3 lines of into 1.
Whereas linearisation of the recursive iterator, would be a lot more beneficial. It would be more efficient in both runtime and memory. As it wouldn't create an additional iterator for each level of recursion.

---

@AlexRadch commented on Tue Jan 12 2016

What is linearisation of the recursive iterator? What code compiler should create? Store all local variables in arrays or where? Or your linearisation of the recursive iterator should create result array in memory?
Now each yield fuction create object where local variables stored but where should be stored local variables in linearised iterator? I think if you can create linearised code for your iterator you can create linearised code for yield foreach also.
I do not see difference in code yield foreach TreeWalk(curr.Left) and code TreeWalk(n.Left, Iterator).
Can you describe difference?
linearisation of the recursive iterator means not more than perpetuum mobile.

---

@AlexRadch commented on Tue Jan 12 2016

I think you mean that linearisation of the recursive iterator should create List<T> to store result and can be coded as

void TreeWalk<T>(BinaryNode<T> curr, IList<T> magicIterator)
{
    if (curr == null) return;
    TreeWalk(curr.Left, magicIterator);
    magicIterator.Add(curr);
    TreeWalk(curr.Rigth, magicIterator);
}

Am I right?

---

@AdamSpeight2008 commented on Tue Jan 12 2016

No. Suggested reading material ( http://www.dreamincode.net/forums/topic/332455-iterators/ ).

You should now see that each recursive call (use the foreach yield) is generates a new instance of a ienumerable and ienumerator.

It should be possible generate a single instance of ienumerable and ienumerator, that encompasses all of the subsequent recursive method calls.

The compiler should capable of building a state machine for a recursive iterator function. It could internally keep a stack of method calls, where it is in each of those methods.

Non tail-recursive would potentially result in stack overflow when evaluated. Tail-recursive (along with tail call optimisation) could potentially never return. (infinite iteration).

---

@AlexRadch commented on Tue Jan 12 2016

It should be possible generate a single instance of ienumerable and ienumerator, that encompasses **all** of the subsequent recursive method calls. is wrong!
If it is possible to do automatic with compiler for your magic iterator, it means that it is possible do the same for yield foreach also. So yield foreach can be compiled to the same magic single IEnumarable with smart tail-recursion also without creation many IEnumerable!

---

@weltkante commented on Wed Jan 13 2016

You may want to read the Microsoft research paper I linked above (which was also mentioned by mattwar) before doing handwaving and talking of magic IEnumerables. You are making too many assumptions without knowing the already presented facts.

Non-quadratic iteration (and implementation of yield foreach compiler magic) is possible without building a list beforehand, but for an efficient implementation it needs a new interface or some other way to extend the current IEnumerable iteration protocol.

Also keep in mind that the paper only presents one possible solution, I know of at least one other possible implementation which is also non-quadratic, but it also needs a different iteration protocol.

Also note that even if new interfaces are introduced they can be optional and the iteration protocol can gracefully fall back to the classic iteration for enumerators which don't implement the new interface (at the cost of the quadratic iteration we currently have).

---

@AdamSpeight2008 commented on Wed Jan 13 2016

I've read the paper again, it doesn't require a new interface.
It still utilises IEnumerable<T> and IEnumerator<T>
Done a VB implementation

---

@weltkante commented on Wed Jan 13 2016

@AdamSpeight2008 then you didn't understand the code you wrote, nor the paper

    Public Shared Function GetNestedEnumerator(e As IEnumerable(Of T))
        Dim ne = TryCast(e, NestedEnumerable(Of T))
        Return If(ne Is Nothing, New EnumeratorAdapter(Of T)(e), ne.GetNestedEnumerator)
    End Function

That's testing for the new iterator protocol. If its not present then it falls back to quadratic behavior using a simple foreach-loop.

Using a class instead of an interface to test for a feature is just an implementation detail. It's been a year or so since I read the paper so I didn't remember their proposed implementation exactly, but the concept is the same.

If you want your custom enumerables support the new protocol they need to implement an NestedEnumerable<T> instead of an IEnumerable<T>. When using the yield language feature the compiler can do it for you, but existing code needs to be recompiled and explicit implementations of IEnumerable must be manually updated.

---

@AlexRadch commented on Sat Jan 16 2016

I made hyperloop https://github.com/AlexRadch/YieldForEachDN/blob/master/Src/YieldForEachApp/Hyperloop.cs to make recursive yielded loops without quadratic runtime performance.

For example next yielded method have quadratic runtime performance because it have recursion.

        static IEnumerable<int> FromToNestedStandart(int b, int e)
        {
            if (b > e)
                yield break;
            yield return b;
            foreach(var v in FromToNestedStandart(b + 1, e))
                yield return v;
        }

To make it with liner runtime performance you should rewrite it with Hyperloop usage:

        static IEnumerable<int> FromToNestedHyperloopWithTail(int b, int e)
        {
            var hl = new Hyperloop<int>();
            hl.AddLoop(FromToNestedHyperloopWithTailLoop(b, e, hl).GetEnumerator());
            return hl;
        }

        private static IEnumerable<int> FromToNestedHyperloopWithTailLoop(int b, int e, IOldHyperloop<int> hl)
        {
            if (b > e)
                yield break;
            yield return b;
            // yield foreach replaced on hyperloop
            hl.GetHyperloop().AddTail(FromToNestedHyperloopWithTailLoop(b + 1, e, hl).GetEnumerator());
        }

AddLoop() used to replace yield foreach calls in middle recursion for more performance.
AddTail() used to replace yield foreach calls in tail recursion for little more performance than AddLoop().

---

@paulomorgado commented on Sat Jan 16 2016

I wonder if local function definitions could be used by the compiler to generate that linear state machine.

---

@weltkante commented on Sat Jan 16 2016

@paulomorgado As far as I understood it, local functions add no benefit for the compiler because its only a language feature and not an IL feature, the compiler could already generate the IL for local functions if he needed it.

Anyways, the whole reason why you need a state machine in the first place is because the control flow is non-local (you return to the caller between states) so local function definitions are unlikely to help.

---

@AlexRadch commented on Sat Jan 16 2016

To reduce quadratic performance in recursive yielded methods you should create fist loop (I called it hyperloop) and send to that hyper loop workitems without creating local loop in local loop in local loop and so on for each recursive call.

Here hyperloop code https://github.com/AlexRadch/YieldForEachDN/blob/master/Src/YieldForEachApp/Hyperloop.cs

Hyperloop execute recursive work in one loop without layered loops for each recursive call and then return control to continue execution if AddLoop() was used. For tail recursion you can use AddTail() so it does not return control.

Next code create Hyperloop and add first loop to them

        static IEnumerable<int> FromToNestedHyperloopWithTail(int b, int e)
        {
            var hl = new Hyperloop<int>();
            hl.AddLoop(FromToNestedHyperloopWithTailLoop(b, e, hl).GetEnumerator());
            return hl;
        }

Next code is like usual yielded method with recursion but it does not create layered loops for each recursive call but add loops to Hyperloop and Hyperloop execute work without layers (than speedup performance from quadratic to linear)

        static IEnumerable<int> FromToNestedHyperloopWithTail(int b, int e)
        {
            var hl = new Hyperloop<int>();
            hl.AddLoop(FromToNestedHyperloopWithTailLoop(b, e, hl).GetEnumerator());
            return hl;
        }

        private static IEnumerable<int> FromToNestedHyperloopWithTailLoop(int b, int e, IOldHyperloop<int> hl)
        {
            if (b > e)
                yield break;
            yield return b;
            // yield foreach replaced on hyperloop
            hl.GetHyperloop().AddTail(FromToNestedHyperloopWithTailLoop(b + 1, e, hl).GetEnumerator());
        }

---

@AdamSpeight2008 commented on Sat Jan 16 2016

@weltkante @paulomorgado VB has iterator / async lambda functions, they won't help in this situation. As any state information held by them is local to that lambda.

Iterator Function Foo() As IEnumerable(Of int)
  Dim lamba = Iterator Function()
                 Yield 0
                 Yield 1
                 Yield 2
                 ' These "yield" from the lambda not from the enclosing function "Foo" 
              End Function 

`

---

@paulomorgado commented on Mon Jan 18 2016

@weltkante, local functions can be reentrant and do not need a delegate invocation. There's a lot that can be done and done better with local functions then with delegates.

Of course the compiler can generate the IL. It already does.

---

@gafter commented on Mon Mar 20 2017

We are now taking language feature discussion on https://github.com/dotnet/csharplang for C# specific issues, https://github.com/dotnet/vblang for VB-specific features, and https://github.com/dotnet/csharplang for features that affect both languages.

[aluanhaddad]

This sure would be nice.
That said, current solutions involving a stack are ugly but they work.
Its probably orthogonal, but I wonder how this cross cuts with #390.

[MgSam]

This feature would of course be really nice, but when it was originally proposed on CodePlex Lucian specifically addressed Erik Meijer's paper and mentioned that implementing this would make the common case more slow. I'm guessing that's a tradeoff the team is unlikely to make.

[MillKaDe]

I would like to add two use-cases to the discussion.

Most discussions of recursive iterators simply assume that

• all collection items are yield-returned unprocessed.
• the recursive iterator just calls itself.

A simple binary tree:

class Tree {
  Tree L; // left subtree (node values smaller than V)
  int V; // node value
  Tree R; // right subtree (node values larger than V)
}

can be enumerated by this recursive iterator:

IEnumerable<int> Iterator1 (Tree t) {
  if (null == t) return;
  foreach (var vl in Iterator1 (t.L)) yield return vl;
  yield return t.V;
  foreach (var vr in Iterator1 (t.R)) yield return vr;
}

In a future version of C#, this might be shortened to:

IEnumerable<int> Iterator2 (Tree t) {
  if (null == t) return;
  yield foreach Iterator2 (t.L);
  yield return t.V;
  yield foreach Iterator2 (t.R);
}

But what if some processing of all items is required ?

1) Iterators with item processing

For example, this iterator converts each int item to string and appends
a letter indicating the items original position in the tree:

IEnumerable<string> Iterator3 (Tree t) {
  if (null == t) return;
  foreach (var vl in Iterator3 (t.L)) yield return $"{vl}L";
  yield return t.V;
  foreach (var vr in Iterator3 (t.R)) yield return $"{vr}R";
}

which converts the balanced tree: (((1)2(3))4((5)6(7)))
to the string sequence: 1LL,2L,3RL,4,5LR,6R,7RR

The new, shorter syntax needs some way to specify an optional operation for each item,
maybe as a lambda function:

IEnumerable<string> Iterator4 (Tree t) {
  if (null == t) return;
  yield foreach Iterator4 (t.L) vl => $"{vl}L";
  yield return t.V;
  yield foreach Iterator4 (t.R) vr => $"{vr}R";
}

If the lambda function is omitted, x => x is assumed instead.

2) Mutual recursive iterators

Lets add another, completly artificial requirement:
Swap the order from ascending to descending (and back) on each recursion level:

IEnumerable<string> Iterator5a (Tree t) { // ascending (L,V,R)
  if (null == t) return;
  foreach (var vl in Iterator5d (t.L)) yield return $"{vl}L";
  yield return t.V;
  foreach (var vr in Iterator5d (t.R)) yield return $"{vr}R";
}
IEnumerable<string> Iterator5d (Tree t) { // descending (R,V,L)
  if (null == t) return;
  foreach (var vr in Iterator5a (t.R)) yield return $"{vr}R";
  yield return t.V;
  foreach (var vl in Iterator5a (t.L)) yield return $"{vl}L";
}

or shorter:

IEnumerable<string> Iterator6a (Tree t) { // ascending (L,V,R)
  if (null == t) return;
  yield foreach Iterator6d (t.L)) vl => $"{vl}L";
  yield return t.V;
  yield foreach Iterator6d (t.R)) vr => $"{vr}R";
}
IEnumerable<string> Iterator6d (Tree t) { // descending (R,V,L)
  if (null == t) return;
  yield foreach Iterator6a (t.R)) vr => $"{vr}R";
  yield return t.V;
  yield foreach Iterator6a (t.L)) vl => $"{vl}L";
}

Yes, the example is idiotic. Instead assume traversing some arbitrary object graph
or serializing an expression tree or ...

So my questions are:

1. Will / shall the requested feature support item processing ?
2. Will / shall the requested feature support mutual recursion ?

[AlexRadch]

@MillKaDe #378 (comment)

So my questions are:

1. Will / shall the requested feature support **item processing** ?

2. Will / shall the requested feature support **mutual recursion** ?

1. No. It is impossible to linearise recursions with item processing.

2. It is possible if there is no item processing in recursions. Your mutual recursion can not be linearised because have item processing in recursions.

[aluanhaddad]

I think the solution in Eric Lippert's blog post is still simple enough (10 extra lines of code and can easily be generalized for any iterator) is simple enough that it really isn't necessary. It would be nice, but we can already get the optimization today.

https://blogs.msdn.microsoft.com/ericlippert/2007/12/19/immutability-in-c-part-seven-more-on-binary-trees/

[svick]

@MillKaDe I think adding item processing does not make any sense. Your code has a quadratic number of string formatting operations and I don't see how could the compiler fix that. And, if I understand it correctly, the proposed implementation would not support this.

When it comes to mutual recursion (without item processing), I think that should work just fine.

[tuespetre]

Keywords for anyone else who might come along looking for this: yield from in Python

[jhbertra]

@MillKaDe

IEnumerable<string> Iterator4 (Tree t) {
  if (null == t) return;
  yield foreach Iterator4 (t.L) vl => $"{vl}L";
  yield return t.V;
  yield foreach Iterator4 (t.R) vr => $"{vr}R";
}

This could also be accomplished with existing language features + yield foreach:

IEnumerable<string> Iterator4 (Tree t) {
  if (null == t) return;
  yield foreach (from v in Iterator4(t.L) select $"{v}L");
  yield return t.V;
  yield foreach (from v in Iterator4(t.R) select $"{v}R");
}

Or, even better:

IEnumerable<string> Iterator4 (Tree t) {
  if (null == t) return;
  yield foreach Iterator4(t.L).Select(v => $"{v}L");
  yield return t.V;
  yield foreach Iterator4(t.R).Select(v => $"{v}R");
}

If anything, an extension to LINQ query syntax might make more sense than lambdas floating around, something like

IEnumerable<string> Iterator4 (Tree t) {
  if (null == t) return;
  from v in Iterator4(t.L) yield $"{v}L";
  yield return t.V;
  from v in Iterator4(t.R) yield $"{v}R";
}

But I'm not sure even that is really necessary... the existing LINQ tools are more than adequate for manipulating IEnumerable<T>s

[jhbertra]

👍 for this feature!

[AlexRadch]

I created next suggestion for roslyn compiler dotnet/roslyn#25052

[Thaina]

We have syntax for yield return x So I think we could just have syntax yield array and it would not conflict with anything right?

[ErikSchierboom]

I would love to have this!

[chrisdunelm]

Would definitely like this functionality. And I can't imagine it's too difficult to design and implement.

[Brondahl]

There's been no actual discussion of this feature for > 3 years. Just ~20 distinct requests for it.
Is there any indication of whether this is going to get any traction?

Is it still being considered as a useful feature by the languages development team?

[CyrusNajmabadi]

@Brondahl there is no one currently championing this.

[DavidHollman]

Adding a link to this article: https://docs.microsoft.com/en-us/archive/blogs/wesdyer/all-about-iterators because I don't think it has been mentioned yet in this issue, and it has a good description of how a "yield foreach" might result in performance optimizations for some cases, which I think is what has been discussed in the above comments somewhat.

If instead of the yield foreach, there was the foreach expansion that yielded each result then the FromTo method would suffer from quadratic performance; however, with nested iterators the performance would be linear.

The article was written by Wes Dyer of Microsoft in 2007.

[znakeeye]

JS dev: "What's up C# guys! What's the yield* equivalent?
C# dev: "Hang on a second. I'll just write this epic for loop..."

F# dev: "What's up C# guys! What's the yield! equivalent?
C# dev: "Hang on a second. I'll just write this epic for loop..."

Seriously, it's just embarrassing.

[CyrusNajmabadi]

@znakeeye we've been clear. The quadratic equivalent is already there. The non-quadratic solution doesn't exist yet because no one has been able to figure out how to provide it without penalizing every existing user of foreach today.

[znakeeye]

You keep talking about quadratics, whereas some of us are just here for the syntactical sugar. There is no way syntactical sugar would automatically penalize existing users.

The quadratic equivalent was there in C# 1.0 too. Back then we also had nifty properties. Guess what happened? The syntax for getters/setters got improved. What ever happened with syntactical improvements for e.g. yield? What, we can't have syntactical improvements anymore? Did we eliminate "syntactical improvements" from the dictionary?

yield! items;
vs
foreach (var item in items) { yield return item; } 🤣

[CyrusNajmabadi]

You keep talking about quadratics, whereas some of us are just here for the syntactical sugar.

This is literally the tracking discussion for non-quadratic iteration. If you want to discuss pure syntax sugar, then the discussion for that is in: #5303

[CyrusNajmabadi]

There is no way syntactical sugar would automatically penalize existing users.

We disagree. We think it would penalize us in terms of future design flexibility.

What ever happened with syntactical improvements for e.g. yield

We don't have a design that is suitable.

yield! items;

This is not an improvement. And it falls afoul of many of the issues already specified, including potentially being highly misleading to users as to the actual behavior this would have and the performance they should expect of it. We will be very unlikely to take such a syntax as it stands a high risk of being excessively misleading which is something we do not want.

[CyrusNajmabadi]

What, we can't have syntactical improvements anymore?

We have added syntactic improvements in every version of the language shipped so far. But in all cases, we felt the net positive was there, and there weren't large negatives coming along with the change as well.

That should be an indication to you why we haven't taken anything in the yield space so far. It's because we both do not see much improvement at all, and we also see it being saddled with severe negatives at the same time. Given that, we would not take such a change as we actually think it would be a net negative for the language both in the near term (for the reasons listed above), and hte long term as it would then limit the design space even further.

[seanblue]

@CyrusNajmabadi I want to circle this conversation back to the main topic/blocker, being the performance issue. I have a couple questions, just so I have a better idea of the likelihood of this feature being added in the near-ish future.

1. Do you (or anyone else you've discussed this with) already have an idea for how to implement non-quadratic recursive iteration, but can't move forward due to time/priorities/complexity/etc.?
2. If not, based on your experience adding features to C#, does this seem unlikely to ever be solved?

[CyrusNajmabadi]

Do you (or anyone else you've discussed this with) already have an idea for how to implement non-quadratic recursive iteration,

Yes. one way to do this would be to have these recursive iterators expose a different interface that can be queried to allow them to directly participate in a callers iteration chain. However, such an interface means that normal iteration would have to query for this and would pay a price even when non-recursive iteration (the common case) was in play. For more details see: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/specsharp-iterators.pdf

Of relevant, see section 4.3 Translation of nested iterators and how it now introduces:

1. extra allocations
2. extra virtual dispatch
3. extra type checking

The issue here is not time/priorities/complexity, it's that we don't have a way currently to support recursive iteration without potentially paying a price for non-recursive iteration.

If not, based on your experience adding features to C#, does this seem unlikely to ever be solved?

It definitely seems solvable. Things like shapes might help out here as they might potentially allow us a way to have thigns like SEnumerable and SRecursiveEnumerable, and we might end up saving enough in the new approach (like no virtual, potentially no allocs) that the cost of the additional typechecks might be ok... but it's very hard to tell as those features are very much in flux.

[Brondahl]

I want to circle this conversation back to the main topic/blocker, being the performance issue.

Can you please open a different discussion for that. This issue really is targeted at "(non-quadratic)" iteration. I'm happy to have that discussed separately.

I've now raised #5503 which addresses the sugar-only ... non-quadratic aspect of the discussion 👍

I imagine that some of the people that voiced opinions on this thread, re the syntactic sugar may wish to summarise / reproduce them over there.

[lbmaian]

Should be #5303

[mburbea]

As a possible dumb solution, why not add a hint via an attribute or contextual keyword to do the special casing for recursive iterators to enable the syntax?

public recursive IEnumerable<T> TreeWalk<T>(BinaryNode<T> root)
{
       if(root is null) yield break;
       yield return foreach TreeWalk(root.Left);
       yield return root.Value;
       yield return foreach TreeWalk(root.Right);
}

Without the recursive keyword, the compiler will generate the equivalent of foreach(x in xs) yield return x;, and in the case of the keyword it could generate something akin to what's mentioned in the research paper? An analyzer could be written to check for misuse of the keyword citing the potential performance downsides.

If a new contextual keyword is unpalatable (as previous discussions have suggested), could it maybe that you can write the method with a different return type? IRecursiveEnumerable<T>. The interface would inherit from IEnumerable<T>.

[Joe4evr]

As a possible dumb solution, why not add a hint via an attribute or contextual keyword to do the special casing for recursive iterators to enable the syntax?

Because the moment someone does

var walk = TreeWalk(root).MaybeSomeLinq();
foreach (var item in walk) { /*.....*/ }

that information is lost and you're back to quadratic evaluation again.

[CyrusNajmabadi]

Sorry, i meant to respond to this yesterday. But yes, @Joe4evr hit the nail on the head. That approach might work, but only for people directly consumign the iterator directly through the method call. in other words: foreach (var item in TreeWalk(root)). However, it would be entirely non-composable. Place the call into a variable, and all we know about it is that it's an IEnumerable<...>. Similarly, use anything else that operates on IEnumerable (like any linq mehtod) and both the linq method, and the conusmer of the resultant IEnumerable will both not only not get the benefit, they'll now observe the awful perf version.

The only suitable way we've foudn that makes this work is to take the approach in the paper i listed above. However, that approach involves both allocations and runtime checks. And you now get that perf issue for all iteration everywhere. It would be a case of us adding a feature, and then literally 100% of all programs having extra overhead even if they never used that feature.

That's a very bitter pill. Imagine you have written apps with tons of iteration in them, and all of a sudden things get slower on upgrade. You didn't do anything, you're not making use of any recursive iteration, but you still have to pay the cost for it everywhere.

We do not like that, and until that thinking changes, it's effectively dead in the water here.

[AartBluestoke]

could we have :

    Interface IRecursiveEnumerable: IEnumerable{
         IRecursiveEnumerator GetRecursiveEnumerator()
    }
    
    Interface IRecursiveEnumerator: public bool MoveNext(IRecursiveEnumerator existingItr){
     ... recursive code can recieve an existing iterator to yield extra items on ...
    }

The compiler can compile the foreach for IRecursiveEnumerable differently to just a recursive enumerable.

unwraping a recursiveEnumerable to an enumerable by enumerating it is fine, as you have already unfolded the quadratic.

It feels like we could setup something where a recursiveEnumerable is convertable to a normal enumerable, and that cast contains the machinery for passing the existing enumerator down through the chain, absorbing the quadratic cost.

downsides

• It would mean that people wanting this behavior would have to opt in deliberately, so quadratic behaviour is still on the books for those who don't expect a trap.
• compiling a foreach would be slightly more expensive as there would be 2 patterns to check for - is this a recursiveEnumerable, is this a normal enumerable
• runtime cost of the conversion from recursive to normal enumerable at whatever boundary the coder ends up (probably the next linq call), but this is still much cheaper than the quadratic cost before, so probably reasonable.

Thoughts?

[AartBluestoke]

• Is it viable to determine whether a method is recursive or not?

Isn't this pretty much the same question as solving the Halting Problem?
@Joe4evr not if we require people wanting a recursive Enumeration to flag those functions themselves.

[lbmaian]

Assuming that the compiler can distinguish between recursive and non-recursive iterators (whether through attribute or interface or whatever), and that yield foreach only works on non-recursive iterators, to preclude the possibility of quadratic runtime, shouldn't iterators be assumed to be recursive by default (and thus ineligible for yield foreach)? That is, marking an iterator as non-recursive needs to be "opt-in" (and thus eligible for yield foreach) rather than "opt-out"?

[AartBluestoke]

what i was suggesting was a way for efficient recursive iteration to be used within yield foreach, be providing for a place where recursive iteration could be explicitly given an efficient implantation.

it is the efficient implementation that is opt-in. you can still write inefficient quadratic iterators, but there is now a path for the implementer of that function (not the consumer) to provide an efficient implementation.

[lbmaian]

Sure, but this statement from Cyrus:

We would not want any feature that gives hte appearance of not being that expensive actually be that expensive. In other words, it's reasonable for people to assume that yield return foreach x; would be efficient and would not have a quadratic perf cliff you could fall off of. Adding it and having that cliff would nto be desirable.

strongly suggests to me that opt-in efficient implementation is insufficient, that yield foreach must not result in quadratic runtime due to recursive iteration. Since iterators currently have no restriction on recursion, doesn't that mean the compile-time indicator for non-recursive iteration for yield foreach eligibility must be opt-in?

[Brondahl]

Is it viable to determine whether a method is recursive or not?

Isn't this pretty much the same question as solving the Halting Problem?

not if we require people wanting a recursive Enumeration to flag those functions themselves.

Perhaps I've mis-understood / mis-expressed something.

I think the exact question we're considering is "does this method (which uses the return yield operator) call itself, either directly or transitively via other methods?"

In which case, it's not the Halting Problem, its just "is there a cyclic loop in this finite graph, passing through this point".

• A codebase is a finite collection of methods (or props, or anonymous functions, etc. etc.).
• Each method is a node in a directed graph where the edges represent "this method calls that method".
• A recursive method is one which ultimately calls itself again, which represents a cycle in the graph.

I would be a bit surpised if the compiler doesn't already construct that graph, and I assume there are efficient algorithms for finding cyclic loops in graphs already exist. (But even if not, in practice, I suspect brute forcing it would be unpleasant, but not actually that computationally expensive, since the graphs aren't going to be that large or have that many connections from any given node.)

[AlexRadch]

I created the DrNet.Hyperloop library https://github.com/AlexRadch/DrNet.Hyperloop to rewrite recursive iterators to non-quadratic recursive iterators with minimal code refactoring.

The library has benchmarks to show that quadratic complexity was decreased to linear complexity. Also, those benchmarks are examples of code refactoring.

I am planning to create a source generator with such automatic code refactoring.

If you have any suggestions or comments on the library, please write about it. I will also be appreciated in any help to create the documentation in good English.

[AartBluestoke]

this type of thing was what i was thinking of above - wrap the potentially quadratic recursive code in an correct handler, presenting this linearly enumerable data source to any downstream consumers. It requires anyone wanting to work around quadratic behaviour to "opt in" to the better behaviour. It should be reasonably easy to make a diagnostic for directly recursive programs suggesting that IEnumerable f(){ ... f();} should instead be a IRecursiveEnumerable.

[AlexRadch]

I created the DrNet.Hyperloop NuGet package https://www.nuget.org/packages/DrNet.Hyperloop/.

[oliver-unifii]

Is this on a roadmap ? recursive yields are very common when processing tree structures such (e.g. Json)

Both JS and F# seem to have a good solution.

[hughesjs]

Would this proposal capture yield return all anotherEnumerable behaviour rather than just specifically recursive enumerables?

Similar to what's being discussed here: https://stackoverflow.com/questions/78438765/multi-yield-mechanism-in-c-sharp?noredirect=1#comment138285851_78438765

[hez2010]

With .. operator being introduced in C#, how about:

yield return ..list;

[HaloFour]

.. outside of collection literals is for ranges, not spreads. Either way, the syntax was never the issue with this feature, it was the behavior.

[hez2010]

list is a collection, not an integer nor an index, so it can be interpreted as a spread operator, not a range operator.

[HaloFour]

See: #8053 (reply in thread)

Either way, the syntax isn't the problem with this proposal.

[aeroelec]

I don't understand why this has not been adopted. All that's needed to operate a yield each is an execution stack, which already exists to operate existing yield operators. When yield each is compiled, it bypasses containering of IEnumerable (i.e. creating new IEnumerable and associated MoveNext, etc. methods), directly calling underlying iterator code just like calling any other function, momentarily breaking at yield return or going up call stack at end of function or yield break. If yield each is being used for non-iterator, like array, it would compile to for loop to create iterator locally. This optimizes execution while also keeping the code easy to read/understand.

As an example, looking at op's BinaryNode, it's much easier to read and understand the result of using yield each than to read the optimized version that directly uses a stack to get the same result, using yield return (it would be even worse if yield operator didn't exist).

Easy to read, but is very inefficient

public IEnumerable<T> TreeWalk<T>(BinaryNode<T> tree)
{
    if (tree == null) yield break;
    foreach (T item in TreeWalk(tree.Left)) yield return item;
    yield return tree.Value;
    foreach (T item in TreeWalk(tree.Right)) yield return item;
}

Easy to read and can be optimized by compiler

public IEnumerable<T> TreeWalk<T>(BinaryNode<T> tree)
{
    if (tree == null) yield break;
    yield each TreeWalk(tree.Left);
    yield return tree.Value;
    yield each TreeWalk(tree.Right);
}

Hard to read, but is optimized

public IEnumerable<T> TreeWalk<T>(BinaryNode<T> tree)
{
    var stack = new Stack<BinaryNode<T>>();
    if (tree == null) yield break;
    for ( ; ; )
    {
        if (tree.Left != null)
        {
            stack.Push(tree);
            tree = tree.Left;
        }
        else
        {
            for ( ; ; )
            {
                yield return tree.Value;
                if (tree.Right != null)
                {
                    tree = tree.Right;
                    break;
                }
                else if (stack.Count > 0)
                {
                    tree = stack.Pop();
                }
                else
                {
                    yield break;
                }
            }
        }
    }
}

[ranma42]

If you do basic linq work at each level, you would still be linear;

How?

For example, this would be linear (in the output size):

public static IEnumerable<(T,U)> Cartesian(IEnumerable<T> a, IEnumerable<T> b)
{
    foreach (var x in a)
        yield each b.Select(y => (x, y));
}

I agree that in the recursive case, most reasonable operations would end up compounding enumerables:

public IEnumerable<T> GetEnumerator()
{
    yield each Left.Where(x => x != null);
    yield each Right.Where(x => x != null);
}
// or
public IEnumerable<T> GetEnumerator()
{
    yield each Left.Union(Right);
}

eventually leading to quadratic scaling (regardless of loops).

if you do something like a .Where on a recursive call, then there's no way to stitch the nested enumerator to the higher enumerator 'stack'.

Doing operations on recursive calls is exactly what I was referring to as "compounding" (opposed to "basic").

This definitely feels like the usual issues you hit with loops vs recursive (tail) calls:

• recursion can sometimes express a problem in a very straightforward way, but if it strays off the TCO "golden path", it can cause worse (stack space) complexity
• loops are sometimes more complex to express, but very explicit and leave more control into the hands of the developer

[CyrusNajmabadi]

This is a different issue. It's not the stack space per se (that's actually not too bad). It's the quadratic performance. :)

Regardless, all of the above reiterates the points and problems we've brought up multiple times in the discussion. There is no known solution here, and the proposals for narrow slices of it both come with drawbacks, or are likely to not satisfy users (due to restrictions), or will cause problems if given without restrictions.

So far, no new data has been shown to change anything here. All the proposed solutions are in line with the solutions we have investigated in the past. But none address the problems that are causing an impasse now.

Note: we are not opposed to a compiler-onbly feature that optimize some cases of direct, non-virtual, recursion. But that needs no language work and is external to teh csharplang repo.

[ranma42]

This is a different issue. It's not the stack space per se (that's actually not too bad). It's the quadratic performance. :)

I know, to me the similarity is that a more inconvenient syntax (loop) can be preferred as it is more explicit and prevents changes in complexity with minor changes to the code.

Regardless, all of the above reiterates the points and problems we've brought up multiple times in the discussion. There is no known solution here, and the proposals for narrow slices of it both come with drawbacks, or are likely to not satisfy users (due to restrictions), or will cause problems if given without restrictions.

Sorry, I had misunderstood the problem; given the recent posts I thought it was mainly an issue of getting an interface that has adequate compatibility/performance and not of avoiding pitfalls when developers mix this syntax with other C# (/.NET) features.
This is indeed a very different problem ("if there is no loop, devs expect linear complexity, even if they keep working on operations that are more and more complex/deep").

So far, no new data has been shown to change anything here. All the proposed solutions are in line with the solutions we have investigated in the past. But none address the problems that are causing an impasse now.

Note: we are not opposed to a compiler-onbly feature that optimize some cases of direct, non-virtual, recursion. But that needs no language work and is external to teh csharplang repo.

Yes, simple cases can probably be handled in the lowering of iterators; this would even make it possible to do it on the existing foreach() yield syntax 🤔
Note that this might introduce a footgun like that in classic TCO: as long as you iterate in a certain way, you get linear scaling, but a minor change regresses it to quadratic.

public static IEnumerable<int> MaybeLinearNumbers(int start)
{
    yield return start;
    foreach (var x in MaybeLinearNumbers(start + 1)) yield return x;
}

public static IEnumerable<int> QuadraticNumbers()
{
    yield return 0;
    foreach (var x in QuadraticNumbers().Select(x => x + 1)) yield return x;
}

Do you think this would still be acceptable? (as in both implementations are at the risk of being quadratic; if the first one got optimized to linear by the compiler, you lucked out, but do not rely on that in general)
In that case, I guess the right place to look into is the IteratorRewriter and related classes in Roslyn.

[aeroelec]

public static IEnumerable<int> QuadraticNumbers()
{
    yield return 0;
    foreach (var x in QuadraticNumbers().Select(x => x + 1)) yield return x;
}

This problem got me thinking on a higher level - can JIT optimize lambda functions? Say we have the lambda function var A = x => x+1; and we set var B = x => A(A(x));. Can JIT optimize this to B = x => x+2? If yes, then the idea of INestedIterator could be modified to include Func<T, (U Result, bool Accept)> filter that returns Result if Accept is true, otherwise it moves iterator again for next. This would enable Linq's Where and Select to add it's function to prior INestedIterator's filter, enabling linear execution by operating filter on Current before returning Result as next item. This filter is passed to deeper nested iterators so Where/Select operation is not lost with non-walking execution.

For example, .Where given f = Func<T,bool> would modify filter to:

if (filter == null)
{
    new_filter = x => (x, f(x));
}
else
{
    new_filter = x => (filter(x).Result, filter(x).Accept && f(filter(x).Result));
}

and .Select given f = Func<T,U> would modify filter to:

if (filter == null)
{
    new_filter = x => (f(x), true);
}
else
{
    new_filter = x => filter(x).Accept ? (f(filter(x).Result), true) : (default, false);
}

If JIT can optimize lambda functions, then even something as nasty as yield each QuadraticNumbers().Select(x => x + 1); could be linearized. If not, status-quo it is.

[CyrusNajmabadi]

@aeroelec at present, the jit exposes no functionality for that. Any discussions on that topic would need to be over at dotnet/runtime. If jit is able to change how they themselves process and optimize lambdas and iterators that could change things.

[znakeeye]

10 years later, I still don't understand the problem. This is just syntactical sugar! A no-brainer. Implement it already.

If the compiler can handle this:

foreach (var item in items)
{
    yield return item;
}

Sure it can also handle a shortened version:

yield each items;

Same IL. Done.

[HaloFour]

10 years later, I still don't understand the problem. This is just syntactical sugar! A no-brainer. Implement it already.

The problem is whether or not it's worth doing, and so far it seems the language team does not believe it is.

[CyrusNajmabadi]

, I still don't understand the problem

The reason was given directly to you several times in the past. Definitely look at the other threads where we discussed it with you on other occasions :-)

[CyrusNajmabadi]

This is just syntactical sugar!

You state that as a positive. That's actively bad here. Sugar should be a good thing. Here we think the sugar is actively making things worse.

Specifically, it's good that quadratic behavior looks quadratic. Mapping quadratic behavior be hidden behind sugar is a bad thing.

[hughesjs]

This is just syntactical sugar!

So are the vast majority of C# language features developed in the last 5 years.

[iam3yal]

@hughesjs You should probably double check history because it's not the case... There are good reasons behind the introduction of syntactical sugar for many features, as it often provides a more productive or powerful alternative to the previous form, with no downsides.

[mattwar]

Here is a gist of a document I presented to C# LDM on this issue a few years ago.
Exploring Non-Quadratic Iterators

The final source code created during the exploration is here:
https://github.com/mattwar/Chunky

[ranma42]

@mattwar IIUC the issue (regardless of the implementation of yield foreach) is that users might inadvertently build up linear-sized iterables as follows:

public static IEnumerable<int> Numbers()
{
    yield return 0;
    yield foreach Numbers().Select(x => x + 1);
}

i.e. accumulate more and more + 1 projections.
This is considered undesirable, because even though there is no explicit looping, the resulting iterator has quadratic complexity.

[mattwar]

I added my document because I go into extensive detail describing the problem, and for the most part the solution. As your example shows, though, there will never be enough of a solution to catch all hidden captures of quadratic behavior.

[GabeSchaffer]

In the "async2" experiment (https://github.com/dotnet/runtimelab/blob/feature/async2-experiment/docs/design/features/runtime-handled-tasks.md), a team explored the possibility of using the runtime to generate async state machines. Is it possible to do something similar with iterators, allowing the runtime to produce iterators that aren't quadratic when used in a nested context and iterators that don't have additional overhead when used in a normal context?

[CyrusNajmabadi]

Someone on the runtime would have to figure that out :)

[oliver-unifii]

Can someone shed some light on how this is implemented in F# and JS? Or do they suffer from the same issue and it's just syntax sugar?

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/yield*
https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/sequences#the-yield-keyword

These are incredibly useful in practice.

[ranma42]

👍 I'll extend https://github.com/ranma42/csharp-recursive-iter/blob/main/README.md to explicitly handle these points.

Note that, assuming that

• we cannot trust the developer to recognize that this would result in quadratic scaling even if there is no explicit loop (the "looping" is implicit in the recursion), and
• we don't want to forbid patterns such as the previous one
  I don't have a safe way to handle stuff like

public static IEnumerable<int> Numbers()
{
    yield return 0;
    yield foreach Numbers().Select(x => x + 1);
}

OTOH I wonder if it would be sufficient to use a "scary" name for the adaptor and leave it explicit 🤔
What I mean is that assuming that yield foreach only accepts INestedEnumerables, Numbers would become:

public static INestedEnumerable<int> BadNumbers()
{
    yield return 0;

    // this would not compile as the return type of Select is not INestedEnumerable
    // yield foreach Numbers().Select(x => x + 1);

    // this compiles, but is explicit about the risk of bad scaling
    yield foreach UnsafeAdaptorThatMightHideQuadraticScaling(BadNumbers().Select(x => x + 1));
}

Compare it to:

public static INestedEnumerable<int> OkNumbers(int start = 0)
{
    yield return start;
    yield foreach OkNumbers(start + 1);
}

in which no adaptor is used and the scaling is the "obvious" one (constant time per element).

I'll try to think more about this and ideally I'll also update the repo with the TODOs I left (experiments with Concat & co), but I might not have time to do so until the weekend 😇

[iam3yal]

@ranma42 Hey, I’m having trouble understanding how your approach addresses the concerns that @CyrusNajmabadi has raised multiple times. Could you please go through each point and clarify how your solution resolves the issues? It seems there are differences between your approach and the points he made and yet you wrote the following:

I have shown an implementation that shows:
good performance (on par with the existing one)
allows simple nesting with linear behavior
could be integrated in a way that is compatible with existing iterables
(if used only on methods containing a yield each) would guarantee no regressions

[ranma42]

@ranma42 Hey, I’m having trouble understanding how your approach addresses the concerns that @CyrusNajmabadi has raised multiple times. Could you please go through each point and clarify how your solution resolves the issues?

@iam3yal I added a file describing a possible implementation strategy and why it would address the concerns raised by @CyrusNajmabadi. In the document I quote the requirements mentioned in #378 (reply in thread) and also tackle the issue around DX/intent/pitfalls around unintentional quadratic scaling.

@CyrusNajmabadi I linked your message in that document and I initially quoted that part literally, but eventually I modified it a little (mostly case and layout), in a way which hopefully conveys the very same contents/requirements. If I misunderstood something, I am happy to correct the file 😇 both in the introduction where I enumerate the requirements and in the following sections where I try to explain why (I believe that) they are met.

Similarly, if there are further requirements or concerns, I will try to understand if they can be handled and (regardless) I would like to add them to the document so that they can be identified as roadblocks

[AlexRadch]

@iam3yal I added a file describing a possible implementation strategy and why it would address the concerns raised by @CyrusNajmabadi.

Adding a stack of iterators to the F# implementation will solve common cases, including virtual methods. Of course, it won't work with Linq, since Linq doesn't support an extended interface for optimizing recursion between enumerators. I have already written them a proposal to add a stack of iterators.

[ranma42]

@AlexRadch IIUC when you mention "virtual methods" or "virtual recursion" you are referring to accepting all types of IEnumerables in yield each (regardless of their provenance) and being linear (at least on) those that respect appropriate constraints (such as not growing the "depth" of the expression as in the Numbers example). Is that correct?

Note that in the implementation strategy document I intentionally avoid detailing the translation and/or the interface; instead I reason about a higher level that I believe would apply to several possible implementations.

[aradalvand]

Now that System.Linq.Async has made it into the standard library, this language feature is more relevant than ever.

[timcassell]

What makes async Linq more relevant than regular Linq?

[aradalvand]

I'd want this feature for both IEnumerable<T>, and IAsyncEnumerable<T>. I'm not sure what you're talking about @timcassell.

[StephenCleary]

For others dealing with the massive link rot, here's the current locations of some of the original sources discussing the performance problem:

• 2004-03-23 Recursive Iterators (aka Perf killers)
• 2004-04-07 Recursive Iterators made Iterative
• 2005-07-26 Iterators revisited: proof rules and implementation (pdf)
• 2007-03-22 All About Iterators
• 2007-12-18 Immutability in C# Part Seven: More on Binary Trees