Lucid (programming language)

Lucid
Paradigm	Dataflow
Designed by	Edward A. Ashcroft; William W. Wadge
First appeared	1976
Typing discipline	Typeless
Major implementations
	pLucid, GIPSY
Dialects
	Granular Lucid, Indexical Lucid, Tensor Lucid, Forensic Lucid, Lucx, JOOIPL
Influenced by
	ISWIM
Influenced
	SISAL, PureData, Lustre

Last updated September 05, 2024

Lucid is a dataflow programming language designed to experiment with non-von Neumann programming models. It was designed by Bill Wadge and Ed Ashcroft and described in the 1985 book Lucid, the Dataflow Programming Language.^[1]

Model

Lucid uses a demand-driven model for data computation. Each statement can be understood as an equation defining a network of processors and communication lines between them through which data flows. Each variable is an infinite stream of values and every function is a filter or a transformer. Iteration is simulated by 'current' values and 'fby' (read as 'followed by') operator allowing composition of streams.

Lucid is based on an algebra of histories, a history being an infinite sequence of data items. Operationally, a history can be thought of as a record of the changing values of a variable, history operations such as first and next can be understood in ways suggested by their names. Lucid was originally conceived as a disciplined, mathematically pure, single-assignment language, in which verification would be simplified. However, the dataflow interpretation has been an important influence on the direction in which Lucid has evolved.

Details

In Lucid (and other dataflow languages) an expression that contains a variable that has not yet been bound waits until the variable has been bound, before proceeding. An expression like x + y will wait until both x and y are bound before returning with the output of the expression. An important consequence of this is that explicit logic for updating related values is avoided, which results in substantial code reduction, compared to mainstream languages.

Each variable in Lucid is a stream of values. An expression n = 1 fby n + 1 defines a stream using the operator 'fby' (a mnemonic for "followed by"). fby defines what comes after the previous expression. (In this instance the stream produces 1,2,3,...). The values in a stream can be addressed by these operators (assuming x is the variable being used):

'first x' - fetches the first value in the stream x,

'x' - the current value of the stream,

'next x' - fetches the next value in the stream.

'asa' - an operator that does some thing 'as soon as' the condition given becomes true.

'x upon p' - upon is an operator that repeats the old value of the stream x, and updates to the new values only when the stream p makes a true value available. (It serves to slow down the stream x) i.e.: x upon p is the stream x with new values appearing upon the truth of p.

The computation is carried out by defining filters or transformation functions that act on these time-varying streams of data.

Examples

Factorial

fac   where     n = 0 fby (n + 1);     fac = 1 fby ( fac * (n + 1) );   end

Fibonacci sequence

fib   where     fib = 0 fby ( 1 fby fib + next fib );   end

Total of a Sequence

total   where      total = 0 fby total + x   end;

Running Average

running_avg   where       sum = first(input) fby sum + next(input);      n = 1 fby n + 1;      running_avg = sum / n;   end;

Prime numbers

prime   where      prime = 2 fby (n whenever isprime(n));      n = 3 fby n+1;      isprime(n) = not(divs) asa divs or prime*prime > N                      where                        N is current n;                        divs = N mod prime eq 0;                      end;   end

Dataflow diagram

Quick sort

qsort(a) = if eof(first a) then a else follow(qsort(b0),qsort(b1)) fi   where      p = first a < a;      b0 = a whenever p;      b1 = a whenever not p;      follow(x,y) = if xdone then y upon xdone else x fi                      where                         xdone = iseod x fby xdone or iseod x;                       end   end

Data flow diagram

    --------> whenever -----> qsort ---------    |             ^                           |    |             |                           |    |            not                          |    |             ^                           |    |---> first   |                           |    |       |     |                           |    |       V     |                           |    |---> less ---                            |    |             |                           |    |             V                           V ---+--------> whenever -----> qsort -----> conc -------> ifthenelse ----->    |                                                       ^   ^    |                                                       |   |     --------> next ----> first ------> iseod --------------    |    |                                                           |     -----------------------------------------------------------

Root mean square

sqroot(avg(square(a)))   where      square(x) = x*x;      avg(y)    = mean         where           n = 1 fby n+1;           mean = first y fby mean + d;           d = (next y - mean)/(n+1);         end;      sqroot(z) = approx asa  err < 0.0001         where           Z is current z;           approx = Z/2 fby (approx + Z/approx)/2;           err    = abs(square(approx)-Z);         end;    end

Hamming problem

h    where      h = 1 fby merge(merge(2 * h, 3 * h), 5 * h);      merge(x,y) = if xx <= yy then xx else yy fi         where            xx = x upon xx <= yy;           yy = y upon yy <= xx;         end;    end;

