Automatic Programming for Streams

I. Introduction

Previous work on automatic programming (e.g., [Biermann et al 84]) has been concerned with sequential programs whose inputs are available before the program executes and whose outputs need not be produced until the program terminates. However. many computations must deal with data which is not available until after the program has started and must produce data before it terminates. In fact , in many cases the program must not terminate; rather it must continually execute, responding to input data as they become available and producing output data whenever appropriate. Such computations are usually modeled as communicating concurrent processes. One form of communication among such processes 1nvolves streams of data. In this paper, the automatic programming problem for stream programs will be defined and an approach to solving the problem will be described.

II. The Problem

A. Streams

There are several ways to model computation with streams, ranging from pure dataflow [Ackerman 82] to coarse-grained dataflow [Kahn and McQueen 77] to pipes [Ritchie and Thompson 74] In our work, we use a model called the Stream Machine, which is essentially a coarse-grained dataflow model with extensions for real -time computations [Barth , Guthery, and Barstow 85].

For the sake of clarity, a somewhat simplified formulation will be used in this paper:

A stream is a sequence of data values:

terms are partitioned into three sets, input terms, output terms, and intermediate terms. There are two sets of predicates: preconditions are predicates whose arguments are input terms; postconditions are predicates whose arguments are input. output, or intermediate terms.

Such a specification is similar to specification techniques for conventional sequential programs [Biermann et al 84]. In fact. if there are no stream terms, we have a conventional style of specification. For such conventional specifications, a program would be said to satisfy the specifications if, for all values of the input terms which satisfy the preconditions. the program terminates with values for the output terms which satisfy all of the postconditions. However, since there may be streams in the specification and since stream programs may not terminate. we must define the requirements for a target program somewhat differently. Informally, we would like the program to guarantee that all postconditions are satisfied by all stream elements which have been consumed or produced so far. Somewhat more formally, a program will be said to satisfy a specification if, for all sequences of initial values on input streams which satisfy the preconditions, the program eventually produces output streams whose initial values satisfy the postconditions. For example, consider the specification:

where INPUT and OUTPUT are input and output streams respectively. A program satisfies this specification if, for all sequences of initial values, INPUT[1], INPUT[2], ... , INPUT[n ], the program eventually produces at least n elements of OUTPUT such that

Thus, the automatic programming problem for streams is to transform a specification of the form given above into a set of programs, each described in a sequential language extended with stream constructs, that satisfies the specification.

Ill. An Approach

A. Relations on Streams

The difficult part in specifying a stream program is to describe the pre- and postconditions. In our work, we initially tried to use a relatively general technique in which relations referenced stream values directly by their indices. We found, however. that subsequent reasoning about the specifications was quite difficult for many common cases (e.g. merging two streams together to create a third) because the manipulations of stream indices was fairly complex. To simplify both specifications and subsequent reasoning we are using a technique based on operators and relations oriented toward streams, rather than toward stream elements. The particular operators which we have found useful Generate(F)

F is a function of one integer argument. The resulting stream consists of successive values of F for the natural numbers. That is:

