Feature Request: Recursive Iterators (non-quadratic)

[AdamSpeight2008]

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]

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

[mattwar]

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]

@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]

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]

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//issues/15#issuecomment-70755229.

[AdamSpeight2008]

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

[HaloFour]

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]

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]

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]

Here #7630 suggested yield foreach

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

[AdamSpeight2008]

@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]

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]

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]

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]

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]

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]

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]

@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]

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]

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

[weltkante]

@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]

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]

@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]

@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]

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.

[gafter]

Issue moved to dotnet/csharplang #378 via ZenHub