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.