Lucid is a
dataflow programming
In computer programming, dataflow programming is a programming paradigm that models a program as a directed graph of the data flowing between operations, thus implementing dataflow principles and architecture. Dataflow programming languages share ...
language designed to experiment with non-
von Neumann Von Neumann may refer to:
* John von Neumann (1903–1957), a Hungarian American mathematician
* Von Neumann family
* Von Neumann (surname), a German surname
* Von Neumann (crater), a lunar impact crater
See also
* Von Neumann algebra
* Von Ne ...
programming models. It was designed by Bill Wadge and Ed Ashcroft and described in the 1985 book ''Lucid, the Dataflow Programming Language''.
pLucid was the first
interpreter for Lucid.
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
Variable may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
is an infinite stream of values and every function is a filter or a transformer.
Iteration
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
is simulated by 'current' values and 'fby' (read as 'followed by') operator allowing composition of streams.
Lucid is based on an
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
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
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
interpretation has been an important influence on the direction in which Lucid has evolve
Details
In Lucid (and other
dataflow
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
languages) an expression that contains a variable that has not yet been
Free variables and bound variables, 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
A mnemonic ( ) device, or memory device, is any learning technique that aids information retention or retrieval (remembering) in the human memory for better understanding.
Mnemonics make use of elaborative encoding, retrieval cues, and imag ...
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
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
fac
where
n = 0 fby (n + 1);
fac = 1 fby ( fac * (n + 1) );
end
Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
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 number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s
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
A data-flow diagram is a way of representing a flow of data through a process or a system (usually an information system). The DFD also provides information about the outputs and inputs of each entity and the process itself. A data-flow diagram ha ...
Quick sort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
qsort(a) = if eof(first a) then 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
In mathematics and its applications, the root mean square of a set of numbers x_i (abbreviated as RMS, or rms and denoted in formulas as either x_\mathrm or \mathrm_x) is defined as the square root of the mean square (the arithmetic mean of the ...
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
Regular numbers are numbers that evenly divide powers of 60 (or, equivalently, powers of 30). Equivalently, they are the numbers whose only prime divisors are 2, 3, and 5. As an example, 602 = 3600 = 48 ×&nb ...
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
References
External links
pLucid
{{Authority control
Academic programming languages
Concurrent programming languages
Declarative programming languages
Experimental programming languages
Reactive programming languages
Query languages