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

Στη θεωρία των γλωσσών προγραμματισμού, η οκνηρή αποτίμηση (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 είναι εξ ορισμού αυστηρό, εκτός και αν χρησιμοποιηθεί το σύμβολο ~ που το κάνει οκνηρό.

Δείτε επίσης

• Συνδυαστική λογική
• Currying
• Ροή δεδομένων
• Πρόθυμη αποτίμηση
• Συναρτησιακός προγραμματισμός
• Αναγωγή γράφου
• λ-λογισμός
• Μη αυστηρή γλώσσα προγραμματισμού
• Αποτίμηση σε κανονική σειρά (Normal order evaluation)

Σημειώσεις

1. Hudak 1989, σελ. 384
2. David Anthony Watt· William Findlay (2004). Programming language design concepts. John Wiley and Sons. σελίδες 367–368. ISBN 9780470853207. Ανακτήθηκε στις 30 Δεκεμβρίου 2010. 
3. Reynolds 1998, σελ. 307
4. Chris Smith (22 Οκτωβρίου 2009). Programming F#. O'Reilly Media, Inc. σελ. 79. ISBN 9780596153649. Ανακτήθηκε στις 31 Δεκεμβρίου 2010. 
5. «OCaml and lazy evaluation». Αρχειοθετήθηκε από το πρωτότυπο στις 28 Ιουνίου 2011. Ανακτήθηκε στις 28 Ιουνίου 2011. 
6. Reynolds 1998, σελ. 312
7. Philip Wadler (2006). Functional and logic programming: 8th international symposium, FLOPS 2006, Fuji-Susono, Japan, April 24-26, 2006 : proceedings. Springer. σελ. 149. ISBN 9783540334385. Ανακτήθηκε στις 14 Ιανουαρίου 2011. 
8. 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. Ανακτήθηκε στις 14 Ιανουαρίου 2011. 
9. Association for Computing Machinery· ACM Special Interest Group on Programming Languages (1 Ιανουαρίου 2002). Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell '02) : Pittsburgh, Pennsylvania, USA ; October 3, 2002. Association for Computing Machinery. σελ. 40. ISBN 9781581136050. Ανακτήθηκε στις 14 Ιανουαρίου 2011. 
10. Lazy and Speculative Execution Αρχειοθετήθηκε 2012-10-10 στο Wayback Machine. Butler Lampson, Microsoft Research OPODIS, Bordeaux, France 12 December 2006

Αναφορές

• Hudak, Paul (September 1989). «Conception, Evolution, and Application of Functional Programming Languages». ACM Computing Surveys 21 (3): 383–385. http://portal.acm.org/citation.cfm?id=72554. 
• Reynolds, John C. (1998). Theories of programming languages. Cambridge University Press. ISBN 978-0521106979. 

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

• Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus.  PhD thesis, Oxford University
• Henderson, Peter; Morris, James H. (January 1976). «A Lazy Evaluator». Conference Record of the Third ACM symposium on Principles of Programming Languages. http://portal.acm.org/citation.cfm?id=811543. 
• Friedman, D. P.; Wise, David S. (1976). S. Michaelson and R. Milner, επιμ. «Cons should not evaluate its arguments». Automata Languages and Programming Third International Colloquium (Edinburgh University Press). http://www.cs.indiana.edu/pub/techreports/TR44.pdf. 

Design patterns

• John Hughes. "Why functional programming matters" Αρχειοθετήθηκε 2011-09-04 στο Wayback Machine.. The Computer Journal - Special issue on lazy functional programming. Volume 32 Issue 2, April 1989.
• Philip Wadler. "How to replace failure by a list of successes a method for exception handling, backtracking, and pattern matching in lazy functional languages"^{[νεκρός σύνδεσμος]}. Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, 1985, Volume 201/1985, 113-128.

Blog posts by computer scientists

• Robert Harper. "The Point of Laziness"
• Lennart Augustsson. "More points for lazy evaluation"

Εξωτερικοί σύνδεσμοι

• Οκνηρή αποτίμηση και αποδείξεις ορθότητας
• Lazy evaluation, Haskell Wiki (Αγγλικά)
• Functional programming in Python becomes lazy (Αγγλικά)
• Lazy programming and lazy evaluation, για την Scheme (Αγγλικά)