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.

  • 1
    A relevant StackOverflow answer: stackoverflow.com/questions/3722084/…
    – jfriend00
    Commented Oct 14, 2013 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
    Commented Oct 14, 2013 at 7:07
  • 6
    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. Commented Oct 14, 2013 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
    Commented Oct 14, 2013 at 13:36

5 Answers 5


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?)

  • 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. Commented Oct 14, 2013 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. Commented Oct 14, 2013 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. Commented Oct 14, 2013 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
    Commented Oct 14, 2013 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
    Commented Oct 14, 2013 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".


State means the ability to respond to a present stimulus in an manner that depends on past stimuli, not just based on the present stimulus.

Purely functional programs are just functions. Thus for practical applications the purely functional program inputs a pair (old_state * present_stimulus) and outputs a pair (new_state * present_response). An external, stateful "looper" is needed to wait for the next stimulus and propagate the state.

A purely functional program doesn't intrinsically have state, and -can't- be used for practical applications directly.

Thus no state-oriented program can be replaced with a different implementation that is purely functional and without state.


You can avoid explicit mutable state as long as you don't have to interact with the outside world.

In JavaScript in order for you program to actually have an effect beyond taking up processor cycles, you have to modify the Dom or the Window object, and these API's are stateful. But I suppose you could create a wrapper which passed the Dom and Window objects as parameters to the JavaScript code, and then received a new Dom/Window as output. This would isolate the JavaScript code from mutable state.

Of course you are still relying on state, since the browser window and DOM is stateful by nature. Any interactive application is inherently stateful, but you can still structure your code in such away as to minimize explicit state.

A different question is if it is a good idea. Even Haskell, which is a pure functional language by design, includes the 'state' monad, which allows you to simulate mutable state. This shows that explicit mutable state sometimes really is a desirable pattern.


Think about how you would implement a "state machine" in a programming language without state.

You could probably actually do it but you would end up using function names as storage. Ending up with gobblyday gook like:

if (sm.atBegining()) sm.start() else if (sm.done()) sm.stop() ) else sm.progress()

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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