IO refactor

[louthy]

IO

I have refactored the IO<A> monad, which is used to underpin all side-effects in language-ext. The API surface is unchanged, but the inner workings have been substantially refactored. Instead of the four concrete implementations of the abstract IO<A> type (IOPure<A>, IOFail<A>, IOSync<A>, and IOAsync<A>), there is now a 'DSL' of operations deriving from IO<A> which are interpreted in the Run and RunAsync methods (it now works like a Free monad).

The DSL is also extensible, so if you have some behaviours you'd like to embed into the IO interpreter than you can derive from one of these four types.

The benefits of the refactored approach are:

• Fixes this issue
• Should have more performance (although not tested fully)
• Extensible DSL
• Can support infinite recursion

The last one is a big win. Previously, infinite recursion only worked in certain scenarios. It should work for all scenarios now.

Take a look at this infinite-loop sample:

static IO<Unit> infinite(int value) =>
    from _ in writeLine($"{value}")
    from r in infinite(value + 1)
    select r;

The second from expression recursively calls infinite which would usually blow the stack. However, now the stack will not blow and this example would run forever*.

*All LINQ expressions require a trailing select ..., that is technically something that needs to be invoked after each recursive call to infinite. Therefore, with the above implementation, we get a space-leak (memory is consumed for each loop).

To avoid that when using recursion in LINQ, you can use the tail function:

static IO<Unit> infinite(int value) =>
    from _ in writeLine($"{value}")
    from r in tail(infinite(value + 1))
    select r;

For other monads and monad-transformers that lift the IO monad into their stacks, you can use the tailIO function. This should bring infinite recursion to all types that use the IO monad (like Eff for example).

What tail does is says "We're not going run the select at all, we'll just return the result of infinite". That means we don't have to keep track of any continuations in memory. It also means you should never do extra processing in the select, just return the r as-is and everything will work: infinite recursion without space leaks.

tail is needed because the SelectMany used by LINQ has the final Func<A, B, C> argument to invoke after the Func<A, IO<B>> monad-bind function (which is the recursive one). The Func<A, B, C> is the trailing select and is always needed. It would be good if C# supported a SelectMany that is more like a regular monadic-bind and recognised the pattern of no additional processing in select, but we have to put up with the hand we're dealt.

Not doing work after a tail-call is a limitation of tail-recursion in every language that supports it. So, I'm OK being explicit about it with LINQ. Just be careful to not do any additional processing or changing of types in the select.

Note, if you don't use LINQ and instead use a regular monad-bind operation, then we don't need the tail call at all:

static IO<Unit> infinite(int value) =>
    writeLine($"{value}")
       .Bind(_ => infinite(value + 1));

That will run without blowing the stack and without space-leaks. Below is a chart of memory-usage after 670 million iterations:

What's nice about looking a the memory-graph is that, not only is it flat in terms of total-usage (around 26mb), it only ever uses the Gen 0 heap. This is something I've always said about functional-programming. We may we generate a lot of temporary objects (lambdas and the like), but they rarely live long enough to cause memory pressures in higher generations of the heap. Even though this is a very simple sample and you wouldn't expect that much pressure, the benefits of most of your memory usage being in Gen 0 is that you're likely using memory addresses already cached by the CPU -- so the churn of objects is less problematic that is often posited.

StreamT made experimental

I'm not sure how I'm going to fix this issue, so until I have a good idea, StreamT will be marked as [Experimental]. To use it, add this to the top of a file:

#pragma warning disable LX_StreamT

Conclusion

This was a pretty large change, so if you're using the beta in production code, please be wary of this release. And, if you spot any issues, please let me know.

---

This discussion was created from the release IO refactor.