13

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.

gnat
  • 21,442
  • 29
  • 112
  • 288
johnbakers
  • 289
  • 1
  • 7
  • 1
    A relevant StackOverflow answer: http://stackoverflow.com/questions/3722084/does-functional-programming-avoid-state – jfriend00 Oct 14 '13 at 07: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 07: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. – Billy ONeal Oct 14 '13 at 07: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

5 Answers5

17

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

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • 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 06: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 07: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 07: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 08:05
  • @EmilioGaravaglia: from what the OP wrote I guess his focus is more on "purely functional" than on "stateless". – Doc Brown Oct 14 '13 at 12:02
  • @wirrbel: state is something physical (think to linear differential equations systems or to discrete systems). A state is introduced every time on thing calls another, otherwise no return is possible, since you don't know where you come from. The fact you don't (need to) "reason" about it doesn't make it disappear. – Emilio Garavaglia Oct 14 '13 at 18:59
  • @BillyONeal: Sate is something physical. You can see it or hide it, but doesn't disappear. There cannot be something that is both "stateful" and "stateless". You can describe it starting from state (and transformation is a consequence) of from transformation (and state is an implicit prerequisite). If there is no "state" there is either no computation or no time/space/energy. – Emilio Garavaglia Oct 14 '13 at 19: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
  • @EmilioGaravaglia You are thinking in terms of a lambda calculus interpreter that introduces state by its execution model. Lambda calculus is not about calling functions and returning values, its about evaluating an expression by applying the transformations. – wirrbel Oct 14 '13 at 21:33
  • @Wirrbel: Transformations need a state to apply to. The whole concept of a transformation makes no sense in absence of state. – Billy ONeal Oct 14 '13 at 22:06
  • Basically, are you saying that computation cannot be done with a stateless system? That basically sounds like a tautology: No state => no (change of) information => no computation. – Thomas Eding Oct 14 '13 at 22:51
  • @wirrbel: "state" is the thing "transformation" transform. Without it you can only transform void into void and all transformations are identical to the identity. In this degenaral universe true and false are the same. – Emilio Garavaglia Oct 15 '13 at 13:06
  • Hey guys, I think you have provided enough input about your different points of view about what "state" is - now let's wait until the OP gives us some feedback what he *really* wanted to know. – Doc Brown Oct 15 '13 at 14:50
14

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".

Emilio Garavaglia
  • 4,289
  • 1
  • 22
  • 23
0

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.

Atsby
  • 1,217
  • 10
  • 9
0

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.

JacquesB
  • 57,310
  • 21
  • 127
  • 176
0

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()
James Anderson
  • 18,049
  • 1
  • 42
  • 72