Αναγωγή γράφου
Στην επιστήμη υπολογιστών, η αναγωγή γράφου (graph reduction) υλοποιεί μια αποδοτική έκδοση της μη-αυστηρής αποτίμησης, μιας στρατηγικής αποτίμησης στην οποία οι παράμετροι σε μια συνάρτηση δεν αποτιμώνται άμεσα. Η μορφή αυτή της μη-αυστηρής αποτίμησης είναι γνωστή και σαν οκνηρή αποτίμηση και χρησιμοποιείται στις γλώσσες συναρτησιακού προγραμματισμού. Η τεχνική χρησιμοποιήθηκε για πρώτη φορά από τον Chris Wadsworth το 1971.
Σκοπός
[Επεξεργασία | επεξεργασία κώδικα]Ακολουθεί ένα απλό παράδειγμα αποτίμησης μια αριθμητικής έκφρασης:
Η παραπάνω ακολουθία αναγωγών ακολουθεί μια στρατηγική γνωστή ως "αναγωγή του πιο εξωτερικού δένδρου" (outermost tree reduction). Η ίδια έκφραση μπορεί να αποτιμηθεί χρησιμοποιώντας "αναγωγή του πιο εσωτερικού δένδρου" (innermost tree reduction), με αποτέλεσμα της εξής ακολουθία αναγωγών:
Όπως φαίνεται παραπάνω η σειρά αποτίμησης δίνεται ρητά από την προσθήκη παρενθέσεων. Η έκφραση αυτή θα μπορούσε επίσης να αποτιμηθεί απλά από τα δεξιά προς τα αριστερά, επειδή η πρόσθεση είναι προσεταιριστική πράξη.
Η παραπάνω έκφραση, αναπαρίσταται σαν δένδρο ως εξής:
Από αυτήν την απεικόνιση προκύπτει και ο όρος αναγωγή δένδρου (tree reduction). Όταν αναπαρίσταται σαν δένδρο, μπορούμε να θεωρούμε την πιο εσωτερική αναγωγή ξεκινώντας από τα κάτω προς τα πάνω, ενώ η εξωτερική δουλεύει από τα πάνω προς τα κάτω.
Η έκφραση μπορεί επίσης να αναπαρασταθεί σαν γράφος, επιτρέποντας κοινές υποεκφράσεις:
Όπως και στα δένδρα, οι εξωτερική και η εσωτερική αναγωγή εφαρμόζονται και στους γράφους, με αποτέλεσμα να έχουμε αναγωγή γράφου.
Σε αυτό το σημείο η αποτίμηση με την αναγωγή του πιο εξωτερικού γράφου συνεχίζει ως εξής:
Τώρα η αναγωγή χρειάζεται μόνο 4 βήματα. Η αναγωγή του πιο εξωτερικού γράφου ονομάζεται οκνηρή αποτίμηση (lazy evaluation) και η αναγωγή του πιο εσωτερικού γράφου ονομάζεται πρόθυμη αποτίμηση (eager evaluation).
Αναγωγή γράφου συνδυαστών (Combinator graph reduction)
[Επεξεργασία | επεξεργασία κώδικα]Η αναγωγή γράφου συνδυαστών είναι μια βασική τεχνική υλοποίησης για γλώσσες συναρτησιακού προγραμματισμού, στην οποία ένα πρόγραμμα απεικονίζεται σε συνδυαστές που αντιστοιχίζονται σε μια δομή δεδομένων κατευθυνόμενου γράφου στη μνήμη του υπολογιστή, και η εκτέλεση του προγράμματος αποτελείται από την αντικαταστάσεις/αναγωγές (rewriting) τμημάτων αυτού του γράφου προς τα τελικά αποτελέσματα.
Ιστορία
[Επεξεργασία | επεξεργασία κώδικα]Η ιδέα της αναγωγής γράφου που επιτρέπει σε τιμές που έχουν αποτιμηθεί να είναι κοινές ανάγεται στη διδακτορική διατριβή του Chris Wadsworth το 1971[1]. Η διατριβή αυτή αναφέρθηκε από τους Peter Henderson και James H. Morris Jr. το 1976 στο “A lazy evaluator” [3] που εισήγαγε την ιδέα της οκνηρης αποτίμησης. Το 1976 ο David Turner ενσωμάτωσε την οκνηρή αποτίμηση στη γλώσσα SASL χρησιμοποιώντας συνδυαστές[2]. Η SASL ήταν μια πρώιμη γλώσσα συναρτησιακού προγραμματισμού που δημιουργήθηκε από τον Turner το 1972.
Πηγές
[Επεξεργασία | επεξεργασία κώδικα]- Simon Peyton Jones, The Implementation of Functional Programming Languages, Prentice Hall, 1987. Full text online.[4]
Αναφορές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ Hudak, Paul, "Conception, evolution, and application of functional programming languages", ACM Computing Surveys, volume 21, issue 3, pages 359–411, September 1989, [1] Αρχειοθετήθηκε 2009-03-20 στο Wayback Machine., doi=10.1145/72551.72554
- ↑ Hudak, Paul, "Hughes, John; Peyton Jones, Simon; Wadler, Philip, A History of Haskell", [2] Αρχειοθετήθηκε 2010-04-25 στο Wayback Machine., History of Programming Languages Conference 2007
Βιβλιογραφία
[Επεξεργασία | επεξεργασία κώδικα]- Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.