Just when is a stackoverflow fair and sensible?

Question

Code updated

For fixing the bug of a filtered Interminable, the following code is updated and merged into original:

public static bool IsInfinity(this IEnumerable x) {
    var it=
        x as Infinity??((Func<object>)(() => {
            var info=x.GetType().GetField("source", bindingAttr);
            return null!=info?info.GetValue(x):x;
        }))();

    return it is Infinity;
}

bindingAttr is declared a constant.

---

• Summary

  I'm trying to implement an infinite enumerable, but encountered something seem to be illogical, and temporarily run out of idea. I need some direction to complete the code, becoming a semantic, logical, and reasonable design.

• The whole story

  I've asked the question a few hours ago:

  Is an infinite enumerable still "enumerable"?

  This might not be a good pattern of implementation. What I'm trying to do, is implement an enumerable to present infinity, in a logical and semantic way(I thought ..). I would put the code at the last of this post.

  The big problem is, it's just for presenting of infinite enumerable, but the enumeration on it in fact doesn't make any sense, since there are no real elements of it.

  So, besides provide dummy elements for the enumeration, there are four options I can imagine, and three lead to the StackOverflowException.

  1. Throw an InvalidOperationException once it's going to be enumerated.

     public IEnumerator<T> GetEnumerator() {
         for(var message="Attempted to enumerate an infinite enumerable"; ; )
             throw new InvalidOperationException(message);
     }
     

  2. and 3. are technically equivalent, let the stack overflowing occurs when it's really overflowed.

     public IEnumerator<T> GetEnumerator() {
         foreach(var x in this)
             yield return x;
     }
     

     public IEnumerator<T> GetEnumerator() {
         return this.GetEnumerator();
     }
     

  3. (described in 2)

  4. Don't wait for it happens, throw StackOverflowException directly.

     public IEnumerator<T> GetEnumerator() {
         throw new StackOverflowException("... ");
     }
     

The tricky things are:

