The idea behind the state of Imperative languages

Question

I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? I know that C is in the Imperative paradigm (In fact in the Procedural paradigm), so it has a state, but I don't understand how it is expressed in language. Is there a special space in memory that contain 1 or 0? But then, what 0 and 1 represent?

If for example we have:

int x = 5;
printf("%d,5);

How the state will be affected by each line? Also, why Functional languages does not have one and what is the impact of having one.

As you can see, I'm a bit confused about the idea behind the state. I think that a small example make a bit clear.

I also read the previous thread from the second site, but it didn't help me to understand.

Answer 1

The simplest kind of state is the configuration of memory. In C this memory is accessed through variables (and arrays and pointers, but let us ignore those), so the state is the values of variables.

For example, suppose we have variables x and y whose values are 23 and 42 respectively (and no other variables). Then we could write the state as $$[x \mapsto 23, y \mapsto 42]$$ If we run the program

x = 1 + y

the state will change to $[x \mapsto 43, y \mapsto 42]$. When we declare a local variable, the state will be extended temporarily with that variable.

There are many other kinds of state, such as:

• in an object-oriented language each object has its own state, namely the values of its attributes
• a finite state automaton has states, obviously

In general, there is going to be a set $S$ of all possible states. For instance, 1 GB of memory corresponds to $S$ with $2^{2^{30}}$ elements because that's how many states there are for 1 GB of memory. A program which uses state and computes a value of type $A$ can then be thought of as a function $S \to A \times S$: it takes the initial state $s \in S$ and returns a pair $(a, s')$ where $a$ is the computed value and $s'$ the final state.

It is not true that functional languages have no state! The pure functional languages such as Haskell and do not have built-in state, but other functional languages do have state. For instance OCaml and SML both have references, which are just mutable memory locations, so they have state. Racket and Scheme have state as well, and they are functional languages.

Perhaps a clarification is in order: a language is functional if functions are values, which means that we can do with functions whatever we can do with other values (pass them around, make arrays of functions, etc.). For some reason people often confuse pure and functional languages.

Supplemental: Since we're on the brink of a religious war about "Does C++/Java/whatever have first-class functions?", let me throw the first grenade. For a language to be functional the following have to be possible:

1. Read an integer n from standard input and create a list or an array of functions $[f_1, \ldots, f_n]$ where $f_i(x) = x + i$. This disqualifies C.

2. Allow function abstractions in the sense that it is possible to create a function based on a function rule, written as $\lambda x . E$, or $x \mapsto E$, or lambda x: E. Very importantly, there must be no scoping limitations on the abstraction, which means that $E$ may refer to any variables that are in scope. This disqualifies Java and C++.

There are fundamental mathematical reasons why function abstraction must be unrestricted. With restricted function abstraction we just don't get what is mathematically called a "function". We get something else, but not functions.

Answer 2

The state of a program is all the information that is needed at runtime to determine what each line does.

Consider a simple example that needs no state:

printf("%d", 1 + 1);

What is the effect of this line? Obviously it prints the number 2. But what about this example:

printf("%d", x + 1);

Now it's not so clear what this line does. The number printed to the screen depends on the value of x. Thus the value of x is part of the state of the program. The result of executing that line of code varies depending on the value of x. If x was a value loaded in from a file the user specified, then the result of this printf may not even be knowable at compile time. It may only be known at runtime!

Programming languages pay attention to this concept because it is an essential aspect of optimization. Consider this silly piece of code:

int a = y * 42;
int b = y * 42;
int c = y * 42;
int d = y * 42;
int e = y * 42;
...

It would be nice to just calculate y * 42 once and re-use the value. But that's not technically what is written. The code written says we need to do the multiplication each time. However, if we can show that y does not change between the first and last line (that portion of the program's state doesn't change), then we can optimize all those extra multiplications away.

Pure functional languages take this to an extreme. An expression in a pure functional language is stateless -- it always evaluates to the same thing. They do all sorts of clever tricks to make this happen. These tricks seem rather absurd (Reading about Haskell's monads for the first time should always be accompanied by a stiff drink). But the reward for all these tricks is that the functional programming languages can do some remarkably clever optimizations that are incredibly difficult to do in a language which requires one to pay attention to state.

Why have state? Why not just go all pure-functional? Well, sometimes the absurdity of those tricks starts to add up, and it can get increasingly hard to figure out what is actually going on because you, as the developer, are responsible for tracking all sorts of details. Meanwhile, with imperative languages like C, it is easier to write these things. (Pure-functional programmers will argue that it's not easier, but the modern development community at large has substantially chosen stateful languages because people find them easier).

And nowdays, with the powerful optimizers that are available, it is often possible to write in an imperative language, with state, and have the optimizer analyze your code and prove that certain segments of the code are stateless and optimize them as such. Optimizers get better every year, so they're now pretty good at figuring these sorts of things out.