Notice that this post was published on April 1, 2009.

For decades, computer science students have been taught that so-called NP-hard problems do not have known efficient solutions. These problems include the infamous Travelling salesman problem, subset sum, 3SAT, and many more.

But – as is often the case – where theoretical Computer Science failed, sound software engineering practices will succeed. By using loosely-coupled OOP, agile methodologies and the model-view-controller architectural pattern, I developed a solution that someone trapped in the world of formulas and big Ohs would never dream of.

Enough with the background, and let’s take a deep dive into the intriguing design.

Introducing the choose expression

As most other elegant designs, this one is very simple. My proposal calls for a choose expression with this syntax:

    choose { boolean_expression1, boolean_expression2 }

Choose expression is basically the || operator, only with a slight twist. The semantics of the choose expression are similarly simple:

  1. If boolean_expression1 or boolean_expression2 will evaluate to true, the runtime will evaluate the true expression, but not the other expression. The return value of the choose expression will be true in this case.
  2. If both expressions will evaluate to false, the runtime will evaluate neither expression. The return value of the choose expression is false in this case.

Let’s look at a few simple usage examples:

    bool a = choose {
        1 == 2,
        1 < 2
    };

Variable a will be set to true, because the condition 1 < 2 is true.

Here is another example:

    bool a = choose {
        ((Func<bool>)(() => { Console.WriteLine("Hello"); return false; }))(),
        1 < 2
    };

There is no point executing the first function, because it would return false anyways. So, this code sample does not print anything to screen. Instead, the choose expression will execute the second function. The second expression returns true, so variable a will be set to true.

And another simple one:

    bool a = choose {
        ((Func<bool>)(() => { Console.WriteLine("Hello1"); return false; })(),
        ((Func<bool>)(() => { Console.WriteLine("Hello2"); return false; })(),
    };

This code sample will not be print anything to screen either. It is obvious; why evaluate either of the two functions if they are going to return false anyways? This code simply assigns false to variable a.

Now, let’s cut to the chase, and use choose expressions to give an efficient implementation of an NP-hard problem. Let’s look at subset sum:

    bool SubsetSum(int[] arr)
    {
        return SubsetSumHelper(arr, 0, 0);
    }

    bool SubsetSumHelper(int[] arr, int index, int sumSoFar)
    {
        if (index == arr.Length)
        {
            return sumSoFar == 0;
        }

        return choose {
            () => SubsetSumHelper(arr, index + 1, sumSoFar + arr[index]),
            () => SubsetSumHelper(arr, index + 1, sumSoFar)
        };
    }

Yes, that’s right! An O(N) implementation of the subset sum problem. There you have it, computer scientists. You said it was impossible. If anyone at the University of British Columbia needs my mailing address to send me a refund check for my education, you can find my contact information in the margin.

Under the hood of the choose expression

After a couple hours of coding, I was able to develop a simple prototype. It works perfectly, but since it is only a prototype, I simplified my life a little bit by allowing choose to execute both functions. After all, I don’t have to slave through all the nitty-gritty details in the initial prototype, right? The performance of my implementation is not that great either, but I haven’t had the time to fire up the profiler so far. Perhaps I need to unroll a loop somewhere, or ensure that method calls are getting inlined optimally.

To further prove the feasibility of my design, I developed a non-deterministic Turing machine construction that evaluates choose expressions extremely efficiently.

Non-deterministic Turing machines are known to be a good realistic abstraction of computing hardware; there was a study that proved that. To be exact, the study was only a moderate success. The researchers built a mechanical non-deterministic Turing machine that solved a Travelling Salesperson problem with 5 cities without a hitch. On the 6-city version of the problem, the experiment had to be abruptly interrupted after sprawling machine replicas filled up the room, and the head of one of the researchers got caught in a loop of tape.

So, it is clear that this design is sound. There may be performance issues in the first release, but they will improve as the technology matures. And once CPU manufacturers include a non-deterministic branching instruction in the instruction set, the cost of evaluating the choose expression will drop down to a couple of instructions.

Summary

I don’t know the detailed plans surrounding the C# language, but if there is a C# 4.1., I would like to see the choose expression included.

And the larger lesson of this post is simple: computer science is largely obsolete in today’s world of technology. Computer science says that this is impossible, that is impossible… As you just saw, anything is possible, so long as you have enough paper to print out all the UML diagrams.

Tags: ,

13 Comments to “Choose expression: proposal for a revolutionary C# construct”

  1. Gunnar says:

    Interesting idea but wouldn’t the compiler/runtime have to run both expressions to be able to find out the return value and than have to return to a state before the evaluation, which can be impossible in more complex situations?

    And for your implementation of the NP-hard problem. The runtime would have to recursively run the SubsetSumHelper to be able to find out the return value.
    A simple || would probably do the same thing there in the same O() scale… maybe I’m just not understanding your solution, a long time since I did my algorithms course :)

  2. Can says:

    what if the function returns, something more dynamic boolean? How the compiler would know that?
    string boo = ReadfromFile();
    return bool.Parse(boo);

  3. Can says:

    Damn it, I should have realised before! :)

  4. Todd says:

    So, like, this is an april fools joke, right?

    Please, please tell me it is.

  5. @Todd: Yes, this post is my lame contribution to honor today’s date.

  6. hr0nix says:

    Yeah, April Fools’ Day!

    That Gunnar and Can are freaking me out.

  7. @hr0nix: In all fairness, if you skip over the ridiculous parts of my article and only look at the code samples, you may well think that I am being serious (and confused). :-)

  8. Abednego says:

    You don’t need non-determinism to make this work. All you need to do is run the C# virtual machine as Administrator and let it change the CPU clock rate every time it encounters a ‘choose’ statement. Temporarily overclocking the CPU by a factor of 2 is not a big deal, as long as you don’t have too many ‘choose’ statements in your code. All of your examples have just one ‘choose’ statement each, so this is easy. By doubling the speed of the CPU, you can execute both branches of the ‘choose’ statement in as little time as it would take to execute just one branch, on average. If you are worried of overheating, you can just start off your program at half-speed.

  9. Abednego says:

    I’ve solved the halting problem!
    bool f() {…};
    bool fHalts() { return choose { ()=>f(), ()=>!f() }; }

  10. @Abednego: Of course! We can always double the frequency. Worst case scenario, we add another CPU. Brilliant solution.

    And yes, I have a proof that your halting problem solution works. I also used the results of this research to prove that the universe has 123 dimensions, tooth fairies exist, and De Morgan’s Laws are wrong.

  11. […] bookmarks tagged agile Choose expression: proposal for a revolutionary C#… saved by 4 others     sakubatzumatsu bookmarked on 04/02/09 | […]

  12. […] Choose expression: proposal for a revolutionary C# construct […]

Leave a Reply

You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>