Lucid (programming language)

Infobox programming language
name = Lucid
logo =
paradigm = Dataflow
year = 1976
designer = Edward A. Ashcroft,William W. Wadge
developer = ,Wadge
latest release version =
latest release date =
typing = Typeless
implementations = pLucid
dialects = GIPSY GLU
influenced_by = ISWIM
influenced = SISAL, PureData, Lustre Lucid is a dataflow programming language. It is designed to experiment with non-von Neumann 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 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 thought of as a kind of very disciplined mathematically pure single assignment language in which verification would be very much simplified. However, the dataflow 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 languages) an expression that contains a variable that was not yet bound 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 mainstreamlanguages.

Each variable in Lucid is a stream of values. An expression n = 1 fby n + 1 defines a streamusing the operator 'fby'. fby (read as 'followed by') defines what comes after the previousexpression. (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 makesa 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-varyingstreams of data.

pLucid was the first interpreter for Lucid.

Examples

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

[http://i.csc.uvic.ca/home/hei/lup/02.html]

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

[http://i.csc.uvic.ca/home/hei/lup/06.html]

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

-----------------------------------------------------------

quare Root

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

[http://i.csc.uvic.ca/home/hei/lup/01.html]

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

* [http://code.google.com/p/plucid/ pLucid]
* [http://c2.com/cgi/wiki?LucidLanguage Language overview]
* [http://hopl.murdoch.edu.au/showlanguage2.prx?exp=960 Evolution of Lucid]
* [http://i.csc.uvic.ca/home/hei/hei.ise Bill Wadge's home page]
* [http://www.artima.com/weblogs/viewpost.jsp?thread=102839 Fluid Programming in Lucid]
* [http://www.haskell.org/haskellwiki/Lucid Lucid page of HaskellWiki]
* [http://i.csc.uvic.ca/home/hei/lup/contents.html Programming in Lucid]
* [http://i.csc.uvic.ca/home/hei/ei/contents.ise An Eductive Interpreter]
* [http://i.csc.uvic.ca/home/LucidPrimer/LPS.ise Lucid Primer]
* [http://newton.cs.concordia.ca/~gipsy/ GIPSY]