Lambda Expressions vs. Anonymous Methods, Part Five

re: Lambda Expressions vs. Anonymous Methods, Part Five

Eric Lippert — Fri, 27 Jul 2007 21:18:04 GMT

Whoops, you are right. My bad.

In fact, we can trivially extend this to an NP-complete problem by simply adding eight more:

static T Or(T a1, T a2, T a3){return new T();}

static T Or(T a1, F a2, T a3){return new T();}

...

static F Or(F a1, F a2, F a3){return new F();}

Because that makes the problem into 3-SAT, which is NP-complete.

re: Lambda Expressions vs. Anonymous Methods, Part Five

John Smith — Fri, 27 Jul 2007 04:33:23 GMT

Awesome example!

I would just like to note that you have shown the 2-SAT problem which is actually in P. But since it's trivially extended to be N-SAT if you have And(x0,x1,...xn-1) and Or(x0,x1,...xn-1) functions I'll buy it.

re: Lambda Expressions vs. Anonymous Methods, Part Five

Tanveer Badar — Thu, 31 May 2007 10:45:49 GMT

'Apparently in Haskell you can encode a Turing machine into the type system and make the compiler run it!'

Same thing goes for C++ templates. They are Turing complete too. The reason behind template meta-programming in C++. I suppose any language with similar inferencing abilities and compiler able to make decision which type makes the best candidate if any will suffer similar problems.

Partial specialization makes life a living hell for C++ compiler writers. One reason VC++ team never got partial specialization right before VC++ 2003.

re: Lambda Expressions vs. Anonymous Methods, Part Five

Clintp — Wed, 28 Mar 2007 21:37:33 GMT

I thought it was going to be the Halting Problem as well.

re: Lambda Expressions vs. Anonymous Methods, Part Five

Eric Lippert — Wed, 28 Mar 2007 21:03:30 GMT

I am pretty sure that overload resolution is decidable in a finite amount of time! It's not THAT bad.

re: Lambda Expressions vs. Anonymous Methods, Part Five

Rob — Wed, 28 Mar 2007 20:53:29 GMT

And here I thought your example was going to show the Halting Problem.