Eduction

We know what a Lucid program means mathematically (see Chapter 3), yet that in itself does not suggest a particular model of computation for deriving the same meaning operationally. The purpose of this chapter is to consider the various ways that Lucid programs can be evaluated and to describe in detail the most appropriate model of computation, namely, eduction. Previously, we have seen that Lucid programs can be viewed globally in geometrical terms or locally in elemental terms. Both these views are equally valid as mental devices to enable the programmer to conceive and understand Lucid programs. And each view suggests its own family of computing models—extensional models that embody the global geometrical view and intensional models that embody the local elemental view. Before we compare these two approaches to evaluating Lucid programs, it is worth relating the operational semantics given by a model of computation to the mathematical semantics. Since Lucid is purely declarative, the correct meaning of a Lucid program is that which is given mathematically. This is done without appealing to any operational notions [8]. Thus, the mathematical semantics of a Lucid program has primacy over the many operational semantics that can be given to the Lucid program using different models of computations. Consequently, the correctness of a model of computation is determined by its ability to operationally give semantics to Lucid programs that coincide with their mathematical semantics. Let us consider an extensional model of computation called reduction [37]. It is the standard model for evaluating declarative programs, and more specifically, functional programs. In reduction, programs are considered to be expressions, and a program is evaluated by repeatedly transforming, or reducing, the expression into a possibly simpler expression. The original expression must include any data that the program is to work on, so that at every stage we are manipulating both program and data, and the two become intimately entwined. The process stops when no further transformation can be applied. At each stage, several transformations may be possible, but it doesn’t matter which we apply. If we get an answer, we always get the same answer, but it is possible to make choices so that we do not arrive at the answer.