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.

This is a theoretical question, but after many years of programming in what I now realize is "normal" imperative technique, using C++ mainly, I've discovered this other world of functional programming, which I stumbled upon accidentally while casually learning JavaScript.

This has led me to wonder if you could technically replace any complete state-oriented program with a different implementation that is purely functional and without state?

It's an intriguing idea and I must admit that there is a clarity and elegance in functional programming that has really blown my mind.

share|improve this question
1  
A relevant StackOverflow answer: stackoverflow.com/questions/3722084/… –  jfriend00 Oct 14 '13 at 7:02
    
Whether or not there is state that persists from one point in time to the next is not dependent upon what programming paradigm you use, but on what problem or task you are coding. If you are counting the number of times a button is clicked, then clearly there is state to record that counter and it doesn't matter what coding technique you use, there will have to be state to keep track of the count during the process. So, that particular task cannot be completed without state along the way no matter how you code it. –  jfriend00 Oct 14 '13 at 7:07
5  
If you want to discuss state; clearly state is required, if only for the program itself. It sounds like you are thinking of mutable vs. immutable state though -- you may wish to indicate which you mean in the question. –  Billy ONeal Oct 14 '13 at 7:52
1  
That's like asking if all programs can be converted into true Turing machines. Technically yes, even programs which save and load from a database however it becomes magnitudes more difficult to simulate this behavior in a Turing machine. Likewise, you could have a program whose controller side in MVC architecture is removed and you do all the calling, though again, it becomes magnitudes more difficult to deal with (you essentially become the controller in order to make the program stateless). –  Neil Oct 14 '13 at 13:36

2 Answers 2

Short answer: yes. According to Wikipedia, the equivalence of lambda calculus to Turing machines as an universal model of computation was shown 1937 by Alan Turing. The computational model of a Turing machine is what you typically have in mind when talking about imperative or stateful programming, and lambda calculus is a mathematically formalization of "pure functional programming".

It is conjected that every effective model of computation is able to carry out the same calculations as a Turing machine, and vice versa. This is called Church-Turing thesis. This conjection, however, cannot be proven, because of the more or less intuitive term "effective model of computation" (perhaps someone will invent a new model in the future?)

share|improve this answer
2  
Your same argument can be reverted saying that being lamba calculus equivalent to touring machines, every computation must have a (more or less hidden) state. Whether is is represented as external to the code (by means of variables) or internal to the flow (by means of stack-based function call) always "state" is. –  Emilio Garavaglia Oct 14 '13 at 6:50
3  
Lambda calculus has state; its constraint is that the state is immutable. Immutable state is still state. Parameters to functions, including lambdas, are still state; presumably you want a function to have different behavior given different parameters. –  Billy ONeal Oct 14 '13 at 7:47
    
@emilio Stating that there is an equivalent state based solution to a problem (as you describe) is not proof that no stateless version of that solution exists. –  Billy ONeal Oct 14 '13 at 7:49
2  
@EmilioGaravaglia you are then refering to the state of a lambda-calculus interpreter. When reasoning in the lambda calculus, there is no need to reason about state. Also the aspect of "Mutability" is different. –  wirrbel Oct 14 '13 at 8:05
1  
@EmilioGaravglia: State in imperative programming is memory configuration at a time, here the parameter space is given by all possible memory values and state is one configuration at a time (band of the turing machine). When writing a program in the lambda calculus, there is no direct entity such as a memory field. Program execution is the application of lambda transforms. Intermediate steps might resemble "state", yet they are just equivalent expressions of of the same value. Nothing changes during evaluation, the expressions are just rewritten and processed into a "simpler" form. –  wirrbel Oct 14 '13 at 21:31

In whatever dynamic system, the "state" is what make your present to be influenced by your past or future (the arrow of time is not a mathematical issue, just a physical constrain).

Whether you have something to "remember" or that depends on what you did, you have a state.

A system with no state is not "dynamic": it is just a combinatorial function. That may not have a state, but -to produce different results- need a state to be somehow supplied.

Now, depending on the computational model you refer to, a state can be represented explicitly (in the form of variable) or implicitly (in the form of "return addresses").

when you do fna(fnb(x)) you are giving a state to fnb that in turn will produce a state for fna. This is due to the fact that x exist before fnb is called (so, it comes from it's own "past").

It's not a matter of "state exisit" or "state don't exist". It's a mater of "I care" or "I don't".

share|improve this answer

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.