Instruction Sequence Notations
with Probabilistic Instructions

arXiv:0906.3083v2 [] 1 Oct 2014

J.A. Bergstra and C.A. Middelburg
Informatics Institute, Faculty of Science, University of Amsterdam,
Science Park 107, 1098 XG Amsterdam, the Netherlands
J.A.Bergstra@uva.nl,C.A.Middelburg@uva.nl

Abstract. This paper concerns instruction sequences that contain probabilistic instructions, i.e. instructions that are themselves probabilistic by
nature. We propose several kinds of probabilistic instructions, provide an
informal operational meaning for each of them, and discuss related work.
On purpose, we refrain from providing an ad hoc formal meaning for the
proposed kinds of instructions. We also discuss the approach of projection semantics, which was introduced in earlier work on instruction
sequences, in the light of probabilistic instruction sequences.
Keywords: instruction sequence, probabilistic instruction, projection semantics.
1998 ACM Computing Classification: D.1.4, F.1.1, F.1.2.

1

Introduction

In this paper, we take the first step on a new subject in a line of research whose
working hypothesis is that the notion of an instruction sequence is relevant
to diverse subjects in computer science (see e.g. [12,13,14,15]). In this line of
research, an instruction sequence under execution is considered to produce a
behaviour to be controlled by some execution environment: each step performed
actuates the processing of an instruction by the execution environment and a
reply returned at completion of the processing determines how the behaviour
proceeds. The term service is used for a component of a system that provides an
execution environment for instruction sequences, and a model of systems that
provide execution environments for instruction sequences is called an execution
architecture. This paper is concerned with probabilistic instruction sequences.
We use the term probabilistic instruction sequence for an instruction sequence that contains probabilistic instructions, i.e. instructions that are themselves probabilistic by nature, rather than an instruction sequence of which the
instructions are intended to be processed in a probabilistic way. We will propose
several kinds of probabilistic instructions, provide an informal operational meaning for each of them, and discuss related work. We will refrain from a formal
semantic analysis of the proposed kinds of probabilistic instructions. Moreover,
we will not claim any form of completeness for the proposed kinds of probabilistic instructions. Other convincing kinds might be found in the future. We

will leave unanalysed the topic of probabilistic instruction sequence processing,
which includes all phenomena concerning services and execution architectures
for which probabilistic analysis is necessary.
Viewed from the perspective of machine-execution, execution of a probabilistic instruction sequence using an execution architecture without probabilistic
features can only be a metaphor. Execution of a deterministic instruction sequence using an execution architecture with probabilistic features, i.e. an execution architecture that allows for probabilistic services, is far more plausible. Thus,
it looks to be that probabilistic instruction sequences find their true meaning
by translation into deterministic instruction sequences for execution architectures with probabilistic features. Indeed projection semantics, the approach to
define the meaning of programs which was first presented in [9], need not be
compromised when probabilistic instructions are taken into account.
This paper is organized as follows. First, we set out the scope of the paper
(Section 2) and review the special notation and terminology used in the paper
(Section 3). Next, we propose several kinds of probabilistic instructions (Sections 4 and 5). Following this, we formulate a thesis on the behaviours produced
by probabilistic instruction sequences under execution (Section 6) and discuss
the approach of projection semantics in the light of probabilistic instruction sequences (Section 7). We also discuss related work (Section 8) and make some
concluding remarks (Section 10).
In the current version of this paper, we moreover mention some outcomes of
a sequel to the work reported upon in this paper (Section 9).

2

On the Scope of this Paper

We go into the scope of the paper and clarify its restrictions by giving the
original motives. However, the first version of this paper triggered off work on the
behaviour of probabilistic instruction sequences under execution and outcomes
of that work invalidated some of the arguments used to motivate the restrictions.
The relevant outcomes of the work concerned will be mentioned in Section 9.
We will propose several kinds of probabilistic instructions, chosen because of
their superficial similarity with kinds of deterministic instructions known from
PGA (ProGram Algebra) [9], PGLD (ProGramming Language D) with indirect
jumps [10], C (Code) [19], and other similar notations and not because any computational intuition about them is known or assumed. For each of these kinds,
we will provide an informal operational meaning. Moreover, we will exemplify
the possibility that the proposed unbounded probabilistic jump instructions are
simulated by means of bounded probabilistic test instructions and bounded deterministic jump instructions. We will also refer to related work that introduces
something similar to what we call a probabilistic instruction and connect the proposed kinds of probabilistic instructions with similar features found in related
work.

2

