Lucid (programming language)


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.
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 is an infinite stream of values and every function is a filter or a transformer. Iteration is simulated by 'current' values and 'fby' 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 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'. fby defines what comes after the previous
expression..
The values in a stream can be addressed by these operators :
'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.
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 ;
fac = 1 fby ;
end

[Fibonacci sequence]

fib
where
fib = 0 fby ;
end

Total of a Sequence

total
where
total = 0 fby total + x
end;

Running Average

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

[Prime number]s

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

[Dataflow diagram]

[Quick sort]

qsort = if eof then else follow,qsort) fi
where
p = first a < a;
b0 = a whenever p;
b1 = a whenever not p;
follow = 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
where
square = x*x;
avg = mean
where
n = 1 fby n+1;
mean = first y fby mean + d;
d = /;
end;
sqroot = approx asa err < 0.0001
where
Z is current z;
approx = Z/2 fby /2;
err = abs;
end;
end

[Hamming problem]

h
where
h = 1 fby merge;
merge = if xx <= yy then xx else yy fi
where
xx = x upon xx <= yy;
yy = y upon yy <= xx;
end;
end;

Dataflow Diagram