Οκνηρή αποτίμηση

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Στη θεωρία των γλωσσών προγραμματισμού, η οκνηρή αποτίμηση (lazy evaluation) ή κλήση κατ' ανάγκη (call-by-need)[1] είναι μια στρατηγική αποτίμησης (evaluation strategy) που καθυστρεί την αποτίμηση μιας έκφρασης μέχρι αυτή να χρειαστεί (μη αυστηρή αποτίμηση, non-strict evaluation) και αποφεύγει επαναλαμβανόμενους υπολογισμούς (μοίρασμα, sharing).[2][3] Το μοίρασμα μπορεί να μειώσει το χρόνο εκτέλεσης συγκεκριμένων συναρτήσεων εκθετικά σε σχέση με άλλες μη αυστηρές στρατηγικές αποτίμησης, όπως η κλήση κατ' όνομα ((call-by-name).

Τα πλεονεκτήματα της οκνηρής αποτίμησης περιλαμβάνουν μεταξύ άλλων: την ελάττωση του χρόνου εκτέλεσης (επειδή αποφεύγονται υπολογισμοί που δε χρειάζονται), λιγότερες εκφράσεις λαθών κατά την αποτίμηση σύνθετων εκφράσεων, τη δυνατότητα κατασκευής δυνητικά άπειρων δομών δεδομένων, και τη δυνατότητα ορισμού των δομών ελέγχου σαν αφαιρέσεις (abstractions), αντί για ενσωματωμένες εντολές. Η οκνηρή αποτίμηση μπορεί να οδηγήσει σε λιγότερη χρήση μνήμης, επειδή οι τιμές δημιουργούνται μόνο όταν χρειάζονται.[4] Η οκνηρή αποτίμηση όμως είναι δύσκολο να συνδυαστεί με προστακτικά χαρακτηριστικά όπως ο χειρισμός εξαιρέσεων και η είσοδος/έξοδος, γιατί δεν είναι εύκολο να προσδιοριστεί η σειρά εκτέλεσης. Επίσης η αποσφαλμάτωση γίνεται πιο δύσκολη.[5]

Το αντίθετο της οκνηρής αποτίμησης είναι η πρόθυμη αποτίμηση (eager evaluation), γνωστή και ως αυστηρή αποτίμηση (strict evaluation). Η αυστηρή αποτίμηση χρησιμοποιείται πιο συχνά στις γλώσσες προγραμματισμού.

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

Η οκνηρή αποτίμηση εισήχθηκε στο λ-λογισμό από τον Wadsworth 1971 και στις γλώσσες προγραμματισμού ανεξάρτητα από τους Henderson & Morris 1976 και τους Friedman & Wise 1976.[6]

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Η καθυστερημένη αποτίμηση χρησιμοποιείται περισσότερο στις συναρτησιακές γλώσσες. Όταν γίνεται χρήση της καθυστερημένης υλοποίησης, μια έκφραση δεν αποτιμάται όταν δεσμεύεται σε μια μεταβλητή, αλλά όταν πρέπει να βρεθεί η τιμή της έκφρασης. Κατά αυτόν τον τρόπο, μια εντολή όπως η x:=έκφραση; (δηλ. η ανάθεση του αποτελέσματος μιας έκφρασης σε μια μεταβλητή) φαίνεται να ζητά την αποτίμηση της έκφρασης ώστε το αποτέλεσμα να τοποθετηθεί στην x, αλλά τα περιεχόμενα της x δεν έχουν σημασία μέχρι να εμφανιστεί ανάγκη για την τιμή της μέσω κάποιας αναφοράς στην x αργότερα, σε κάποια άλλη έκφραση, η οποία με τη σειρά της μπορεί να καθυστερεί, αν και τελικά το δέντρο των εξαρτήσεων που θα προκύψει θα πρέπει να παράγει κάποιο σύμβολο για τον έξω κόσμο.[7]

Κάποιες γλώσσες προγραμματισμού καθυστερούν πάντα την αποτίμηση των εκφράσεων, ενώ άλλες προσφέρουν συναρτήσεις ή ειδική σύνταξη για την καθυστέρηση της αποτίμησης. Στη Miranda και τη Haskell, οι παράμετροι των συναρτήσεων αποτιμώνται καθυστερημένα. Σε πολλές άλλες γλώσσες, η αποτίμηση μπορεί να καθυστερήσει σταματώντας ρητά τον υπολογισμό, με χρήση ειδικής σύνταξης (όπως οι "delay" και "force" της Scheme και οι "lazy" και "Lazy.force" της OCaml) ή γενικότερα με το πακετάρισμα της έκφρασης σε ένα thunk (καθυστερημένος υπολογισμός). Το αντικείμενο που αναπαριστά μια ρητα καθυστερημένη αποτίμηση ονομάζεται μέλλον (future) ή υπόσχεση (promise). Η Perl 6 χρησιμοποιεί οκνηρή αποτίμηση στις λίστες: ο προγραμματιστής μπορεί να αναθέσει άπειρες λίστες σε μεταβλητές και να τις περάσει σε συναρτήσεις, αλλά, σε αντίθεση με τη Haskell και τη Miranda, η Perl 6 δεν χρησιμοποιεί οκνηρή αποτίμηση από προεπιλογή στους αριθμητικούς τελεστές και στις συναρτήσεις.[7]

Η καθυστερημένη αποτίμηση έχει το πλεονέκτημα ότι μπορεί να δημιουργήσει υπολογίσιμες άπειρες λίστες χωρίς άπειρους βρόχους ή άλλα προβλήματα μεγέθους στον υπολογισμό. Για παράδειγμα, μπορεί να δημιουργηθεί μια συνάρτηση που δημιουργεί μια άπειρη λίστα (η οποία λίστα συχνά αποκαλείται ροή, αγγλ.stream) από αριθμούς Φιμπονάτσι. Ο υπολογισμός του ν-οστού αριθμού Φιμπονάτσι είναι απλά η εξαγωγή αυτού του στοιχείου από την άπειρη λίστα, που προκαλεί την αποτίμηση μόνο των πρώτων ν στοιχείων της λίστας.[8][9]

Για παράδειγμα, στη Haskell, η λίστα όλων των αριθμών Φιμπονάτσι μπορεί να γραφτεί ως εξής:[9]

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Στη σύνταξη της Haskell, ο τελεστής ":" προσθέτει ένα στοιχείο στην αρχή της λίστας, η συνάρτηση tail επιστρεφει μια λίστα χωρίς το πρώτο της στοιχείο και η zipWith χρησιμοποιεί κάποια συνάρτηση (εδώ την πρόσθεση) για να συνδυάσει ένα-προς-ένα τα στοιχεία από δύο λίστες για να δημιουργήσει μια τρίτη.[8]

Αν ο προγραμματιστής είναι προσεκτικός, μπορούν να αποτιμηθούν μόνο οι τιμές που χρειάζονται για να παράγουν ένα συγκεκριμένο αποτέλεσμα. Όμως, κάποιοι υπολογισμοί μπορεί να έχουν σαν αποτέλεσμα το πρόγραμμα να προσπαθήσει να αποτιμήσει έναν άπειρο αριθμό από στοιχεία -- για παράδειγμα, όταν ζητείται το μήκος ή το συνολικό άθροισμα των στοιχείων μιας λίστας με μια λειτουργία fold, που μπορεί να κάνει το πρόγραμμα να εκτελείται επ' άπειρον ή να καταναλώσει όλη τη μνήμη.

Δομές ελέγχου[Επεξεργασία | επεξεργασία κώδικα]

Η εντολή if είναι πάντα οκνηρή, ακόμα και στις κοινές (πρόθυμες) γλώσσες. Η έκφραση

if a then b else c

υπολογίζει την υποέκφραση (a) και μετά, αν και μόνο αν η (a) είναι αληθής, υπολογίζει την (b), αλλιώς υπολογίζει την (c). Δηλαδή, κάποια από τις (b) και (c) δε θα υπολογιστεί. Αντίθετα, σε μια πρόθυμη γλώσσα ο παρακάτω κώδικας

define f(x,y) = 2*x
set k = f(e,5)

αναμένεται να υπολογίσει την (e) και την (f) όταν υπολογίζει την (k). Όμως, οι δομές ελέγχου (control structures) που ορίζονται από το χρήστη βασίζονται στη σύνταξη της γλώσσας και στο παράδειγμα

define g(a,b,c) = if a then b else c
l = g(h,i,j)

και η (i) και η (j) θα υπολογιστούν σε μια οκνηρή γλώσσα. Αντίθετα, στον κώδικα

l' = if h then i else j

θα υπολογιστεί η (i) ή η (j), αλλά ποτέ και οι δύο.

Η οκνηρή αποτίμηση επιτρέπει τον ορισμό δομών ελέγχου από το χρήστη, χωρίς να απαιτούνται ειδικές βασικές εντολές (primitives) ή τεχνικές του χρόνου μεταγλώττισης (compile-time). Αν η (i) ή η (j) έχει παρενέργειες (side effects), ή εισάγει σφάλματα χρόνου εκτέλεσης (run time errors), η συμπεριφορά της έκφρασης μπορεί να είναι πολύπλοκη. Επειδή οι περισσότερες γλώσσες προγραμματισμού είναι Τούρινγκ-πλήρεις (Turing-complete), μπορούν να γραφτούν από το χρήστη οκνηρές δομές ελέγχου σε πρόθυμες γλώσσες, σαν συναρτήσεις, αλλά τότε δεν ακολουθούν τη σύνταξη της γλώσσας για πρόθυμη αποτίμηση: συχνά οι υποεκφράσεις (όπως η (i) και η (j)) πρέπει να πακετάρονται σαν συναρτήσεις, ώστε να εκτελούνται μόνο όταν καλούνται.

Η βραχυκυκλωμένη αποτίμηση (short-circuit evaluation) των δομών ελέγχου αληθείας, όπως οι τελεστές && και || της C, συχνά καλείται επίσης "οκνηρή" ("lazy").

Άλλες χρήσεις[Επεξεργασία | επεξεργασία κώδικα]

Στα παραθυρικά περιβάλλοντα (windowing systems) των υπολογιστών, η εμφάνιση γραφικής πληροφορίας στην οθόνη οδηγείται από "γεγονότα έκθεσης" ("expose events") που ενεργοποιούν τον κώδικα εμφάνισης την τελευταία στιγμή. Με αυτόν τον τρόπο, αποφεύγεται ο υπολογισμός περιεχομένου που δεν χρειάζεται.[10]

Ένα άλλο παράδειγμα οκνηρίας (laziness) στους υπολογιστές είναι δέσμευση σελίδων μνήμης με την τεχνική αντιγραφή-όταν-γράφεται (copy-on-write) ή demand paging, όπου η μνήμη δεσμεύεται μόνο όταν η τιμή που αποθηκεύεται σε αυτήν τη θέση αλλάζει.[10]

Η οκνηρία μπορεί να είναι χρήσιμη σε περιπτώσεις υψηλής απόδοσης. Ένα παράδειγμα είναι η λειτουργία της κλήσης mmap του Unix. Η mmap φορτώνει σελίδες από το δίσκο με βάση τη ζήτηση ("demand driven"), ώστε να φορτώνονται μόνο οι σελίδες που χρειάζονται πραγματικά και να μην δεσμεύεται μνήμη που δε χρειάζεται.

Πρόθυμη αποτίμηση και οκνηρές γλώσσες[Επεξεργασία | επεξεργασία κώδικα]

Σε οκνηρές γλώσσες προγραμματισμού όπως η Haskell, αν και εξ ορισμού οι εκφράσεις αποτιμώνται μόνο όταν χρειάζονται, κάποιες φορές είναι απαραίτητη η πρόθυμη αποτίμηση. Αυτό μπορεί να γίνει κωδικοποιώντας κάτι ρητά ώστε να προκαλεί αποτίμηση. Η αυστηρή αποτίμηση (strict evaluation) συνήθως υλοποιείται μέσω της πρόθυμης υλοποίησης, αλλά δεν ταυτίζονται.

Παρόλα αυτά, υπάρχει μια βελτιστοποίηση σε κάποιους μεταγλωττιστές που ονομάζεται ανάλυση αυστηρότητας (strictness analysis), η οποία σε κάποιες περιπτώσεις επιτρέπει στο μεταγλωττιστή να βρει αν μια τιμή θα χρειάζεται πάντα. Σε αυτές τις περιπτώσεις ο μεταγλωττιστής επιβάλλει την αυστηρή αποτίμηση.

Στη Haskell, η σημείωση πεδίων κατασκευαστών (constructor fields) σαν πρόθυμα, σημαίνει ότι οι τιμές τους θα χρειαστούν κατευθείαν. Η συνάρτηση seq μπορεί επίσης να χρησιμοποιηθεί για να ζητηθεί μια τιμή άμεσα και στη συνέχεια να δοθεί σε μια άλη έκφραση, που είναι χρήσιμη αν κάποιο πεδίο κατασκευαστή είναι οκνηρό. Όμως καμία από αυτές τις τεχνικές δεν υοποιεί αναδρομική αυστηρότητα -- για αυτήν την περίπτωση χρειάζεται η ειδική συνάρτηση deepSeq.

Επίσης, το ταίριασμα προτύπων (pattern matching) στην Haskell 98 είναι εξ ορισμού αυστηρό, εκτός και αν χρησιμοποιηθεί το σύμβολο ~ που το κάνει οκνηρό.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Σημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

  1. Hudak 1989, σελ. 384
  2. David Anthony Watt; William Findlay (2004). Programming language design concepts. John Wiley and Sons. σελ. 367–368. ISBN 9780470853207. http://books.google.com/books?id=vogP3P2L4tgC&pg=PA367. Ανακτήθηκε στις 30 December 2010. 
  3. Reynolds 1998, σελ. 307
  4. Chris Smith (22 October 2009). Programming F#. O'Reilly Media, Inc.. σελ. 79. ISBN 9780596153649. http://books.google.com/books?id=gzVdyw2WoXMC&pg=PA79. Ανακτήθηκε στις 31 December 2010. 
  5. OCaml and lazy evaluation
  6. Reynolds 1998, σελ. 312
  7. 7,0 7,1 Philip Wadler (2006). Functional and logic programming: 8th international symposium, FLOPS 2006, Fuji-Susono, Japan, April 24-26, 2006 : proceedings. Springer. σελ. 149. ISBN 9783540334385. http://books.google.com/books?id=gZzLFFZfc1sC&pg=PA149. Ανακτήθηκε στις 14 January 2011. 
  8. 8,0 8,1 Daniel Le Métayer (2002). Programming languages and systems: 11th European Symposium on Programming, ESOP 2002, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002, Grenoble, France, April 8-12, 2002 : proceedings. Springer. σελ. 129–132. ISBN 9783540433637. http://books.google.com/books?id=dYZyzp-I9hQC&pg=PA129. Ανακτήθηκε στις 14 January 2011. 
  9. 9,0 9,1 Association for Computing Machinery; ACM Special Interest Group on Programming Languages (1 January 2002). Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell '02) : Pittsburgh, Pennsylvania, USA ; October 3, 2002. Association for Computing Machinery. σελ. 40. ISBN 9781581136050. http://books.google.com/books?id=hsBQAAAAMAAJ. Ανακτήθηκε στις 14 January 2011. 
  10. 10,0 10,1 Lazy and Speculative Execution Butler Lampson, Microsoft Research OPODIS, Bordeaux, France 12 December 2006

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Design patterns
Blog posts by computer scientists

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Lazy evaluation της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).