What is a stateful computation?

I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means.

(search for "XRP")

• What specific field? What are you reading, who uses this term? What are the definitions/references they give? Where have you looked? – Raphael Feb 8 '16 at 15:24
• See edit; in the link. – Astrid Feb 8 '16 at 15:57

1 Answer

Stateful computation basically means that the model of computation has got a memory storage to store information, and it uses this information to compute. For example, let us say you have a function $f()$ computing something using state information. Then, if you do,

$x_1 = f()$
$x_2 = f()$
$x_3 = f()$
...

$x_1, x_2, x_3,..$ may be all different. In functions, defined as mapping in set theory, we cannot have functions returning different values from different calls. We will need to define something like $\langle y, store_{i+1}\rangle = f(\langle x, store_i\rangle)$ in that case. A sample code for $f()$ that is stateful is given below.

function f()
output: integer x;

global integer store initialized to 0;

x = store
increment store by 1
return x


This function will return 1, 2, 3, 4, ..., in sequence when it is called multiple times. Here store is the memory storage it uses to compute differently.

The function can also use other inputs to compute its output, such as events from an event queue, input data, interactive data, etc. but stateful computation must assume an underlying saving of state in the model of computation.

By the way, the model of computation for computers is Turing Machine, which can be thought as stateful computation if you use functions as subroutines, i.e., you do not start Turing machine from beginning at every function call.

• Ok so if I were to call function $f()$ with say argument $a$ as so $f(a)$, then I will always return, lets say; $b = f(a)$ $-$ if it is a stateful computation? I.e. the computation is as such that it stores the mapped values between all inputs and outputs the functions has in its domain? – Astrid Feb 8 '16 at 14:22
• If the function stores the mapping for efficiency purposes, then usually we do not call it stateful computation. Sometimes we use this trick where a function is called repeatedly (example: in computation of fibonacci number f(n) = f(n-1) + f (n-2), n>1, f(0) = 0, f(1) = 1). – Shreesh Feb 8 '16 at 14:27
• Aha, I see so the computation of the Fibonacci sequence is in fact a stateful computation; a unique input-output between all the integers and the results sums? In which case, then memoized procedures must be stateful computations as well? – Astrid Feb 8 '16 at 14:29
• I meant the opposite, I am differentiating between functions those have storage and those using storage (to actively compute different output). – Shreesh Feb 8 '16 at 14:33
• See for example: stackoverflow.com/questions/6835777/… – Shreesh Feb 8 '16 at 14:34