Kahn Process Networks and a Reactive Extension - Signal Processing Systems - page 1026

of channels to a non-empty string. A finite history is a finite element of the CPO of
histories. (Recall from [ 14 ] that an element k ∈ X of a CPO ( X , ) is a finite element

if for every chain D ⊆ X ,if k D then there is some d ∈ D such that k d .)

2 Denotational Semantics

We discuss the formal definition of the semantics, i.e., the behavior, of a KPN.
Traditionally, the focus is on the functional input/output behavior of the network,
abstracting from the timing. More precisely, we are interested in a function relating
the output produced by the network to the input provided to the network. For the
JPEG decoder for instance, the sequence of decoded output blocks is a function
of the compressed input data. We first concentrate on a denotational semantics,
focussing on what input/output relation a KPN computes and later, in Sect. 3 on an
operational semantics, which also captures how that output is computed.
The denotational semantics of KPNs [ 29 ] defines the behavior of a KPN as
a Scott-continuous input/output function on the input or output stream histories.
Assuming that the (Scott-continuous) input/output functions of the individual
processes are known, then the input/output function of the KPN as a whole can be
defined as the least fixed-point of a collection of equations specifying the relations
between channel histories based on the processes. For the JPEG example, the overall
function is straightforwardly obtained by function composition. A more challenging
situation arises when there is feedback, such as in the Fibonacci example.
AKPN process with m inputs and n outputs is a function f : ( Σ ∗, ω ) → ( Σ ∗, ω )

n
with the characteristic (Scott-continuity) such that it preserves least upper bounds :
f

m

( i k )= f ( i k ) . This implies that such a processes is monotone :if i j then f ( i )

; when additional input is provided, additional output may be produced, but
existing output cannot be changed.
Because processes may exhibit memory (the current output may depend on input
from the past), the function is defined in terms of the sequences representing the
entire input history of the channel.
The functions of the individual processes of the Fibonacci example can be
defined as follows. Delayn :

f ( j )

N ∗, ω → N ∗, ω ; i ∈ N ∗, ω ; n

∈{ 0 , 1 } :

Delayn( i )= n · i (1)

(N ∗, ω )

2

→ N ∗, ω is defined inductively by the following equations ( i ∈ N ∗, ω ;

Add : , j

x , y ∈ N , ε is the empty sequence):

⎧
⎨

Add( , ε )= ε

Add( ε ,

i

(2)

i )= ε

⎩

Add( x · i , y · j )=( x + y ) · Add( i , j )