always better than using more. Hence,
there is no need to make energy consumption a semantic property of computing. Time, on the other hand, needs
to be a semantic property.
Time is a nonfunctional property.
What is the “function” of a program?
In computation, it is a mapping from
sequences of input bits to sequences
of output bits (or an equivalent finite
alphabet). The Turing-Church thesis
defines “computable functions” as
those that can be expressed by a terminating sequence of such bits-to-bits
functions or mathematically by a finite
composition of functions whose domain and co-domain are the set of sequences of bits.
In a CPS application, the function of
a computation is defined by its effect
on the physical world. This effect is no
less a function than a mapping from
bits to bits. It is a function in the intuitive sense of “what is the function of
the system” and can be expressed as a
function in the mathematical sense of
a mapping from a domain to a co-domain. 15 But as a function, the domain
and co-domain are not sequences of
bits. Why do software designers insist
on the wrong definition of “function”?
Designers of operating systems,
Web servers, and communication protocols reactively view programs as a
sequence of input/output events rather
than as a mapping from bits to bits.
This view needs to be elevated from
the theoretical level to the application-programmer level and augmented with
explicit temporal dynamics.
Real time is a quality-of-service (QoS)
problem. Everybody, from architect to
programmer to user, wants quality.
Higher quality is always better than
lower quality (at least under constant
resource use). Indeed, in general-purpose computing, a key quality measure
is execution time (or “performance”).
But time in embedded systems plays
a different role. Less time is not better
than more time, as it is with performance. That less time is better than
more time would imply that it is better for an automobile engine controller to fire the spark plugs earlier than
later. Finishing early is not always a
good thing and can lead to paradoxical
behaviors where finishing early causes
deadlines to be missed. 7 In an analysis
that remains as valid today as it was
when first spelled out by Stankovic
26
who lamented the resulting misconception that real-time computing “is
equivalent to fast computing” or “is
performance engineering.” A CPS requires repeatable behavior much more
than optimized performance.
Precision and variability in timing
are QoS problems, but time itself is
much more than a matter of QoS. If time
is missing from the semantics of programs, then no amount of QoS will adequately address CPS timing properties.
correctness
To solidify this discussion, I’ll now define some terms based on the formal
computational model known as the
“tagged signal model.” 15 A design is a
description of a system; for example,
a C program is a design, so is a C program together with a choice of microprocessor, peripherals, and operating
system. The latter design (a C program
combined with these design choices) is
more detailed (less abstract) than the
former.
More precisely, a design is a set of
behaviors. A behavior is a valuation
of observable variables, including all
externally supplied inputs. These variables may themselves be functions;
for example, in a very detailed design,
each behavior may be a trace of electrical signals at the system’s inputs and
outputs. The semantics of a design is a
set of behaviors.
In practice, a design is given in a design language that may be formal, informal, or some mixture of formal and
informal. A design in a design language
expresses the intent of the designer by
defining the set of acceptable behaviors. Clearly, if the design language
has precise (mathematical) semantics,
then the set of behaviors is unambiguous. There could, of course, be errors
in the expression, in which case the
semantics will include behaviors not
intended by the designer. For example,
a function given in a pure functional
programming language is a design. A
designer can define a behavior to be a
pair of inputs and outputs (arguments
and results). The semantics of the program is the set of all possible behaviors
that defines the function specified by
the program. Alternatively, we could
define a behavior to include timing information (when the input is provided
and the output is produced); in this
case, the semantics of the program includes all possible latencies (outputs
can be produced arbitrarily later than
the corresponding inputs), since nothing about the design language constrains timing.
A correct execution is any execution
that is consistent with the semantics of
the design. That is, given a certain set of
inputs, a correct execution finds a behavior consistent with these inputs in
the semantics. If the design language
has loose or imprecise semantics, then
“correct” executions may be unexpected. Conversely, if the design expresses
every last detail of the implementation,
down to printed circuit boards and
wires, then a correct execution may, by
definition, be any execution performed
by said implementation. For the functional program just described, an execution is correct regardless of how long
it takes to produce the output, because
a program in a functional language
says nothing about timing.
A repeatable property is a property
of behaviors exhibited by every correct execution, given the same inputs;
for example, the numerical value of
the outputs of a pure functional program is repeatable. The timing of the
production of the outputs is not. The
timing can be made repeatable by giving more detail in the design by, for
example, specifying a particular computer, compiler, and initial condition
on caches and memory. The design has
to get far less abstract to make timing
repeatable.
A predictable property is a property
of behaviors that can be determined
in finite time through analysis of the
design. That is, given only the information expressed in the design language,
it needs to be possible to infer that the
property is held by every behavior of a
correct execution. For a particular functional program, the numerical value of
the outputs may be predictable, but
given an expressive-enough functional
language, it will always be possible to
write programs where these outputs
are not predictable. If the language is
Turing complete, then the numerical
value of the outputs may be undecid-able. In practice, even “finite time” is
insufficient for a property to be predictable in practice. To be usefully predictable, properties must be inferred by a