We will refrain from a formal semantic analysis of the proposed kinds of
probabilistic instructions. When we started with the work reported upon in this
paper, the reasons for doing so were as follows:
– In the non-probabilistic case, the subject reduces to the semantics of PGA.
Although it seems obvious at first sight, different models, reflecting different
levels of abstraction, can and have been distinguished (see e.g. [9]). Probabilities introduce a further ramification.
– What we consider sensible is to analyse this double ramification fully. What
we consider less useful is to provide one specific collection of design decisions
and working out its details as a proof of concept.
– We notice that for process algebra the ramification of semantic options after
the incorporation of probabilistic features is remarkable, and even frustrating
(see e.g. [24,27]). There is no reason to expect that the situation is much
simpler here.
– Once that a semantic strategy is mainly judged on its preparedness for a
setting with multi-threading, the subject becomes intrinsically complex –
like the preparedness for a setting with arbitrary interleaving complicates
the semantic modeling of deterministic processes in process algebra.
– We believe that a choice for a catalogue of kinds of probabilistic instructions
can be made beforehand. Even if that choice will turn out to be wrong,
because prolonged forthcoming semantic analysis may give rise to new, more
natural, kinds of probabilistic instructions, it can at this stage best be driven
by direct intuitions.
In this paper, we will leave unanalysed the topic of probabilistic instruction
sequence processing, i.e. probabilistic processing of instruction sequences, which
includes all phenomena concerning services and concerning execution architectures for which probabilistic analysis is necessary. At the same time, we admit
that probabilistic instruction sequence processing is a much more substantial
topic than probabilistic instruction sequences, because of its machine-oriented
scope. We take the line that a probabilistic instruction sequence finds its operational meaning by translation into a deterministic instruction sequence and
execution using an execution architecture with probabilistic features.

3

Preliminaries

In the remainder of this paper, we will use the notation and terminology regarding instructions and instruction sequences from PGA. The mathematical
structure that we will use for quantities is a signed cancellation meadow. That
is why we briefly review PGA and signed cancellation meadows in this section.
In PGA, it is assumed that a fixed but arbitrary set of basic instructions has
been given. The primitive instructions of PGA are the basic instructions and in
addition:
– for each basic instruction a, a positive test instruction +a;
3

– for each basic instruction a, a negative test instruction −a;
– for each natural number l, a forward jump instruction #l;
– a termination instruction !.
The intuition is that the execution of a basic instruction a produces either T
or F at its completion. In the case of a positive test instruction +a, a is executed
and execution proceeds with the next primitive instruction if T is produced.
Otherwise, the next primitive instruction is skipped and execution proceeds with
the primitive instruction following the skipped one. If there is no next instruction to be executed, execution becomes inactive. In the case of a negative test
instruction −a, the role of the value produced is reversed. In the case of a plain
basic instruction a, execution always proceeds as if T is produced. The effect
of a forward jump instruction #l is that execution proceeds with the l-th next
instruction. If l equals 0 or the l-th next instruction does not exist, execution
becomes inactive. The effect of the termination instruction ! is that execution
terminates.
The constants of PGA are the primitive instructions and the operators of
PGA are:
– the binary concatenation operator ; ;
– the unary repetition operator ω .
Terms are built as usual. We use infix notation for the concatenation operator
and postfix notation for the repetition operator.
A closed PGA term is considered to denote a non-empty, finite or periodic
infinite sequence of primitive instructions.1 Closed PGA terms are considered
equal if they denote the same instruction sequence. The axioms for instruction
sequence equivalence are given in [9]. The unfolding equation X ω = X ; X ω is
derivable from those equations. Moreover, each closed PGA term is derivably
equal to one of the form P or P ; Qω , where P and Q are closed PGA terms in
which the repetition operator does not occur.
In [9], PGA is extended with a unit instruction operator u which turns
sequences of instructions into single instructions. The result is called PGAu .
In [35], the meaning of PGAu programs is described by a translation from PGAu
programs into PGA programs.
In the sequel, the following additional assumption is made: a fixed but arbitrary set of foci and a fixed but arbitrary set of methods have been given.
Moreover, we will use f.m, where f is a focus and m is a method, as a general
notation for basic instructions. In f.m, m is the instruction proper and f is the
name of the service that is designated to process m.
The signature of signed cancellation meadows consists of the following constants and operators:
– the constants 0 and 1;
– the binary addition operator + ;
1

A periodic infinite sequence is an infinite sequence with only finitely many distinct
suffixes.

4

–
–
–
–

the
the
the
the

binary multiplication operator · ;
unary additive inverse operator −;
unary multiplicative inverse operator
unary signum operator s.

−1

;

