Lucid (programming language)

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): ; : fetches the first value in the stream x, ; : the current value of the stream, ; : fetches the next value in the stream. ; : an operator that does some thing 'as soon as' the condition given becomes true. ; : 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 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 Hamming problem h where h = 1 fby merge(merge(2 * h, 3 * h), 5 * h); merge(x,y) = if xx Dataflow Diagram dataflow diagram == Intensionality and Lucid ==

Viewed from an intensional logic perspective , Lucid can be thought of as a multidimensional programming language, where time is one of its many dimensions. Lucid, viewed this way, can naturally express multidimensional computation that not only vary in time but in other dimensions. The examples below illustrate the power of Lucid in expressing a wide range of multidimensional computations. Prime Numbers primes where dimension i; primes = first.i sieve; natsFrom2 = i+2; sieve = natsFrom2 fby.time ( sieve wvr.i ( sieve mod ( ( first.i sieve ) ne 0 ) ) ); end Merge Sort r0t8.v,time( output ) where dimension v,h,t; output = mergeSort asa.t inputSize == sizeOfMerge; merge(x,y) = if iseod xx then yy else if iseod yy then xx else if xx yy; end; mergeSort = Inputdata(h) fby.t merge(leftChild.h(mergeSort), rightChild.h(mergeSort)); sizeOfMerge = 1 fby.t 2*sizeOfMerge; r0t8.a,b( x ) = x @.a b; end Matrix Multiplication ( matmult( A, B, n ) @.aux_i r ) @.aux_j c where dimension aux_i, aux_j; matmult( aux_a, aux_b, n ) = c asa.t s == (n*n*n) where dimension t, i, j, k; s = 1 fby.t 8*s; d = 1 fby.t 2*d; a = r0t8.aux_i.i( r0t8.aux_j.j( aux_a ) ); b = r0t8.aux_i.i( r0t8.aux_j.j( aux_b ) ); c = (a @.j k) * (b @.i k) fby.t ( ( reduce @.k (2*k) ) @.j (2*j) ) @.i (2*i) where reduce = block( c + next.k c, next.j c + next.k next.j c, next.i c + next.k next.i c, next.j next.i c + next.k next.j next.i c, d ); block( tl, tr, bl, br, d ) = p where p = append.aux_i( append.aux_j( tl, tr, d ), append.aux_j( bl, br, d ), d ); append.dim( a, b, d ) = if( dim ==References==