Dataflow Diagram

Related Research Articles

Erlang is a general-purpose, concurrent, functional high-level programming language, and a garbage-collected runtime system. The term Erlang is used interchangeably with Erlang/OTP, or Open Telecom Platform (OTP), which consists of the Erlang runtime system, several ready-to-use components (OTP) mainly written in Erlang, and a set of design principles for Erlang programs.

In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed and which also avoids repeated evaluations.

Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic of this article, is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. In 1936, Church found a formulation which was logically consistent, and documented it in 1940.

In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties. This is often written as $or where is the Laplace operator, is the divergence operator, is the gradient operator, and is a twice-differentiable real-valued function. The Laplace operator therefore maps a scalar function to another scalar function.$

<span class="mw-page-title-main">Partial differential equation</span> Type of differential equation

In mathematics, a partial differential equation (PDE) is an equation which computes a function between various partial derivatives of a multivariable function.

In combinatory logic for computer science, a fixed-point combinator, is a higher-order function that returns some fixed point of its argument function, if one exists.

<span class="mw-page-title-main">Covariance matrix</span> Measure of covariance of components of a random vector

In probability theory and statistics, a covariance matrix is a square matrix giving the covariance between each pair of elements of a given random vector.

In materials science and solid mechanics, Poisson's ratio $ν$ (nu) is a measure of the Poisson effect, the deformation of a material in directions perpendicular to the specific direction of loading. The value of Poisson's ratio is the negative of the ratio of transverse strain to axial strain. For small values of these changes, $ν$ is the amount of transversal elongation divided by the amount of axial compression. Most materials have Poisson's ratio values ranging between 0.0 and 0.5. For soft materials, such as rubber, where the bulk modulus is much higher than the shear modulus, Poisson's ratio is near 0.5. For open-cell polymer foams, Poisson's ratio is near zero, since the cells tend to collapse in compression. Many typical solids have Poisson's ratios in the range of 0.2 to 0.3. The ratio is named after the French mathematician and physicist Siméon Poisson.

In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:

Oz is a multiparadigm programming language, developed in the Programming Systems Lab at Université catholique de Louvain, for programming-language education. It has a canonical textbook: Concepts, Techniques, and Models of Computer Programming.

In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be a match." The patterns generally have the form of either sequences or tree structures. Uses of pattern matching include outputting the locations of a pattern within a token sequence, to output some component of the matched pattern, and to substitute the matching pattern with some other token sequence.

In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values. However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator.

In mathematics and computer algebra, automatic differentiation, also called algorithmic differentiation, computational differentiation, is a set of techniques to evaluate the partial derivative of a function specified by a computer program.

In applied statistics, total least squares is a type of errors-in-variables regression, a least squares data modeling technique in which observational errors on both dependent and independent variables are taken into account. It is a generalization of Deming regression and also of orthogonal regression, and can be applied to both linear and non-linear models.

<span class="mw-page-title-main">Corner detection</span> Approach used in computer vision systems

Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D reconstruction and object recognition. Corner detection overlaps with the topic of interest point detection.

In probability theory and statistics, partial correlation measures the degree of association between two random variables, with the effect of a set of controlling random variables removed. When determining the numerical relationship between two variables of interest, using their correlation coefficient will give misleading results if there is another confounding variable that is numerically related to both variables of interest. This misleading information can be avoided by controlling for the confounding variable, which is done by computing the partial correlation coefficient. This is precisely the motivation for including other right-side variables in a multiple regression; but while multiple regression gives unbiased results for the effect size, it does not give a numerical value of a measure of the strength of the relationship between the two variables of interest.

In differential calculus, there is no single uniform notation for differentiation. Instead, various notations for the derivative of a function or variable have been proposed by various mathematicians. The usefulness of each notation varies with the context, and it is sometimes advantageous to use more than one notation in a given context. The most common notations for differentiation are listed below.

This article describes the features in the programming language Haskell.

In mathematics, the Kronecker sum of discrete Laplacians, named after Leopold Kronecker, is a discrete version of the separation of variables for the continuous Laplacian in a rectangular cuboid domain.

Lambda calculus is a formal mathematical system based on lambda abstraction and function application. Two definitions of the language are given here: a standard definition, and a definition using mathematical formulas.

References

↑ Wadge, William W.; Ashcroft, Edward A. (1985). Lucid, the Dataflow Programming Language . Academic Press. ISBN 0-12-729650-6 . Retrieved 8 January 2015.

External links

pLucid

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[book-1] Wadge, William W.; Ashcroft, Edward A. (1985). Lucid, the Dataflow Programming Language . Academic Press. ISBN 0-12-729650-6 . Retrieved 8 January 2015.

[1]