StreamMap(F,s 1 ,s2"'.,sk)

The S; are all streams: F is a function of k arguments defined on the types of the elements of the s. streams. The resulting stream contains the value of F ~pplied to successive elements of the s. streams: I

Fi/ler(S,P)

s and P are streams. The elements of s are of any type; the elements of P are Booleans. The elements of the resulting filtered stream are those elements of s for which the corresponding element of Pis true. More formally:

where i is the smallest integer such that True occurs i times in {P[1],P[2], ... P[j]}. Note that this implies that P[j] = True.

The elements of the S; streams are all of the same type; the elements of c are integers in the range [1 .... ,k]. The resulting stream contains all of the elements of the s; streams, merged according to the elements of c:

where i is the number of occurrences of c[i] in { c[1],c[2], .... c[i]}.

Shifi(S,k)

s is a stream; k is an integer. The elements of the resulting stream are the same as the elements of s, shifted by k indices. More formally,

Packing(S,k)

s is a stream; k is an integer. The elements of th~ resulting stream are vectors · of length k whose elements, are of the same type as the elements of s. The vectors in the resulting stream correspond to continuous sub~equences of the elements of s:

Window(S,k)

sis a stream; k is an integer. The elements of the resulting stream are vectors of length k whose elements are of the same type as the elements of s. The vectors in the resulting stream correspond to a moving window over s:

In addition. we require one type of stream predicate which cannot be expressed as a simple stream operator:

The s; are all streams; R is a relation of k arguments

· Angle brackets will be used lo denote the construction of a vector from a sequence of values; individual vector elements will be denoted by enclosing the index in angle brackets.

defined on the types of the elements of the s; streams. The s. streams satisfy the StreamRelation expression if succe~sive elements of the s; streams satisfy R:

As a simple example of a specification, consider a switching problem: the elements of INPUT are to be split off into one of two other streams, OUTPUT 1 or OUTPUT 2 , depending on the value of CONTROL, which is a stream whose elements are either 1 or 2. Informally, INPUT is a merge of OUTPUT 1 and OUTPUT 2 . More formally:

We do not claim that this particular set of operators is complete or in any sense primitive. Rather they seem to cover well the software tasks which we have been studying. As our work continues, we expect the set of operators to grow and evolve

Input Terms: INPUT, CONTROL Output Terms: OUTPUT 1 , OUTPUT 2 Postconditions: INPUT = Merge(CONTROL,OUTPUT 1 ,OUTPUT 2 )

As a second example, consider the specification of a simple feedback loop which adjusts the gain on an amplifier to keep the amplitude of a signal close to 1:

Input Terms: AMPLITUDE Output Terms: GAIN Postconditions: GAIN(1) = 0 Shift(GAIN, 1) = StreamMap(NewGain,GAIN,AMPLITUDE) NewGain(x,y) ( = > x if .9 =::; y :5 1. 1 X+ I if y <.9 X+ 1 if 1. 1 ( y

B. Target language

As stated earlier, a stream program consists of a set of concurrently executing sequential programs. The sequential programs themselves are written in a traditional sequential programming language, extended to include stream operations. The details of the sequential language are not particularly important. In this paper, we will consider the basic primitives to be the two stream operations, Produce(s,x) and Consume(s) , and assignment to a local variable. In addition, we will consider as primitive any problem specification which does not involve streams. We will assume that such programming problems can be handled adequately by some other technique (e.g., algebraic manipulation [Barstow et al 82)) , leaving us free to focus in this paper on automatic programming techniques for streams.

In addition to these primitive operations, we will include in our target language the following three control structures:

sequence conditional (program: . . . program} case expression of {v 1 : program; v 2 : program: vk: program}

repetition while expression do prqgram

C. Transformation Rules for Stream Programs

Our approach to automatic programming for stream programs involves the use of transformations: we represent knowledge about programming with streams as transformations which replace one part of a partially developed program by another. To date, we have identified three general types of transformations: algorithm instantiation transformations produce sequential algorithms for stream problems: problem· reduction transformations split a single stream problem into several. presumably simpler, stream problems; stream elimination transformations remove unnecessary streams by collapsing several sequential processes into a single one.

C.1 . Algorithm Instantiation Transformations

The algorithm instantiation transformations have two parts:

patterns consisting of particular types of relations on streams

replacements consisting of particular sequential algorithms

In general, the patterns may involve several relations. To date, however, we have been working only with transformations whose patterns involve a single relation, such as the following:

s = Generate(F) Output: s -> { i : = 1; while True do {Produce(s,F(i}): i := i+l}} F = Filter(S,P) Input: P, s Output: F ·> while True do {x := Consume( s); case Consume(P} of {True : Produce(F,x)}} M = Merge(c,s 1 , ... ,sk) Input: c, s 1 ..... sk Output: M -) while True do (case Consume( C) of {1: rn ·= Consume(s 1 ): k: m ·= Consume(sk)} : Produce(M.m)} M = Merge(C,S 1 , ... ,Sk) Input: c, M Output: s 1 , ... , sk -> while True do (m := Consume(M}; case Consume(c) of (1 : Produce(s 1 ,m); k : Produce(sk ,m)}}

S'[1] = x 1 S'[k]=xk S' = Shift(S,k ) Input: s Output: S' -> (Produce(s· .x 1 ); Produce(S', x·) ; while True do Produce (S' ,Consume(s)) P = Packing(S ,k) Input: P,k Output: s -> whil e True do (p : = Consume(P) ; i : = l : P = Packing(S ,k) Input: s ,k Output: P whil e i <= k do (Produce(S,p<i >) ; i := i+l)} .) while True do ( i : = 1: while i <= k do (p<i > := Consume(S); i : = i +1}: Produce(P.p)) w = Window(S,k) Input: s,k Output: w -) ( i : = 1; while i <k do {w<i > := · Consume(S) ; i : = i+1} ; while True do {w<k> := Consume(S); Produce(w . w); i : = 1; while i <k do ( w<i > := w<i+1 >; i : = i+l})) s = StreamMap(F,s 1 , .. ,sk) Input: s 1 , ... sk -) Output: s while True do (x 1 : = Consume(S 1 ) ; xk : = Consume (sk) ; Produce(s. F( x 1 · . . . · xk))} StreamRelation(R .s 1 , .. . ,sk) Input: s. , ... s 11 lm Output: s. , ... s It In

