Lucid

Η Lucid είναι μια γλώσσα προγραμματισμού ροής δεδομένων (dataflow). Σχεδιάστηκε από τους Bill Wadge και Ed Ashcroft.

Μοντέλο

Η Lucid χρησιμοποιεί ένα μοντέλο που εξαρτάται από τη ζήτηση δεδομένων για τον υπολογισμό. Κάθε εντολή μπορεί να θεωρηθεί σαν μια εξίσωση που ορίζει ένα δίκτυο επεξεργαστών και γραμμών επικοινωνίας μεταξύ αυτών (μέσω των οποίων γραμμών ρέουν τα δεδομένα). Κάθε μεταβλητή είναι μια άπειρη ροή από τιμές και κάθε συνάρτηση είναι ένα φίλτρο ή ένας μετασχηματιστής (transformer). Η ακολουθιακή εκτέλεση των εντολών προσομοιώνεται από τις τρέχουσες τιμές των μεταβλητών και τον τελεστή 'fby' (διαβάζεται σαν 'ακολουθούμενο από', 'followed by') που επιτρέπει τη σύνθεση ροών.
Η Lucid βασίζεται σε μια άλγεβρα ιστοριών με κάθε ιστορία να είναι μια άπειρη ακολουθία από δεδομένα. Λειτουργικά, μια ιστορία μπορεί να θεωρηθεί σαν μια καταγραφή των μεταβαλλόμενων τιμών μιας μεταβλητής, με τις λειτουργίες 'first' και 'next' σαν την πρώτη και την επόμενη τιμή της. Η Lucid αρχικά δημιουργήθηκε σαν ένα είδος αυστηρής αμιγούς γλώσσας προγραμματισμού με μοναδική ανάθεση, που θα διευκόλυνε την επαλήθευση των προγραμμάτων σε αυτή. Όμως, η θεώρησή της σαν γλώσσα ροής δεδομένων υπήρξε πολύ σημαντική για την κατεύθυνση προς την οποία εξελίχθηκε.

Λεπτομέρειες

Στη Lucid (και σε άλλες γλώσσες ροής δεδομένων) μια έκφραση που περιέχει μια μεταβλητή που δεν έχει δεσμευτεί ακόμα περιμένει μέχρι η μεταβλητή αυτή να δεσμευτεί πριν να συνεχίσει. Μια έκφραση όπως η x + y θα περιμένει μέχρι και η x και η y να δεσμευτούν πριν να επιστρέψει το αποτέλεσμά της. Αυτό έχει αποτέλεσμα να αποφεύγεται ρητή λογική για την ενημέρωση συσχετισμένων μεταβλητών, με συνέπεια αρκετά μικρότερο κώδικα σε σχέση με τις γνωστές γλώσσες.
Κάθε μεταβλητή στη Lucid είναι μια ροή από τιμές. Μια έκφραση n = 1 fby n + 1 ορίζει μια ροή χρησιμοποιώντας τον τελεστή 'fby'. Ο fby ορίζει αυτό που ακολουθεί την προηγούμενη έκφραση. (Σε αυτήν την περίπτωση η ροή παράγει τις τιμές 1,2,3,...).
Οι τιμές σε μια ροή μπορούν να προσπελαστούν από τους εξής τελεστές (θεωρώντας ότι χρησιμοποιείται η μεταβλητή x):
'first x' - φέρνει την πρώτη τιμή της ροής x
'x' - η τρέχουσα τιμή της ροής
'next x' - επιστρέφει την επόμενη τιμή στη ροή
'asa' - ένας τελεστής που κάνει κάτι 'μόλις' ('as soon as') μια συνθήκη γίνεται αληθής
'x upon p' - ο τελεστής upon επαναλαμβάνει την παλιά τιμή μιας ροής x, και ενημερώνει με νέες τιμές μόνο όταν η ροή p εμφανίζει αληθείς τιμές (χρησιμοποιείται για να καθυστερεί τη ροή x), δηλ.: x upon p είναι η ροή x με τις νέες τιμές να εμφανίζονται στις αληθείς τιμές της p
Ο υπολογισμός διεξάγεται ορίζοντας φίλτρα ή συναρτήσεις μετασχηματισμού που εφαρμόζονται σε αυτές τις χρονικά μεταβαλλόμενες ροές δεδομένων.
Ο pLucid ήταν ο πρώτος διερμηνέας της Lucid.

Σύνολο μιας Ακολουθίας

total
  where
     total = 0 fby total + x
  end;

Συνεχές Άθροισμα

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

Πρώτοι Αριθμοί

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

Διάγραμμα Ροής Δεδομένων

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

Διάγραμμα Ροής Δεδομένων

--------> whenever -----> qsort ---------
   |             ^                           |
   |             |                           |
   |            not                          |
   |             ^                           |
   |---> first   |                           |
   |       |     |                           |
   |       V     |                           |
   |---> less ---                            |
   |             |                           |
   |             V                           V
---+--------> whenever -----> qsort -----> conc -------> ifthenelse ----->
   |                                                       ^   ^
   |                                                       |   |
    --------> next ----> first ------> iseod --------------    |
   |                                                           |
    -----------------------------------------------------------

Τετραγωνική Ρίζα

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

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;

Διάγραμμα Ροής Δεδομένων

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