Terms are build as usual. We use infix notation for the binary operators
+ and · , prefix notation for the unary operator −, and postfix notation for
the unary operator −1 . We use the usual precedence convention to reduce the
need for parentheses. We introduce subtraction and division as abbreviations:
p − q abbreviates p + (−q) and p/q abbreviates p · (q −1 ). We use the notation n
for numerals and the notation pn for exponentiation with a natural number as
exponent. The term n is inductively defined as follows: 0 = 0 and n + 1 = n + 1.
The term pn is inductively defined as follows: p0 = 1 and pn+1 = pn · p.
The constants and operators from the signature of signed cancellation meadows are adopted from rational arithmetic, which gives an appropriate intuition
about these constants and operators. The equational theories of signed cancellation meadows is given in [8]. In signed cancellation meadows, the functions min
and max have a simple definition (see also [8]).
A signed cancellation meadow is a cancellation meadow expanded with a
signum operation. The prime example of cancellation meadows is the field of rational numbers with the multiplicative inverse operation made total by imposing
that the multiplicative inverse of zero is zero, see e.g. [20].

4

Probabilistic Basic and Test Instructions

In this section, we propose several kinds of probabilistic basic and test instructions. It is assumed that a fixed but arbitrary signed cancellation meadow M
has been given. Moreover, we write q̂, where q ∈ M, for max(0, min(1, q)).
We propose the following probabilistic basic instructions:
– %(), which produces T with probability 1/2 and F with probability 1/2;
– %(q), which produces T with probability q̂ and F with probability 1 − q̂,
for q ∈ M.
The probabilistic basic instructions have no side-effect on a state.
The basic instruction %() can be looked upon as a shorthand for %(1/2). We
distinguish between %() and %(1/2) for reason of putting the emphasis on the
fact that it is not necessary to bring in a notation for quantities ranging from 0
to 1 in order to design probabilistic instructions.
Once that probabilistic basic instructions of the form %(q) are chosen, an
unbounded ramification of options for the notation of quantities is opened up. We
will assume that closed terms over the signature of signed
√ cancellation meadows
are used to denote quantities. Instructions such as %( 1 + 1) are implicit in the
√
form %(q), assuming that it is known how to view
as a notational extension
of signed cancellation meadows (see e.g. [8]).
Like all basic instructions, each probabilistic basic instruction give rise to
two probabilistic test instructions:
5

– %() gives rise to +%() and −%();
– %(q) gives rise to +%(q) and −%(q).
Probabilistic primitive instructions of the form +%(q) and −%(q) can be considered probabilistic branch instructions where q is the probability that the branch
is not taken and taken, respectively, and likewise the probabilistic primitive instructions +%() and −%().
We find that the primitive instructions %() and %(q) can be replaced by #1
without loss of (intuitive) meaning. Of course, in a resource aware model, #1
may be much cheaper than %(q), especially if q is hard to compute. Suppose
that %(q) is realized at a lower level by means of %(), which is possible, and
suppose that q is a computable real number. The question arises whether the
expectation of the time to execute %(q) is finite.
To exemplify the possibility that %(q) is realized by means of %() in the case
where q is a rational number, we look at the following probabilistic instruction
sequences:
−%(2/3) ; #3 ; a ; ! ; b ; ! ,

