The idea behind the state of Imperative languages

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.

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:

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

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

StackExchange Computer Science Q#104565, answer score: 10