Lucid
Η Lucid είναι μια γλώσσα προγραμματισμού ροής δεδομένων (dataflow). Σχεδιάστηκε από τους Bill Wadge και Ed Ashcroft[1].
Μοντέλο
ΕπεξεργασίαΗ Lucid χρησιμοποιεί ένα μοντέλο που εξαρτάται από τη ζήτηση δεδομένων για τον υπολογισμό. Κάθε εντολή μπορεί να θεωρηθεί σαν μια εξίσωση που ορίζει ένα δίκτυο επεξεργαστών και γραμμών επικοινωνίας μεταξύ αυτών (μέσω των οποίων γραμμών ρέουν τα δεδομένα). Κάθε μεταβλητή είναι μια άπειρη ροή από τιμές και κάθε συνάρτηση είναι ένα φίλτρο ή ένας μετασχηματιστής (transformer). Η ακολουθιακή εκτέλεση των εντολών προσομοιώνεται από τις τρέχουσες τιμές των μεταβλητών και τον τελεστή 'fby' (διαβάζεται σαν 'ακολουθούμενο από', 'followed by') που επιτρέπει τη σύνθεση ροών.
Η Lucid βασίζεται σε μια άλγεβρα ιστοριών με κάθε ιστορία να είναι μια άπειρη ακολουθία από δεδομένα. Λειτουργικά, μια ιστορία μπορεί να θεωρηθεί σαν μια καταγραφή των μεταβαλλόμενων τιμών μιας μεταβλητής, με τις λειτουργίες 'first' και 'next' σαν την πρώτη και την επόμενη τιμή της. Η Lucid αρχικά δημιουργήθηκε σαν ένα είδος αυστηρής αμιγούς γλώσσας προγραμματισμού με μοναδική ανάθεση, που θα διευκόλυνε την επαλήθευση των προγραμμάτων σε αυτή. Όμως, η θεώρησή της σαν γλώσσα ροής δεδομένων υπήρξε πολύ σημαντική για την κατεύθυνση προς την οποία εξελίχθηκε[2].
Λεπτομέρειες
ΕπεξεργασίαΣτη 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
Αναφορές
Επεξεργασία- ↑ William W. Wadge, Edward A. Ashcroft, "LUCID, the dataflow programming language", Academic Press Professional, Inc. San Diego, CA, USA, 1985, ISBN 0-12-729650-6
- ↑ Lucid as a dataflow language