(+%() ; #3 ; a ; ! ; +%() ; #3 ; b ; !)ω .

It is easy to see that these instruction sequences produce on execution the same
behaviour: with probability 2/3, first a is performed and then termination follows; and with probability 1/3, first b is performed and then termination follows.
In the case of computable real numbers other than rational numbers, use must
be made of a service that does duty for the tape of a Turing machine (such a
service is, for example, described in [18]).
Let q ∈ M, and let random(q) be a service with a method get whose reply is T with probability q̂ and F with probability 1 − q̂. Then a reasonable
view on the meaning of the probabilistic primitive instructions %(q), +%(q) and
−%(q) is that they are translated into the deterministic primitive instructions
random(q).get, +random(q).get and −random(q).get, respectively, and executed
using an execution architecture that provides the probabilistic service random(q).
Another option is possible here: instead of a different service random(q) for each
q ∈ [0, 1] and a single method get, we could have a single service random with
a different method get(q) for each q ∈ [0, 1]. In the latter case, %(q), +%(q)
and −%(q) would be translated into the deterministic primitive instructions
random.get(q), +random.get(q) and −random.get(q).

5

Probabilistic Jump Instructions

In this section, we propose several kinds of probabilistic jump instructions. It
is assumed that the signed cancellation meadow M has been expanded with an
operation N such that, for all q ∈ M, N(q) = 0 iff q = n for some n ∈ N.
We write l̄, where l ∈ M is such that N(l) = 0, for the unique n ∈ N such that
l = n.
We propose the following probabilistic jump instructions:
6

– #%U(k), having the same effect as #j with probability 1/k for j ∈ [1, k̄],
for k ∈ M with N(k) = 0;
– #%G(q)(k), having the same effect as #j with probability q̂ · (1 − q̂)j−1 for
j ∈ [1, k̄], for q ∈ M and k ∈ M with N(k) = 0;
– #%G(q)l, having the same effect as #l̄ · j with probability q̂ · (1 − q̂)j−1 for
j ∈ [1, ∞), for q ∈ M and l ∈ M with N(l) = 0.
The letter U in #%U(k) indicates a uniform probability distribution, and the
letter G in #%G(q)(k) and #%G(q)l indicates a geometric probability distribution. Instructions of the forms #%U(k) and #%G(q)(k) are bounded probabilistic jump instructions, whereas instructions of the form #%G(q)l are unbounded
probabilistic jump instructions.
Like in the case of the probabilistic basic instructions, we propose in addition
the following probabilistic jump instructions:
– #%G()(k) as the special case of #%G(q)(k) where q = 1/2;
– #%G()l as the special case of #%G(q)l where q = 1/2.
We believe that it must be possible to eliminate all probabilistic jump instructions. In particular, we believe that it must be possible to eliminate all
unbounded probabilistic jump instructions. This belief can be understood as the
judgement that it is reasonable to expect from a semantic model of probabilistic
instruction sequences that the following identity and similar ones hold:
+a ; #%G()2 ; (+b ; ! ; c)ω =
+a ; +%() ; #8 ; #10 ;
(+b ; #5 ; #10 ; +%() ; #8 ; #10 ;
! ; #5 ; #10 ; +%() ; #8 ; #10 ;
c ; #5 ; #10 ; +%() ; #8 ; #10)ω .
Taking this identity and similar ones as our point of departure, the question arises
what is the most simple model that justifies them. A more general question is
whether instruction sequences with unbounded probabilistic jump instructions
can be translated into ones without probabilistic jump instructions provided it
does not bother us that the instruction sequences may become much longer (e.g.
expectation of the length bounded, but worst case length unbounded).

6

The Probabilistic Process Algebra Thesis

In the absence of probabilistic instructions, threads as considered in BTA (Basic
Thread Algebra) [9] or its extension with thread-service interaction [17] can
be used to model the behaviours produced by instruction sequences under execution.2 Processes as considered in general process algebras such as ACP [6],
2

In [9], BTA is introduced under the name BPPA (Basic Polarized Process Algebra).

7

CCS [32] and CSP [26] can be used as well, but they give rise to a more complicated modeling of the behaviours of instruction sequences under execution (see
e.g. [13]).
In the presence of probabilistic instructions, we would need a probabilistic
thread algebra, i.e. a variant of BTA or its extension with thread-service interaction that covers probabilistic behaviours. When we started with the work
reported upon in this paper, it appeared that any probabilistic thread algebra is
inherently more complicated to such an extent that the advantage of not using a
general process algebra evaporates. Moreover, it appeared that any probabilistic
thread algebra requires justification by means of an appropriate probabilistic
process algebra. This led us to the following thesis:
Thesis. Modeling the behaviours produced by probabilistic instruction sequences
under execution is a matter of using directly processes as considered in some
probabilistic process algebra.
A probabilistic thread algebra has to cover the interaction between instruction sequence behaviours and services. Two mechanisms are involved in that.
They are called the use mechanism and the apply mechanism (see e.g. [17]).
The difference between them is a matter of perspective: the former is concerned
with the effect of services on behaviours of instruction sequences and therefore
produces behaviours, whereas the latter is concerned with the effect of instruction sequence behaviours on services and therefore produces services. When we
started with the work reported upon in this paper, it appeared that the use
mechanism would make the development of a probabilistic thread algebra very
intricate.
The first version of this paper triggered off work on the behaviour of probabilistic instruction sequences under execution by which the thesis stated above
is refuted. The ultimate point is that meanwhile an appropriate and relatively
simple probabilistic thread algebra has been devised (see [16]). Moreover, our
original expectations about probabilistic process algebras turned out to be too
high.
The first probabilistic process algebra is presented in [23] and the first probabilistic process algebra with an asynchronous parallel composition operator is
presented in [5]. A recent overview of the work on probabilistic process algebras
after that is given in [29]. This overview shows that the multitude of semantic
ideas applied and the multitude of variants of certain operators devised have
kept growing, and that convergence is far away. In other words, there is little well-established yet. In particular, for modeling the behaviours produced by
probabilistic instruction sequences, we need operators for probabilistic choice,
asynchronous parallel composition, and abstraction from internal actions. For
this case, the attempts by one research group during about ten years to develop a satisfactory ACP-like process algebra (see e.g. [1,2,3]) have finally led
to a promising process algebra. However, it is not yet clear whether the process
algebra concerned will become well-established.

8

All this means that a justification of the above-mentioned probabilistic thread
algebra by means of an appropriate probabilistic process algebra will be of a
provisional nature for the time being.

7

Discussion of Projectionism

Notice that once we move from deterministic instructions to probabilistic instructions, instruction sequence becomes an indispensable concept. Instruction
sequences cannot be replaced by threads or processes without taking potentially
premature design decisions. In preceding sections, however, we have outlined
how instruction sequences with the different kinds of probabilistic instructions
can be translated into instruction sequences without them. Therefore, it is a
reasonable to claim that, like for deterministic instruction sequence notations,
all probabilistic instruction sequence notations can be provided with a probabilistic semantics by translation of the instruction sequences concerned into
appropriate single-pass instruction sequences. Thus, we have made it plausible
that projectionism is feasible for probabilistic instruction sequences.
Projectionism is the point of view that:
– any instruction sequence P , and more general even any program P , first and
for all represents a single-pass instruction sequence as considered in PGA;
– this single-pass instruction sequence, found by a translation called a projection, represents in a natural and preferred way what is supposed to take
place on execution of P ;
– PGA provides the preferred notation for single-pass instruction sequences.
In a rigid form, as in [9], projectionism provides a definition of what constitutes
a program.
The fact that projectionism is feasible for probabilistic instruction sequences,
does not imply that it is uncomplicated. To give an idea of the complications
that may arise, we will sketch below found challenges for projectionism.
First, we introduce some special notation. Let N be a program notation. Then
we write N2pga for the projection function that gives, for each program P in N,
the closed PGA terms that denotes the single-pass instruction sequence that
produces on execution the same behaviour as P .
We have found the following challenges for projectionism:
– Explosion of size. If N2pga(P ) is much longer than P , then the requirement
that it represents in a natural way what is supposed to take place on execution of P is challenged. For example, if the primitive instructions of N include
instructions to set and test up to n Boolean registers, then the projection to
N2pga(P ) may give rise to a combinatorial explosion of size. In such cases,
the usual compromise is to permit single-pass instruction sequences to make
use of services (see e.g. [17]).
– Degradation of performance. If N2pga(P )’s natural execution is much slower
than P ’s execution, supposing a clear operational understanding of P , then
9

the requirement that it represents in a natural way what is supposed to
take place on execution of P is challenged. For example, if the primitive
instructions of N include indirect jump instructions, then the projection to
N2pga(P ) may give rise to a degradation of performance (see e.g. [10]).
– Incompatibility of services. If N2pga(P ) has to make use of services that are
not deterministic, then the requirement that it represents in a natural way
what is supposed to take place on execution of P is challenged. For example,
if the primitive instructions of N include instructions of the form +%(q) or
−%(q), then P cannot be projected to a single-pass instruction sequence
without the use of probabilistic services. In this case, either probabilistic
services must be permitted or probabilistic instruction sequences must not
be considered programs.
– Complexity of projection description. The description of N2pga may be so
complex that it defeats N2pga(P )’s purpose of being a natural explanation of
what is supposed to take place on execution of P . For example, the projection semantics given for recursion in [7] suffers from this kind of complexity
when compared with the conventional denotational semantics. In such cases,
projectionism may be maintained conceptually, but rejected pragmatically.
– Aesthetic degradation. In N2pga(P ), something elegant may have been replaced by nasty details. For example, if N provides guarded commands, then
N2pga(P ), which will be much more detailed, might be considered to exhibit
signs of aesthetic degradation. This challenge is probably the most serious
one, provided we accept that such elegant features belong to program notations. Of course, it may be decided to ignore aesthetic criteria altogether.
However, more often than not, they have both conceptual and pragmatic
importance.
One might be of the opinion that conceptual projectionism can accept explosion of size and/or degradation of performance. We do not share this opinion:
both challenges require a more drastic response than a mere shift from a pragmatic to a conceptual understanding of projectionism. This drastic response may
include viewing certain mechanisms as intrinsically indispensable for either execution performance or program compactness. For example, it is reasonable to
consider the basic instructions of the form %(q), where q is a computable real
number, indispensable if the expectations of the times to execute their realizations by means of %() are not all finite.
Nevertheless, projectionism looks to be reasonable for probabilistic programs:
they can be projected adequately to deterministic single-pass instruction sequences for an execution architecture with probabilistic services.

8

Related Work

In [38], a notation for probabilistic programs is introduced in which we can write,
for example, random(p·δ0 +q·δ1 ). In general, random(λ) produces a value according to the probability distribution λ. In this case, δi is the probability distribution
that gives probability 1 to i and probability 0 to other values. Thus, for p+q = 1,
10

p·δ0 +q·δ1 is the probability distribution that gives probability p to 0, probability
q to 1, and probability 0 to other values. Clearly, random(p·δ0 +q·δ1 ) corresponds
to %(p). Moreover, using this kind of notation, we could write #( k1 ·(δ1 +· · ·+δk̄ ))
for #%U(k) and #(q̂ · δ1 + q̂ · (1 − q̂) · δ2 + · · · + q̂ · (1 − q̂)k−1 · δk ) for #%G(q)(k).
In much work on probabilistic programming, see e.g. [25,30,33], we find the
binary probabilistic choice operator p ⊕ (for p ∈ [0, 1]). This operator chooses
between its operands, taking its left operand with probability p. Clearly, P p ⊕ Q
can be taken as abbreviations for +%(p);u(P ;#2);u(Q). This kind of primitives
dates back to [28] at least.
Quite related, but from a different perspective, is the toss primitive introduced in [21]. The intuition is that toss(bm, p) assigns to the Boolean memory
cell bm the value T with probability p̂ and the value F with probability 1− p̂. This
means that toss(bm, p) has a side-effect on a state, which we understand as making use of a service. In other words, toss(bm, p) corresponds to a deterministic
instruction intended to be processed by a probabilistic service.
Common in probabilistic programming are assignments of values randomly
chosen from some interval of natural numbers to program variables (see e.g. [37]).
Clearly, such random assignments correspond also to deterministic instructions
intended to be processed by probabilistic services. Suppose that x=i is a primitive instruction for assigning value i to program variable x. Then we can write:
#%U(k) ; u(x=1 ; #k) ; u(x=2 ; #k−1) ; . . . ; u(x=k ; #1). This is a realistic representation of the assignment to x of a value randomly chosen from {1, . . . , k}.
However, it is clear that this way of representing random assignments leads to
an exponential blow up in the size of any concrete instruction sequence representation, provided the concrete representation of k is its decimal representation.
The refinement oriented theory of programs uses demonic choice, usually
written ⊓, as a primitive (see e.g. [30,31]). A demonic choice can be regarded as a
probabilistic choice with unknown probabilities. Demonic choice could be written
+⊓ in a PGA-like notation. However, a primitive instruction corresponding to
demonic choice is not reasonable: no mechanism for the execution of +⊓ is
conceivable. Demonic choice exists in the world of specifications, but not in the
world of instruction sequences. This is definitely different with +%(p), because
a mechanism for its execution is conceivable.
Features similar to probabilistic jump instructions are not common in probabilistic programming. To our knowledge, the mention of probabilistic goto statements of the form pr goto {l1 , l2 } in [4] is the only mention of a similar feature
in the computer science literature. The intuition is that pr goto {l1 , l2 }, where
l1 and l2 are labels, has the same effect as goto l1 with probability 1/2 and has
the same effect as goto l2 with probability 1/2. Clearly, this corresponds to a
probabilistic jump instruction of the form #%U(1/2).
It appears that quantum computing has something to offer that cannot be
obtained by conventional computing: it makes a stateless generator of random
bits available (see e.g. [22,34]). By that quantum computing indeed provides a
justification of +%(1/2) as a probabilistic instruction.

11

9

On the Sequel to this Paper

The first version of this paper triggered off work on the behaviour of probabilistic
instruction sequences under execution and outcomes of that work invalidated
some of the arguments used to motivate the restricted scope of this paper. In
this section, we mention the relevant outcomes of that work.
After the first version of this paper (i.e. [11]) appeared, it was found that:
– The different levels of abstraction that have been distinguished in the nonprobabilistic case can be distinguished in the probabilistic case as well and
only the models at the level of the behaviour of instruction sequences under
execution are not essentially the same.
– The semantic options at the behavioural level after the incorporation of
probabilistic features are limited because of (a) the orientation towards behaviours of a special kind and (b) the semantic constraints induced by the
informal explanations of the enumerated kinds of probabilistic instructions
and the desired elimination property of all but one kind.
– For the same reasons, preparedness for a setting with multi-threading does
not really complicate matters.
The current state of affairs is as follows:
– BTA and its extension with thread-service interaction, which are used to
describe the behaviour of instruction sequences under execution in the nonprobabilistic case, have been extended with probabilistic features in [16].
– In [16], we have added the probabilistic basic and test instructions proposed in Section 4 to PGLB (ProGramming Language B), an instruction
sequence notation rooted in PGA and close to existing assembly languages,
and have given a formal definition of the behaviours produced by the instruction sequences from the resulting instruction sequence notation in terms of
non-probabilistic instructions and probabilistic services.
– The bounded probabilistic jump instructions proposed in Section 5 can be
given a behavioural semantics in the same vein. The unbounded probabilistic
jump instructions fail to have a natural behavioural semantics in the setting
of PGA because infinite instruction sequences are restricted to eventually
periodic ones.
– The extension of BTA with multi-threading, has been generalized to probabilistic multi-threading in [16] as well.

10

Conclusions

We have made a notational proposal of probabilistic instructions with an informal semantics. By that we have contrasted probabilistic instructions in an execution architecture with deterministic services with deterministic instructions in
an execution architecture with partly probabilistic services. The history of the
proposed kinds of instructions can be traced.
12

We have refrained from an ad hoc formal semantic analysis of the proposed
kinds of instructions. There are many solid semantic options, so many and so
complex that another more distant analysis is necessary in advance to create a
clear framework for the semantic analysis in question.
The grounds of this work are our conceptions of what a theory of probabilistic
instruction sequences and a complementary theory of probabilistic instruction
sequence processing (i.e. execution architectures with probabilistic services) will
lead to:
– comprehensible explanations of relevant probabilistic algorithms, such as the
Miller-Rabin probabilistic primality test [36], with precise descriptions of the
kinds of instructions and services involved in them;
– a solid account of pseudo-random Boolean values and pseudo-random numbers;
– a thorough exposition of the different semantic options for probabilistic instruction sequences;
– explanations of relevant quantum algorithms, such as Shor’s integer factorization algorithm [39], by first giving a clarifying analysis in terms of probabilistic instruction sequences or execution architectures with probabilistic
services and only then showing how certain services in principle can be realized very efficiently with quantum computing.
Projectionism looks to be reasonable for probabilistic programs: they can be
projected adequately to deterministic single-pass instruction sequences for an
execution architecture with appropriate probabilistic services. At present, it is
not entirely clear whether this extends to quantum programs.

References
1. Andova, S., Baeten, J.C.M.: Abstraction in probabilistic process algebra. In: Margaria, T., Yi, W. (eds.) TACAS 2001. Lecture Notes in Computer Science, vol.
2031, pp. 204–219. Springer-Verlag (2001)
2. Andova, S., Baeten, J.C.M., Willemse, T.A.C.: A complete axiomatisation of
branching bisimulation for probabilistic systems with an application in protocol
verification. In: Baier, C., Hermans, H. (eds.) CONCUR 2006. Lecture Notes in
Computer Science, vol. 4137, pp. 327–342. Springer-Verlag (2006)
3. Andova, S., Georgievska, S.: On compositionality, efficiency, and applicability of
abstraction in probabilistic systems. In: Nielsen, M., et al. (eds.) SOFSEM 2009.
Lecture Notes in Computer Science, vol. 5404, pp. 67–78. Springer-Verlag (2009)
4. Arons, T., Pnueli, A., Zuck, L.: Parameterized verification by probabilistic abstraction. In: Gordon, A.D. (ed.) FOSSACS 2003. Lecture Notes in Computer Science,
vol. 2620, pp. 87–102. Springer-Verlag (2003)
5. Baeten, J.C.M., Bergstra, J.A., Smolka, S.A.: Axiomatizing probabilistic processes:
ACP with generative probabilities. Information and Computation 121(2), 234–255
(1995)
6. Baeten, J.C.M., Weijland, W.P.: Process Algebra, Cambridge Tracts in Theoretical
Computer Science, vol. 18. Cambridge University Press, Cambridge (1990)

13

7. Bergstra, J.A., Bethke, I.: Predictable and reliable program code: Virtual machine
based projection semantics. In: Bergstra, J.A., Burgess, M. (eds.) Handbook of
Network and Systems Administration, pp. 653–685. Elsevier, Amsterdam (2007)
8. Bergstra, J.A., Bethke, I., Ponse, A.: Cancellation meadows: A generic basis theorem and some applications. Computer Journal 56(1), 3–14 (2013)
9. Bergstra, J.A., Loots, M.E.: Program algebra for sequential code. Journal of Logic
and Algebraic Programming 51(2), 125–156 (2002)
10. Bergstra, J.A., Middelburg, C.A.: Instruction sequences with indirect jumps. Scientific Annals of Computer Science 17, 19–46 (2007)
11. Bergstra, J.A., Middelburg, C.A.: Instruction sequence notations with probabilistic
instructions. arXiv:0906.3083v1 [] (June 2009)
12. Bergstra, J.A., Middelburg, C.A.: Instruction sequence processing operators. Acta
Informatica 49(3), 139–172 (2012)
13. Bergstra, J.A., Middelburg, C.A.: On the behaviours produced by instruction sequences under execution. Fundamenta Informaticae 120(2), 111–144 (2012)
14. Bergstra, J.A., Middelburg, C.A.: On the expressiveness of single-pass instruction
sequences. Theory of Computing Systems 50(2), 313–328 (2012)
15. Bergstra, J.A., Middelburg, C.A.: Instruction sequence based non-uniform complexity classes. Scientific Annals of Computer Science 24(1), 47–89 (2014)
16. Bergstra, J.A., Middelburg, C.A.: A thread algebra with probabilistic features.
arXiv:1409.6873v1 [cs.LO] (September 2014)
17. Bergstra, J.A., Ponse, A.: Combining programs and state machines. Journal of
Logic and Algebraic Programming 51(2), 175–192 (2002)
18. Bergstra, J.A., Ponse, A.: Execution architectures for program algebra. Journal of
Applied Logic 5(1), 170–192 (2007)
19. Bergstra, J.A., Ponse, A.: An instruction sequence semigroup with involutive antiautomorphisms. Scientific Annals of Computer Science 19, 57–92 (2009)
20. Bergstra, J.A., Tucker, J.V.: The rational numbers as an abstract data type. Journal of the ACM 54(2), Article 7 (2007)
21. Chadha, R., Cruz-Filipe, L., Mateus, P., Sernadas, A.: Reasoning about probabilistic sequential programs. Theoretical Computer Science 379(1–2), 142–165 (2007)
22. Gay, S.J.: Quantum programming languages: Survey and bibliography. Mathematical Structures in Computer Science 16(4), 581–600 (2006)
23. Giacalone, A., Jou, C.C., Smolka, S.A.: Algebraic reasoning for probabilistic concurrent systems. In: Proceedings IFIP TC2 Working Conference on Programming
Concepts and Methods. pp. 443–458. North-Holland (1990)
24. van Glabbeek, R.J., Smolka, S.A., Steffen, B.: Reactive, generative and stratified models of probabilistic processes. Information and Computation 121(1), 59–80
(1995)
25. He Jifeng, Seidel, K., McIver, A.K.: Probabilistic models for the guarded command
language. Science of Computer Programming 28(2–3), 171–192 (1997)
26. Hoare, C.A.R.: Communicating Sequential Processes. Prentice-Hall, Englewood
Cliffs (1985)
27. Jonsson, B., Larsen, K.G., Yi, W.: Probabilistic extensions of process algebras. In:
Bergstra, J.A., Ponse, A., Smolka, S.A. (eds.) Handbook of Process Algebra, pp.
685–710. Elsevier, Amsterdam (2001)
28. Kozen, D.: A probabilistic PDL. Journal of Computer and System Sciences 30(2),
162–178 (1985)
29. López, N., Núñez, M.: An overview of probabilistic process algebras and their
equivalences. In: Baier, C., et al. (eds.) Validation of Stochastic Systems. Lecture
Notes in Computer Science, vol. 2925, pp. 89–123. Springer-Verlag (2004)

14

30. McIver, A.K., Morgan, C.C.: Demonic, angelic and unbounded probabilistic choices
in sequential programs. Acta Informatica 37(4–5), 329–354 (2001)
31. Meinicke, L., Solin, K.: Refinement algebra for probabilistic programs. Electronic
Notes in Theoretical Computer Science 201, 177–195 (2008)
32. Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs
(1989)
33. Morgan, C.C., McIver, A.K., Seidel, K.: Probabilistic predicate transformers. ACM
Transactions on Programming Languages and Systems 18(3), 325–353 (1996)
34. Perdrix, S., Jorrand, P.: Classically controlled quantum computation. Mathematical Structures in Computer Science 16(4), 601–620 (2006)
35. Ponse, A.: Program algebra with unit instruction operators. Journal of Logic and
Algebraic Programming 51(2), 157–174 (2002)
36. Rabin, M.O.: Probabilistic algorithms. In: Traub, J.F. (ed.) Algorithms and Complexity: New Directions and Recent Results, pp. 21–39. Academic Press, New York
(1976)
37. Schöning, U.: A probabilistic algorithm for k-SAT based on limited local search
and restart. Algorithmica 32(4), 615–623 (2002)
38. Sharir, M., Pnueli, A., Hart, S.: Verification of probabilistic programs. SIAM Journal of Computing 13(2), 292–314 (1984)
39. Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: FOCS ’94. pp. 124–134. IEEE Computer Society Press (1994)

15

