16

I have recently been refactoring large chunks of code and replacing them with Linq queries.

Removing the language bias - Linq is essentially a set of Map / Filter and Reduce operations that operate on a sequence of data.

This got me thinking, how far would I theoretically be able to take this. Would I be able to rewrite the whole code base into a series (or even a single) of Map / Filter and Reduce operations.

Unfortunately I get paid to do useful stuff, so I haven't been able to experiment much further, but I can't think of any code structure that couldn't be re structured as such. Side effected code can be dealt with via monads.. Even output is essentially mapping memory addresses to screen addresses.

Is there anything that couldn't be (theoretically) rewritten as a Linq query?

Improve this question
  • For trees see here: stackoverflow.com/questions/250377/… – blueberryfields Nov 16 '11 at 16:59
  • I always thought that "reduce" is enough to guarantee Turing completion (map and filter can be implemented as reduce operations, no?)- at least, the functional language equivalent of reduce. I don't know enough about Linq to be sure how closely the implementation there follows the functional one. – blueberryfields Nov 16 '11 at 17:06
  • 1
    I don't know, but a rough rule of thumb is that anything anybody would even consider writing all their code in will turn out to be Turing complete. But the corollary of that is that being Turing complete isn't very exciting. – psr Nov 16 '11 at 17:42
  • 1
    I agree with psr; I think a valid answer to this question needs to address Turing completeness. A proof might attempt to implement a Turing machine using only these operations. – Rob Nov 16 '11 at 20:07
  • Idle thought: Even if we allow nonsense like my_list.map(_ignored => a copy of my_list), it seems like the space use of such a program is bounded by some polynomial (depending on the program length). Then such a language certainly couldn't compute problems that are not in PSPACE. However, as many problems in PSPACE are considered intractible, to say nothing of larger classes, this may not be a very serious restriction. – user7043 Aug 13 '15 at 10:20
1

It's called functional programming, and is considered by many to be a foundational concept. here's a good intro on Joel On Software. The more technical answer is no, there is no currently known way of asking your computer questions (in a well defined way) that cannot be answered via SKI calculus.

Improve this answer
  • 1
    There's far more to functional programming than the functions map, filter and reduce (this goes thrice if we ignore turing completeness and use practical FP languages). In fact, they just happen to be rather general and thus generally useful, but are actually very simple applications of functional programming. Bare minimum lambda calculus can define those functions among many others, not the other way around. – user7043 Nov 16 '11 at 21:10
  • "here's a good intro on Joel On Software" -- which manages to confuse Fortran with Basic, so I wouldn't put much trust in other facts in it. – quant_dev Apr 2 '12 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.