Οκνηρή αποτίμηση: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε

Ενδογραμμικά

Έκδοση από την 01:28, 28 Ιουνίου 2011

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

Δείτε επίσης

Σημειώσεις

↑ Hudak 1989, σελ. 384
↑ David Anthony Watt· William Findlay (2004). Programming language design concepts. John Wiley and Sons. σελίδες 367–368. ISBN 9780470853207. Ανακτήθηκε στις 30 Δεκεμβρίου 2010.
↑ Reynolds 1998, σελ. 307
↑ Chris Smith (22 Οκτωβρίου 2009). Programming F#. O'Reilly Media, Inc. σελ. 79. ISBN 9780596153649. Ανακτήθηκε στις 31 Δεκεμβρίου 2010.
↑ OCaml and lazy evaluation
↑ Reynolds 1998, σελ. 312
↑ ^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. Ανακτήθηκε στις 14 Ιανουαρίου 2011.
↑ ^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. Ανακτήθηκε στις 14 Ιανουαρίου 2011.
↑ ^9,0 ^9,1 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.

Αναφορές

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 978052159414 Check |isbn= value: length (βοήθεια).

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

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". 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

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

Lazy evaluation, Haskell Wiki (Αγγλικά)
Functional programming in Python becomes lazy (Αγγλικά)
Lazy programming and lazy evaluation, για την Scheme

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

[1] Hudak 1989, σελ. 384

[WattFindlay2004-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

[Smith2009-4] Chris Smith (22 Οκτωβρίου 2009). Programming F#. O'Reilly Media, Inc. σελ. 79. ISBN 9780596153649. Ανακτήθηκε στις 31 Δεκεμβρίου 2010.

[5] OCaml and lazy evaluation

[6] Reynolds 1998, σελ. 312

[Wadler2006-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. Ανακτήθηκε στις 14 Ιανουαρίου 2011.

[Métayer2002-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. Ανακτήθηκε στις 14 Ιανουαρίου 2011.

[MachineryLanguages2002-9] 9,0 ^9,1 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]