This paper examines the use of dataflow parallel processing for the execution of digital filtering algorithms. The dataflow language used is Lucid. FIR and recursive filtering algorithms are formulated in Lucid. Analysis of the parallelism achievable in the dataflow implementations is presented.

A constructive criticism of recent work in the semantics of programming languages is offered.The criticism is directed not so much at the techniques and results obtained as at the use to which they are put.The fact that denotational (or "mathematical") semantics plays on the whole a passive ("descriptive") role, whil e operational semantics plays on the whole an active ("prescriptive") role, is seen as the basic problem.It is suggested that these roles be reversed.

In this paper we describe how Lucid can be extended to allow user-defined functions and scope conventions, i.e. conventions for limiting the range or scope of the validity of definitions. This is done using new constructs called clauses which are similar in form to the blocks and procedure declarations of Algol-like languages, but are nevertheless strictly non-imperative, because a clause is actually a compound assertion, i.e. an assertion formed, as a program is, by combining a collection of assertions.Each type of clause (there are four) has a straightforward mathematical semantics together with its own characteristic "manipulation rules" for general program massage. In addition, the informal operational view of (some) Lucid programs (described in a previous paper) can be extended to give an (incomplete) operational understanding of the effect of the clauses. In this framework a "compute" clause defines a block; a "mapping" clause defines a conventional (pointwise) function; a "produce" clause defines a block with persistent memory (or an anonymous 'process' or 'actor'); and a "function" clause defines a sort of procedure with own variables (or a general kind of coroutine).

The problem of defining an adequate semantics for recursive definitions which allow various types of parameter-passing mechanisms has generated a considerable amount of interest in the literature. (See [B1], [M4], [R3], [V2]) Consider for example the well-known recursive definition

Lucid is both a programming language and a formal system for proving properties of Lucid programs. The programming language is unconventional in many ways, although programs are readily understood as using assignment statements and loops in a “structured” fashion. Semantically, an assignment statement is really an equation between “histories”, and a whole program is simply an unordered set of such equations. From these equations, properties of the program can be derived by straightforward mathematical reasoning, using the Lucid formal system. The rules of this system are mainly those of first order logic, together with extra axioms and rules for the special Lucid functions. This paper formally describes the syntax and semantics of programs, and justifies the axioms and rules of the formal system.

While-schemas are defined as program schemas without goto statements, in which iteration is achieved using while statements. We present two translations of program schemas into equivalent while-schemas, the first one by adding extra program variables, and the second one by adding extra logical variables. In both cases we aim to preserve as much of the structure of the original program schemas as possible. We also show that, in general, any translation must add variables.

A class of (monadic) functional schemas which properly includes “Ianov” flowchart schemas is defined. It is shown that the termination, divergence, and freedom problems for functional schemas are decidable. Although it is possible to translate a large class of non-free functional schemas into equivalent free functional schemas, it is shown that in general this cannot be done. It is also shown that the equivalence problem for free functional schemas is decidable. Most of the results are obtained from well-known results in formal languages and automata theory.