Informal Summary of Action Notation
The systematic informal description of action notation
summarizes Action Notation, and gives further details. It is
intended for reference.
To make it self-contained, it starts by repeating most of the
to the concepts of actions, data, and yielders given in
Actions are essentially dynamic, computational entities. The
performance of an action directly represents information processing
behaviour and reflects the gradual, step-wise nature of computation. Items of
data are, in contrast, essentially static, mathematical entities,
representing pieces of information, e.g., particular numbers.
Of course actions are `mathematical' too, in the sense that they are abstract,
formally-defined entities, analogous to abstract machines defined in automata
theory. A yielder represents an unevaluated item of data,
whose value depends on the current information, i.e., the
previously-computed and input values that are available to the performance of
the enclosing action. For example, a yielder might always evaluate to the
datum currently stored in a particular cell, which could change during the
performance of an action.
A performance of an action, which may be part
of an enclosing action, either:
Actions can be used to represent the semantics of programs: action
performances correspond to possible program behaviours. Furthermore,
actions can represent the (perhaps indirect) contribution that
parts of programs, such as statements and expressions, make to the
semantics of entire programs.
- completes, corresponding to normal termination (the
performance of the enclosing action proceeds normally); or
- escapes, corresponding to exceptional termination
(parts of the enclosing action are skipped until the escape is trapped); or
- fails, corresponding to abandoning the performance
of an action (the enclosing action performs an alternative action,
if there is one, otherwise it fails too); or
- diverges, corresponding to nontermination (the
enclosing action also diverges).
An action may be nondeterministic, having different possible
performances for the same initial information. Nondeterminism
represents implementation-dependence, where the behaviour of a
program (or the contribution of a part of it) may vary between
different implementations---or even between different instants of
time on the same implementation. Note that nondeterminism does not imply
actual randomness: each implementation of a nondeterministic behaviour may be
The information processed by action performance may be classified
according to how far it tends to be propagated, as follows:
Transient information is made available to an action for immediate
use. Scoped information, in contrast, may generally be referred to
throughout an entire action, although it may also be hidden
temporarily. Stable information can be changed, but not hidden, in
the action, and it persists until explicitly destroyed. Permanent
information cannot even be changed, merely augmented.
- transient: tuples of data, corresponding
to intermediate results;
- scoped: bindings of tokens to data,
corresponding to symbol tables;
- stable: data stored in cells, corresponding to
the values assigned to variables;
- permanent: data communicated between distributed
When an action is performed, transient information is given only on
completion or escape, and scoped information is produced only on
completion. In contrast, changes to stable information and extensions
to permanent information are made during action performance,
and are unaffected by subsequent divergence, failure, or escape.
The different kinds of information give rise to so-called
facets of actions, focusing on the processing of at most one kind
of information at a time:
These facets of actions are independent. For instance,
changing the data stored in a cell---or even unreserving the
cell---does not affect any bindings. There are, however, some
directive actions, which process a mixture of scoped
and stable information, so as to provide finite representations of
self-referential bindings. There are also some hybrid primitive actions
and combinators, which involve more than one kind of information at once, such
as an action that both reserves a cell of storage and gives it as transient
- the basic facet, processing independently of
information (control flows);
- the functional facet, processing transient
information (actions are given and give data);
- the declarative facet, processing scoped
information (actions receive and produce bindings);
- the imperative facet, processing stable
information (actions reserve and unreserve cells
of storage, and change the data stored in cells); and
- the communicative facet, processing permanent
information (actions send messages, receive messages in buffers,
and offer contracts to em agents).
The notation for specifying actions consists of action
primitives, which may involve yielders, and action
combinators, which operate on one or two subactions.
See Section D.9.3 for an explanation of the notation for specifying
sorts of actions.
Yielders are entities that can be evaluated to
yield data during action performance. The data yielded may depend on
the current information, i.e., the given transients, the received
bindings, and the current state of the storage and buffer. In fact action
notation provides primitive yielders that evaluate to compound data (tuples,
maps, lists) representing entire slices of the current information, such as the
current state of storage. Evaluation cannot affect the current information.
Compound yielders can be formed by the application of data
operations to yielders. The data yielded by evaluating a
compound yielder are the result of applying the operation to
the data yielded by evaluating the operands. For instance, one can form the
sum of two number yielders. Items of data are a special case of data yielders,
and always yield themselves when evaluated.
See Section D.9.4 for an explanation of the notation for specifying
sorts of yielders.
The information processed by actions consists of items of
data, organized in structures that give access to the individual
items. Data can include various familiar mathematical entities, such
as truth-values, numbers, characters, strings, lists, sets, and maps.
It can also include entities such as tokens, cells, and agents, used
for accessing other items, and some compound entities with data
components, such as messages and contracts.
Actions themselves are
not data, but they can be incorporated in so-called abstractions,
which are data, and subsequently enacted back into actions.
(Abstraction and enaction are a special case of so-called
reification and reflection.) New kinds of data can be introduced
ad hoc, for representing special pieces of information.
Action Notation |
[Created by Jin Jin Yi and Ana Carla Santos. Last modified at 21 Dec 1997 by Ana Carla]