.) while True do (x. 't X. 'm Con sume(s. ); 't Con sume(si ) ; m R(x 1 , ... ,xk)* Produce(s . ,x . ) ; h Jt Produce(s. ,x . )) Jn Jn

C.2. Problem Reduction Transformations

Problem reduction transformations are intended to reduce complex problems to problems which are simple enough to be handled by the algorithm instantiation transformations. Since subproblems handled by the algorithm instantiation transformations correspond to separate processes in the target program, the effect of a problem reduction transformation is to introduce additional processes into the final program. Two examples, stated informally, are:

A postcondition relation may be separated into a separate problem specification if it involves only input streams and at most one intermediate or output stream.

A postcondition relation may be separated into a separate problem specification if none of the remaining postcondition relations involve any of the first relation's intermediate or output streams.

C.3. Stream Elimination Transformations

While streams are convenient conceptual tools which can contribute to simplicity and modularity in programming, there may be a computational cost associated with their use. For this reason, we are developing stream elimination rules. ·· Two such rules, stated informally, are the following:

If two processes consume a stream exactly once during each iteration of the loop in the process body. the loop bodies of the two processes may be combined.

If a process produces a single output stream which is consumed by only one other process, and the second process consumes the stream exactly once in the body of the loop, then the body of the loop of the second process may be merged with the body of the loop of the first process at the point at which the stream is produced by the first process.

IV. Example

In this section, we will consider an example drawn from a program designed to control a remote physical device communicating with a computer through streams of signals and commands. The primary job of the computer is to command the device to alternate between two measurements. Associated with each measurement is an A/D converter whose gain must be set with each command. The gain commands for the measurements are received on separate streams but must be sent to the device on a single output stream.

'Note that Alx r .... xk) is simply another program specification whose input terms are x ..... ,x. and whose output terms are x. , .... x. 1 1 1 m 1 1 1 n

"Note. however, that the use of such rules does not necessarily produce more efficient code, since the efficiency of streams depends on the architecture of the target machine. For example, reducing the number of streams and processes may prevent taking advantage of parallelism on a multiprocessor architecture.

A. Specification

The specification of the stream program for this example IS as follows:

Initial Problem

Input Terms: GAIN 1 ,GAIN 2 Output Terms: COMMAND,GAIN Intermediates: CONTROL Preconditions: Postconditions: CONTROL= Generate(F) F(i) = ((i + 1) mod 2) + 1 GAIN= Merge(CONTROL,GAIN 1 ,GAIN 2 ) StreamReiation(Measurement,CONTROL,COMMAND) Measurement(x,y) ( = > x = 1 andy= "Measurement 1 " or x = 2 andy= "Measurement 2 "

B. Synthesis

B. 1. Problem Reduction

This specification can be reduced to three simple subproblems by applying each of the two problem reduction transformations shown earlier. The specifications of the resulting subproblems are:

Subproblem 1

Subproblem 2

Subproblem 3

Input Terms: Output Terms: CONTROL Preconditions: Postconditions: CONTROL= Generate(F) F(i) = ((i + 1) mod 2) + 1 Input Terms: GAIN 1 ,GAIN 2 ,CONTROL Output Terms: GAIN Preconditions: Postconditions: GAIN= Merge(CONTROL,GAIN 1 ,GAIN 2 ) Input Terms: CONTROL Output Terms: COMMAND Preconditions: Postconditions: StreamRelation(Measurement ,CONTROL,COMMAND) Measurement(x,y) ( = > x = 1 andy= "Measurement 1 " or x = 2 andy= "Measurement 2 "

B.2. Algorithm Instantiation

The first two subproblems may each be transformed into algorithms by applying one of the transformations shown earlier. The resulting algorithms are:

Subprogram 1

( i : = 1: while True do (Produce(CONTROL , (( i+l) mod 2)+1): i := i+l}}

Subprogram 2

while True do {case Consume(CONTROL) of (1: m := Consume(GAIN 1 ): 2: m := Consume(GAIN 2 )}: Produce (GAIN , m)}

The third subproblem may also be transformed by an algorithm instantiation transformation, but the relation Measurement remains as a subproblem:

Subprogram 3

while True do {x := Consume(CONTROL): Measurement(x,y); Produce(COMMAND,y)}

The relation Measurement does not involve any streams and may be replaced by its definition, solved for y:

Subprogram 3

while True do {x := Consume(CONTROL): case x of {1 : y := "Measurement 1 "; 2: y := "Measurement 2 "}; Produce(COMMAND , y)}

B.3. Stream Elimination

The second and third subprograms may be combined by applying the first stream elimination transformation given earlier. The result is:

Combined Subprograms: 2, 3

while True do {x := Consume(CONTROL): case x of {1 : m : = Consume(GAIN 1 ): 2: m := Consume(GAIN 2 )}; Produce(GAIN ,m); case x of {1 : y := "Measurement 1 " ; 2: y := "Measurement 2 "}; Produce(COMMAND,y)}

Note that, in this case, the StreamRelation postcondition could have been expressed as a Stream Map :

COMMAND= StreamMap(MeasurementFunction,CONTROL) MeasurementFunction(x) = "Measurement 1 " if x = 1 = "Measurement 2 " if x = 2

The relation form was chosen for the sake of illustration.

This may be combined with the first process by applying the second stream elimination transformation given earlier, yielding:

Combined Subprograms: 1, 2, 3

{ i : = 1: while True do { x : = ( ( i + 1) mod 2) + 1: case x of {1: m := Consume(GAIN 1 ): 2: m := Consume(GAIN 2 )}: Produce(GAIN,m): case x of {1: y := "Measurement 1 ": 2: y := "Measurement 2 "}; Produce(COMMAND , y): i : = i + 1}

8 .4. Simplification and Optimization

Several simplifications and optimizations not related to streams may now be applied, resulting in the final code for the original specification:

Final Program

{ i : = 1; while True do (case of {1: {m ·= Consume(GAIN 1 ): y ·= ''Measurement 1 ''}: 0: {m Consume{GAIN 2 ): y ·= "Measurement 2 "}}; Produce{COMMAND,y); Produce(GAIN,m); i := (i+l) mod 2}

V. Discussion

To date we have tested these techniques by hand simulation on a variety of specifications for software to control and record data from Schlumberger's well logging tools. The tasks to be performed by the software include encoding and decoding of signals, multiplexing and demultiplexing of communication channels. feedback loops, and simple calculations. We have also done partial simulations for a few log interpretation programs. In both situations, the specification and implementation techniques seem to work well. As we implement the techniques, we expect to make changes and extensions at a detailed level , but we also expect the overall approach to remain essentially the same.

It should be noted that these techniques address only one aspect of the problem of programming with streams. In a previous study, we characterized.the programming process for log interpretation software in terms of four activities: informal problem solving, formal manipulation, implementation selection, and target language translation [Barstow 84] . The techniques described in this paper only address issues which arise during formal manipulation. Work is also underway on the other activities. such as informal problem solving in which streams are used to approximate continuous functions.

Acknowledgements

I am grateful to many colleagues for their criticisms and insights, including Paul Barth, Paul Dietz, Rick Dinitz, Sol Greenspan, Elaine Kant, David Steier, Stephen Smoliar, and Peter Will.