Αναγωγή γράφου

Στην επιστήμη υπολογιστών, η **αναγωγή γράφου** (**graph reduction**) υλοποιεί μια αποδοτική έκδοση της μη-αυστηρής αποτίμησης, μιας στρατηγικής αποτίμησης στην οποία οι παράμετροι σε μια συνάρτηση δεν αποτιμώνται άμεσα. Η μορφή αυτή της μη-αυστηρής αποτίμησης είναι γνωστή και σαν οκνηρή αποτίμηση και χρησιμοποιείται στις γλώσσες συναρτησιακού προγραμματισμού. Η τεχνική χρησιμοποιήθηκε για πρώτη φορά από τον Chris Wadsworth το 1971. 

## Σκοπός
Ακολουθεί ένα απλό παράδειγμα αποτίμησης μια αριθμητικής έκφρασης:

:
\begin{align}
& {} \qquad ((2+2)+(2+2))+(3+3) \\
& {} =((2+2)+(2+2))+(6) \\
& {} =((2+2)+ 4)+6 \\
& {} =(4+4)+6 \\
& {} =8+6 \\
& {} =14
\end{align}


Η παραπάνω ακολουθία αναγωγών ακολουθεί μια στρατηγική γνωστή ως "αναγωγή του πιο εξωτερικού δένδρου" (outermost tree reduction). Η ίδια έκφραση μπορεί να αποτιμηθεί χρησιμοποιώντας "αναγωγή του πιο εσωτερικού δένδρου" (innermost tree reduction), με αποτέλεσμα της εξής ακολουθία αναγωγών:

:
\begin{align}
& {} \qquad ((2+2)+(2+2))+(3+3) \\
& {} = ((2+2)+4)+(3+3) \\
& {} = (4+4)+(3+3) \\
& {} = (4+4)+6 \\
& {} = 8+6 \\
& {} = 14
\end{align}


Όπως φαίνεται παραπάνω η σειρά αποτίμησης δίνεται ρητά από την προσθήκη παρενθέσεων. Η έκφραση αυτή θα μπορούσε επίσης να αποτιμηθεί απλά από τα δεξιά προς τα αριστερά, επειδή η πρόσθεση είναι προσεταιριστική πράξη.

Η παραπάνω έκφραση, αναπαρίσταται σαν δένδρο ως εξής:

300px

Από αυτήν την απεικόνιση προκύπτει και ο όρος αναγωγή δένδρου (tree reduction). Όταν αναπαρίσταται σαν δένδρο, μπορούμε να θεωρούμε την πιο εσωτερική αναγωγή ξεκινώντας από τα κάτω προς τα πάνω, ενώ η εξωτερική δουλεύει από τα πάνω προς τα κάτω.

Η έκφραση μπορεί επίσης να αναπαρασταθεί σαν γράφος, επιτρέποντας κοινές υποεκφράσεις:

300px

Όπως και στα δένδρα, οι εξωτερική και η εσωτερική αναγωγή εφαρμόζονται και στους γράφους, με αποτέλεσμα να έχουμε **αναγωγή γράφου**.

Σε αυτό το σημείο η αποτίμηση με την αναγωγή του πιο εξωτερικού γράφου συνεχίζει ως εξής:

200px

Τώρα η αναγωγή χρειάζεται μόνο 4 βήματα. Η αναγωγή του πιο εξωτερικού γράφου ονομάζεται οκνηρή αποτίμηση (lazy evaluation) και η αναγωγή του πιο εσωτερικού γράφου ονομάζεται πρόθυμη αποτίμηση (eager evaluation).

## Αναγωγή γράφου συνδυαστών (Combinator graph reduction)
Η **αναγωγή γράφου συνδυαστών** είναι μια βασική τεχνική υλοποίησης για γλώσσες συναρτησιακού προγραμματισμού, στην οποία ένα πρόγραμμα απεικονίζεται σε συνδυαστές που αντιστοιχίζονται σε μια δομή δεδομένων κατευθυνόμενου γράφου στη μνήμη του υπολογιστή, και η εκτέλεση του προγράμματος αποτελείται από την αντικαταστάσεις/αναγωγές (rewriting) τμημάτων αυτού του γράφου προς τα τελικά αποτελέσματα.

## Ιστορία
Η ιδέα της αναγωγής γράφου που επιτρέπει σε τιμές που έχουν αποτιμηθεί να είναι κοινές ανάγεται στη διδακτορική διατριβή του Chris Wadsworth το 1971. Η διατριβή αυτή αναφέρθηκε από τους Peter Henderson και James H. Morris Jr. το 1976 στο “A lazy evaluator” http://portal.acm.org/citation.cfm?id=811543 που εισήγαγε την ιδέα της οκνηρης αποτίμησης. Το 1976 ο David Turner ενσωμάτωσε την οκνηρή αποτίμηση στη γλώσσα SASL χρησιμοποιώντας συνδυαστές.
Η SASL ήταν μια πρώιμη γλώσσα συναρτησιακού προγραμματισμού που δημιουργήθηκε από τον Turner το 1972.

## Πηγές
* Simon Peyton Jones, *The Implementation of Functional Programming Languages*, Prentice Hall, 1987. Full text online.https://web.archive.org/web/20080430085409/http://research.microsoft.com/Users/simonpj/papers/slpj-book-1987/index.htm

## Αναφορές


## Βιβλιογραφία
* 

## Δείτε επίσης
* Συναρτησιακός πρόγραμματισμός
* Haskell
* Miranda

Κατηγορία:Αλγόριθμοι γράφων