If option 1 is applied, that is, enumerate on this enumerable, becomes an invalid operation. Isn't it weird to say that this lamp isn't used to illuminate(though it's true in my case).

If option 2 or option 3 is applied, that is, we planned the stack overflowing. Is it really as the title, just when stackoverflow is fair and sensible? Perfectly logical and reasonable?

The last choice is option 4. However, the stack in fact does not really overflow, since we prevented it by throwing a fake StackOverflowException. This reminds me that when Tom Cruise plays John Anderton said that: "But it didn't fall. You caught it. The fact that you prevented it from happening doesnt change the fact that it was going to happen."

Some good ways to avoid the illogical problems?

---

The code is compile-able and testable, note that one of OPTION_1 to OPTION_4 shoule be defined before compile.

• Simple test

  var objects=new object[] { };
  Debug.Print("{0}", objects.IsInfinity());
  var infObjects=objects.AsInterminable();
  Debug.Print("{0}", infObjects.IsInfinity());
  

• Classes

  using System.Collections.Generic;
  using System.Collections;
  using System;
  
  public static partial class Interminable /* extensions */ {
      public static Interminable<T> AsInterminable<T>(this IEnumerable<T> x) {
          return Infinity.OfType<T>();
      }
  
      public static Infinity AsInterminable(this IEnumerable x) {
          return Infinity.OfType<object>();
      }
  
      public static bool IsInfinity(this IEnumerable x) {
          var it=
              x as Infinity??((Func<object>)(() => {
                  var info=x.GetType().GetField("source", bindingAttr);
                  return null!=info?info.GetValue(x):x;
              }))();
  
          return it is Infinity;
      }
  
      const BindingFlags bindingAttr=
          BindingFlags.Instance|BindingFlags.NonPublic;
  }
  
  public abstract partial class Interminable<T>: Infinity, IEnumerable<T> {
      IEnumerator IEnumerable.GetEnumerator() {
          return this.GetEnumerator();
      }
  
  #if OPTION_1
      public IEnumerator<T> GetEnumerator() {
          for(var message="Attempted to enumerate an infinite enumerable"; ; )
              throw new InvalidOperationException(message);
      }
  #endif
  
  #if OPTION_2
      public IEnumerator<T> GetEnumerator() {
          foreach(var x in this)
              yield return x;
      }
  #endif
  
  #if OPTION_3
      public IEnumerator<T> GetEnumerator() {
          return this.GetEnumerator();
      }
  #endif
  
  #if OPTION_4
      public IEnumerator<T> GetEnumerator() {
          throw new StackOverflowException("... ");
      }
  #endif
  
      public Infinity LongCount<U>(
          Func<U, bool> predicate=default(Func<U, bool>)) {
          return this;
      }
  
      public Infinity Count<U>(
          Func<U, bool> predicate=default(Func<U, bool>)) {
          return this;
      }
  
      public Infinity LongCount(
          Func<T, bool> predicate=default(Func<T, bool>)) {
          return this;
      }
  
      public Infinity Count(
          Func<T, bool> predicate=default(Func<T, bool>)) {
          return this;
      }
  }
  
  public abstract partial class Infinity: IFormatProvider, ICustomFormatter {
      partial class Instance<T>: Interminable<T> {
          public static readonly Interminable<T> instance=new Instance<T>();
      }
  
      object IFormatProvider.GetFormat(Type formatType) {
          return typeof(ICustomFormatter)!=formatType?null:this;
      }
  
      String ICustomFormatter.Format(
          String format, object arg, IFormatProvider formatProvider) {
          return "Infinity";
      }
  
      public override String ToString() {
          return String.Format(this, "{0}", this);
      }
  
      public static Interminable<T> OfType<T>() {
          return Instance<T>.instance;
      }
  }
  

Answer 1

public IEnumerator<T> GetEnumerator()
{
    while (true)
        yield return default(T);
}

This will create an infinite enumerator - a foreach on it will never end and will just continue to give out the default value.

Note that you will not be able to determine IsInfinity() the way you wrote in your code. That is because new Infinity().Where(o => o == /*do any kind of comparison*/) will still be infinite but will have a different type.

Answer 2

As mentioned in the other post you linked, an infinite enumeration makes perfectly sense for C# to enumerate and there are an huge amount of real-world examples where people write enumerators that just do never end(first thing that springs off my mind is a random number generator).

So you have a particular case in your mathematical problem, where you need to define a special value (infinite number of points of intersection). Usually, that is where I use simple static constants for. Just define some static constant IEnumerable and test against it to find out whether your algorithm had the "infinite number of intersection" as result.

To more specific answer your current question: DO NOT EVER EVER cause a real stack overflow. This is about the nastiest thing you can do to users of your code. It can not be caught and will immediately terminate your process(probably the only exception is when you are running inside an attached instrumenting debugger).

If at all, I would use NotSupportedException which is used in other places to signal that some class do not support a feature(E.g. ICollections may throw this in Remove() if they are read-only).

Answer 3

If I understand correctly -- infinite is a confusing word here. I think you need a monad which is either enumerable or not. But let's stick with infinite for now.

I cannot think of a nice way of implementing this in C#. All ways this could be implemented don't integrate with C# generators.

With C# generator, you can only emit valid values; so there's no way to indicate that this is an infinite enumerable. I don't like idea of throwing exceptions from generator to indicate that it is infinite; because to check that it is infinite, you will have to to try-catch every time.

If you don't need to support generators, then I see following options :

1. Implement sentinel enumerable:

   public class InfiniteEnumerable<T>: IEnumerable<T> {
       private static InfiniteEnumerable<T> val;
   
       public static InfiniteEnumerable<T> Value {
           get {
               return val;
           }
       }
   
       public IEnumerator<T> GetEnumerator() {
           throw new InvalidOperationException(
               "This enumerable cannot be enumerated");
       }
   
       IEnumerator IEnumerable.GetEnumerator() {
           throw new InvalidOperationException(
                "This enumerable cannot be enumerated");
       }
   }
   

   Sample usage:

   IEnumerable<int> enumerable=GetEnumerable();
   
   if(enumerable==InfiniteEnumerable<int>.Value) {
       // This is 'infinite' enumerable.
   }
   else {
       // enumerate it here.
   }
   

2. Implement Infinitable<T> wrapper:

   public class Infinitable<T>: IEnumerable<T> {
       private IEnumerable<T> enumerable;
       private bool isInfinite;
   
       public Infinitable(IEnumerable<T> enumerable) {
           this.enumerable=enumerable;
           this.isInfinite=false;
       }
   
       public Infinitable() {
           this.isInfinite=true;
       }
   
       public bool IsInfinite {
           get {
               return isInfinite;
           }
       }
   
       public IEnumerator<T> GetEnumerator() {
           if(isInfinite) {
               throw new InvalidOperationException(
                   "The enumerable cannot be enumerated");
           }
   
           return this.enumerable.GetEnumerator();
       }
   
       IEnumerator IEnumerable.GetEnumerator() {
           if(isInfinite) {
               throw new InvalidOperationException(
                    "The enumerable cannot be enumerated");
           }
   
           return this.enumerable.GetEnumerator();
       }
   }
   

   Sample usage:

   Infinitable<int> enumerable=GetEnumerable();
   
   if(enumerable.IsInfinite) {
       // This is 'infinite' enumerable.
   }
   else {
       // enumerate it here.
       foreach(var i in enumerable) {
       }
   }
   

Answer 4

Infinite sequences may be perfectly iterable/enumerable. Natural numbers are enumerable and so are rational numbers or PI digits. Infinite is the opposite of finite, not enumerable.

The variants that you've provided don't represent the infinite sequences. There are infinitely many different infinite sequences and you can see that they're different by iterating through them. Your idea, on the other hand, is to have a singleton, which goes against that diversity.

If you have something that cannot be enumerated (like the set of real numbers), then you just shouldn't define it as IEnumerable as it's breaking the contract. If you want to discern between finite and infinite enumerable sequences, just crate a new interface IInfiniteEnumerable : IEnumerable and mark infinite sequences with it.

Interface that marks infinite sequences

public interface IInfiniteEnumerable<T> : IEnumerable<T> {
}

A wrapper to convert an existing IEnumerable<T> to IInfiniteEnumerable<T> (IEnumerables are easily created with C#'s yield syntax, but we need to convert them to IInfiniteEnumerable )

public class InfiniteEnumerableWrapper<T> : IInfiniteEnumerable<T> {
    IEnumerable<T> _enumerable;

    public InfiniteEnumerableWrapper(IEnumerable<T> enumerable) {
        _enumerable = enumerable;
    }

    public IEnumerator<T> GetEnumerator() {
        return _enumerable.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return _enumerable.GetEnumerator();
    }
}

Some infinity-aware routines (like calculating the sequence length)

//TryGetCount() returns null if the sequence is infinite
public static class EnumerableExtensions {
    public static int? TryGetCount<T>(this IEnumerable<T> sequence) {
        if (sequence is IInfiniteEnumerable<T>) {
            return null;
        } else {
            return sequence.Count();
        }
    }
}

Two examples of sequences - a finite range sequence and the infinite Fibonacci sequence.

public class Sequences {
    public static IEnumerable<int> GetIntegerRange(int start, int count) {
        return Enumerable.Range(start, count);
    }

    public static IInfiniteEnumerable<int> GetFibonacciSequence() {
        return new InfiniteEnumerableWrapper<int>(GetFibonacciSequenceInternal());
    }

    static IEnumerable<int> GetFibonacciSequenceInternal() {
        var p = 0;
        var q = 1;
        while (true) {
            yield return p;
            var newQ = p + q;
            p = q;
            q = newQ;
        }
    }
}

A test app that generates random sequences and tries to calculate their lengths.

public class TestApp {
    public static void Main() {
        for (int i = 0; i < 20; i++) {
            IEnumerable<int> sequence = GetRandomSequence();
            Console.WriteLine(sequence.TryGetCount() ?? double.PositiveInfinity);
        }
        Console.ReadLine();
    }

    static Random _rng = new Random();
    //Randomly generates an finite or infinite sequence
    public static IEnumerable<int> GetRandomSequence() {
        int random = _rng.Next(5) * 10;
        if (random == 0) {
            return Sequences.GetFibonacciSequence();
        } else {
            return Sequences.GetIntegerRange(0, random);
        }
    }
}

The program output something like this:

20
40
20
10
20
10
20
Infinity
40
30
40
Infinity
Infinity
40
40
30
20
30
40
30