Concurrent and serializable computations

and the evaluation order for function's arguments and the body

Notions of serializability and concurrency appear at first sight contradictory : one seems to preclude the other. This article aims to understand when truly concurrently-running processes are serializable. The impetus comes from the following passage describing the order of argument evaluation in every compliant Scheme system (R5RS, Sec 4.1.3):

Note: In contrast to other dialects of Lisp, the order of evaluation is unspecified, and the operator expression and the operand expressions are always evaluated with the same evaluation rules.

Note: Although the order of evaluation is otherwise unspecified, the effect of any concurrent evaluation of the operator and operand expressions is constrained to be consistent with some sequential order of evaluation. The order of evaluation may be chosen differently for each procedure call.

Let's take an example of two processes, P1 and P2.

Example Ex1

The processes are to perform the computation:

P1:

(load (r 0) (constant 1)) (store (r 0) (location 'A))

P2:

(load (r 0) (constant 2)) (store (r 0) (location 'B))

We use some sort of a "portable" assembler in these examples. (r n) denotes a register n, which is a "process' local variable," a part of process' context. (r 0) in P1 has no relation whatsoever to (r 0) in P2. (location sym) denotes locations in shared memory. We assume that load, store, etc. operations are atomic. A process can be interrupted (and forced off a CPU) only after one operation completes and before another starts. On no occasion, e.g., a load operation is performed halfway, that is, loads only a part of the bits of a value. All old CPUs literally check for interrupts only when their ALUs finish. Newer CPUs are far more complex, yet they try to give the same impression.

There can be two sequential schedules of executing P1 and P2, which are listed in the following table. The table also shows one parallel schedule:

Schedule	Operations	Result
Sequential SS1	P1 then P2	'((A 1) (B 2))
Sequential SS2	P2 then P1	'((A 1) (B 2))
Parallel PS1	P1::load, P2::load, P2::store, P1::store	'((A 1) (B 2))

It is easy to see that any other parallel schedule gives the same result. No matter what the sequence of loads and stores to the common memory is, the outcome is always the same as that of SS1.
 

Example Ex2

The processes are to execute:

P1:

(load (r 0) (constant 1)) (store (r 0) (location 'A))

P2:

(load (r 0) (constant 2)) (store (r 0) (location 'A))

Schedule	Operations	Result
Sequential SS1	P1 then P2	'((A 2))
Sequential SS2	P2 then P1	'((A 1))
Parallel PS1	P1::load, P2::load, P2::store, P1::store	'((A 1))
Parallel PS2	P1::load, P2::load, P1::store, P2::store	'((A 2))

Obviously any other parallel schedule will yield either the result of SS1 or the result of SS2. In this example, for each parallel schedule there exists a sequential schedule which gives the same result.
 

Example Ex3

Schedule	Operations	Result
Sequential SS1	P1 then P2	'((A 2))
Sequential SS2	P2 then P1	'((A 3))
Parallel PS1	P1::load, P1::add, P2::load, P1::store, P2::store	'((A 2))
Parallel PS2	P1::load, P1::add, P2::load, P2::store, P1::store	'((A 1))

While PS1 gives the same result as the sequential schedule SS1, PS2 yields something that cannot be produced with any sequential schedule. R5RS, Sec 4.1.3 specifically outlaws this kind of schedule. Yet PS1 is allowed -- so argument expressions in a function call can be evaluated in parallel after all.

Computations like {P1, P2} in Ex2 are called serializable: no matter how you run the processes concurrently, there is always a way to achieve the same final result by executing these processes sequentially on a single CPU. Computation as in Ex3 is non-serializable: there exists a parallel schedule whose final result cannot be achieved in any sequential computation. In databases, for example, non-serializable transactions are considered great evil, and the perpetrators are publicly flogged (or ought to be).

One can make Example Ex3 serializable by defining a critical section around P1 and P2::store. The example will still permit a certain degree of concurrency: P2::load can run in parallel with P1::load, but then P2 must wait for P1 to complete.

Chapter "11.1 Basic concepts of concurrency" of Jeffrey Ullman's Principles of Database Systems (2nd Edition, 1982) talks about these issues in great detail. This book is remarkable in more ways than one. There is the third edition of this book.
 

Evaluation order of argument expressions

The examples 1 through 3 should help to understand the passage from R5RS quoted at the beginning of this page. One has to distinguish however between

• the order of evaluating one argument expression vs. another argument expression,
• the order of evaluating function's body wrt computing argument expressions

Assuming

(define (adder x)
  (lambda (y z) (+ x y z)))

We have to perform four evaluations to get to the final result:

Ev#1: (adder 3) ==> (lambda (y z) (+ 3 y z))
Ev#2: (- 4 5) ==> -1
Ev#3: (* 4 5) ==> 20
Ev#4: applying the result of Ev#1 to the results of Ev#2 and Ev#3:
        (apply (lambda (y z) (+ 3 y z)) -1 20) ==> 22

According to R5RS, Ev#1, Ev#2, and Ev#3 can proceed in any order: for example, Ev#1 - Ev#2 - Ev#3 or Ev#3 - Ev#2 - Ev#1. This order can even change from one invocation of a procedure to another invocation of the same procedure. Furthermore, Ev#1, Ev#2 and Ev#3 can proceed in parallel, on concurrently running CPUs if available -- provided that they are serializable: i.e., there exists a sequential schedule that gives the same final results.

In any case, Ev#4 may commence only after Ev#1, Ev#2, and Ev#3 are all finished. This is required by a strict, call-by-value semantics of Scheme: procedure's body is evaluated only after all its arguments yield the value. If evaluation of one argument takes forever, the procedure body will never gets a chance to run -- even if the procedure will not require the value of that particular argument.

Note, Scheme actually has other evaluators, some of them with a non-strict semantics. See "Four evaluators of CL/Scheme and their bottom terms" for an illustration.

The present page is a compilation of two articles posted on a comp.lang.scheme newsgroups on Jan 5 and Jan 8, 2000.
 

Articles' Posting Headers

From: oleg
Message-ID: <856bda$quc$1@nnrp1.deja.com>
Subject: Concurrent and serializable computations [Re: Order of evaluations of arguments...]
Date: Sat, 08 Jan 2000 03:37:15 GMT
Newsgroups: comp.lang.scheme
X-Article-Creation-Date: Sat Jan 08 03:37:15 2000 GMT

From: oleg
Message-Id: <84u6ua$t7q$1@nnrp1.deja.com>
Subject: Order of evaluations of arguments and bodies [Re: question about Scheme standards and SRFI process
Date: Wed, 05 Jan 2000 01:31:54 GMT
Newsgroups: comp.lang.scheme
References: <RT5hONljzGn0S30mwmVXTGmMOBES@personalnews.de.uu.net> <B48A883C9668315CC0@0.0.0.0> <946211855.7638.0.nnrp-14.9e987a3c@news.demon.co.uk> <B491ADFC96683F4844@hearsay.demon.co.uk> <946643419.27673.0.nnrp-01.9e987a3c@news.demon.co.uk>
X-Article-Creation-Date: Wed Jan 05 01:31:54 2000 GMT

Last updated April 7, 2000