Functional evaluation of conditionals in C#?

Question

In functional programming a statement like if (a || b) can be evaluated in parallel by default, since we don't make any assumptions about the evaluation order due to referential transparency. Is there any easy way to introduce this type of functional parallelism for conditionals in C#?

For instance in C# we can introduce parallelism over for loops easily using Parallel.For(), so I'm wondering if there's something similar to conditionals?

I'm trying to bring some of the benefits from functional programming to the way I write C#.

Answer 1

While possible in theory, I haven't heard about any language that supports this with syntax or simple APIs (but I also only know a handful of languages). As you may know, Haskell is often considered the gold standard of FP, but Boolean expressions in Haskell are just normal, short-circuiting expressions, just like they are in C#.

ghci> a = True
ghci> b = undefined
ghci> (a || b)
True

Here, b is undefined which means that actually trying to evaluate it will throw an exception:

ghci> b
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries\base\GHC\Err.hs:74:14 in base:GHC.Err
  undefined, called at <interactive>:2:5 in interactive:Ghci2

But as you can see in the top example, (a || b) evaluates to True because it short-circuits.

In fact, Haskell is, in general, automatically short-circuiting because of lazy evaluation, but most languages have short-circuiting Boolean expressions.

That's already a good optimization. If you have one cheap and one expensive Boolean expression, put the cheap one first.

So how often do you need more optimization than that? Particularly in the context of referentially transparent functions. Usually, expensive operations are the ones involving I/O.

Not that having two (or more) expensive, but referentially transparent Boolean expressions, is entirely inconceivable. If you're working in the realms of cryptography, protein folding, or the like, I suppose you could have two Boolean expressions, a and b, that are both referentially transparent and expensive to compute.

While not unconceivable, it seems like a sufficiently niche problem that I wouldn't expect a mainstream language to have that as a feature built into the language itself.

As Dai writes in a comment, concurrency comes with an overhead, so the expressions need to be more expensive than the overhead before such an optimization is warranted.

Can you write an API that gets you there? Yes, absolutely, and I'm sure other people here will tell you how to use Task.WhenAll and Task.WhenAny for that.

If you want hints on how to design such an API, it may help considering that Boolean comparisons form monoids, and that all monoids can be made lazy:

Lazy<bool> x = // ...
Lazy<bool> y = // ...
Lazy<bool> b = x.And(y);

You could do something similar with the TPL, since you can lift any monoid into an applicative functor pointwise:

(Applicative f, Monoid a) => Monoid (Ap f a)

Since C# Tasks are monads, they are also applicative functors, so we know from Haskell that this is possible, and how the API ought to look.

Answer 2

I created the AnyConditionIsMetAsync method for your usecase.

It accepts any number of condition tasks/async methods/sync methods and waits until either any of them finish executing and return true or until all of them finish (if none return true).

Here's the usage example program code, and the method's code alongisde some flexibility signatures/overrides:

using System.Diagnostics;

namespace ParallelConditioning
{
    public class Program
    {
        public static async Task Main(string[] args)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            if (await AnyConditionIsMetAsync(Condition1Async(), Condition2Async(), Condition3Async(), Condition4Async()))
            {
                // #1:
                // We start the execution of all condition async methods in parallel and pass their tasks to the AnyConditionIsMetAsync method
                // which waits until any task finishes with a true result
                Console.WriteLine("1 || 2 || 3 || 4: " + stopwatch.Elapsed);
            }

            stopwatch.Restart();
            if (await AnyConditionIsMetAsync(Condition4Async, Condition3Async, Condition2Async, Condition1Async))
            {
                // #2:
                // equivalent to #1,
                // except we're passing the async methods so that the condition tasks are started by the AnyConditionIsMet method
                Console.WriteLine("4 || 3 || 2 || 1: " + stopwatch.Elapsed);
            }

            stopwatch.Restart();
            if (await AnyConditionIsMetAsync(Condition1, Condition3, Condition4, Condition2))
            {
                // #3: passing sync functions that will be run in parallel
                Console.WriteLine("1 || 3 || 4 || 2: " + stopwatch.Elapsed);
            }

            stopwatch.Stop();
        }

        private static async Task<bool> Condition1Async()
        {
            await Task.Delay(1000);
            return false;
        }

        private static async Task<bool> Condition2Async()
        {
            await Task.Delay(2000);
            return true;
        }

        private static async Task<bool> Condition3Async()
        {
            await Task.Delay(3000);
            return false;
        }

        private static async Task<bool> Condition4Async()
        {
            await Task.Delay(4000);
            return true;
        }

        private static bool Condition1() => Condition1Async().Result;
        private static bool Condition2() => Condition2Async().Result;
        private static bool Condition3() => Condition3Async().Result;
        private static bool Condition4() => Condition4Async().Result;


        #region AnyConditionIsMetAsync
        private static async Task<bool> AnyConditionIsMetAsync(IEnumerable<Task<bool>> conditionTasks)
        {
            HashSet<Task<bool>> conditionTaskSet = new(conditionTasks);
            while (conditionTaskSet.Count > 0)
            {
                Task<bool> completedConditionTask = await Task.WhenAny(conditionTaskSet);
                if (completedConditionTask.Result)
                {
                    return true;
                }
                conditionTaskSet.Remove(completedConditionTask);
            }
            return false;
        }
        private static Task<bool> AnyConditionIsMetAsync(Task<bool> conditionTask, params Task<bool>[] additionalConditionTasks)
            => AnyConditionIsMetAsync(additionalConditionTasks.Prepend(conditionTask));

        private static Task<bool> AnyConditionIsMetAsync(IEnumerable<Func<Task<bool>>> conditionAsyncFunctions)
            => AnyConditionIsMetAsync(conditionAsyncFunctions.Select(Task.Run));
        private static Task<bool> AnyConditionIsMetAsync(Func<Task<bool>> conditionAsyncFunction, params Func<Task<bool>>[] additionalConditionAsyncFunctions)
            => AnyConditionIsMetAsync(additionalConditionAsyncFunctions.Prepend(conditionAsyncFunction));

        private static Task<bool> AnyConditionIsMetAsync(IEnumerable<Func<bool>> conditionFunctions)
            => AnyConditionIsMetAsync(conditionFunctions.Select(Task.Run));
        private static Task<bool> AnyConditionIsMetAsync(Func<bool> conditionFunction, params Func<bool>[] additionalConditionFunctions)
            => AnyConditionIsMetAsync(additionalConditionFunctions.Prepend(conditionFunction));


        #endregion
    }
}