Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|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. –  robjb Nov 16 '11 at 20:07
add comment

1 Answer

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.

share|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. –  delnan 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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