Q:

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.
See: http://projects.csail.mit.edu/church/wiki/Simple_Generative_Models
(search for "XRP")

A:

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.

