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.

For definitions and examples of "state", see: http://en.wikipedia.org/wiki/Program_state , http://en.wikipedia.org/wiki/Finite_state_machine , http://en.wikipedia.org/wiki/State_diagram

A diagram showing a very easy example, notice how the current state changes how the turnstile operates when the same input (inserting a coin, pushing on the turnstile) is given twice in a row: http://en.wikipedia.org/wiki/File:Turnstile_state_machine_colored.svg

I thought about this question for a bit and came up with nothing other than:

  1. Reduce the scope/features of the project/software.
  2. Push the burden of making intelligent decisions to the user and/or supply the program with a "cheat sheet" that makes decisions easier (for example: instead of trying to write a program that drives a car using only two webcams, you could embed waypoint markers in the road every 100 ft, place special reflective markers in between lanes, and use a database of terrain maps to help the program make decisions; one would require the work of a Tesla/Newton -level genius [assuming the program can do things like (1) dodge animals, the remnants of exploded tires, etc. while taking less drastic measures for things like cardboard and plastic bottles, (2) deal with the occlusion of landmarks and indicators caused by other vehicles, (3) adjust to weather, etc. conditions, and so on] vs. someone who can write a "connect the dots" algorithm)

PS: I would classify these two methods as "cheating" because you are significantly changing the input/output of the program. In the first case, you are whittling away your program to nothing, and in the second, you are shifting much of the burden of decision-making onto whoever maintains the database and transit system.

Are there any valid ways of eliminating/reducing state?

share|improve this question
2  
Can you explain what you exactly mean by state? Why would you want to reduce it? –  Greg Ros Jul 18 '12 at 13:32
    
@GregRos a state is a unique configuration of information in a program or machine en.wikipedia.org/wiki/State_%28computer_science%29 ; for diagrams, see: en.wikipedia.org/wiki/Finite_state_machine, en.wikipedia.org/wiki/State_diagram (quote: For a real-world example [of state], consider a three-way light switch. An ordinary switch turns on a light when it's in the "up" position, but in a three-way switch the "up" position could be on or off, depending on the state or "configuration" of the other switch...) –  Michael Jul 18 '12 at 14:26
2  
Go read up on automata theory. I think you are looking for methods of reduction. If I remembered how to formally do it I would write it up as an answer. However, I took the class 20+ years ago. It was not a class that I enjoyed so I have no interest in trying to relearn it so I can explain it here. –  Dunk Jul 18 '12 at 14:45
1  
Yup, Dunk is right. There is (more than one) systematic way of reducing a well defined state machine to the absolute minimum it can be. Some are easier than others...though like Dunk it has been years since I've had to do it and am too far removed... –  Rig Jul 18 '12 at 15:43

1 Answer 1

up vote 1 down vote accepted

The turnstyle example is already at the 'minimal' state needed to work. It has a locked state. You can trick this by changing the object (having a LockedTurnstyle and an UnlockedTurnstyle), but that mostly obscures the state rather than eliminating it.

In most code though, the problem is not so clear cut. In most cases, the code has state that it does not strictly need to operate. Reducing that unneeded state is much of what you'll end up doing in practice.

Further, state in and of itself isn't that bad. Varying state is the more troublesome culprit. By making state invariant at certain limited times or situations will reduce many of the practical problems in software. This too is what you'll end up doing to get practical benefits in software engineering.

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.