Lucid is a dataflow programming

Dataflow

Dataflow is a term used in computing, and may have various shades of meaning. It is closely related to message passing.-Software architecture:...

 language. It is designed to experiment with non-von Neumann

Von Neumann architecture

The term Von Neumann architecture, aka the Von Neumann model, derives from a computer architecture proposal by the mathematician and early computer scientist John von Neumann and others, dated June 30, 1945, entitled First Draft of a Report on the EDVAC...

 programming models. It was designed by Bill Wadge and Ed Ashcroft and described in the book Lucid, the Dataflow Programming Language.

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

Variable may refer to:* Variable , a logical set of attributes* Variable , a symbol that represents a quantity in an algebraic expression....

 is an infinite stream of values and every function is a filter or a transformer. Iteration

Iteration

Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...

 is simulated by 'current' values and 'fby' (read as 'followed by') operator allowing composition of streams.

Lucid is based on an algebra

Algebra

Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...

 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 kind of very disciplined mathematically pure single assignment language in which verification would be very much simplified. However, the dataflow

Dataflow

Dataflow is a term used in computing, and may have various shades of meaning. It is closely related to message passing.-Software architecture:...

 interpretation has been very important in helping the direction in which Lucid has evolved.http://www.chilton-computing.org.uk/acd/dcs/projects/p026.htm

Details

In Lucid (and other dataflow

Dataflow

Dataflow is a term used in computing, and may have various shades of meaning. It is closely related to message passing.-Software architecture:...

 languages) an expression that contains a variable that was not yet bound

Free variables and bound variables

In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place...

 waits until the variable is 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 result 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'. 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)
ie: 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.

pLucid was the first interpreter for Lucid.

Factorial

Factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

fac
where
n = 0 fby (n + 1);
fac = 1 fby ( fac * (n + 1) );
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

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

s

prime
where
prime = 2 fby (n whenever isprime(n));
n = 3 fby n+2;
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

---+1<--- -->isprime----
| | |
| | V
->fby--------------->whenever--->
^
|
2

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 -------------- |
| |
-----------------------------------------------------------

Square root

Square root

In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...

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

--------------------*2---------
| -------------*3---------|
| | --*5---------|
| | | |
| V V |
--->merge----->merge----->fby-------->
^
|
1

External links

• pLucid
• Language overview
• Evolution of Lucid
• Bill Wadge's home page
• Fluid Programming in Lucid
• Lucid page of HaskellWiki
• Programming in Lucid
• An Eductive Interpreter
• Lucid Primer
• GIPSY
• The Quil Language Website